Discovering Data Structures: Nearest Neighbor Search and Beyond
CMSA EVENTS: CMSA NEW TECHNOLOGIES IN MATHEMATICS
As neural networks learn increasingly sophisticated tasks—from image recognition to mastering the game of Go—we ask: can deep learning discover data structures entirely from scratch? We introduce a general framework for data structure discovery, which adapts to the underlying data distribution and provides fine-grained control over query and space complexity. For nearest neighbor (NN) search, our model (re)discovers classic algorithms like binary search in one dimension and learns structures reminiscent of k-d trees and locality-sensitive hashing in higher dimensions. 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 our framework 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.
Via Zoom:
https://harvard.zoom.us/j/92220006185?pwd=V3mrb4cNSbgRXtNJtRJkTvWFVhmbI5.1
Password: cmsa