Finding smallest k-Compact tree set for keyword queries on graphs using mapreduce

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.