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: h889be45ff82251f0
Venue: VLDB
Year: 2002
Pagerank: 7.2626877e-05
Overall Rank: 3,490 | 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,023	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012432693
4,433	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.6015942e-05
5,816	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD	5.9844725e-05
6,070	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	5.896379e-05
6,946	Indexing Temporal XML Documents	2004	VLDB	5.6371099e-05
7,699	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.4751052e-05
9,029	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.2342004e-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
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00043130126
740	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014325275
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013083677
921	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00013069413
2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5622073e-05

Semantically Similar Papers

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