Incremental Maintenance of XML Structural Indexes

Summary: Incremental maintenance algorithms for XML structural indexes (1-index and A(k)-index) with provable guarantees on index quality. Maintains a minimal index; for acyclic data the 1-index is minimum, and the minimal A(k)-index is unique for both acyclic and cyclic graphs, with experiments showing reduced index size and faster updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3605
Venue: SIGMOD
Year: 2004
Pagerank: 6.1208788e-05
Overall Rank: 5,688 | 60.98%
DOI: 10.1145/1007568.1007624

Incoming Non-self Citations Over Time

Authors

1. Ke Yi (Duke University)
2. Hao He (Duke University)
3. Ioana Stanoi (IBM)
4. Jun Yang (Duke University)

BibTeX Citation

@inproceedings{yi_sigmod04,
        title = {{Incremental Maintenance of XML Structural Indexes}},
        author = {Yi, Ke and He, Hao and Stanoi, Ioana and Yang, Jun},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007624},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007624},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
5,952	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	6.031089e-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 6 of 6 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
470	Query Optimization for XML	1999	VLDB	0.00017965707
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012688008
2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.748172e-05
3,421	Updates for Structure Indexes	2002	VLDB	7.4273213e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
2	2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB
3	718	Covering Indexes for Branching Path Queries	2002	SIGMOD
4	7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB
5	8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD
6	2,006	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD
7	1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
8	6,808	Indexing Temporal XML Documents	2004	VLDB
9	1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD
10	3,421	Updates for Structure Indexes	2002	VLDB