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: h2b708605a86c9e42
Venue: SIGMOD
Year: 2012
Pagerank: 5.3966407e-05
Overall Rank: 8,058 | 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
934	Probase: A Probabilistic Taxonomy for Text Understanding	2012	SIGMOD	0.0001300429
6,233	Fine-grained Concept Linking using Neural Networks in Healthcare	2018	SIGMOD	5.8420918e-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
934	Probase: A Probabilistic Taxonomy for Text Understanding	2012	SIGMOD	0.0001300429
2,316	Fast Set Intersection in Memory	2011	VLDB	8.6496494e-05
3,259	On the Complexity of the View-Selection Problem	1999	PODS	7.4855259e-05
6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.7000336e-05
12,680	Web Scale Taxonomy Cleansing	2011	VLDB	4.9793485e-05

Semantically Similar Papers

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