{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T03:54:30Z","timestamp":1769313270936,"version":"3.49.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T00:00:00Z","timestamp":1665792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T00:00:00Z","timestamp":1665792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006447","name":"University of Zurich","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006447","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 trie-based 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 tree to scale it to data-intensive applications with a high insertion rate. We illustrate RSCAS\u2019s robustness and scalability by indexing data from the Software Heritage (SWH) archive, which is the world\u2019s largest, publicly available source code archive.<\/jats:p>","DOI":"10.1007\/s00778-022-00764-y","type":"journal-article","created":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T17:02:27Z","timestamp":1665853347000},"page":"689-715","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Robust and scalable content-and-structure indexing"],"prefix":"10.1007","volume":"32","author":[{"given":"Kevin","family":"Wellenzohn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael H.","family":"B\u00f6hlen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9666-1932","authenticated-orcid":false,"given":"Sven","family":"Helmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Pietri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Zacchiroli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,15]]},"reference":[{"key":"764_CR1","unstructured":"Apache Lucene.: https:\/\/lucene.apache.org\/ (2021). Accessed September 2021"},{"issue":"10","key":"764_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/3183558","volume":"61","author":"J Abramatic","year":"2018","unstructured":"Abramatic, J., Cosmo, R.D., Zacchiroli, S.: Building the universal archive of source code. Commun. ACM 61(10), 29\u201331 (2018)","journal-title":"Commun. ACM"},{"issue":"14","key":"764_CR3","first-page":"1834","volume":"6","author":"D Achakeev","year":"2013","unstructured":"Achakeev, D., Seeger, B.: Efficient bulk updates on multiversion B-trees. PVLDB 6(14), 1834\u20131845 (2013)","journal-title":"PVLDB"},{"issue":"9","key":"764_CR4","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"issue":"14","key":"764_CR5","first-page":"1905","volume":"7","author":"S Alsubaiee","year":"2014","unstructured":"Alsubaiee, S., et al.: AsterixDB: a scalable, open source BDMS. PVLDB 7(14), 1905\u20131916 (2014)","journal-title":"PVLDB"},{"key":"764_CR6","unstructured":"Apache.: Apache Jackrabbit Oak. https:\/\/jackrabbit.apache.org\/oak\/ (2021). Accessed September 2021"},{"issue":"1","key":"764_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1021-x","volume":"37","author":"L Arge","year":"2003","unstructured":"Arge, L.: The buffer tree: a technique for designing batched external data structures. Algorithmica 37(1), 1\u201324 (2003)","journal-title":"Algorithmica"},{"key":"764_CR8","unstructured":"den Bercken, J.V., Seeger, B., Widmayer, P.: A generic approach to bulk loading multidimensional index structures. In: VLDB, pp. 406\u2013415 (1997)"},{"key":"764_CR9","doi-asserted-by":"crossref","unstructured":"Brunel, R., Finis, J., Franz, G., May, N., Kemper, A., Neumann, T., F\u00e4rber, F.: Supporting hierarchical data in SAP HANA. In: ICDE, pp. 1280\u20131291 (2015)","DOI":"10.1109\/ICDE.2015.7113376"},{"issue":"2","key":"764_CR10","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/1365815.1365816","volume":"26","author":"F Chang","year":"2008","unstructured":"Chang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E.: Bigtable: a distributed storage system for structured data. ACM Trans. Comput. Syst. 26(2), 4:1-4:26 (2008)","journal-title":"ACM Trans. Comput. Syst."},{"key":"764_CR11","doi-asserted-by":"crossref","unstructured":"Cooper, B.F., Sample, N., Franklin, M.J., Hjaltason, G.R., Shadmon, M.: A fast index for semistructured data. In: VLDB, pp. 341\u2013350 (2001)","DOI":"10.1145\/508791.508963"},{"key":"764_CR12","doi-asserted-by":"crossref","unstructured":"DeCandia, G., et\u00a0al.: Dynamo: Amazon\u2019s highly available key-value store. In: ACM SOSP, pp. 205\u2013220. ACM (2007)","DOI":"10.1145\/1323293.1294281"},{"key":"764_CR13","doi-asserted-by":"crossref","unstructured":"Di\u00a0Cosmo, R., Zacchiroli, S.: Software heritage: Why and how to preserve software source code. In: iPRES (2017)","DOI":"10.1145\/3059009.3059066"},{"key":"764_CR14","doi-asserted-by":"crossref","unstructured":"Finis, J., Brunel, R., Kemper, A., Neumann, T., F\u00e4rber, F., May, N.: DeltaNI: an efficient labeling scheme for versioned hierarchical data. In: SIGMOD, pp. 905\u2013916 (2013)","DOI":"10.1145\/2463676.2465329"},{"issue":"10","key":"764_CR15","first-page":"986","volume":"8","author":"J Finis","year":"2015","unstructured":"Finis, J., Brunel, R., Kemper, A., Neumann, T., May, N., F\u00e4rber, F.: Indexing highly dynamic hierarchical data. PVLDB 8(10), 986\u2013997 (2015)","journal-title":"PVLDB"},{"key":"764_CR16","doi-asserted-by":"crossref","unstructured":"Gilad, E., Bortnikov, E., Braginsky, A., Gottesman, Y., Hillel, E., Keidar, I., Moscovici, N., Shahout, R.: Evendb: Optimizing key-value storage for spatial locality. In: Proceedings of the 15th European Conference on Computer Systems (EuroSys\u201920) (2020)","DOI":"10.1145\/3342195.3387523"},{"key":"764_CR17","unstructured":"Goldman, R., Widom, J.: DataGuides: enabling query formulation and optimization in semistructured databases. In: VLDB, pp. 436\u2013445 (1997)"},{"key":"764_CR18","doi-asserted-by":"crossref","unstructured":"He, R., McAuley, J.J.: Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In: WWW, pp. 507\u2013517 (2016)","DOI":"10.1145\/2872427.2883037"},{"issue":"2","key":"764_CR19","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1147\/sj.452.0321","volume":"45","author":"C Kanne","year":"2006","unstructured":"Kanne, C., Moerkotte, G.: The importance of sibling clustering for efficient bulkload of XML document trees. IBM Syst. J. 45(2), 321\u2013334 (2006)","journal-title":"IBM Syst. J."},{"key":"764_CR20","doi-asserted-by":"crossref","unstructured":"Kaushik, R., Krishnamurthy, R., Naughton, J.F., Ramakrishnan, R.: On the integration of structure indexes and inverted lists. In: SIGMOD, pp. 779\u2013790 (2004)","DOI":"10.1145\/1007568.1007656"},{"key":"764_CR21","doi-asserted-by":"crossref","unstructured":"Leis, V., Kemper, A., Neumann, T.: The adaptive radix tree: ARTful indexing for main-memory databases. In: ICDE, pp. 38\u201349 (2013)","DOI":"10.1109\/ICDE.2013.6544812"},{"issue":"4","key":"764_CR22","doi-asserted-by":"publisher","first-page":"449","DOI":"10.14778\/3372716.3372719","volume":"13","author":"C Luo","year":"2019","unstructured":"Luo, C., Carey, M.J.: On performance stability in LSM-based storage systems. Proc. VLDB Endow. 13(4), 449\u2013462 (2019)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"764_CR23","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s00778-019-00555-y","volume":"29","author":"C Luo","year":"2020","unstructured":"Luo, C., Carey, M.J.: LSM-based storage techniques: a survey. VLDB J. 29(1), 393\u2013418 (2020)","journal-title":"VLDB J."},{"key":"764_CR24","doi-asserted-by":"crossref","unstructured":"Luo, S., Chatterjee, S., Ketsetsidis, R., Dayan, N., Qin, W., Idreos, S.: Rosetta: A robust space-time optimized range filter for key-value stores. In: SIGMOD \u201920, pp. 2071\u20132086 (2020)","DOI":"10.1145\/3318464.3389731"},{"issue":"1","key":"764_CR25","first-page":"1","volume":"30","author":"C Mathis","year":"2015","unstructured":"Mathis, C., H\u00e4rder, T., Schmidt, K., B\u00e4chle, S.: XML indexing and storage: fulfilling the wish list. Comput. Sci. - R &D 30(1), 1 (2015)","journal-title":"Comput. Sci. - R &D"},{"issue":"12","key":"764_CR26","doi-asserted-by":"publisher","first-page":"3217","DOI":"10.14778\/3415478.3415546","volume":"13","author":"Y Matsunobu","year":"2020","unstructured":"Matsunobu, Y., Dong, S., Lee, H.: MyRocks: LSM-tree database storage engine serving Facebook\u2019s social graph. Proc. VLDB Endow. 13(12), 3217\u20133230 (2020)","journal-title":"Proc. VLDB Endow."},{"key":"764_CR27","doi-asserted-by":"crossref","unstructured":"Merkle, R.C.: A digital signature based on a conventional encryption function. In: CRYPTO, vol. 293, pp. 369\u2013378 (1987)","DOI":"10.1007\/3-540-48184-2_32"},{"key":"764_CR28","doi-asserted-by":"crossref","unstructured":"Milo, T., Suciu, D.: Index structures for path expressions. In: ICDT, pp. 277\u2013295 (1999)","DOI":"10.1007\/3-540-49257-7_18"},{"issue":"4","key":"764_CR29","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA - practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"764_CR30","unstructured":"Morton, G.: A computer oriented geodetic data base; and a new technique in file sequencing. Tech. rep, IBM Ltd (1966)"},{"issue":"5","key":"764_CR31","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1137\/060653780","volume":"37","author":"BG Nickerson","year":"2008","unstructured":"Nickerson, B.G., Shi, Q.: On k-d range search with patricia tries. SIAM J. Comput. 37(5), 1373\u20131386 (2008)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"764_CR32","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s002360050048","volume":"33","author":"PE O\u2019Neil","year":"1996","unstructured":"O\u2019Neil, P.E., Cheng, E., Gawlick, D., O\u2019Neil, E.J.: The log-structured merge-tree (LSM-Tree). Acta Informatica 33(4), 351\u2013385 (1996)","journal-title":"Acta Informatica"},{"key":"764_CR33","doi-asserted-by":"crossref","unstructured":"Orenstein, J.A., Merrett, T.H.: A class of data structures for associative searching. In: PODS, pp. 181\u2013190 (1984)","DOI":"10.1145\/588011.588037"},{"key":"764_CR34","doi-asserted-by":"crossref","unstructured":"Pietri, A., Spinellis, D., Zacchiroli, S.: The software heritage graph dataset: Large-scale analysis of public software development history. In: MSR, pp. 138\u2013142 (2020)","DOI":"10.1145\/3379597.3387510"},{"key":"764_CR35","doi-asserted-by":"crossref","unstructured":"Procopiuc, O., Agarwal, P.K., Arge, L., Vitter, J.S.: Bkd-tree: A dynamic scalable kd-tree. In: SSTD, pp. 46\u201365 (2003)","DOI":"10.1007\/978-3-540-45072-6_4"},{"key":"764_CR36","unstructured":"Ramsak, F., Markl, V., Fenk, R., Zirkel, M., Elhardt, K., Bayer, R.: Integrating the UB-Tree into a database system kernel. In: VLDB, pp. 263\u2013272 (2000)"},{"issue":"4","key":"764_CR37","doi-asserted-by":"publisher","first-page":"2930","DOI":"10.1007\/s10664-020-09828-5","volume":"25","author":"G Rousseau","year":"2020","unstructured":"Rousseau, G., Cosmo, R.D., Zacchiroli, S.: Software provenance tracking at the scale of public source code. Empir. Softw. Eng. 25(4), 2930\u20132959 (2020)","journal-title":"Empir. Softw. Eng."},{"key":"764_CR38","unstructured":"Samet, H.: Foundations of multidimensional and metric data structures. Morgan Kaufmann series in data management systems. Academic Press (2006)"},{"key":"764_CR39","doi-asserted-by":"crossref","unstructured":"Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: XMark: A benchmark for XML data management. In: VLDB, pp. 974\u2013985 (2002)","DOI":"10.1016\/B978-155860869-6\/50096-2"},{"key":"764_CR40","doi-asserted-by":"crossref","unstructured":"Shanbhag, A., Jindal, A., Madden, S., Quian\u00e9-Ruiz, J., Elmore, A.J.: A robust partitioning scheme for ad-hoc query workloads. In: SoCC, pp. 229\u2013241 (2017)","DOI":"10.1145\/3127479.3131613"},{"issue":"12","key":"764_CR41","first-page":"1668","volume":"8","author":"D Shukla","year":"2015","unstructured":"Shukla, D., et al.: Schema-agnostic indexing with Azure DocumentDB. PVLDB 8(12), 1668\u20131679 (2015)","journal-title":"PVLDB"},{"issue":"10","key":"764_CR42","first-page":"1641","volume":"13","author":"K Wellenzohn","year":"2020","unstructured":"Wellenzohn, K., B\u00f6hlen, M.H., Helmer, S.: Dynamic interleaving of content and structure for robust indexing of semi-structured hierarchical data. PVLDB 13(10), 1641\u20131653 (2020)","journal-title":"PVLDB"},{"key":"764_CR43","doi-asserted-by":"crossref","unstructured":"Wellenzohn, K., B\u00f6hlen, M.H., Helmer, S., Pietri, A., Zacchiroli, S.: Robust and scalable content-and-structure indexing (extended version). Tech. rep., CoRR (2022). https:\/\/arxiv.org\/abs\/2209.05126","DOI":"10.1007\/s00778-022-00764-y"},{"key":"764_CR44","doi-asserted-by":"crossref","unstructured":"Wellenzohn, K., Popovic, L., B\u00f6hlen, M., Helmer, S.: Inserting keys into the robust content-and-structure (RCAS) index. In: ADBIS, pp. 121\u2013135 (2021)","DOI":"10.1007\/978-3-030-82472-3_10"},{"key":"764_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, H., Lim, H., Leis, V., Andersen, D.G., Kaminsky, M., Keeton, K., Pavlo, A.: Surf: Practical range query filtering with fast succinct tries. In: SIGMOD \u201918, pp. 323\u2013336 (2018)","DOI":"10.1145\/3183713.3196931"},{"key":"764_CR46","unstructured":"Zhong, W., Chen, C., Wu, X., Jiang, S.: REMIX: efficient range query for lsm-trees. In: 19th USENIX Conf. on File and Storage Technologies, (FAST\u201921), pp. 51\u201364 (2021)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00764-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-022-00764-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00764-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,29]],"date-time":"2023-05-29T02:05:21Z","timestamp":1685325921000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-022-00764-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,15]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["764"],"URL":"https:\/\/doi.org\/10.1007\/s00778-022-00764-y","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,15]]},"assertion":[{"value":"21 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}