Neural networks as building blocks for the design of efficient learned indexes

The new area of Learned Data Structures consists of mixing Machine Learning techniques with those specific to Data Structures, with the purpose to achieve time/space gains in the performance of those latter. The perceived paradigm shift in computer architectures, that would favor the employment of graphics/tensor units over traditional central processing units, is one of the driving forces behind this new area. The advent of the corresponding branch-free programming paradigm would then favor the adoption of Neural Networks as the fundamental units of Classic Data Structures. This is the case of Learned Bloom Filters. The equally important field of Learned Indexes does not appear to make use of Neural Networks at all. In this paper, we offer a comparative experimental investigation regarding the potential uses of Neural Networks as a fundamental building block of Learned Indexes. Our results provide a solid and much-needed evaluation of the role Neural Networks can play in Learned Indexing. Based on our findings, we highlight the need for the creation of highly specialised Neural Networks customised to Learned Indexes. Because of the methodological significance of our findings and application of Learned Indexes in strategic domains, such as Computer Networks and Databases, care has been taken to make the presentation of our results accessible to the general audience of scientists and engineers working in Neural Networks and with no background about Learned Indexing.

Automated summary

The new field of Learned Data Structures combines Machine Learning techniques with Data Structures to improve their performance. The shift towards using graphics/tensor units in computer architectures is driving this field. Neural Networks are proposed as the fundamental units of Classic Data Structures, such as Learned Bloom Filters. This paper investigates the use of Neural Networks in Learned Indexes and highlights the need for specialized Neural Networks customized for Learned Indexes.