CoChat
Sign Up
Cited by 956Advanced Database Systems and QueriesAlgorithms and Data CompressionData Management and Algorithms

The Case for Learned Index Structures

Open access
Kraska, Tim, Beutel, Alex, Chi, Ed H., Dean, Jeffrey, Polyzotis, Neoklis·2018·Proceedings of the 2018 International Conference on Management of Data
DOI 10.1145/3183713.3196909
Open this paper in CoChat — free accountOpen PDF

Abstract

Indexes are models: a \btree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this exploratory research paper, we start from this premise and posit that all existing index structures can be replaced with other types of models, including deep-learning models, which we term \em learned indexes. We theoretically analyze under which conditions learned indexes outperform traditional index structures and describe the main challenges in designing learned index structures. Our initial results show that our learned indexes can have significant advantages over traditional indexes. More importantly, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work provides just a glimpse of what might be possible.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3183713.3196909

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Kraska et al. empirically showed that better indexes can be built using machine-learned models, but their work does not provide provable guarantees for its methods.

    “Another recent work is that of Kraska et al. [17] that empirically shows that better indexes can be built using machine learned models; it does not provide any provable guarantees for its methods.”

    From Improving Online Algorithms via ML Predictions (2024) · cites this paper as [17]

    The Introduction and the learned-index comparison report promising empirical results, supporting the first part of the claim. But the categorical statement that the methods provide no guarantees is too broad: the Range Index section describes min-and max-error bounds, and the Biased Quaternary Search section says its search technique guarantees finding all existing keys. The paper leaves other guarantees, including lookup and insertion costs under changing data distributions, for future work. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 58

  1. M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghe- mawat, G. Irving, M. Isard, et al. Tensorflow: A system for large-scale machine learning. In OSDI, volume 16, pages 265-283, 2016.
  2. S. Abu-Nimeh, D. Nappa, X. Wang, and S. Nair. A comparison of machine learning techniques for phishing detection. In eCrime, pages 60-69, 2007.
  3. K. Alexiou, D. Kossmann, and P.-A. Larson. Adaptive range filters for cold data: Avoiding trips to siberia. Proc. VLDB Endow., 6(14):1714-1725, Sept. 2013.
  4. M. Athanassoulis and A. Ailamaki. BF-tree: Approximate Tree Indexing. In VLDB, pages 1881-1892, 2014.
  5. R. Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Inf., 1(4):290-306, Dec. 1972.
  6. R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. In SIGFIDET (Now SIGMOD), pages 107-141, 1970.
  7. S. Bickel, M. Brückner, and T. Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10(Sep):2137-2155, 2009.
  8. M. Böhm, B. Schlegel, P. B. Volk, U. Fischer, D. Habich, and W. Lehner. Efficient in-memory indexing with generalized prefix trees. In BTW, pages 227-246, 2011.
  9. J. Boyar and K. S. Larsen. Efficient rebalancing of chromatic search trees. Journal of Computer and System Sciences, 49(3):667 -682, 1994. 30th IEEE Conference on Foundations of Computer Science.
  10. M. Brantner, D. Florescu, D. A. Graf, D. Kossmann, and T. Kraska. Building a database on S3. In SIGMOD, pages 251-264, 2008.
  11. A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet mathematics, 1(4):485-509, 2004.
  12. F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A distributed storage system for structured data (awarded best paper!). In OSDI, pages 205-218, 2006.
  13. A. Crotty, A. Galakatos, K. Dursun, T. Kraska, C. Binnig, U. Çetintemel, and S. Zdonik. An architecture for compiling udf-centric workflows. PVLDB, 8(12):1466-1477, 2015.
  14. M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auF der Heide, H. Rohn- ert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4):738-761, 1994.
  15. J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):2121-2159, 2011.
  16. A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
  17. B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher. Cuckoo filter: Practically better than bloom. In CoNEXT, pages 75-88, 2014.
  18. T. Fawcett. An introduction to roc analysis. Pattern recognition letters, 27(8):861-874, 2006.
  19. E. Fredkin. Trie memory. Commun. ACM, 3(9):490-499, Sept. 1960.
  20. A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska. A-tree: A bounded approximate index structure. CoRR, abs/1801.10207, 2018. · arXiv
  21. J. Goldstein, R. Ramakrishnan, and U. Shaft. Compressing Relations and Indexes. In ICDE, pages 370-379, 1998.
  22. I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In NIPS, pages 2672-2680, 2014.
  23. G. Graefe and P. A. Larson. B-tree indexes and CPU caches. In ICDE, pages 349-358, 2001.
  24. A. Graves. Generating sequences with recurrent neural networks. arXiv preprint arXiv:1308.0850, 2013. · arXiv
  25. R. Grossi, A. Gupta, and J. S. Vitter. High-order entropy-compressed text indexes. In SODA, pages 841-850. Society for Industrial and Applied Mathematics, 2003.
  26. R. Grossi and G. Ottaviano. The wavelet trie: Maintaining an indexed sequence of strings in compressed space. In PODS, pages 203-214, 2012.
  27. J. Guo and J. Li. CNN based hashing for image retrieval. CoRR, abs/1509.01354, 2015. · arXiv
  28. M. Gupta, A. Cotter, J. Pfeifer, K. Voevodski, K. Canini, A. Mangylov, W. Moczydlowski, and A. Van Esbroeck. Monotonic calibrated interpolated look-up tables. The Journal of Machine Learning Research, 17(1):3790-3836, 2016.
  29. C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, and P. Dubey. Fast: Fast architecture sensitive tree search on modern cpus and gpus. In SIGMOD, pages 339-350, 2010.
  30. T. Kissinger, B. Schlegel, D. Habich, and W. Lehner. Kiss-tree: Smart latch- free in-memory indexing on modern architectures. In DaMoN, pages 16-23, 2012.
  31. T. J. Lehman and M. J. Carey. A study of index structures for main memory database management systems. In VLDB, pages 294-303, 1986.
  32. V. Leis, A. Kemper, and T. Neumann. The adaptive radix tree: Artful indexing for main-memory databases. In ICDE, pages 38-49, 2013.
  33. W. Litwin. Readings in database systems. chapter Linear Hashing: A New Tool for File and Table Addressing., pages 570-581.
  34. M. Magdon-Ismail and A. F. Atiya. Neural networks for density estimation. In M. J. Kearns, S. A. Solla, and D. A. Cohn, editors, NIPS, pages 522-528. MIT Press, 1999.
  35. D. J. Miller and H. S. Uyar. A mixture of experts classifier with learning based on both labelled and unlabelled data. In NIPS, pages 571-577, 1996.
  36. M. Mitzenmacher. Compressed bloom filters. In PODC, pages 144-150, 2001.
  37. M. Mitzenmacher. A model for learned bloom filters and related structures. arXiv preprint arXiv:1802.00884, 2018. · arXiv
  38. G. Moerkotte. Small Materialized Aggregates: A Light Weight Index Struc- ture for Data Warehousing. In VLDB, pages 476-487, 1998.
  39. T. Neumann and G. Weikum. RDF-3X: A RISC-style Engine for RDF. Proc. VLDB Endow., pages 647-659, 2008.
  40. R. Pagh and F. F. Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122- 144, 2004.
  41. J. Rao and K. A. Ross. Making b+-trees cache conscious in main memory. In SIGMOD, pages 475-486, 2000.
  42. S. Richter, V. Alvarez, and J. Dittrich. A seven-dimensional analysis of hashing methods and its implications on query processing. Proc. VLDB Endow., 9(3):96-107, Nov. 2015.
  43. D. G. Severance and G. M. Lohman. Differential files: Their application to the maintenance of large data bases. In SIGMOD, pages 43-43, 1976.
  44. A. Shahvarani and H.-A. Jacobsen. A hybrid b+-tree as solution for in- memory indexing on cpu-gpu heterogeneous computing platforms. In SIGMOD, pages 1523-1538, 2016.
  45. N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and J. Dean. Outrageously large neural networks: The sparsely-gated mixture- of-experts layer. arXiv preprint arXiv:1701.06538, 2017. · arXiv
  46. M. Stonebraker and L. A. Rowe. The Design of POSTGRES. In SIGMOD, pages 340-355, 1986.
  47. I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. In NIPS, pages 3104-3112, 2014.
  48. F. Tramèr, A. Kurakin, N. Papernot, D. Boneh, and P. McDaniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint arXiv:1705.07204, 2017. · arXiv
  49. M. Turcanik and M. Javurek. Hash function generation by neural network. In NTSP, pages 1-5, Oct 2016.
  50. J. Wang, W. Liu, S. Kumar, and S. F. Chang. Learning to hash for indexing big data;a survey. Proceedings of the IEEE, 104(1):34-57, Jan 2016.
  51. J. Wang, H. T. Shen, J. Song, and J. Ji. Hashing for similarity search: A survey. CoRR, abs/1408.2927, 2014. · arXiv
  52. J. Wang, J. Wang, N. Yu, and S. Li. Order preserving hashing for approxi- mate nearest neighbor search. In MM, pages 133-142, 2013.
  53. Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, et al. Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144, 2016. · arXiv
  54. S. You, D. Ding, K. Canini, J. Pfeifer, and M. Gupta. Deep lattice networks and partial monotonic functions. In NIPS, pages 2985-2993, 2017.
  55. Y. You, Z. Zhang, C. Hsieh, J. Demmel, and K. Keutzer. Imagenet training in minutes. CoRR, abs/1709.05011, 2017. · arXiv
  56. J. Yu and M. Sarwat. Two Birds, One Stone: A Fast, Yet Lightweight, Indexing Scheme for Modern Database Systems. In VLDB, pages 385-396, 2016.
  57. E. Zamanian, C. Binnig, T. Kraska, and T. Harris. The end of a myth: Distributed transaction can scale. PVLDB, 10(6):685-696, 2017.
  58. H. Zhang, D. G. Andersen, A. Pavlo, M. Kaminsky, L. Ma, and R. Shen. Reducing the storage overhead of main-memory OLTP databases with hybrid indexes. In SIGMOD, pages 1567-1581, 2016.

