Skip to Main content Skip to Navigation
New interface
Journal articles

Robust and Scalable Content-and-Structure Indexing

Abstract : Frequent queries on semi-structured hierarchical data are Content-and-Structure (CAS) queries that filter data items based on their location in the hierarchical structure and their value for some attribute. We propose the Robust and Scalable Content-and-Structure (RSCAS) index to efficiently answer CAS queries on big semi-structured data. To get an index that is robust against queries with varying selectivities we introduce a novel dynamic interleaving that merges the path and value dimensions of composite keys in a balanced manner. We store interleaved keys in our triebased RSCAS index, which efficiently supports a wide range of CAS queries, including queries with wildcards and descendant axes. We implement RSCAS as a log-structured merge (LSM) tree to scale it to data-intensive applications with a high insertion rate. We illustrate RSCAS's robustness and scalability by indexing data from the Software Heritage (SWH) archive, which is the world's largest, publiclyavailable source code archive.
Complete list of metadata
Contributor : Stefano Zacchiroli Connect in order to contact the contributor
Submitted on : Saturday, September 24, 2022 - 2:44:16 PM
Last modification on : Friday, September 30, 2022 - 5:33:18 PM


Files produced by the author(s)


  • HAL Id : hal-03787268, version 1



Kevin Wellenzohn, Michael H. Böhlen, Sven Helmer, Antoine Pietri, Stefano Zacchiroli. Robust and Scalable Content-and-Structure Indexing. The VLDB Journal, inPress. ⟨hal-03787268⟩



Record views


Files downloads