Applying the XML-based Technique to Support Keyword Search in Graph Data

Abstract

Graphs have been important and proper structures to represent data with complex relationships in the Web, and keyword search provides a convenient way to querying graphs. Some researchers considered to return r-cliques as answers for keyword search in graph databases. Such concepts can retrieve meaningful information effectively, but the existing approach is computationally expensive. In this paper, we propose to utilize the efficient technique originally designed for keyword search in XML data to help identify answers. The main idea is first transforming the input graph into a tree, and then applying the efficient ELCA technique on the transformed tree to find the subtrees which consist of closely-related matches. The specially-designed SRE and SRE* algorithms are then applied on these subtrees to identify r-cliques. We have proposed several strategies for transforming graphs into trees and designed a series of experiments to examine their performance. Experimental results show that our approaches perform very well in terms of efficiency and recall.