FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
read the original abstract
Approximate nearest neighbor search (ANNS) is a fundamental building block in information retrieval with graph-based indices being the current state-of-the-art and widely used in the industry. Recent advances in graph-based indices have made it possible to index and search billion-point datasets with high recall and millisecond-level latency on a single commodity machine with an SSD. However, existing graph algorithms for ANNS support only static indices that cannot reflect real-time changes to the corpus required by many key real-world scenarios (e.g. index of sentences in documents, email, or a news index). To overcome this drawback, the current industry practice for manifesting updates into such indices is to periodically re-build these indices, which can be prohibitively expensive. In this paper, we present the first graph-based ANNS index that reflects corpus updates into the index in real-time without compromising on search performance. Using update rules for this index, we design FreshDiskANN, a system that can index over a billion points on a workstation with an SSD and limited memory, and support thousands of concurrent real-time inserts, deletes and searches per second each, while retaining $>95\%$ 5-recall@5. This represents a 5-10x reduction in the cost of maintaining freshness in indices when compared to existing methods.
This paper has not been read by Pith yet.
Forward citations
Cited by 20 Pith papers
-
Leveraging I/O Stalls for Efficient Scheduling in ANNS
LIOS executes ANNS index updates inside search I/O stall windows via resumable subtasks, overrun bounding, and dynamic fraction adjustment, delivering up to 2.68x insertion and 2.18x deletion speedups in FreshDiskANN ...
-
IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer
IVF-TQ replaces learned codebooks with a fixed random rotation and precomputed scalar quantizer in the residual layer of an IVF index, delivering streaming recall stability at fixed bit budgets via a uniform-over-sphe...
-
Mycelium-Index: A Streaming Approximate Nearest Neighbor Index with Myelial Edge Decay, Traffic-Driven Reinforcement, and Adaptive Living Hierarchy
Mycelium-index matches state-of-the-art recall on streaming and static ANN benchmarks while using 5x less RAM and delivering higher query throughput on SIFT-1M.
-
Decoupling Vector Data and Index Storage for Space Efficiency
DecoupleVS decouples vector data and index storage in ANNS systems to cut storage space by up to 58.7% with competitive search and update performance.
-
Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN
BatANN delivers near-linear throughput scaling for distributed disk-based approximate nearest neighbor search on a single global graph, with 3.5-5.59x gains over scatter-gather baselines on 1B-point datasets at 0.95 recall.
-
Extreme Meta-Classification for Large-Scale Zero-Shot Retrieval
EMMETT and IRENE enable on-the-fly synthesis of classifiers for novel items in extreme classification, yielding up to 15% Recall@10 gains in zero-shot retrieval and 4.2% CTR lift in a production A/B test.
-
Slipstream: Locality-Aware Graph Index Construction for Streaming Approximate Nearest Neighbor Search
Slipstream exploits continuity in vector streams to reduce insertion costs in graph ANNS indexes via prior-insertion candidates and an adaptive controller, delivering up to 30.8x higher throughput at >=0.95 recall@10 ...
-
Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap [Technical Report]
Multi-segment tree graph supports generalized RRANN queries for arbitrary predicates like containment and overlap, with up to 12.5x speedups over baselines on real data while keeping index size comparable.
-
Onyx: Cost-Efficient Disk-Oblivious ANN Search
Onyx inverts ANN-ORAM optimization priorities with a compact pruning representation and locality-aware shallow tree to deliver 1.7-9.9x lower cost and 2.3-12.3x lower latency for disk-oblivious ANN search.
-
Opal: Private Memory for Personal AI
Opal enables private long-term memory for personal AI by decoupling reasoning to a trusted enclave with a lightweight knowledge graph and piggybacking reindexing on ORAM accesses.
-
DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries
DGAI decouples vector storage from graph topology in on-disk ANN indexes and adds similarity-aware dynamic layout plus hierarchical PQ two-stage querying to achieve 8x faster insertions/deletions and 67% lower peak qu...
-
LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search
LSM-VEC integrates hierarchical graphs with LSM-tree levels for out-of-place dynamic updates, sampling-based search, and connectivity-aware reordering, outperforming prior disk-based ANN systems on billion-scale data ...
-
When to Repair a Graph ANN Index: Navigability-Signal-Triggered Local Repair Protects Tail Recall Under Bursty Churn
Signal-triggered local repair in graph ANN indexes improves minimum recall@10 by 0.014-0.050 under bursty churn versus fixed-cadence repair at matched budget on SIFT-128 and Fashion-MNIST-784.
-
ACRONYM: Accelerated Approximate Nearest Neighbor Search in Memory for Dynamic Vector Databases
ACRONYM claims a CAM-accelerated platform for dynamic vector databases that delivers over 90% recall at 8 million queries per second using 32 MB memory and 2.56 uJ per query while supporting updates without stalling.
-
EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
EMA attaches Markers as compact summaries to graph edges for predicate-aware guidance in filtering ANN search, delivering 1.68x-12.25x speedups over prior general filtering methods while supporting dynamic updates.
-
CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces
CHRONOS is a three-layer system for evolving data marketplaces that applies neural-ODE temporal decay, changepoint-aware Shapley valuation, and EXP3-IX private coordination to achieve 0.937 recall, 2.74 qps, 161 ms la...
-
IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer
IVF-TQ pairs IVF coarse clustering with a codebook-free TurboQuant-style residual layer to deliver streaming-robust ANN search, supported by multi-seed experiments and an IP-error bound.
-
NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search
NAVIS improves concurrent search and update throughput in on-SSD graph vector search by up to 2.74x for insertions and 1.37x for searches through reduced position-seeking overhead.
-
Decoupling Vector Data and Index Storage for Space Efficiency
COMPASS decouples vector data and index storage in disk-resident graph ANNS systems to enable component-specific lossless compression, reducing space by up to 58.7% with improved or competitive performance.
-
ScaleGANN: Accelerate Large-Scale ANN Indexing by Cost-effective Cloud GPUs
ScaleGANN accelerates graph-based ANN index construction up to 9x faster and 6x cheaper than DiskANN by using divide-and-merge on distributed low-cost spot GPUs with optimized partitioning and a cost-aware scheduler.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.