Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data

Summary: Dynamic interleaving of path and value in composite keys enables CAS indexing for hierarchical data. Trie-based Robust CAS index supports wildcards and descendant axes, robust to selectivity variation, delivering up to 100x gains over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12257
Venue: VLDB
Year: 2020
Pagerank: 5.093636e-05
Overall Rank: 11,794 | 19.09%
DOI: 10.14778/3401960.3401963

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Kevin Wellenzohn (University of Zurich)
2. Michael H. Böhlen (University of Zurich)
3. Sven Helmer (University of Zurich)

BibTeX Citation

@article{wellenzohn_vldb20,
        title = {{Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data}},
        author = {Wellenzohn, Kevin and Böhlen, Michael H. and Helmer, Sven},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {10},
        pages = {1641--1653},
        doi = {10.14778/3401960.3401963},
        url = {https://doi.org/10.14778/3401960.3401963},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
719	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014637695
880	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013432693
882	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.0001342403
1,015	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00012647763
2,006	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.3190255e-05
2,155	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	9.0713545e-05
3,424	Schema-Agnostic Indexing with Azure DocumentDB	2015	VLDB	7.4241655e-05
6,335	QUILTS: Multidimensional Partitioning Framework Based on Query-Aware and Skew-Tolerant Space-Filling Curves	2017	SIGMOD	5.9090498e-05
7,981	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.5146136e-05
9,576	Indexing Highly Dynamic Hierarchical Data	2015	VLDB	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
2	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
3	1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB
4	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
5	1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD
6	430	A Fast Index for Semistructured Data	2001	VLDB
7	7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB
8	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
9	9,576	Indexing Highly Dynamic Hierarchical Data	2015	VLDB
10	3,007	Towards Robust Indexing for Ranked Queries	2006	VLDB