5 papers
VQ-bench: A Composable Vector Quantization Framework
Ashwin Padaki, Amir Ingber, Edo Liberty
Vector quantization is an old problem but has recently become central to AI infrastructure. It is therefore experiencing a surge of renewed engineering and research activity. This…
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…