log in  |  register  |  feedback?  |  help  |  web accessibility
MS Defense: Approximate Nearest Neighbor Search with Filters
Ben Landrum
Thursday, April 25, 2024, 2:00-3:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

Approximate nearest neighbor search (ANNS) on high-dimensional vectors is a fundamental primitive used widely for search over neural embeddings of unstructured data. Prior work on ANNS has produced indices which provide fast and accurate search on datasets up to billions of points, but are not well suited to queries restricted to some subset of the original dataset.

Filtered ANNS is a formulation of the problem which adds metadata to points in the dataset which can be used to filter points at query time. This setting requires indexing a dataset in a metadata-aware way to support filtered queries. Filtered ANNS is important for applications such as product and image search, and necessary to give recently popular 'vector databases' functionality similar to more traditional tabular databases.

This work concerns two versions of the filtered ANNS problem. The most popular formulation in prior work associates points with boolean metadata in the form of labels and filters queries using a boolean predicate on these labels. In this setting, we present a novel index with state-of-the-art performance for queries with filters requiring either one label or both of a pair of labels which won a large benchmarking competition's track focused on the problem. We also introduce a novel formulation of filtered ANNS called 'window filtered' ANNS, in which points are associated with a continuous metadata value (in practical use, this corresponds to a timestamp, measure of popularity, etc.), and queries are filtered to a range of metadata values. In addition to describing the problem, we present a practical and theoretically motivated index which handily outperforms baselines.

Examining Committee


Dr. Laxman Dhulipala

Department Representative:

Dr. Alan Sussman


Dr. Amol Deshpande


Ben Landrum is a MS student advised by Laxman Dhulipala. His work focuses on graph-based approaches to approximate nearest neighbor search in high dimensions. He completed his undergrad in Mathematics and Computer Science at UMD and is going on to a PhD in Computer Science at Cornell this fall.

This talk is organized by Migo Gui