W. Loh

Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases

Vector search runs as an operator in database systems, where a missed neighbor can make a filter, join, or aggregate wrong, yet approximate nearest neighbor (ANN) indexes are tuned only for an average recall target. In our measurements, indexes tuned to an average recall of 0.99 left 5-19% of in-distribution queries an...