{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T14:30:21Z","timestamp":1785335421528,"version":"3.55.0"},"reference-count":58,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,3,3]],"date-time":"2023-03-03T00:00:00Z","timestamp":1677801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"MIUR Project of National Relevance 2017WR7SHH \u201cMulticriteria Data Structures and Algorithms: from compressed to learned indexes, and beyond\u201d"},{"name":"Project INdAM\u2014GNCS \u201cModellizazzione ed analisi di big knowledge graphs per la risoluzione di problemi in ambito medico e web\u201d"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Data"],"abstract":"<jats:p>Machine-learning techniques, properly combined with data structures, have resulted in Learned Static Indexes, innovative and powerful tools that speed up Binary Searches with the use of additional space with respect to the table being searched into. Such space is devoted to the machine-learning models. Although in their infancy, these are methodologically and practically important, due to the pervasiveness of Sorted Table Search procedures. In modern applications, model space is a key factor, and a major open question concerning this area is to assess to what extent one can enjoy the speeding up of Binary Searches achieved by Learned Indexes while using constant or nearly constant-space models. In this paper, we investigate the mentioned question by (a) introducing two new models, i.e., the Learned k-ary Search Model and the Synoptic Recursive Model Index; and (b) systematically exploring the time\u2013space trade-offs of a hierarchy of existing models, i.e., the ones in the reference software platform Searching on Sorted Data, together with the new ones proposed here. We document a novel and rather complex time\u2013space trade-off picture, which is informative for users as well as designers of Learned Indexing data structures. By adhering to and extending the current benchmarking methodology, we experimentally show that the Learned k-ary Search Model is competitive in time with respect to Binary Search in constant additional space. Our second model, together with the bi-criteria Piece-wise Geometric Model Index, can achieve speeding up of Binary Search with a model space of 0.05% more than the one taken by the table, thereby, being competitive in terms of the time\u2013space trade-off with existing proposals. The Synoptic Recursive Model Index and the bi-criteria Piece-wise Geometric Model complement each other quite well across the various levels of the internal memory hierarchy. Finally, our findings stimulate research in this area since they highlight the need for further studies regarding the time\u2013space relation in Learned Indexes.<\/jats:p>","DOI":"10.3390\/data8030056","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T04:29:58Z","timestamp":1678076998000},"page":"56","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Learned Sorted Table Search and Static Indexes in Small-Space Data Models"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4004-9338","authenticated-orcid":false,"given":"Domenico","family":"Amato","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e1 degli Studi di Palermo, 90123 Palermo, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6286-8871","authenticated-orcid":false,"given":"Raffaele","family":"Giancarlo","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e1 degli Studi di Palermo, 90123 Palermo, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1602-0693","authenticated-orcid":false,"given":"Giosu\u00e9","family":"Lo Bosco","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e1 degli Studi di Palermo, 90123 Palermo, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,3]]},"reference":[{"key":"ref_1","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Kraska, T., Beutel, A., Chi, E.H., Dean, J., and Polyzotis, N. (2018, January 10\u201315). The case for learned index structures. Proceedings of the 2018 International Conference on Management of Data, Houston, TX, USA.","DOI":"10.1145\/3183713.3196909"},{"key":"ref_3","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming, Volume 3 (Sorting and Searching), Addison-Wesley."},{"key":"ref_4","unstructured":"Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1974). The Design and Analysis of Computer Algorithms, Addison Wesley."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","article-title":"Ubiquitous B-Tree","volume":"11","author":"Comer","year":"1979","journal-title":"ACM Comput. Surv. CSUR"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Amato, D., Lo Bosco, G., and Giancarlo, R. (2021, January 1\u20133). Learned Sorted Table Search and Static Indexes in Small Model Space. Proceedings of the AIxIA 2021\u2014Advances in Artificial Intelligence: 20th International Conference of the Italian Association for Artificial Intelligence, Virtual. Revised Selected Papers.","DOI":"10.1007\/978-3-031-08421-8_32"},{"key":"ref_7","unstructured":"Ferragina, P., and Vinciguerra, G. (2020). Recent Trends in Learning from Data, Springer International Publishing."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/3528087","article-title":"Algorithms with Predictions","volume":"65","author":"Mitzenmacher","year":"2022","journal-title":"Commun. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.14778\/3421424.3421425","article-title":"Benchmarking Learned Indexes","volume":"14","author":"Marcus","year":"2020","journal-title":"Proc. VLDB Endow."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Iliadis, L., Jayne, C., Tefas, A., and Pimenidis, E. (2022, January 17\u201320). On the Suitability of Neural Networks as Building Blocks for the Design of Efficient Learned Indexes. Proceedings of the Engineering Applications of Neural Networks, Crete, Greece.","DOI":"10.1007\/978-3-031-08223-8"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.14778\/3510397.3510405","article-title":"A critical analysis of recursive model indexes","volume":"15","author":"Maltry","year":"2022","journal-title":"Proc. VLDB Endow."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Marcus, R., Zhang, E., and Kraska, T. (2020, January 14\u201319). CDFShop: Exploring and optimizing learned index structures. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD\u201920, Portland, OR, USA.","DOI":"10.1145\/3318464.3384706"},{"key":"ref_13","first-page":"1162","article-title":"The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds","volume":"13","author":"Ferragina","year":"2020","journal-title":"PVLDB"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1007\/s00453-012-9658-y","article-title":"Approximating Points by a Piecewise Linear Function","volume":"66","author":"Chen","year":"2012","journal-title":"Algorithmica"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Galakatos, A., Markovitch, M., Binnig, C., Fonseca, R., and Kraska, T. (July, January 30). FITing-Tree: A data-aware index structure. Proceedings of the 2019 International Conference on Management of Data, Amsterdam, The Netherlands. SIGMOD\u201919.","DOI":"10.1145\/3299869.3319860"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Kipf, A., Marcus, R., van Renen, A., Stoian, M., Kemper, A., Kraska, T., and Neumann, T. (2019, January 12\u201314). SOSD: A benchmark for learned indexes. Proceedings of the ML for Systems at NeurIPS, MLForSystems @ NeurIPS\u201919, Vancouver, BC, USA.","DOI":"10.14778\/3421424.3421425"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kipf, A., Marcus, R., van Renen, A., Stoian, M., Kemper, A., Kraska, T., and Neumann, T. (2020, January 14\u201320). RadixSpline: A single-pass learned index. Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, Portland, OR, USA.","DOI":"10.1145\/3401071.3401659"},{"key":"ref_18","unstructured":"Neumann, T., and Michel, S. (2008, January 7\u201310). Smooth Interpolating Histograms with Error Guarantees. Proceedings of the Sharing Data, Information and Knowledge, Cardiff, UK."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ding, J., Minhas, U.F., Yu, J., Wang, C., Do, J., Li, Y., Zhang, H., Chandramouli, B., Gehrke, J., and Kossmann, D. (2020, January 14\u201319). ALEX: An Updatable Adaptive Learned Index. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland, OR, USA. SIGMOD\u201920.","DOI":"10.1145\/3318464.3389711"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1002\/spe.3150","article-title":"Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform","volume":"53","author":"Amato","year":"2023","journal-title":"Softw. Pract. Exp."},{"key":"ref_21","unstructured":"Kipf, A., Marcus, R., van Renen, A., Stoian, M., Kemper, A., Kraska, T., and Neumann, T. (2022, June 05). SOSD Leaderboard. Available online: https:\/\/learnedsystems.github.io\/SOSDLeaderboard\/leaderboard\/."},{"key":"ref_22","unstructured":"Rao, J., and Ross, K.A. (1999, January 7\u201310). Cache conscious indexing for decision-support in main memory. Proceedings of the 25th International Conference on Very Large Data, Edinburgh, Scotland, UK."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1.3:1","DOI":"10.1145\/3053370","article-title":"Array layouts for comparison-based searching","volume":"22","author":"Khuong","year":"2017","journal-title":"J. Exp. Algorithmics"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3003665.3003669","article-title":"Database Meets Deep Learning: Challenges and Opportunities","volume":"45","author":"Wang","year":"2016","journal-title":"SIGMOD Rec."},{"key":"ref_25","unstructured":"Kraska, T., Alizadeh, M., Beutel, A., Chi, E.H., Ding, J., Kristo, A., Leclerc, G., Madden, S., Mao, H., and Nathan, V. (2019, January 13\u201316). Sagedb: A Learned Database System. Proceedings of the CIDR 2019-9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Li, P., Lu, H., Zheng, Q., Yang, L., and Pan, G. (2020, January 14\u201319). LISA: A Learned Index Structure for Spatial Data. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland, OR, USA. SIGMOD\u201920.","DOI":"10.1145\/3318464.3389703"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Wang, H., Fu, X., Xu, J., and Lu, H. (2019, January 10\u201313). Learned Index for Spatial Queries. Proceedings of the 2019 20th IEEE International Conference on Mobile Data Management (MDM), Hong Kong, China.","DOI":"10.1109\/MDM.2019.00121"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ol\u2019ha, J., Slanin\u00e1kov\u00e1, T., Gendiar, M., Antol, M., and Dohnal, V. (2022). Learned Indexing in Proteins: Substituting Complex Distance Calculations with Embedding and Clustering Techniques. arXiv.","DOI":"10.1007\/978-3-031-17849-8_22"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1705","DOI":"10.14778\/3342263.3342644","article-title":"Neo: A Learned Query Optimizer","volume":"12","author":"Marcus","year":"2019","journal-title":"Proc. VLDB Endow."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1016\/j.ins.2020.09.070","article-title":"LAQP: Learning-based approximate query processing","volume":"546","author":"Zhang","year":"2021","journal-title":"Inf. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/3542700.3542703","article-title":"Bao: Making Learned Query Optimization Practical","volume":"51","author":"Marcus","year":"2022","journal-title":"SIGMOD Rec."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"75205","DOI":"10.1109\/ACCESS.2022.3190376","article-title":"Learned Query Optimizers: Evaluation and Improvement","volume":"10","author":"Mikhaylov","year":"2022","journal-title":"IEEE Access"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/Time Trade-Offs in Hash Coding with Allowable Errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"ref_34","unstructured":"Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (2018, January 2\u20138). A model for learned bloom filters and optimizing by sandwiching. Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada."},{"key":"ref_35","unstructured":"Vaidya, K., Knorr, E., Kraska, T., and Mitzenmacher, M. (2020). Partitioned Learned Bloom Filter. arXiv."},{"key":"ref_36","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","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Fumagalli, G., Raimondi, D., Giancarlo, R., Malchiodi, D., and Frasca, M. (2022, January 3\u20135). On the Choice of General Purpose Classifiers in Learned Bloom Filters: An Initial Analysis within Basic Filters. Proceedings of the 11th International Conference on Pattern Recognition Applications and Methods (ICPRAM), Online.","DOI":"10.5220\/0010889000003122"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2565","DOI":"10.1007\/s10115-022-01734-0","article-title":"Learning to hash: A comprehensive survey of deep learning-based hashing methods","volume":"64","author":"Singh","year":"2022","journal-title":"Knowl. Inf. Syst."},{"key":"ref_39","unstructured":"Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (2022, January 17\u201323). Learning Augmented Binary Search Trees. Proceedings of the 39th International Conference on Machine Learning, Baltimore, MD, USA."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Boffa, A., Ferragina, P., and Vinciguerra, G. (2021, January 10\u201311). A \u201clearned\u201d approach to quicken and compress rank\/select dictionaries. Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), Alexandria, VA, USA.","DOI":"10.1137\/1.9781611976472.4"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1093\/bioinformatics\/btaa911","article-title":"Sapling: Accelerating suffix array queries with learned data models","volume":"37","author":"Kirsche","year":"2020","journal-title":"Bioinformatics"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Boffa, A., Ferragina, P., Tosoni, F., and Vinciguerra, G. (2022, January 8\u201310). Compressed string dictionaries via data-aware subtrie compaction. Proceedings of the 29th International Symposium on String Processing and Information Retrieval (SPIRE), Concepcion, Chile.","DOI":"10.1007\/978-3-031-20643-6_17"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Kristo, A., Vaidya, K., \u00c7etintemel, U., Misra, S., and Kraska, T. (2020, January 14\u201319). The Case for a Learned Sorting Algorithm. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland, OR, USA. SIGMOD\u201920.","DOI":"10.1145\/3318464.3389752"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Bishop, C.M. (1995). Neural Networks for Pattern Recognition, Oxford University Press, Inc.","DOI":"10.1201\/9781420050646.ptb6"},{"key":"ref_45","unstructured":"Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep Learning, The MIT Press."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"3222","DOI":"10.14778\/3476311.3476392","article-title":"Towards Instance-Optimized Data Systems","volume":"14","author":"Kraska","year":"2021","journal-title":"Proc. VLDB Endow."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1145\/3524284","article-title":"The Seattle Report on Database Research","volume":"65","author":"Abadi","year":"2022","journal-title":"Commun. ACM"},{"key":"ref_48","unstructured":"(2022, June 05). Available online: https:\/\/github.com\/globosco\/A-learned-sorted-table-search-library."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","article-title":"Addressing for random-access storage","volume":"1","author":"Peterson","year":"1957","journal-title":"IBM J. Res. Dev."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Van Sandt, P., Chronis, Y., and Patel, J.M. (July, January 30). Efficiently searching in-memory sorted arrays: Revenge of the interpolation search?. Proceedings of the 2019 International Conference on Management of Data, Amsterdam, The Netherlands. SIGMOD\u201919.","DOI":"10.1145\/3299869.3300075"},{"key":"ref_51","unstructured":"Amato, D. (2022). A Tour of Learned Static Sorted Sets Dictionaries: From Specific to Generic with an Experimental Performance Analysis. [Ph.D. Thesis, University of Palermo]."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Freedman, D. (2005). Statistical Models: Theory and Practice, Cambridge University Press.","DOI":"10.1017\/CBO9781139165495"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Schlegel, B., Gemulla, R., and Lehner, W. (2009, January 28). K-Ary Search on Modern Processors. Proceedings of the Fifth International Workshop on Data Management on New Hardware, Providence, RI, USA. DaMoN\u201909.","DOI":"10.1145\/1565694.1565705"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1550","DOI":"10.14778\/3236187.3236205","article-title":"An eight-dimensional systematic evaluation of optimized search algorithms on modern processors","volume":"11","author":"Schulz","year":"2018","journal-title":"Proc. VLDB Endow."},{"key":"ref_55","unstructured":"Kipf, A. Personal Communication."},{"key":"ref_56","unstructured":"(2022, June 05). Available online: https:\/\/osf.io\/qtyu7\/?view_only=b48e6cc6e01b441383b26b81588090ec."},{"key":"ref_57","first-page":"3","article-title":"Estimate of deviation between empirical distribution functions in two independent samples","volume":"2","author":"Smirnov","year":"1939","journal-title":"Bull. Mosc. Univ."},{"key":"ref_58","unstructured":"Kullback, S. (1968). Information Theory and Statistics, Dover Publications."}],"container-title":["Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2306-5729\/8\/3\/56\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:47:10Z","timestamp":1760122030000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2306-5729\/8\/3\/56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,3]]},"references-count":58,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["data8030056"],"URL":"https:\/\/doi.org\/10.3390\/data8030056","relation":{},"ISSN":["2306-5729"],"issn-type":[{"value":"2306-5729","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,3]]}}}