Open Access Open Access  Restricted Access Subscription or Fee Access

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

Ya-Hui Chang, Si-Yen Zhuang

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.

Keywords: Keyword search, Graph database, ELCA


Full Text:

PDF

References


Ding B., Lin X., Qin L., et al. Finding Top-k Min-cost Connected Trees in Databases. Proceedings of the ICDE Conference, 2007, 836–845p.

Gubichev A., Neumann T. Fast Approximation of Steiner Trees in Large Graphs. Proceedings of the CIKM Conference, ACM New York, NY, USA, 2012, 1497–1501p.

Kargar M., An A. Keyword Search in Graphs: Finding r-cliques. Proceedings of the VLDB Conference, 2011, 681–692p.

Li G., B. Ooi B, Feng J., et al. Ease: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data. Proceedings of the SIGMOD Conference, Vancouver, Canada, 2008, 903–914p.

Qin L., Yu J., Chang L., et al. Querying Communities in Relational Databases. Proceedings of the ICDE Conference, 2009.

Xu Y., Papakonstantinou Y. Efficient Keyword Search for Smallest LCAS in xml Databases. Proceedings of the SIGMOD Conference, 2005, 527–538p.

Xu Y., Papakonstantinou Y. Efficient lca based Keyword Search in XML Data. Proceedings of the EDBT Conference, 2008, 535–546p.

Zhou J., Bao Z., Wang W., et al. Fast SLCA and ELCA Computation for XML Keyword Queries based on Set Intersection. Proceedings of the ICDE Conference, Washington, DC, 2012, 905–916p.

H.-I. Lu, Ravi R. Approximating Maximum Leaf Spanning Trees in almost

Linear Time. J. Algorithms. 1998; 29(1): 132–41p.

Chu A., Chao K., Wu B. A Linear-time Algorithm for finding an Edge-Partition with Max-min Ratio at Most Two. Discrete Appl. Math. 2013; 161(7-8): 932–43p.


Refbacks

  • There are currently no refbacks.


This site has been shifted to https://stmcomputers.stmjournals.com/