Discovering Data Structures: Nearest Neighbor Search and Beyond
We propose a general framework for end-to-end learning of data structures. Our framework 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/algorithms. We first apply this framework to the problem of nearest neighbor search. 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, they have elements of locality-sensitive hashing. The model can also learn useful representations of high-dimensional data and exploit them to design effective data structures. We also adapt our framework to the problem of estimating frequencies over a data stream, and believe it could also be a powerful discovery tool for new problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Novel Approaches to Artificial Intelligence Development Based on the Nearest Neighbor Method
Modern neural network technologies, including large language models, have achieved remarkable success in various applied artificial intelligence applications, however, they face a range of fundamental limitations. Among …
Handwritten Digit RecognitionA Multilabel Classification Framework for Approximate Nearest Neighbor Search
Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning t…
ClassificationGeneral ClassificationMulti-Label ClassificationA learning framework for nearest neighbor search
Can we leverage learning techniques to build a fast nearest-neighbor (NN) retrieval data structure? We present a general learning framework for the NN problem in which sample queries are used to learn the parameters of a…
RetrievalMulti-View Semi-Supervised Label Distribution Learning with Local Structure Complementarity
Label distribution learning (LDL) is a paradigm that each sample is associated with a label distribution. At present, the existing approaches are proposed for the single-view LDL problem with labeled data, while the mult…
Graph LearningOn Class Distributions Induced by Nearest Neighbor Graphs for Node Classification of Tabular Data
Researchers have used nearest neighbor graphs to transform classical machine learning problems on tabular data into node classification tasks to solve with graph representation learning methods. Such artificial structure…