Top-down keyword query processing on XML data

ABSTRACT

Efficiently answering XML keyword queries has attracted much research effort in the last decade. One key factors resulting in the inefficiency of existing methods are the common-ancestor-repetition (CAR) and visiting-useless-nodes (VUN) problems. In this paper, we propose a generic top-down processing strategy to answer a given keyword query w.r.t. LCA/SLCA/ELCA semantics. By top-down, we mean that we visit all common ancestor (CA) nodes in a depth-first, left-to-right order, thus avoid the CAR problem; by generic, we mean that our method is independent of the labeling schemes and query semantics. We show that the satisfiability of a node v w.r.t. the given semantics can be determined by v's child nodes, based on which our methods avoid the VUN problem. We propose two algorithms that are based on either traditional inverted lists or our newly proposed LLists to improve the overall performance. The experimental results verify the benefits of our methods according to various evaluation metrics.

References

1. L. J. Chen and Y. Papakonstantinou. Supporting top-k keyword search in xml databases. In ICDE, pages 689--700, 2010.
2. Y. Chen, W. Wang, and Z. Liu. Keyword-based search and exploration on databases. In ICDE, pages 1380--1383, 2011.
3. S. Cohen, J. Mamou, Y. Kanza, and Y. Sagiv. Xsearch: A semantic search engine for xml. In VLDB, pages 45--56, 2003.
4. L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. Xrank: Ranked keyword search over xml documents. In SIGMOD Conference, pages 16--27, 2003.
5. V. Hristidis, N. Koudas, Y. Papakonstantinou, and D. Srivastava. Keyword proximity search in xml trees. IEEE Trans. Knowl. Data Eng., 18(4):525--539, 2006.
6. L. Kong, R. Gilleron, and A. Lemay. Retrieving meaningful relaxed tightest fragments for xml keyword search. In EDBT, pages 815--826, 2009.
7. G. Li, J. Feng, J. Wang, and L. Zhou. Effective keyword search for valuable lcas over xml documents. In CIKM, pages 31--40, 2007.
8. Y. Li, C. Yu, and H. V. Jagadish. Schema-free xquery. In VLDB, pages 72--83, 2004.
9. Z. Liu and Y. Chen. Reasoning and identifying relevant matches for xml keyword search. PVLDB, 1(1):921--932, 2008.
10. C. Sun, C. Y. Chan, and A. K. Goenka. Multiway slca-based keyword search in xml data. In WWW, pages 1043--1052, 2007.
11. I. Tatarinov, S. Viglas, K. S. Beyer, J. Shanmugasundaram, E. J. Shekita, and C. Zhang. Storing and querying ordered xml using a relational database system. In SIGMOD Conference, pages 204--215, 2002.
12. W. Wang, X. Wang, and A. Zhou. Hash-search: An efficient slca-based keyword search algorithm on xml documents. In DASFAA, pages 496--510, 2009.
13. Y. Xu and Y. Papakonstantinou. Efficient keyword search for smallest lcas in xml databases. In SIGMOD Conference, pages 537--538, 2005.
14. Y. Xu and Y. Papakonstantinou. Efficient lca based keyword search in xml data. In EDBT, pages 535--546, 2008.
15. J. Zhou, Z. Bao, W. Wang, T. W. Ling, Z. Chen, X. Lin, and J. Guo. Fast slca and elca computation for xml keyword queries based on set intersection. In ICDE, pages 905--916, 2012.
16. J. Zhou, Z. Bao, W. Wang, J. Zhao, and X. Meng. Efficient query processing for xml keyword queries based on the idlist index. The VLDB Journal, DOI: 10.1007/s00778-013-0313-2.
17. J. Zhou, X. Zhao, W. Wang, Z. Chen, and J. X. Yu. Topdown keyword query processing on xml data. Technical report, University of New South Wales, CSR-TR-2013-21, 2013.
18. R. Zhou, C. Liu, and J. Li. Fast elca computation for keyword queries on xml data. In EDBT, pages 549--560, 2010.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

  • Information retrieval

    • Information retrieval query processing

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching