{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:07:44Z","timestamp":1757614064281,"version":"3.44.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>\n            By\n            <jats:italic toggle=\"yes\">adaptive indexing<\/jats:italic>\n            , an index grows dynamically and progressively through query processing. This mode of index-building, well explored over the past fifteen years, proves especially useful in exploratory scenarios where prebuilt indexes do not pay off the time to construct them, as the query workload variably focuses on particular areas of the search space, or the data become quickly obsolete. Despite a significant body of work in multidimensional adaptive indexing, there remains a gap in comparative studies that evaluate these methods on equal terms in a wide spectrum of settings, including data types, distributions, sizes, and workload patterns. This work fills this gap with a comprehensive benchmark to thoroughly evaluate the performance, strengths, and limitations of existing multidimensional adaptive indexing methods across diverse scenarios, contributing valuable insights that complement previous works. Further, we suggest supplementary technical extensions that enhance the efficiency of existing methods.\n          <\/jats:p>","DOI":"10.14778\/3749646.3749709","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4505-4517","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Benchmarking Adaptive Multidimensional Indices"],"prefix":"10.14778","volume":"18","author":[{"given":"Konstantinos","family":"Lampropoulos","sequence":"first","affiliation":[{"name":"U. of Ioannina &amp; Aarhus U."}]},{"given":"Fatemeh","family":"Zardbani","sequence":"additional","affiliation":[{"name":"Aarhus University"}]},{"given":"Nikos","family":"Mamoulis","sequence":"additional","affiliation":[{"name":"U. of Ioannina &amp; Archimedes, Athena R.C."}]},{"given":"Panagiotis","family":"Karras","sequence":"additional","affiliation":[{"name":"U. of Copenhagen &amp; Aarhus U."}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Main memory adaptive indexing for multi-core systems","volume":"3","author":"Alvarez Victor","year":"2014","unstructured":"Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, and Stefan Richter. 2014. Main memory adaptive indexing for multi-core systems. In DaMoN. 3:1\u20133:10.","journal-title":"DaMoN."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1007\/s007780050076"},{"doi-asserted-by":"crossref","unstructured":"Boost. 2015. Boost C++ Libraries. http:\/\/www.boost.org\/. Last accessed 2025-01-10.","key":"e_1_2_1_3_1","DOI":"10.1016\/S0262-1762(15)30089-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.3233\/AIS-200565"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.14778\/3425879.3425880"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/JSEN.2022.3149901"},{"key":"e_1_2_1_7_1","volume-title":"Mokbel","author":"Eldawy Ahmed","year":"2015","unstructured":"Ahmed Eldawy and Mohamed F. Mokbel. 2015. SpatialHadoop: A MapReduce Framework for Spatial Data. In ICDE. 1352\u20131363."},{"key":"e_1_2_1_8_1","volume-title":"Discovery, and Ranking for the Internet of Things (IoT). ACM Comput. Surv. 51, 2","author":"Fathy Yasmin","year":"2018","unstructured":"Yasmin Fathy, Payam Barnaghi, and Rahim Tafazolli. 2018. Large-Scale Indexing, Discovery, and Ranking for the Internet of Things (IoT). ACM Comput. Surv. 51, 2 (2018)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/BF00288933"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.14778\/2180912.2180918"},{"key":"e_1_2_1_11_1","volume-title":"Transactional support for adaptive indexing. The VLDB Journal 23 (04","author":"Graefe Goetz","year":"2014","unstructured":"Goetz Graefe, Felix Halim, Stratos Idreos, Harumi Kuno, Stefan Manegold, and Bernhard Seeger. 2014. Transactional support for adaptive indexing. The VLDB Journal 23 (04 2014), 303\u2013328."},{"key":"e_1_2_1_12_1","volume-title":"Kuno","author":"Graefe Goetz","year":"2010","unstructured":"Goetz Graefe and Harumi A. Kuno. 2010. Self-selecting, self-tuning, incrementally optimized indexes. In EDBT. 371\u2013381."},{"doi-asserted-by":"crossref","unstructured":"Antonin Guttman. 1984. R-trees: a dynamic index structure for spatial searching. In SIGMOD. 47\u201357.","key":"e_1_2_1_13_1","DOI":"10.1145\/971697.602266"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.14778\/2168651.2168652"},{"key":"e_1_2_1_15_1","volume-title":"Progressive Mergesort: Merging Batches of Appends into Progressive Indexes. In EDBT. 481\u2013486.","author":"Holanda Pedro","year":"2021","unstructured":"Pedro Holanda and Stefan Manegold. 2021. Progressive Mergesort: Merging Batches of Appends into Progressive Indexes. In EDBT. 481\u2013486."},{"doi-asserted-by":"crossref","unstructured":"Pedro Holanda Matheus Nerone Eduardo C. de Almeida and Stefan Manegold. 2018. Cracking KD-Tree: The First Multidimensional Adaptive Indexing (Position Paper). In DATA. 393\u2013399.","key":"e_1_2_1_16_1","DOI":"10.5220\/0006944203930399"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.14778\/3358701.3358705"},{"unstructured":"Stratos Idreos. 2010. Database Cracking: Towards Auto-tuning Database Kernels. CWI PhD Thesis (2010).","key":"e_1_2_1_18_1"},{"unstructured":"Stratos Idreos Martin L. Kersten and Stefan Manegold. 2007. Database Cracking. In CIDR. 68\u201378.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"crossref","unstructured":"Stratos Idreos Martin L. Kersten and Stefan Manegold. 2007. Updating a cracked database. In SIGMOD. 413\u2013424.","key":"e_1_2_1_20_1","DOI":"10.1145\/1247480.1247527"},{"doi-asserted-by":"crossref","unstructured":"Stratos Idreos Martin L. Kersten and Stefan Manegold. 2009. Self-organizing tuple reconstruction in column-stores. In SIGMOD. 297\u2013308.","key":"e_1_2_1_21_1","DOI":"10.1145\/1559845.1559878"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.14778\/2002938.2002944"},{"unstructured":"Anders Hammersh\u00f8j Jensen Frederik Lauridsen Fatemeh Zardbani Stratos Idreos and Panagiotis Karras. 2021. Revisiting Multidimensional Adaptive Indexing [Experiment & Analysis]. In EDBT. 469\u2013474.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","volume-title":"Kersten and Stefan Manegold","author":"Martin","year":"2005","unstructured":"Martin L. Kersten and Stefan Manegold. 2005. Cracking the Database Store. In CIDR. 213\u2013224."},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.14778\/3603581.3603592"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1109\/ACCESS.2018.2849865"},{"volume-title":"Spatial Data Management","author":"Mamoulis Nikos","unstructured":"Nikos Mamoulis. 2011. Spatial Data Management. Morgan & Claypool Publishers.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"crossref","unstructured":"Vikram Nathan Jialin Ding Mohammad Alizadeh and Tim Kraska. 2020. Learning Multi-Dimensional Indexes. In SIGMOD. 985\u20131000.","key":"e_1_2_1_28_1","DOI":"10.1145\/3318464.3380579"},{"doi-asserted-by":"crossref","unstructured":"Matheus Agio Nerone Pedro Holanda Eduardo C. de Almeida and Stefan Manegold. 2021. Multidimensional Adaptive & Progressive Indexes. In ICDE. 624\u2013635.","key":"e_1_2_1_29_1","DOI":"10.1109\/ICDE51399.2021.00060"},{"key":"e_1_2_1_30_1","volume-title":"QUASII: QUery-Aware Spatial Incremental Index. In EDBT. 325\u2013336.","author":"Pavlovic Mirjana","year":"2018","unstructured":"Mirjana Pavlovic, Darius Sidlauskas, Thomas Heinis, and Anastasia Ailamaki. 2018. QUASII: QUery-Aware Spatial Incremental Index. In EDBT. 325\u2013336."},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"Database cracking: fancy scan, not poor man's sort!","volume":"4","author":"Pirk Holger","year":"2014","unstructured":"Holger Pirk, Eleni Petraki, Stratos Idreos, Stefan Manegold, and Martin Kersten. 2014. Database cracking: fancy scan, not poor man's sort!. In DaMoN. 4:1\u20134:8.","journal-title":"DaMoN."},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.14778\/2732228.2732229"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1007\/s00778-015-0397-y"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1080\/136588197242185"},{"key":"e_1_2_1_35_1","volume-title":"Zdonik","author":"Stonebraker Michael","year":"2005","unstructured":"Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel Madden, Elizabeth J. O'Neil, Patrick E. O'Neil, Alex Rasin, Nga Tran, and Stanley B. Zdonik. 2005. C-Store: A Column-oriented DBMS. In VLDB. 553\u2013564."},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.14778\/3503585.3503606"},{"doi-asserted-by":"crossref","unstructured":"Dimitrios Tsitsigkos Konstantinos Lampropoulos Panagiotis Bouros Nikos Mamoulis and Manolis Terrovitis. 2021. A Two-layer Partitioning for Non-point Spatial Data. In ICDE. 1787\u20131798.","key":"e_1_2_1_37_1","DOI":"10.1109\/ICDE51399.2021.00157"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.14778\/3598581.3598596"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749709","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T02:51:11Z","timestamp":1757040671000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":38,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749709"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749709","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}