Efficient Keyword Search for Smallest LCAs in XML Databases

Summary: XML as labeled trees; returns smallest trees with keywords. Indexed Lookup Eager, exploiting smallest-tree properties to beat methods with uneven keyword frequencies; Scan Eager handles similar frequencies; XKSearch implements them and extends to LCA. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3725
Venue: SIGMOD
Year: 2005
Pagerank: 0.00013939786
Overall Rank: 795 | 94.55%
DOI: 10.1145/1066157.1066217

Incoming Non-self Citations Over Time

Authors

1. Yu Xu (University of California San Diego)
2. Yannis Papakonstantinou (University of California San Diego)

BibTeX Citation

@inproceedings{xu_sigmod05,
        title = {{Efficient Keyword Search for Smallest LCAs in XML Databases}},
        author = {Xu, Yu and Papakonstantinou, Yannis},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066217},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066217},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 29 of 29 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
1,878	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.5651166e-05
2,220	Identifying Meaningful Return Information for XML Keyword Search	2007	SIGMOD	8.9277765e-05
2,379	Structured Search Result Differentiation	2009	VLDB	8.666326e-05
3,239	Keyword Search on Structured and Semi-Structured Data	2009	SIGMOD	7.6078324e-05
4,048	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.9372074e-05
4,131	Querying Complex Structured Databases	2007	VLDB	6.8834743e-05
4,318	XSeek: A Semantic XML Search Engine Using Keywords	2007	VLDB	6.7640367e-05
4,408	Reasoning and Identifying Relevant Matches for XML Keyword Search	2008	VLDB	6.7190081e-05
4,703	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	6.5549049e-05
5,100	Indexing Dataspaces	2007	SIGMOD	6.3646337e-05
5,221	Query Biased Snippet Generation in XML Search	2008	SIGMOD	6.310752e-05
5,750	DDE: From Dewey to a Fully Dynamic XML Labeling Scheme	2009	SIGMOD	6.100444e-05
6,150	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD	5.9579906e-05
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05
7,209	EXTRUCT: Using Deep Structural Information in XML Keyword Search	2010	VLDB	5.6723214e-05
7,931	MESSIAH: Missing Element-Conscious SLCA Nodes Search in XML Data	2013	SIGMOD	5.5181056e-05
8,757	Search Driven Analysis of Heterogeneous XML Data	2009	CIDR	5.3766157e-05
9,352	Querying Virtual Hierarchies using Virtual Prefix-Based Numbers	2014	SIGMOD	5.2831061e-05
9,791	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD	5.2204332e-05
9,792	An Effective and Versatile Keyword Search Engine on Heterogenous Data Sources	2008	VLDB	5.2204332e-05
11,185	Temporal JSON Keyword Search	2024	SIGMOD	5.093636e-05
12,136	Virtual eXist-db: Liberating Hierarchical Queries from the Shackles of Access Path Dependence	2015	VLDB	5.093636e-05
12,448	Using XMorph to Transform XML Data	2010	VLDB	5.093636e-05
12,477	Searching Workflows with Hierarchical Views	2010	VLDB	5.093636e-05
12,555	Relational-Style XML Query	2008	SIGMOD	5.093636e-05
12,580	Relaxation in Text Search using Taxonomies	2008	VLDB	5.093636e-05
12,584	eXtract: A Snippet Generation System for XML Search	2008	VLDB	5.093636e-05
12,711	An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments	2006	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00048017193
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
301	Proximity Search in Databases	1998	VLDB	0.00022032878
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
362	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00020125068
399	XSEarch: A Semantic Search Engine for XML	2003	VLDB	0.00019177959
496	Schema-Free XQuery	2004	VLDB	0.0001750537

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,711	An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments	2006	VLDB
2	187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS
3	4,408	Reasoning and Identifying Relevant Matches for XML Keyword Search	2008	VLDB
4	341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
5	3,450	Keyword Search on External Memory Data Graphs	2008	VLDB
6	1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
7	6,150	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD
8	8,333	Efficient Keyword Search over Virtual XML Views	2007	VLDB
9	7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD
10	7,773	A System for Keyword Proximity Search on XML Databases	2003	VLDB