short-paper

Open access

CDFShop: Exploring and Optimizing Learned Index Structures

Authors:

Ryan Marcus,

Emily Zhang,

Tim KraskaAuthors Info & Claims

SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Pages 2789 - 2792

https://doi.org/10.1145/3318464.3384706

Published: 31 May 2020 Publication History

PDF eReader

Abstract

Indexes are a critical component of data management applications. While tree-like structures (e.g., B-Trees) have been employed to great success, recent work suggests that index structures powered by machine learning models (learned index structures) can achieve low lookup times with a reduced memory footprint. This demonstration showcases CDFShop, a tool to explore and optimize recursive model indexes (RMIs), a type of learned index structure. This demonstration allows audience members to (1) gain an intuition about various tuning parameters of RMIs and why learned index structures can greatly accelerate search, and (2) understand how automatic optimization techniques can be used to explore space/time tradeoffs within the space of RMIs.

References

[1]

MIT RMI, https://learned.systems/rmi .

Google Scholar

[2]

R. Binna et al. HOT : A height optimized trie index. In SIGMOD '18.

Google Scholar

[3]

J. Ding et al. ALEX : An Updatable Adaptive Learned Index. arXiv '19.

Google Scholar

[4]

P. Ferragina et al. The PGM -index. arXiv '19.

Google Scholar

[5]

A. Galakatos et al. FITing -Tree. In SIGMOD '19.

Google Scholar

[6]

C. Kim et al. FAST: Fast architecture sensitive tree. In SIGMOD '10.

Google Scholar

[7]

A. Kipf et al. SOSD. In MLForSystems @ NeurIPS '19.

Google Scholar

[8]

T. Kraska et al. Learned Index Structures. In SIGMOD '18.

Google Scholar

[9]

V. Leis et al. The adaptive radix tree. In ICDE '13.

Google Scholar

[10]

R. Marcus et al. NashDB: An Economic Approach to Fragmentation, Replication and Provisioning for Elastic Databases. In SIGMOD '18.

Google Scholar

[11]

V. Nathan et al. Learning Multi -dimensional Indexing. In MLForSystems @ NeurIPS '19.

Google Scholar

Cited By

View all

Kim MHwang JHeo GCho SMahajan DPark J(2024)Accelerating String-Key Learned Index Structures via Memoization-Based Incremental TrainingProceedings of the VLDB Endowment10.14778/3659437.365943917:8(1802-1815)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659439
Malchiodi DRaimondi DFumagalli GGiancarlo RFrasca M(2024)The role of classifiers and data complexity in learned Bloom filters: insights and recommendationsJournal of Big Data10.1186/s40537-024-00906-911:1Online publication date: 27-Mar-2024
https://doi.org/10.1186/s40537-024-00906-9
Zhang JSu KZhang H(2024)Making In-Memory Learned Indexes Efficient on DiskProceedings of the ACM on Management of Data10.1145/36549542:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654954
Show More Cited By

Index Terms

CDFShop: Exploring and Optimizing Learned Index Structures
1. Information systems
  1. Data management systems

Recommendations

The Case for Learned Index Structures
SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

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 ...
ALMSS: Automatic Learned Index Model Selection System
Web and Big Data
Abstract
Index is an indispensable part of database. As we enter the era of big data, the traditional index structure is found not to support large-scale data well. Although many index structures such as learned indexes based on machine learning have been ...
A learned spatial textual index for efficient keyword queries
Abstract
Spatial textual indexing techniques allow one to efficiently access and process large volume of geospatial data, and recent research efforts have demonstrated that learned indexes can lead to better performance in comparison to conventional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

June 2020

2925 pages

ISBN:9781450367356

DOI:10.1145/3318464

General Chairs:
David Maier
Portland State University, USA
,
Rachel Pottinger
University of British Columbia, Canada
,
Program Chairs:
AnHai Doan
University of Wisconsin, USA
,
Wang-Chiew Tan
Megagon Labs, USA
,
Publications Chairs:
Abdussalam Alawini
University of Illinois at Urbana-Champaign, USA
,
Hung Q. Ngo
RelationalAI, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

SIGMOD/PODS '20

Sponsor:

SIGMOD

SIGMOD/PODS '20: International Conference on Management of Data

June 14 - 19, 2020

OR, Portland, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
2,897
Total Downloads

Downloads (Last 12 months)416
Downloads (Last 6 weeks)57

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kim MHwang JHeo GCho SMahajan DPark J(2024)Accelerating String-Key Learned Index Structures via Memoization-Based Incremental TrainingProceedings of the VLDB Endowment10.14778/3659437.365943917:8(1802-1815)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659439
Malchiodi DRaimondi DFumagalli GGiancarlo RFrasca M(2024)The role of classifiers and data complexity in learned Bloom filters: insights and recommendationsJournal of Big Data10.1186/s40537-024-00906-911:1Online publication date: 27-Mar-2024
https://doi.org/10.1186/s40537-024-00906-9
Zhang JSu KZhang H(2024)Making In-Memory Learned Indexes Efficient on DiskProceedings of the ACM on Management of Data10.1145/36549542:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654954
Zhang SQi JYao XBrinkmann A(2024)Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid ConstructionProceedings of the ACM on Management of Data10.1145/36549482:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654948
Choi MYoo SChoi J(2024)Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offsProceedings of the ACM on Management of Data10.1145/36549192:3(1-25)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654919
Liang LYang GHadian ACroquevielle LHeinis T(2024)SWIX: A Memory-efficient Sliding Window Learned IndexProceedings of the ACM on Management of Data10.1145/36392962:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639296
Liu JZhang FLu LQi CGuo XDeng DLi GZhang HZhai JZhang HChen YPan ADu X(2024)G-Learned Index: Enabling Efficient Learned Index on GPUIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.338121435:6(950-967)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2024.3381214
Qiao PZhang ZLi YYuan YWang SWang GYu J(2024)AStore: Uniformed Adaptive Learned Index and Cache for RDMA-enabled Key-Value StoreIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.3355100(1-18)Online publication date: 2024
https://doi.org/10.1109/TKDE.2024.3355100
Li PHua YJia JZuo P(2024)A Fast Learned Key-Value Store for Concurrent and Distributed SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3327009(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3327009
Amato DGiancarlo RLo Bosco G(2023)Learned Sorted Table Search and Static Indexes in Small-Space Data ModelsData10.3390/data80300568:3(56)Online publication date: 3-Mar-2023
https://doi.org/10.3390/data8030056
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

The Case for Learned Index Structures

ALMSS: Automatic Learned Index Model Selection System

A learned spatial textual index for efficient keyword queries