Optimizing Index for Taxonomy Keyword Search

Summary: Proposes an auxiliary index for taxonomy-driven keyword search, complementing the inverted index. Shows NP-hardness of index selection under space constraints; provides a DP pseudo-polynomial algorithm and a 1/4(1-1/e) approximation; experiments show ~10% extra index space substantially reduces query cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4610
Venue: SIGMOD
Year: 2012
Pagerank: 5.5201308e-05
Overall Rank: 7,896 | 45.83%
DOI: 10.1145/2213836.2213892

Incoming Non-self Citations Over Time

Authors

1. Bolin Ding (University of Illinois Urbana-Champaign)
2. Haixun Wang (Microsoft)
3. Ruoming Jin (Kent State University)
4. Jiawei Han (University of Illinois Urbana-Champaign)
5. Zhongyuan Wang (Microsoft)

BibTeX Citation

@inproceedings{ding_sigmod12,
        title = {{Optimizing Index for Taxonomy Keyword Search}},
        author = {Ding, Bolin and Wang, Haixun and Jin, Ruoming and Han, Jiawei and Wang, Zhongyuan},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213892},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213892},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
908	Probase: A Probabilistic Taxonomy for Text Understanding	2012	SIGMOD	0.00013300624
6,115	Fine-grained Concept Linking using Neural Networks in Healthcare	2018	SIGMOD	5.9709282e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
908	Probase: A Probabilistic Taxonomy for Text Understanding	2012	SIGMOD	0.00013300624
2,245	Fast Set Intersection in Memory	2011	VLDB	8.8734284e-05
3,188	On the Complexity of the View-Selection Problem	1999	PODS	7.6547735e-05
6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.7836523e-05
12,389	Web Scale Taxonomy Cleansing	2011	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,703	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB
2	8,329	Understanding Queries in a Search Database System	2010	PODS
3	1,989	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
4	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	11,790	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD
6	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
7	1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
8	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
9	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
10	12,580	Relaxation in Text Search using Taxonomies	2008	VLDB