{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T13:57:44Z","timestamp":1785333464874,"version":"3.55.0"},"reference-count":42,"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":[[2024,7]]},"abstract":"<jats:p>There is significant interest in examining large datasets using complex domain-specific queries. In many cases, these queries can be accelerated using specialized indexes. Unfortunately, the development of a practical index is difficult, because databases generally require additional features such as updates, concurrency support, crash recovery, etc. There are three major lines of work to alleviate the pain: (1) automatic index composition\/tuning which composes indexes out of core data structure primitives to optimize for specific workloads; (2) generalized index templates which generalize common data structures such as B+-trees for custom queries over custom data types, and (3) data structure dynamization frameworks such as the Bentley-Saxe method which converts a static data structure into an updatable data structure with bounded additional query cost. The first two are limited to very specific queries and\/or data structures and, thus, are not suitable for building a general index dynamization framework. The last one is more promising in its generality but also has limitations on query types, deletion support, and performance tuning. In this paper, we discuss the limitations of the classic index dynamization techniques and propose a path towards a more general and systematic solution. We demonstrate the viability of our framework by realizing it as a C++20 metaprogramming library and conducting case studies on four example queries with their corresponding static index structures. With this framework, many theoretical\/early-stage index designs can easily be extended with support for updates, along with a wide tuning space for query\/update performance trade-offs. This allows index designers to focus on efficient data layouts and query algorithms, thereby dramatically narrowing the gap between novel index designs and deployment.<\/jats:p>","DOI":"10.14778\/3681954.3681969","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"2867-2879","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Towards Systematic Index Dynamization"],"prefix":"10.14778","volume":"17","author":[{"given":"Douglas B.","family":"Rumbaugh","sequence":"first","affiliation":[{"name":"The Pennsylvania State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dong","family":"Xie","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhuoyue","family":"Zhao","sequence":"additional","affiliation":[{"name":"University at Buffalo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2024. BigANN Dataset. https:\/\/big-ann-benchmarks.com\/neurips21.html"},{"key":"e_1_2_1_2_1","unstructured":"2024. Brown Bear Genome v1. https:\/\/www.ncbi.nlm.nih.gov\/datasets\/genome\/GCF_023065955.1\/"},{"key":"e_1_2_1_3_1","unstructured":"2024. English Words Dataset. https:\/\/github.com\/dwyl\/english-words?tab=readme-ov-file"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/BIOINFORMATICS\/BTAC142"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3315507.3330197"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_7_1","unstructured":"Cristian Cardellino. 2019. Spanish Billion Words Corpus and Embeddings. https:\/\/crscardellino.github.io\/SBWCE\/"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485461"},{"key":"e_1_2_1_9_1","volume-title":"M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB.","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB."},{"key":"e_1_2_1_10_1","volume-title":"Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska.","author":"Ding Jialin","year":"2020","unstructured":"Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David B. Lomet, and Tim Kraska. 2020. ALEX: An Updatable Adaptive Learned Index. In SIGMOD."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494136"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.18420\/BTW2019-06"},{"key":"e_1_2_1_14_1","volume-title":"Retrieved","author":"The PostgreSQL Global Development Group","year":"2024","unstructured":"The PostgreSQL Global Development Group. 2024. GIN Indexes. Retrieved April, 2024 from https:\/\/www.postgresql.org\/docs\/16\/gin.html"},{"key":"e_1_2_1_15_1","unstructured":"Joseph M. Hellerstein Jeffrey F. Naughton and Avi Pfeffer. 1995. Generalized Search Trees for Database Systems. In VLDB Umeshwar Dayal Peter M. D. Gray and Shojiro Nishio (Eds.). Morgan Kaufmann 562--573. http:\/\/www.vldb.org\/conf\/1995\/P562.PDF"},{"key":"e_1_2_1_16_1","unstructured":"Xiaocheng Hu Miao Qiao and Yufei Tao. 2014. Independent range sampling. In PODS."},{"key":"e_1_2_1_17_1","first-page":"64","article-title":"The Periodic Table of Data Structures","volume":"41","author":"Idreos Stratos","year":"2018","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Manos Athanassoulis, Niv Dayan, Brian Hentschel, Michael S. Kester, Demi Guo, Lukas M. Maas, Wilson Qin, Abdul Wasay, and Yiyou Sun. 2018. The Periodic Table of Data Structures. IEEE Data Eng. Bull. 41, 3 (2018), 64--75. http:\/\/sites.computer.org\/debull\/A18sept\/p64.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_18_1","first-page":"47","article-title":"Learning Data Structure Alchemy","volume":"42","author":"Idreos Stratos","year":"2019","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Subarna Chatterjee, Wilson Qin, Abdul Wasay, Brian Hentschel, Mike S. Kester, Niv Dayan, Demi Guo, Minseo Kang, and Yiyou Sun. 2019. Learning Data Structure Alchemy. IEEE Data Eng. Bull. 42, 2 (2019), 47--58. http:\/\/sites.computer.org\/debull\/A19june\/p47.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_19_1","volume-title":"Ravishankar Krishnawamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2019\/file\/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177102.3177114"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253272"},{"key":"e_1_2_1_22_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In SIGMOD (SIGMOD '18)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btad243"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.08.002"},{"key":"e_1_2_1_28_1","unstructured":"Frank Olken and Doron Rotem. 1989. Random Sampling from B+ Trees. In VLDB Peter M. G. Apers and Gio Wiederhold (Eds.). Morgan Kaufmann 269--277. http:\/\/www.vldb.org\/conf\/1989\/P269.PDF"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0014927"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241781"},{"key":"e_1_2_1_31_1","volume-title":"Mantis: A Fast, Small, and Exact Large-Scale Sequence-Search Index. In Research in Computational Molecular Biology - 22nd Annual International Conference, Benjamin J","author":"Pandey Prashant","year":"2018","unstructured":"Prashant Pandey, Fatemeh Almodaresi, Michael A. Bender, Michael Ferdman, Rob Johnson, and Rob Patro. 2018. Mantis: A Fast, Small, and Exact Large-Scale Sequence-Search Index. In Research in Computational Molecular Biology - 22nd Annual International Conference, Benjamin J. Raphael (Ed.), Vol. 10812. Springer, 271--273. https:\/\/link.springer.com\/content\/pdf\/bbm%3A978-3-319-89929-9%2F1.pdf"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45072-6_4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626744"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622840"},{"key":"e_1_2_1_35_1","volume-title":"PLEX: Towards Practical Learned Indexing. CoRR abs\/2108.05117","author":"Stoian Mihail","year":"2021","unstructured":"Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. 2021. PLEX: Towards Practical Learned Indexing. CoRR abs\/2108.05117 (2021)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526068"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740097"},{"key":"e_1_2_1_38_1","volume-title":"Are Updatable Learned Indexes Ready? PVDLB 15, 11","author":"Wongkham Chaichon","year":"2022","unstructured":"Chaichon Wongkham, Baotong Lu, Chris Liu, Zhicong Zhong, Eric Lo, and Tianzheng Wang. 2022. Are Updatable Learned Indexes Ready? PVDLB 15, 11 (2022)."},{"key":"e_1_2_1_39_1","volume-title":"ACM","author":"Xie Dong","year":"2021","unstructured":"Dong Xie, Jeff M. Phillips, Michael Matheny, and Feifei Li. 2021. Spatial Independent Range Sampling. In SIGMOD, Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 2023--2035."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494132"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636232"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313789"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:28:34Z","timestamp":1725474514000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":42,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681969"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681969","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}