Back to Search
Start Over
The Case for Learned Index Structures
- Source :
- SIGMOD Conference, ACM
- Publication Year :
- 2017
-
Abstract
- Indexes are models: a B-Tree-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 learned indexes. The key idea is that a model can learn the sort order or structure of lookup keys and use this signal to effectively predict the position or existence of records. 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 by using neural nets we are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. More importantly though, 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 just provides a glimpse of what might be possible.
- Subjects :
- FOS: Computer and information sciences
Computer science
Data management
Sorted array
02 engineering and technology
Machine learning
computer.software_genre
B-tree
Computer Science - Databases
020204 information systems
Computer Science - Data Structures and Algorithms
Data_FILES
0202 electrical engineering, electronic engineering, information engineering
Data Structures and Algorithms (cs.DS)
Neural and Evolutionary Computing (cs.NE)
business.industry
Computer Science - Neural and Evolutionary Computing
Databases (cs.DB)
Bloom filter
Hash table
Term (time)
Index (publishing)
Key (cryptography)
020201 artificial intelligence & image processing
Artificial intelligence
business
computer
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- SIGMOD Conference, ACM
- Accession number :
- edsair.doi.dedup.....011eb9a1ff067c2fe654adbfedb1e760