Article

Efficient keyword search for smallest LCAs in XML databases

Authors:

Yannis PapakonstantinouAuthors Info & Claims

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data

Pages 527 - 538

https://doi.org/10.1145/1066157.1066217

Published: 14 June 2005 Publication History

Abstract

Keyword search is a proven, user-friendly way to query HTML documents in the World Wide Web. We propose keyword search in XML documents, modeled as labeled trees, and describe corresponding efficient algorithms. The proposed keyword search returns the set of smallest trees containing all keywords, where a tree is designated as "smallest" if it contains no tree that also contains all keywords. Our core contribution, the Indexed Lookup Eager algorithm, exploits key properties of smallest trees in order to outperform prior algorithms by orders of magnitude when the query contains keywords with significantly different frequencies. The Scan Eager variant is tuned for the case where the keywords have similar frequencies. We analytically and experimentally evaluate two variants of the Eager algorithm, along with the Stack algorithm [13]. We also present the XKSearch system, which utilizes the Indexed Lookup Eager, Scan Eager and Stack algorithms and a demo of which on DBLP data is available at http://www.db.ucsd.edu/projects/xksearch. Finally, we extend the Indexed Lookup Eager algorithm to answer Lowest Common Ancestor (LCA) queries.

References

[1]

S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A system for keyword-based search over relational databases. In ICDE, 2002.

Digital Library

[2]

V. Aguilera et al. Querying XML documents in XYleme. In SIGIR Workshop on XML and Information Retrieval, 2000.

[3]

S. Amer-Yahia, S. Cho, and D. Srivastava. Tree pattern relaxation. In EDBT, 2002.

Digital Library

[4]

BerkeleyDB. http://www.sleepycat.com/.

[5]

G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. In ICDE, 2002.

Digital Library

[6]

S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1--7):107--117, 1998.

Digital Library

[7]

Z. Chen, H. Jagadish, F. Korn, and N. Koudas. Counting twig matches in a tree. In ICDE, 2001.

Digital Library

[8]

S. Cohen, J. Namou, Y. Kanza, and Y. Sagiv. XSEarch: A semantic search engine for XML. In VLDB, 2003.

Digital Library

[9]

D. Florescu, D. Kossmann, and I. Manolescu. Integrating keyword search into XML query processing. In WWW9, 2000.

Digital Library

[10]

N. Fuhr and K. Grojohann. XIRQL: A Query Language for Information Retrieval in XML documents. In SIGIR, 2001.

Digital Library

[11]

H. Garcia-Molina, J. Ullman, and J. Widom. Database System Implementation. Prentice-Hall, 2000.

Digital Library

[12]

R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. Proximity Search in Databases. In VLDB, 1998.

Digital Library

[13]

L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. XRANK: Ranked keyword search over XML documents. In SIGMOD, 2003.

Digital Library

[14]

V. Hristidis, N. Koudas, Y. Papakonstantinou, and D. Srivastava. Keyword Proximity Search in XML Trees. Available at http://www.db.ucsd.edu/publications/treeproximity.pdf.

[15]

V. Hristidis and Y. Papakonstantinou. Discover: Keyword search in relational databases. In VLDB, 2002.

Digital Library

[16]

V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword proximity search on XML graphs. In ICDE, 2003.

[17]

Q. Li and B. Moon. Indexing and Querying XML data for regular path expressions. In VLDB, 2001.

Digital Library

[18]

Y. Li, C. Yu, and H. V. Jagadish. Schema-free xquery. In VLDB, 2004.

Digital Library

[19]

J. Naughton et al. The Niagara Internet Query System. IEEE Data Engineering Bulletin, 24(2):27--33, 2001.

[20]

B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM J. Computing, 17(6):1253--1262, 1988.

Digital Library

[21]

A. Schmidt, M. L. Kersten, and M. Windhouwer. Querying XML documents made easy: Nearest concept queries. In ICDE, 2001.

Digital Library

[22]

D. Srivastava et al. Structural joins: A primitive for efficient XML query pattern matching. In ICDE, 2002.

[23]

I. Tatarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang. Storing and querying ordered XML using a relational database system. In SIGMOD, 2002.

Digital Library

[24]

A. Theobald and G. Weikum. Adding relevance to XML. In WebDB, 2000.

Digital Library

[25]

A. Theobald and G. Weikum. The index-based XXL search engine for querying XML data with relevance ranking. In EDBT, 2002.

Digital Library

[26]

Z. Wen. New algorithms for the LCA problem and the binary tree reconstruction problem. Information Processing. Lett, 51(1): 11--16, 1994.

Digital Library

[27]

XYZFind. http://www.searchtools.com/tools/xyzfind.html.

Cited By

