Doctoral Thesis Oral Defense - Magdalen Dobson Manohar

— 1:00pm

Location:
In Person and Virtual - ET - Traffic21 Classroom and Zoom

Speaker:
MAGDALEN DOBSON MANOHAR , Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://magdalendobson.github.io/

New Techniques for Parallelism and Concurrency in Nearest Neighbor Search

Nearest neighbor search in both high and low dimensions is an important problem in the field of computer science and beyond. In this thesis, we extend the capabilities of nearest neighbor search algorithms to meet modern demands, including support for billion-scale indices, parallelism and concurrency on machines with hundreds of cores, efficient updates, and extensions to related geometric problems such as range search. We progress towards this goal by introducing the zd-tree, a data structure for low-dimensional nearest neighbor search with provable guarantees on the work and span of search, build, and update, a scalable parallel build, and the ability to perform batch-dynamic updates in parallel.

Building on the zd-tree, we also present the CLEANN-Tree (for Concurrent Linearizable Efficient Augmented Nearest Neighbor Search Tree), a generalization of the zd-tree which supports concurrent queries and updates utilizing versioned pointers and lock-free locks. In high dimensions, we introduce techniques to make existing nearest neighbor search algorithms lock-free, deterministic, and scalable to billion-size datasets. We apply these techniques to four existing graph-based nearest neighbor search algorithms in a library called ParlayANN. Building off our work in ParlayANN, we extend the search algorithms for graph-based nearest neighbor indices to the related but relatively under-studied problem of range search in high dimensions, making significant gains over a naive baseline. 

Thesis Committee

Guy E. Blelloch (Chair)
Phillip B. Gibbons
Andrew Pavlo
Harsha Vardhan Simhadri (Microsoft Azure)
Matthijs Douze (Meta AI Research)

In Person and Zoom Participation.  See announcement.

Add event to Google
Add event to iCal