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.00014325275
Overall Rank: 740 | 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.00020765078
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017972038
1,023	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012432693
1,174	Projecting XML Documents	2003	VLDB	0.00011668225
1,784	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.6511778e-05
1,901	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.4044288e-05
2,046	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.1269888e-05
2,715	A Framework for Using Materialized XPath Views in XML Query Processing	2004	VLDB	8.1017908e-05
3,490	Updates for Structure Indexes	2002	VLDB	7.2626877e-05
4,200	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.7395481e-05
4,433	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.6015942e-05
5,220	Indexing Dataspaces	2007	SIGMOD	6.2220078e-05
5,421	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.1361863e-05
5,709	BLAS : An Efficient XPath Processing System	2004	SIGMOD	6.0242536e-05
5,971	Efficient Mining of XML Query Patterns for Caching	2003	VLDB	5.9316289e-05
6,070	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	5.896379e-05
6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.7000336e-05
6,946	Indexing Temporal XML Documents	2004	VLDB	5.6371099e-05
7,339	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5490881e-05
7,592	XQuery Optimization	2003	VLDB	5.4880486e-05
7,635	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.4785904e-05
7,995	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	5.4111901e-05
8,548	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	5.3171525e-05
8,561	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.314012e-05
9,514	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.1692468e-05
9,679	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1430855e-05
9,901	Fast Optimal Twig Joins	2010	VLDB	5.1115496e-05
13,064	XSeq: An Indexing Infrastructure for Tree Pattern Queries	2004	SIGMOD	4.9793485e-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.00043130126
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029294114
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020251513
441	A Fast Index for Semistructured Data	2001	VLDB	0.00018215078

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,382	Benchmarking Queries over Trees: Learning the Hard Truth the Hard Way	2000	SIGMOD
2	921	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD
3	14,314	Efficient XML Path Expression Processing Techniques	2002	VLDB
4	5,816	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD
5	6,070	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB
6	7,995	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB
7	918	Accelerating XPath Location Steps	2002	SIGMOD
8	7,563	Benefits of Path Summaries in an XML Query Optimizer Supporting Multiple Access Methods	2005	VLDB
9	2,046	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD
10	441	A Fast Index for Semistructured Data	2001	VLDB