Finding smallest k-compact tree set for keyword queries on graphs using MapReduce
Date
2016
Authors
Liu, C.
Yao, L.
Li, J.
Zhou, R.
He, Z.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
World Wide Web, 2016; 19(3):499-518
Statement of Responsibility
Chengfei Liu, Liang Yao, Jianxin Li, Rui Zhou, Zhenying He
Conference Name
Abstract
Keyword search is integrated in many applications on account of the convenience to convey users’ query intention. Most existing works in keyword search on graphs modeled the query results as individual minimal connected trees or connected graphs that contain the keywords. We observe that significant overlap may exist among those query results, which would affect the result diversification. Besides, most solutions required accessing graph data and pre-built indexes in memory, which is not suitable to process big dataset. In this paper, we define the smallest k-compact tree set as the keyword query result, where no shared graph node exists between any two compact trees. We then develop a progressive A* based scalable solution using MapReduce to compute the smallest k-compact tree set, where the computation process could be stopped once the generated compact tree set is sufficient to compute the keyword query result. We conduct experiments to show the efficiency of our proposed algorithm.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Springer Science+Business Media New York 2015