Quake: Adaptive Indexing for Vector Search
summary
Quake implements a multi-level partitioning index with a practical cost model that picks splits/merges by estimated query cost, an online adaptive partition scanning recall estimator that sets per-query probes from geometric overlap, and NUMA-aware intra-query parallelism for throughput. Evaluated on a Wikipedia growth workload using the authors’ workload generator, it reports query latency reductions of about 1.5–38× and update latency reductions of 4.5–126× versus SVS, DiskANN, HNSW, and SCANN, and the system is open source.
AI-written summary · about
chapters (8)
- 0:00Quake and vector search
- 3:26Index imbalance and recall loss
- 4:31Quake’s adaptive indexing
- 5:35Cost-driven maintenance
- 9:10Adaptive partition scanning
- 10:35Wikipedia workload evaluation
- 13:02Comparison with baselines
- 14:05Summary and release
related talks
32mUnder the Hood: Key Algorithms Powering Vector Search
16mTowards High-throughput and Low-latency Billion-scale Vector Search via CPU/GPU...
01h 09mVector Search: Ask Me Anything!
43mOpenSearch and the Path to a Trillion-scale Vector Database
32mRetrieval Augmentation and Semantic Search at Scale
40mUnder the hood of vector search with JVector
24mVector Search at Uber
44mVector Search Beyond the Hype: Real-World Implementation and Performance Insights