Cited by

Sorted by citations

Authors
Kraska, T., Beutel, A., Chi, E. H., Dean, J., & Polyzotis, N.
Affiliations
  • Massachusetts Institute of Technology (US)
  • Google (United States) (US)
  • Google, Inc., Mountain View, CA, USA
ORCID
Venue
Proceedings of the 2018 International Conference on Management of Data
Publisher
ACM
Published
2018-05-27
Pages
489-504
ISSN
0730-8078 (ISSN-L)
DOI
10.1145/3183713.3196909
OpenAlex
W2773466258
Cited by
956
References
1
Citations by year
2026: 103 · 2025: 116 · 2024: 121 · 2023: 102 · 2022: 122 · 2021: 138 · 2020: 108 · 2019: 101 · 2018: 44 · 2016: 1
FWCI
81.00
Type
conference paper
Language
en
Open access
Licence
Locations
  • ACM SIGMOD International Conference on Management of Data (SIGMOD) (publishedVersion, cc-by-nc-sa)
  • arXiv (Cornell University) (submittedVersion)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Funders
  • Defense Advanced Research Projects Agency (16-43-D3M-FP-040)
  • Air Force Office of Scientific Research (FA9550-15-1-0144)
  • National Science Foundation (IIS-1453171)
Topics
  • Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Database Systems and Queries
  • Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
  • Physical Sciences › Computer Science › Signal Processing › Data Management and Algorithms
Keywords
learned indexes, index structures, B-trees, hash index, bitmap index, data management systems, index design

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review