Dyreson CShatnawi ABhowmick SSharma V(2024)Temporal JSON Keyword SearchProceedings of the ACM on Management of Data10.1145/36549802:3(1-27)Online publication date: 30-May-2024
https://doi.org/10.1145/3654980
Bikaki APeters MKrozel JKakadiaris I(2024)Building an open-source collaborative platform for migration researchKnowledge-Based Systems10.1016/j.knosys.2024.111823299:COnline publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1016/j.knosys.2024.111823
Bai LZhu L(2023)Keyword Coupling Query of Spatiotemporal XML DataUncertain Spatiotemporal Data Management for the Semantic Web10.4018/978-1-6684-9108-9.ch012(211-226)Online publication date: 15-Dec-2023
https://doi.org/10.4018/978-1-6684-9108-9.ch012
Show More Cited By

Efficient keyword search for smallest LCAs in XML databases
1. Information systems

Recommendations

Identifying meaningful return information for XML keyword search
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Keyword search enables web users to easily access XML data without the need to learn a structured query language and to study possibly complex data schemas. Existing work has addressed the problem of selecting qualified data nodes that match keywords ...
Efficient Top-k Keyword Search on XML Streams
ICYCS '08: Proceedings of the 2008 The 9th International Conference for Young Computer Scientists

Keywords can be used to query XML data without schema information. In this paper, a novel kind of query is proposed, top-k keyword search over XML streams. According to the set of keywords and the number of results, such query can retrieve the top-k XML ...
Towards an Effective XML Keyword Search

Inspired by the great success of information retrieval (IR) style keyword search on the web, keyword search on XML has emerged recently. The difference between text database and XML database results in three new challenges: 1) Identify the user search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data

June 2005

990 pages

ISBN:1595930604

DOI:10.1145/1066157

Conference Chair:
Fatma Ozcan
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS05

Sponsor:

SIGMOD/PODS05: International Conference on Management of Data and Symposium on Principles Database and Systems

June 14 - 16, 2005

Maryland, Baltimore

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

354
Total Citations
View Citations
1,415
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dyreson CShatnawi ABhowmick SSharma V(2024)Temporal JSON Keyword SearchProceedings of the ACM on Management of Data10.1145/36549802:3(1-27)Online publication date: 30-May-2024
https://doi.org/10.1145/3654980
Bikaki APeters MKrozel JKakadiaris I(2024)Building an open-source collaborative platform for migration researchKnowledge-Based Systems10.1016/j.knosys.2024.111823299:COnline publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1016/j.knosys.2024.111823
Bai LZhu L(2023)Keyword Coupling Query of Spatiotemporal XML DataUncertain Spatiotemporal Data Management for the Semantic Web10.4018/978-1-6684-9108-9.ch012(211-226)Online publication date: 15-Dec-2023
https://doi.org/10.4018/978-1-6684-9108-9.ch012
Bai LDuan XQin B(2021) Adaptive query relaxation and top‐ k result sorting of fuzzy spatiotemporal data based on XML International Journal of Intelligent Systems10.1002/int.22781Online publication date: 13-Dec-2021
https://doi.org/10.1002/int.22781
Wang YLi YFan JYe CChai M(2020)A survey of typical attributed graph queriesWorld Wide Web10.1007/s11280-020-00849-024:1(297-346)Online publication date: 20-Nov-2020
https://doi.org/10.1007/s11280-020-00849-0
P. DSowmyarani C. N. (2019)Review on Keyword Search and Ranking Techniques for Semi-Structured DataKnowledge-Intensive Economies and Opportunities for Social, Organizational, and Technological Growth10.4018/978-1-5225-7347-0.ch013(248-270)Online publication date: 2019
https://doi.org/10.4018/978-1-5225-7347-0.ch013
Amini LKeyvanpour M(2019)A Crowdsourcing-based Approach for Efficient XML Keyword Search2019 5th International Conference on Web Research (ICWR)10.1109/ICWR.2019.8765281(16-21)Online publication date: Apr-2019
https://doi.org/10.1109/ICWR.2019.8765281
Jiang L(2019)Application Research of XML Parsing Technology Based on AndroidJournal of Physics: Conference Series10.1088/1742-6596/1314/1/0122131314(012213)Online publication date: 6-Nov-2019
https://doi.org/10.1088/1742-6596/1314/1/012213
Naseriparsa MLiu CIslam MZhou R(2019)XPloreRankWorld Wide Web10.1007/s11280-018-0630-x22:4(1727-1750)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s11280-018-0630-x
Li TMa Z(2018)A structure-based approach of keyword querying for fuzzy XML dataInternational Journal of Knowledge-based and Intelligent Engineering Systems10.3233/KES-18037922:2(125-140)Online publication date: 25-Jul-2018
https://doi.org/10.3233/KES-180379
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents