4 papers · 1 filter
Learning Partition Trees for Nearest Neighbor Search
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset of size and sample access to a query distributio…
Prune, Don't Rebuild: Efficiently Tuning -Reachable Graphs for Nearest Neighbor Search
Tian Zhang, Ashwin Padaki, Jiaming Liang +2
Vector similarity search is an essential primitive in modern AI and ML applications. Most vector databases adopt graph-based approximate nearest neighbor (ANN) search algorithms, s…
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, Krish Singal +1
We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stre…
Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
We initiate the study of approximation algorithms and computational barriers for constructing sparse -navigable graphs [IX23, DGM+24], a core primitive underlying recent advanc…