Loading Events

« All Events

  • This event has passed.

Discovering Data Structures: Nearest Neighbor Search and Beyond

February 12, 2025 @ 2:00 pm - 3:00 pm

New Technologies in Mathematics Seminar

Speaker: Omar Salemohamed, Mila

Title: Discovering Data Structures: Nearest Neighbor Search and Beyond

Abstract: 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.

Details

Date:
February 12, 2025
Time:
2:00 pm - 3:00 pm
Event Category:

Venue

Virtual