Covering Indexes for Branching Path Queries

Summary: Forward-and-backward index as a covering index analogue for branching path queries on XML graphs; shown to be the smallest index that covers all such expressions. Introducing restricted index-definition schemes yields dramatically smaller, practical indexes with stronger performance when queries match the index, validated on relational XML decompositions and native storage. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf25537fa4a62d601
Venue: SIGMOD
Year: 2002
Pagerank: 0.00014318553
Overall Rank: 741 | 95.03%
DOI: 10.1145/564691.564707

Incoming Non-self Citations Over Time

Authors

1. Raghav Kaushik (University of Wisconsin)
2. Philip Bohannon (AT&T)
3. Jeffrey F Naughton (University of Wisconsin)
4. Henry F Korth (AT&T)

BibTeX Citation

@inproceedings{kaushik_sigmod02,
        title = {{Covering Indexes for Branching Path Queries}},
        author = {Kaushik, Raghav and Bohannon, Philip and Naughton, Jeffrey F and Korth, Henry F},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564707},
        url = {https://dl.acm.org/doi/10.1145/564691.564707},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020756016
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017963727
1,024	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012426975
1,174	Projecting XML Documents	2003	VLDB	0.00011662712
1,784	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.6466168e-05
1,902	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3999798e-05
2,048	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.1227281e-05
2,715	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB	8.0979555e-05
3,490	Updates for Structure Indexes	2002	VLDB	7.2592618e-05
4,201	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.7363634e-05
4,434	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.5985379e-05
5,225	Indexing Dataspaces	2007	SIGMOD	6.2190653e-05
5,425	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.1332823e-05
5,710	BLAS : An Efficient XPath Processing System	2004	SIGMOD	6.0214073e-05
5,971	Efficient Mining of XML Query Patterns for Caching	2003	VLDB	5.928821e-05
6,073	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	5.8935926e-05
6,720	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.6973355e-05
6,949	Indexing Temporal XML Documents	2004	VLDB	5.6344414e-05
7,342	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5464639e-05
7,599	XQuery Optimization	2003	VLDB	5.4854551e-05
7,641	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.475997e-05
8,000	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	5.4086285e-05
8,555	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	5.3146354e-05
8,568	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.3114964e-05
9,525	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.1667997e-05
9,686	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1406509e-05
9,908	Fast Optimal Twig Joins	2010	VLDB	5.1091349e-05
13,070	XSeq: An Indexing Infrastructure for Tree Pattern Queries	2004	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.0004311045
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.0002928095
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020241971
441	A Fast Index for Semistructured Data	2001	VLDB	0.00018206766

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB
2	922	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD
3	14,319	Efficient XML Path Expression Processing Techniques	2002	VLDB
4	5,817	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD
5	6,073	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB
6	8,000	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB
7	918	Accelerating XPath Location Steps	2002	SIGMOD
8	7,569	Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods	2005	VLDB
9	2,048	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD
10	441	A Fast Index for Semistructured Data	2001	VLDB