Nearest Keyword Search in XML Documents

Summary: Introduces Nearest Keyword (NK) search on XML trees and an index that returns the nearest keyword node to a query node. Delivers logarithmic query time in the number of keyword-bearing nodes with linear space and fast construction, with experiments validating NK as a practical building block for XPath and keyword search. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3a81b5c63df9a36b
Venue: SIGMOD
Year: 2011
Pagerank: 5.5321368e-05
Overall Rank: 7,344 | 50.78%
DOI: 10.1145/1989323.1989385

Incoming Non-self Citations Over Time

Authors

1. Yufei Tao (Chinese University of Hong Kong)
2. Stavros Papadopoulos (Chinese University of Hong Kong)
3. Cheng Sheng (Chinese University of Hong Kong)
4. Kostas Stefanidis (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{tao_sigmod11,
        title = {{Nearest Keyword Search in XML Documents}},
        author = {Tao, Yufei and Papadopoulos, Stavros and Sheng, Cheng and Stefanidis, Kostas},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989385},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989385},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,699	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0139119e-05
7,031	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6000241e-05
8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	5.2733276e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
81	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00036224963
180	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026534482
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022559588
294	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021884041
377	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019634591
412	XSEarch: A Semantic Search Engine for XML	2003	VLDB	0.00018712693
449	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018112854
456	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017946233
681	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014792999
827	Efficient Keyword Search for Smallest LCAs in XML Databases	2005	SIGMOD	0.00013598945
1,450	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010593808
2,058	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.0944201e-05
2,276	Identifying Meaningful Return Information for XML Keyword Search	2007	SIGMOD	8.7023244e-05
2,756	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.0322898e-05
4,176	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.7488554e-05
4,219	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.7141046e-05
4,410	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.6011343e-05
5,720	BLAS : An Efficient XPath Processing System	2004	SIGMOD	6.0015097e-05
9,943	Fast Optimal Twig Joins	2010	VLDB	5.0922518e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,049	An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments	2006	VLDB
2	4,523	Reasoning and Identifying Relevant Matches for XML Keyword Search	2008	VLDB
3	352	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
4	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
5	6,285	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD
6	303	Proximity Search in Databases	1998	VLDB
7	8,523	Efficient Keyword Search over Virtual XML Views	2007	VLDB
8	1,450	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
9	827	Efficient Keyword Search for Smallest LCAs in XML Databases	2005	SIGMOD
10	7,953	A System for Keyword Proximity Search on XML Databases	2003	VLDB