On the Integration of Structure Indexes and Inverted Lists

Summary: Unifies structure indexes with inverted lists for XML path/keyword queries via a unified strategy and a path-based evaluation algorithm. Shows cross-index applicability; Niagara XML experiments reveal gains and top-k optimality via Fagin’s Threshold Algorithm. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3629
Venue: SIGMOD
Year: 2004
Pagerank: 9.3190255e-05
Overall Rank: 2,006 | 86.24%
DOI: 10.1145/1007568.1007656

Incoming Non-self Citations Over Time

Authors

1. Raghav Kaushik (University of Wisconsin)
2. Rajasekar Krishnamurthy (University of Wisconsin)
3. Jeffrey F Naughton (University of Wisconsin)
4. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@inproceedings{kaushik_sigmod04,
        title = {{On the Integration of Structure Indexes and Inverted Lists}},
        author = {Kaushik, Raghav and Krishnamurthy, Rajasekar and Naughton, Jeffrey F and Ramakrishnan, Raghu},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007656},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007656},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
748	Effective Keyword Search in Relational Databases	2006	SIGMOD	0.00014381224
1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.3804693e-05
2,359	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.698016e-05
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
3,209	An Efficient and Versatile Query Engine for TopX Search	2005	VLDB	7.6357297e-05
4,113	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.8941988e-05
5,100	Indexing Dataspaces	2007	SIGMOD	6.3646337e-05
5,525	Structure and Content Scoring for XML	2005	VLDB	6.186487e-05
5,952	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	6.031089e-05
6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.7596335e-05
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05
8,333	Efficient Keyword Search over Virtual XML Views	2007	VLDB	5.4519621e-05
11,794	Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data	2020	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
212	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.000247733
301	Proximity Search in Databases	1998	VLDB	0.00022032878
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
470	Query Optimization for XML	1999	VLDB	0.00017965707
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
1,371	DTL’s DataSpot: Database Exploration Using Plain Language	1998	VLDB	0.00010995344
1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010502089
1,849	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.6191884e-05
2,472	Path Queries on Compressed XML	2003	VLDB	8.5327655e-05
3,728	Querying Structured Text in an XML Database	2003	SIGMOD	7.1685118e-05
3,814	Mixed Mode XML Query Processing	2003	VLDB	7.1026815e-05
8,806	XQueC: Pushing Queries to Compressed XML Data	2003	VLDB	5.367725e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,952	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB
2	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
3	430	A Fast Index for Semistructured Data	2001	VLDB
4	1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
5	3,421	Updates for Structure Indexes	2002	VLDB
6	7,423	Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods	2005	VLDB
7	5,688	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD
8	3,728	Querying Structured Text in an XML Database	2003	SIGMOD
9	718	Covering Indexes for Branching Path Queries	2002	SIGMOD
10	3,814	Mixed Mode XML Query Processing	2003	VLDB