{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:07:40Z","timestamp":1779131260109,"version":"3.51.4"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"JSPS Bilateral Program","award":["JPJSBP120259915"],"award-info":[{"award-number":["JPJSBP120259915"]}]},{"name":"JSPS KAKENHI","award":["25KJ0754"],"award-info":[{"award-number":["25KJ0754"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>Learned indexes are a class of index data structures that enable fast search by approximating the cumulative distribution function (CDF) using machine learning models (Kraska et al., SIGMOD'18). However, recent studies have shown that learned indexes are vulnerable to poisoning attacks, where injecting a small number of poison keys into the training data can significantly degrade model accuracy and reduce index performance (Kornaropoulos et al., SIGMOD'22). In this work, we provide a rigorous theoretical analysis of poisoning attacks targeting linear regression models over CDFs, one of the most basic regression models and a core component in many advanced learned indexes. Our main contributions are as follows: (i) We present a theoretical proof characterizing the optimal single-point poisoning attack and show that the existing method yields the optimal attack. (ii) We show that in multi-point attacks, the existing greedy approach is not always optimal, and we rigorously derive the key properties that an optimal attack should satisfy. (iii) We propose a method to compute an upper bound of the multi-point poisoning attack's impact and empirically demonstrate that the loss under the greedy approach is often close to this bound. Our study deepens the theoretical understanding of attack strategies against linear regression models on CDFs and provides a foundation for the theoretical evaluation of attacks and defenses on learned indexes.<\/jats:p>","DOI":"10.1145\/3802085","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-5366-4842","authenticated-orcid":false,"given":"Atsuki","family":"Sato","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7212-6476","authenticated-orcid":false,"given":"Martin","family":"Aum\u00fcller","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1529-0154","authenticated-orcid":false,"given":"Yusuke","family":"Matsui","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Aref","author":"Al-Mamun Abdullah","year":"2025","unstructured":"Abdullah Al-Mamun, Hao Wu, Qiyang He, Jianguo Wang, and Walid G. Aref. 2025. A Survey of Learned Indexes for the Multi-dimensional Space. ACM Comput. Surv., Vol. 58 (2025), 37 pages."},{"key":"e_1_2_1_2_1","first-page":"668","volume-title":"Proceedings of the International Conference on Extending Database Technology. OpenProceedings","author":"Amarasinghe Kasun","year":"2025","unstructured":"Kasun Amarasinghe, Farhana Choudhury, Jianzhong Qi, and James Bailey. 2025. Learned Indexes with Distribution Smoothing via Virtual Points. In Proceedings of the International Conference on Extending Database Technology. OpenProceedings, Barcelona, Spain, 668-680."},{"key":"e_1_2_1_3_1","volume-title":"Information Systems","volume":"87","author":"Aum\u00fcller Martin","year":"2020","unstructured":"Martin Aum\u00fcller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, Vol. 87 (2020), 13 pages."},{"key":"e_1_2_1_4_1","first-page":"89","article-title":"Recent Approaches and Trends in Approximate Nearest Neighbor Search, with Remarks on Benchmarking","volume":"47","author":"Aum\u00fcller Martin","year":"2023","unstructured":"Martin Aum\u00fcller and Matteo Ceccarello. 2023. Recent Approaches and Trends in Approximate Nearest Neighbor Search, with Remarks on Benchmarking. IEEE Data Eng. Bull., Vol. 47 (2023), 89-105.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_5_1","article-title":"Organization and maintenance of large ordered indexes","volume":"1","author":"Bayer Rudolf","year":"1972","unstructured":"Rudolf Bayer and Edward M. McCreight. 1972. Organization and maintenance of large ordered indexes. Acta Inf., Vol. 1 (1972), 17 pages.","journal-title":"Acta Inf."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press, Cambridge, MA.","edition":"3"},{"key":"e_1_2_1_8_1","volume-title":"Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes. In International Conference on Database Theory. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik","author":"Croquevielle Luis Alberto","year":"2025","unstructured":"Luis Alberto Croquevielle, Guang Yang, Liang Liang, Ali Hadian, and Thomas Heinis. 2025. Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes. In International Conference on Database Theory. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 19:1-19:21."},{"key":"e_1_2_1_9_1","first-page":"155","volume-title":"USENIX Symposium on Operating Systems Design and Implementation. USENIX Association","author":"Dai Yifan","year":"2020","unstructured":"Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2020. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In USENIX Symposium on Operating Systems Design and Implementation. USENIX Association, Berkeley, CA, USA, 155-171."},{"key":"e_1_2_1_10_1","first-page":"11700","article-title":"Adaptive learned bloom filter (ada-bf): Efficient utilization of the classifier with application to real-time information filtering on the web","volume":"33","author":"Dai Zhenwei","year":"2020","unstructured":"Zhenwei Dai and Anshumali Shrivastava. 2020. Adaptive learned bloom filter (ada-bf): Efficient utilization of the classifier with application to real-time information filtering on the web. Advances in Neural Information Processing Systems, Vol. 33 (2020), 11700-11710.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_11_1","first-page":"969","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery","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 Lomet, and Tim Kraska. 2020a. ALEX: An Updatable Adaptive Learned Index. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 969-984."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_13_1","article-title":"Learning-augmented count-min sketches via Bayesian nonparametrics","volume":"24","author":"Dolera Emanuele","year":"2023","unstructured":"Emanuele Dolera, Stefano Favaro, and Stefano Peluchetti. 2023. Learning-augmented count-min sketches via Bayesian nonparametrics. Journal of Machine Learning Research, Vol. 24 (2023), 60 pages.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2025.3528993"},{"key":"e_1_2_1_15_1","volume-title":"ICLR Tiny Papers Track. OpenReview.net","author":"Farwah Harman Singh","unstructured":"Harman Singh Farwah, Gagandeep Singh, and Cheng Tan. 2024. Exploiting Time Channel Vulnerability of Learned Bloom Filters. In ICLR Tiny Papers Track. OpenReview.net, Vienna, Austria, 5 pages."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Machine Learning. PMLR, Virtual, 3123-3132","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. 2020. Why Are Learned Indexes So Effective?. In Proceedings of the International Conference on Machine Learning. PMLR, Virtual, 3123-3132."},{"key":"e_1_2_1_17_1","volume-title":"Proc. VLDB Endow.","volume":"13","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow., Vol. 13 (2020), 14 pages."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/358669.358692"},{"key":"e_1_2_1_19_1","first-page":"1189","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM","author":"Galakatos Alex","year":"2019","unstructured":"Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, Amsterdam, The Netherlands, 1189-1206."},{"key":"e_1_2_1_20_1","article-title":"The Google file system","volume":"37","author":"Ghemawat Sanjay","year":"2003","unstructured":"Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003. The Google file system. SIGOPS Oper. Syst. Rev., Vol. 37 (2003), 15 pages.","journal-title":"SIGOPS Oper. Syst. Rev."},{"key":"e_1_2_1_21_1","volume-title":"FlexFlood: Efficiently Updatable Learned Multi-dimensional Index. In NeurIPS Workshop on Machine Learning for Systems. NeurIPS Workshop on Machine Learning for Systems","author":"Hidaka Fuma","year":"2024","unstructured":"Fuma Hidaka and Yusuke Matsui. 2024. FlexFlood: Efficiently Updatable Learned Multi-dimensional Index. In NeurIPS Workshop on Machine Learning for Systems. NeurIPS Workshop on Machine Learning for Systems, Vancouver, BC, Canada, 13 pages."},{"key":"e_1_2_1_22_1","volume-title":"Learning-Based Frequency Estimation Algorithms. In International Conference on Learning Representations. OpenReview.net","author":"Hsu Chen-Yu","year":"2019","unstructured":"Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. 2019. Learning-Based Frequency Estimation Algorithms. In International Conference on Learning Representations. OpenReview.net, New Orleans, LA, USA, 20 pages."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4380-9_35"},{"key":"e_1_2_1_24_1","first-page":"209","volume-title":"IEEE International Conference on Trust, Security and Privacy in Computing and Communications. IEEE","author":"Jing Xuyang","year":"2022","unstructured":"Xuyang Jing, Xiaojun Cheng, Zheng Yan, and Xian Li. 2022. Deceiving Learning-based Sketches to Cause Inaccurate Frequency Estimation. In IEEE International Conference on Trust, Security and Privacy in Computing and Communications. IEEE, Wuhan, China, 209-216."},{"key":"e_1_2_1_25_1","volume-title":"Proc. VLDB Endow.","volume":"17","author":"Kim Minsu","year":"2024","unstructured":"Minsu Kim, Jinwoo Hwang, Guseul Heo, Seiyeon Cho, Divya Mahajan, and Jongse Park. 2024. Accelerating String-Key Learned Index Structures via Memoization-Based Incremental Training. Proc. VLDB Endow., Vol. 17 (2024), 14 pages."},{"key":"e_1_2_1_26_1","volume-title":"International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. Association for Computing Machinery","author":"Kipf Andreas","year":"2020","unstructured":"Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. 2020. RadixSpline: a single-pass learned index. In International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. Association for Computing Machinery, New York, NY, USA, 5 pages."},{"key":"e_1_2_1_27_1","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley, Reading, Massachusetts.","edition":"2"},{"key":"e_1_2_1_28_1","first-page":"1331","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM","author":"Kornaropoulos Evgenios M","year":"2022","unstructured":"Evgenios M Kornaropoulos, Silei Ren, and Roberto Tamassia. 2022. The price of tailoring the index to your data: Poisoning attacks on learned index structures. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, Philadelphia, PA, USA, 1331-1344."},{"key":"e_1_2_1_29_1","first-page":"489","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery","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 Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 489-504."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_2_1_31_1","volume-title":"A scalable learned index scheme in storage systems. CoRR","author":"Li Pengfei","year":"2019","unstructured":"Pengfei Li, Yu Hua, Pengfei Zuo, and Jingnan Jia. 2019. A scalable learned index scheme in storage systems. CoRR, Vol. abs\/1905.06256 (2019), 13 pages."},{"key":"e_1_2_1_32_1","first-page":"2119","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery","author":"Li Pengfei","year":"2020","unstructured":"Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan. 2020. LISA: A learned index structure for spatial data. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 2119-2133."},{"key":"e_1_2_1_33_1","volume-title":"Proc. VLDB Endow.","volume":"18","author":"Liu Qiyu","year":"2025","unstructured":"Qiyu Liu, Siyuan Han, Yanlin Qi, Jingshu Peng, Jin Li, Longlong Lin, and Lei Chen. 2025. Why Are Learned Indexes So Effective but Sometimes Ineffective? Proc. VLDB Endow., Vol. 18 (2025), 13 pages."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494141"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3118599"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_37_1","first-page":"2789","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery","author":"Marcus Ryan","year":"2020","unstructured":"Ryan Marcus, Emily Zhang, and Tim Kraska. 2020b. Cdfshop: Exploring and optimizing learned index structures. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 2789-2792."},{"key":"e_1_2_1_38_1","first-page":"464","article-title":"A model for learned bloom filters and optimizing by sandwiching","volume":"31","author":"Mitzenmacher Michael","year":"2018","unstructured":"Michael Mitzenmacher. 2018. A model for learned bloom filters and optimizing by sandwiching. Advances in Neural Information Processing Systems, Vol. 31 (2018), 464-473.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_39_1","volume-title":"Proc. ACM Manag. Data","volume":"1","author":"Mo Dingheng","year":"2023","unstructured":"Dingheng Mo, Fanchao Chen, Siqiang Luo, and Caihua Shan. 2023. Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads. Proc. ACM Manag. Data, Vol. 1 (2023), 25 pages."},{"key":"e_1_2_1_40_1","first-page":"985","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery","author":"Nathan Vikram","year":"2020","unstructured":"Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim Kraska. 2020. Learning Multi-Dimensional Indexes. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 985-1000."},{"key":"e_1_2_1_41_1","volume-title":"Optimized Learned Count-Min Sketch. In NeurIPS Workshop on Machine Learning for Systems. NeurIPS Workshop","author":"Nishishita Kyosuke","year":"2025","unstructured":"Kyosuke Nishishita, Atsuki Sato, and Yusuke Matsui. 2025. Optimized Learned Count-Min Sketch. In NeurIPS Workshop on Machine Learning for Systems. NeurIPS Workshop, San Diego, CA, USA, 13 pages."},{"key":"e_1_2_1_42_1","volume-title":"Numerical recipes","author":"Press William H","unstructured":"William H Press. 2007. Numerical recipes 3rd edition: The art of scientific computing. Cambridge University Press, New York, NY, USA.","edition":"3"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_1_44_1","volume-title":"Database Management Systems","author":"Ramakrishnan Raghu","unstructured":"Raghu Ramakrishnan and Johannes Gehrke. 2002. Database Management Systems. McGraw-Hill, Inc., United States."},{"key":"e_1_2_1_45_1","first-page":"1","volume-title":"IEEE International Conference on High Performance Switching and Routing. IEEE","author":"Reviriego Pedro","year":"2021","unstructured":"Pedro Reviriego, Jos\u00e9 Alberto Hern\u00e1ndez, Zhenwei Dai, and Anshumali Shrivastava. 2021. Learned bloom filters in adversarial environments: A malicious URL detection use-case. In IEEE International Conference on High Performance Switching and Routing. IEEE, Paris, France, 1-6."},{"key":"e_1_2_1_46_1","volume-title":"Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions. CoRR","author":"Sato Atsuki","year":"2026","unstructured":"Atsuki Sato, Martin Aum\u00fcller, and Yusuke Matsui. 2026. Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions. CoRR, Vol. abs\/2603.00537 (2026), 26 pages."},{"key":"e_1_2_1_47_1","volume-title":"Advances in Neural Information Processing Systems","volume":"36","author":"Sato Atsuki","year":"2023","unstructured":"Atsuki Sato and Yusuke Matsui. 2023. Fast Partitioned Learned Bloom Filter. Advances in Neural Information Processing Systems, Vol. 36 (2023), 28 pages."},{"key":"e_1_2_1_48_1","article-title":"Learned-Database Systems Security","volume":"2025","author":"Schuster Roei","year":"2025","unstructured":"Roei Schuster, Jin Peng Zhou, Thorsten Eisenhofer, Paul Grubbs, and Nicolas Papernot. 2025. Learned-Database Systems Security. Transactions on Machine Learning Research, Vol. 2025 (2025), 23 pages.","journal-title":"Transactions on Machine Learning Research"},{"key":"e_1_2_1_49_1","volume-title":"Introduction to Information Retrieval","author":"Sch\u00fctze Hinrich","unstructured":"Hinrich Sch\u00fctze, Christopher D. Manning, and Prabhakar Raghavan. 2008. Introduction to Information Retrieval. Cambridge University Press, Cambridge, England."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.23"},{"key":"e_1_2_1_51_1","volume-title":"Umar Farooq Minhas, and Tim Kraska","author":"Spector Benjamin","year":"2021","unstructured":"Benjamin Spector, Andreas Kipf, Kapil Vaidya, Chi Wang, Umar Farooq Minhas, and Tim Kraska. 2021. Bounding the last mile: Efficient learned string indexing. CoRR, Vol. abs\/2111.14905 (2021), 5 pages."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594528"},{"key":"e_1_2_1_53_1","first-page":"308","volume-title":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery","author":"Tang Chuzhe","year":"2020","unstructured":"Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang, Minjie Wang, and Haibo Chen. 2020. XIndex: a scalable learned index for multicore data storage. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery, New York, NY, USA, 308-320."},{"key":"e_1_2_1_54_1","volume-title":"Partitioned Learned Bloom Filters. In International Conference on Learning Representations. OpenReview.net, Online, 17 pages.","author":"Vaidya Kapil","year":"2021","unstructured":"Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. 2021. Partitioned Learned Bloom Filters. In International Conference on Learning Representations. OpenReview.net, Online, 17 pages."},{"key":"e_1_2_1_55_1","first-page":"569","volume-title":"Learned Index for Spatial Queries. In IEEE International Conference on Mobile Data Management. IEEE","author":"Wang Haixin","year":"2019","unstructured":"Haixin Wang, Xiaoyi Fu, Jianliang Xu, and Hua Lu. 2019. Learned Index for Spatial Queries. In IEEE International Conference on Mobile Data Management. IEEE, Hong Kong, Hong Kong, 569-574."},{"key":"e_1_2_1_56_1","first-page":"245","volume-title":"International Conference on Spatial Data and Intelligence. Springer-Verlag","author":"Wang Ning","year":"2020","unstructured":"Ning Wang and Jianqiu Xu. 2020. Spatial queries based on learned index. In International Conference on Spatial Data and Intelligence. Springer-Verlag, Berlin, Heidelberg, 245-257."},{"key":"e_1_2_1_57_1","volume-title":"Proc. ACM Manag. Data","volume":"3","author":"Wang Taiyi","year":"2025","unstructured":"Taiyi Wang, Liang Liang, Guang Yang, Thomas Heinis, and Eiko Yoneki. 2025. A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach. Proc. ACM Manag. Data, Vol. 3 (2025), 26 pages."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the ACM SIGOPS Asia-Pacific Workshop on Systems. Association for Computing Machinery","author":"Wang Youyun","year":"2020","unstructured":"Youyun Wang, Chuzhe Tang, Zhaoguo Wang, and Haibo Chen. 2020. SIndex: a scalable learned index for string keys. In Proceedings of the ACM SIGOPS Asia-Pacific Workshop on Systems. Association for Computing Machinery, New York, NY, USA, 8 pages."},{"key":"e_1_2_1_59_1","volume-title":"Proc. VLDB Endow.","volume":"14","author":"Wu Jiacheng","year":"2021","unstructured":"Jiacheng Wu, Yong Zhang, Shimin Chen, Yu Chen, Jin Wang, and Chunxiao Xing. 2021. Updatable Learned Index with Precise Positions. Proc. VLDB Endow., Vol. 14 (2021), 13 pages."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547322"},{"key":"e_1_2_1_61_1","volume-title":"Proc. VLDB Endow.","volume":"13","author":"Yang Lei","year":"2020","unstructured":"Lei Yang, Hong Wu, Tieying Zhang, Xuntao Cheng, Feifei Li, Lei Zou, Yujie Wang, Rongyao Chen, Jianying Wang, and Gui Huang. 2020. Leaper: a learned prefetcher for cache invalidation in LSM-tree based storage engines. Proc. VLDB Endow., Vol. 13 (2020), 14 pages."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636232"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","first-page":"3415","DOI":"10.14778\/3681954.3682010","article-title":"LITS","volume":"17","author":"Yang Yifan","year":"2024","unstructured":"Yifan Yang and Shimin Chen. 2024. LITS: An Optimized Learned Index for Strings. Proc. VLDB Endow., Vol. 17 (2024), 3415-3427.","journal-title":"An Optimized Learned Index for Strings. Proc. VLDB Endow."},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of the International Conference on Machine Learning. PMLR","author":"Zeighami Sepanta","year":"2023","unstructured":"Sepanta Zeighami and Cyrus Shahabi. 2023. On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing. In Proceedings of the International Conference on Machine Learning. PMLR, Honolulu, Hawaii, USA, 12 pages."},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the International Conference on Machine Learning. JMLR.org","author":"Zeighami Sepanta","year":"2024","unstructured":"Sepanta Zeighami and Cyrus Shahabi. 2024. Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability. In Proceedings of the International Conference on Machine Learning. JMLR.org, Vienna, Austria, 23 pages."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639292"},{"key":"e_1_2_1_67_1","volume-title":"Information Sciences","volume":"507","author":"Zhang Meifan","year":"2020","unstructured":"Meifan Zhang, Hongzhi Wang, Jianzhong Li, and Hong Gao. 2020. Learned Sketches for Frequency Estimation. Information Sciences, Vol. 507 (2020), 21 pages."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639265"},{"key":"e_1_2_1_69_1","first-page":"42","volume-title":"IEEE International Conference on Data Engineering. IEEE","author":"Zhou Wei","year":"2024","unstructured":"Wei Zhou, Chen Lin, Xuanhe Zhou, Guoliang Li, and Tianqing Wang. 2024. TRAP: Tailored Robustness Assessment for Index Advisors via Adversarial Perturbation. In IEEE International Conference on Data Engineering. IEEE, Utrecht, The Netherlands, 42-55."},{"key":"e_1_2_1_70_1","first-page":"69","volume-title":"Proceedings of the International Conference on Big-Data Service and Intelligent Computation. Association for Computing Machinery","author":"Zhou Weihong","year":"2024","unstructured":"Weihong Zhou and Shiyu Yang. 2024. SLIPP: a space-efficient learned index for string keys. In Proceedings of the International Conference on Big-Data Service and Intelligent Computation. Association for Computing Machinery, New York, NY, USA, 69-77."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:33:41Z","timestamp":1779129221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802085"],"URL":"https:\/\/doi.org\/10.1145\/3802085","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}