Discovering Data Structures: Nearest Neighbor Search and Beyond
Omar Salemohamed Université de Montréal, Mila, Laurent Charlin HEC Montréal, Mila, Shivam GargMicrosoft Research, Vatsal SharanUniversity of Southern California, Gregory ValiantStanford University · 2024
Read Discovering Data Structures: Nearest Neighbor Search and Beyond by Omar Salemohamed Université de Montréal, Mila, Laurent Charlin HEC Montréal, Mila, Shivam GargMicrosoft Research, Vatsal SharanUniversity of Southern California, Gregory ValiantStanford University (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-03253.txt.
Description
Abstract We explore if it is possible to learn data structures end-to-end with neural networks, with a focus on the problem of nearest-neighbor (NN) search. To answer this question, we introduce a framework for data structure discovery which adapts to the underlying data distribution and provides fine-grained control over query and space complexity.
Catalog record
| CREATOR | Omar Salemohamed Université de Montréal, Mila, Laurent Charlin HEC Montréal, Mila, Shivam GargMicrosoft Research, Vatsal SharanUniversity of Southern California, Gregory ValiantStanford University |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 117 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-03253
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Discovering Data Structures: Nearest Neighbor Search and Beyond Omar Salemohamed Université de Montréal, Mila, Laurent Charlin HEC Montréal, Mila, Shivam GargMicrosoft Research, Vatsal SharanUniversity of Southern California, Gregory ValiantStanford University Abstract We explore if it is possible to learn data structures end-to-end with neural networks, with a focus on the problem of nearest-neighbor (NN) search. To answer this question, we introduce a framework for data structure discovery which adapts to the underlying data distribution and provides fine-grained control over query and space complexity. Crucially, the data structure is learned from scratch, and does not require careful initialization or seeding with candidate data structures. In several settings, we are able to reverse-engineer the learned data structures and query algorithms. For 1D nearest neighbor search, the model discovers optimal distribution (in)dependent algorithms such as binary search and variants of interpolation search. In higher dimensions, the model learns solutions that resemble k-d trees in some regimes, while in others, elements of locality-sensitive hashing emerge. Additionally, the model learns useful representations of high-dimensional data such as images and exploits them to design effective data structures. Beyond NN search, we believe the framework could be a powerful tool for data structure discovery for other problems, and adapt it to the problem of estimating frequencies over a data stream. To encourage future work in this direction, we conclude with a discussion on some of the opportunities and remaining challenges of learning data structures end-to-end. 1 1 1 Our code is available at: https://github.com/omar-s1/data_structure_discovery 1 Introduction Can neural networks discover data structures from scratch? There are several motivations for this question. The first is scientific. Deep learning models are increasingly performing tasks once considered exclusive to humans, from image recognition and mastering the game of Go to engaging in natural language conversations. Designing data structures and algorithms, along with solving complex math problems, are particularly challenging tasks. They require searching through a vast combinatorial space with a difficult to define structure. It is therefore natural to ask what it would take for deep learning models to solve such problems. There are already promising signs: these models have discovered fast matrix-multiplication algorithms [ 29 ] , solved SAT problems [ 52 ] , and learned optimization algorithms for various learning tasks [ 32 , 31 , 56 ] . The second motivation is practical. Data structures are ubiquitous objects that enable efficient querying. Traditionally, they have been designed to be worst-case optimal and therefore agnostic to the underlying data and query distributions. However, in many applications there are patterns in these distributions that can be exploited to design more efficient data structures. This has motivated recent work on learning-augmented data structures which leverages knowledge of the data distribution to modify existing data structures with predictions [ 44 , 24 , 43 , 45 ] . In much of this work, the goal of the learning algorithm is to learn distributional properties of the data, while the underlying query algorithm/data structure is hand-designed. Though this line of work clearly demonstrates the potential of leveraging distributional information, it still relies on expert knowledge to incorporate learning into such structures. It is natural to ask if we can go a step further and let deep learning models discover entire data structures and query algorithms in an end-to-end manner. In this work, we investigate the possibility of end-to-end data structure discovery, with a focus on the nearest neighbor search problem. A priori , it is not obvious how to frame data structure discovery as an end-to-end learning problem. What are the underlying principles that unify different data structure problems? How can a data structure be represented and queried using neural networks? How do we ensure some notion of efficiency is enforced? Thus a main contribution of our work is in proposing how to frame the problem. To help chart the landscape of this paradigm and explore its scope and limits, we focus more on understanding the kind of algorithms that end-to-end learning discovers than results on any given benchmark. 1.1 Framework for data structure discovery Figure 1: Our model has two components: 1) A data-processing network transforms raw data into structured data, arranging it for efficient querying and generating additional statistics when given extra space (not shown in the figure). 2) A query-execution network performs M lookups into the output of the data-processing network to retrieve the answer to some query q . Each lookup i is managed by a separate query model Q^{i} , which takes q and the lookup history H_{i} , and outputs a one-hot lookup vector m_{i} indicating the position to query. Data structure problems are often divided into two steps: 1) construction and 2) query execution. The first step transforms a raw dataset D into a structured database \hat{D} , while the second performs lookups into \hat{D} to answer a query q . The performance of a data structure is typically quantified in terms of two measures: space complexity —the memory required to store the structure, and query complexity —the number of lookups needed to answer a query. One can typically tradeoff larger space complexity for smaller query complexity, and vice versa. We focus on these criteria as they are well-studied and directly impact practical efficiency. To learn data structures, we have a data-processing network that learns how to map a raw dataset to a data structure, and a query network that learns an algorithm to answer queries using the data structure (Fig. 1 ). To ensure efficiency, we impose constraints on the data structure’s size and the number of lookups the query network makes. Crucially, we propose end-to-end training of both networks such that the learned data structure and query algorithm are optimized for one another. In settings where it is beneficial to learn lower-dimensional representations from high-dimensional data, end-to-end training also encourages the representations to capture features that the data structure can exploit. Why should learning data-structures end-to-end be possible? On one hand, jointly learning the data-processing and query networks end-to-end seems obvious, given the many successes of end-to-end learning over the past decade. On the other hand, it can be hard to imagine such learning getting off the ground. For instance, if the data-processing network produces a random garbled function of the dataset, the query model cannot do anything meaningful. In fact, we do observe cases where end-to-end learning fails. This challenge is further compounded by the discrete and combinatorial nature of how the query model accesses the data structure and the minimal supervision provided to the models. Despite these challenges, we find that in several settings end-to-end learning can recover a variety of classical algorithms. 1.2 Summary of Results We focus our investigation on the problem of nearest neighbor (NN) search in both low and high dimensions. NN search is an ideal starting point for understanding the landscape of end-to-end data structure discovery given the extensive theoretical work on this topic, along with its widespread practical applications (e.g., similarity search over language/image embeddings [ 5 ] ). Moreover, the NN search problem has a rich design space and remains an active area of research [ 2 , 28 , 42 ] . In addition to NN search, we also explore the problem of