Updates for Structure Indexes

Summary: Incrementally maintains graph-bisimilarity structure indexes for subgraph and edge insertions, modeling new files and small XML changes. Real-data experiments show order-of-magnitude speedups over rebuilding, addressing a previously unstudied maintenance problem. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9039
Venue: VLDB
Year: 2002
Pagerank: 7.4273213e-05
Overall Rank: 3,421 | 76.54%
DOI: 10.1016/B978-155860869-6/50029-9

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. Pradeep Shenoy (University of Washington)

BibTeX Citation

@article{kaushik_vldb02,
        title = {{Updates for Structure Indexes}},
        author = {Kaushik, Raghav and Bohannon, Philip and Naughton, Jeffrey F and Shenoy, Pradeep},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50029-9},
        url = {https://doi.org/10.1016/B978-155860869-6/50029-9},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012688008
4,360	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.7443622e-05
5,688	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD	6.1208788e-05
5,952	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	6.031089e-05
6,808	Indexing Temporal XML Documents	2004	VLDB	5.7664516e-05
7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.5985266e-05
8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.3543292e-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
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
897	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00013339862
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.748172e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,808	Indexing Temporal XML Documents	2004	VLDB
2	8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD
3	7,494	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB
4	2,006	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD
5	6,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
6	1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
7	430	A Fast Index for Semistructured Data	2001	VLDB
8	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
9	1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD
10	5,688	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD