FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search

1 Introduction

• Fresh-ANNS requires searches to use only the active dataset at query time while supporting point insertions, deletions, and searches as the dataset changes.Relevant scenarios include changing sentences in enterprise documents and arrivals or deletions of email.Source: §1 · p. 1

1.1 Shortcoming of existing algorithms

• Graph-based ANNS indices are strong for static search but do not support updates, so industry practice periodically rebuilds them at substantial cost.Building a good-quality HNSW index over 100M points takes about 1.5–2 hours on a dedicated high-end 48-core machine.Source: §1.1 · p. 2

1.2 Our Contributions

• FreshDiskANN is presented as a Euclidean-space system for real-time freshness that uses 5–10× fewer machines than the current state of the art.The paper identifies LSH-based methods as update-friendly but often memory-intensive or slow on secondary storage.Source: §1.2 · p. 2, §1.1 · p. 2
• FreshDiskANN combines a long-term SSD index with an in-memory index for recent updates, periodically consolidating them through a two-pass merge proportional in time and space to the change set.The merge is designed to use an order of magnitude less compute and memory than rebuilding the large index from scratch.Source: §1.2 · p. 3
• FreshDiskANN supports 1,000 searches/s at 95+% 5-recall@5, with mean search latency well under 20 ms, alongside 1,800 inserts and 1,800 deletes/s.The reported system uses less than 128GB of DRAM at all times.Source: §1.2 · p. 3

Trees

• Tree methods work well for low-dimensional data, but their performance degrades in high dimensions; the cited tree variants are also static, and graph methods outperform them on most datasets.Source: §2 · p. 3

Hashing

• LSH can provide provably approximate solutions and simple data-independent variants make updates almost trivial, but DRAM-heavy indices do not scale well and auxiliary-storage variants have much slower query latencies than graph methods.Source: §2 · p. 3

Data quantization and Inverted indices based algorithms

• Quantization and inverted-index methods reduce memory use, but the cited approaches can lose accuracy and often support only weaker recall guarantees; ADBV and other hybrid approaches also retain search-throughput or scaling trade-offs.FAISS supports insertions and deletions under conditions such as stationary data distributions; ADBV spreads its on-disk index across multiple machines.Source: §2 · pp. 3–4

3.1 Notation

• A graph index represents dataset points as vertices connected by directed edges, with in-edges, out-edges, and pairwise distances defining its search structure.Source: §3.1 · p. 4

3.2 Navigability and Index Search

• Navigable graphs support greedy search from a designated start node, while construction seeks fast convergence to nearby points under a bounded out-degree.Construction iteratively generates candidates through search and prunes redundant edges to respect the degree bound.Source: §3.2 · pp. 4–5

3.3 Why are Deletions Hard?

• Simple deletion policies remove incident edges either without replacement or by connecting local predecessors to successors, but deleted points may have served as navigating paths.Source: §3.3 · p. 5
• Recall declines across repeated 5% delete-and-reinsert cycles even though each cycle returns the dataset to its prior contents.The experiment uses SIFT1M; HNSW and Vamana use Delete Policy A, while NSG uses Delete Policy B.Source: Figure 1 · p. 5, §3.3 · p. 5

4 The FreshVamana algorithm

• Existing updates made graphs sparser and less navigable; FreshVamana uses relaxed α-RNG pruning to preserve navigability, with density increasing as α rises.The pruning rule removes an edge only when a detour is significantly closer to its endpoint.Source: §4 · pp. 5–6

4.1 Insertion

• Insertion searches the current index for candidates, prunes them, and adds bidirectional edges; its throughput scales near-linearly with threads.If a vertex exceeds the out-degree bound R, the pruning procedure can reduce it to R.Source: §4.1 · p. 6

4.2 Deletion

• FreshVamana lazily records deletions in a DeleteList, uses deleted nodes for search navigation but filters them from results, then consolidates graph changes in batches.Consolidation updates neighborhoods around deleted nodes using the deletion algorithm and relaxed α-pruning.Source: §4.2 · p. 6

4.3 Recall stability of FreshVamana

• Recall stayed stable across update cycles for all tested indices except α=1, supporting α>1; Figure 2 covers million-point datasets and the 100-million-point SIFT100M dataset.Some plots show a small initial recall drop, possibly because the starting static Vamana indices received two refinement passes and may have had slightly better quality than streaming FreshVamana.Source: §4.3 · p. 7

5 The FreshDiskANN system

• FreshDiskANN places recent updates in an in-memory FreshVamana index and longer-term data in an SSD-resident index, avoiding direct updates to the SSD index.The system also uses compressed vector representations to reduce memory use; direct SSD updates could require many random writes per insertion or eager deletion.Source: §5 · p. 7

5.1 Components

• The system combines an SSD-resident Long-Term Index, recent-point TempIndexes in DRAM, and a DeleteList that filters points requested for deletion.A mutable read-write TempIndex accepts inserts; it is periodically converted to a read-only TempIndex and snapshotted.Source: §5.1 · p. 8

5.2 FreshDiskANN API

• Insertions go to the read-write TempIndex, deletions to the DeleteList, and searches query the long-term and temporary indexes before filtering deleted results.Search aggregates candidates from the LTI, RW-TempIndex, and each RO-TempIndex.Source: §5.2 · p. 8

5.3 The StreamingMerge Procedure

• StreamingMerge produces an SSD-resident index over (P ∪ N) \ D while keeping memory proportional to changes and allowing searches during background merging.It processes deletions, inserts new points while buffering backward edges in memory, then patches those edges into the output index block by block.Source: §5.3 · pp. 8–9

5.4 Complexity of StreamingMerge

• StreamingMerge makes two sequential SSD passes for deletion and patching, uses about 100 random 4KB reads per inserted point, and keeps its Δ structure at O(|N|R).For 30M new points and R=64, the Δ structure is about 7GB; insert and patch computation is essentially linear in the number of new points.Source: §5.4 · p. 9

5.5 Recall Stability of StreamingMerge

• Recall stabilized after about 20 cycles of 10% deletion and insertion on the 80M-point index, at a lower level than the starting static index.The experiment ran 40 cycles; Figure 4 also shows recall evolution for an 800M-point index with 30M insertions and deletions.Source: §5.5 · p. 9, Figure 4 · p. 9

5.6 Crash Recovery

• A redo-log rebuilds the lost RW-TempIndex and DeleteList after a crash; snapshot frequency trades shorter reconstruction against more indexes to search.A 5M-point RW-TempIndex takes about 2.5 minutes to reconstruct on a 48-core machine, versus 16 minutes for 30M points.Source: §5.6 · pp. 9–10

6.2 Billion-Scale FreshDiskANN Evaluation

• The deployment's peak memory footprint was about 100GB, corresponding to roughly 125GB for a billion-point index.The experiment used an 800M-point steady-state index on a 48-core machine with a 3.2TB SSD.Source: §6.2 · p. 10, §6.1 · p. 10
• During ramp-up to an 800M-point index, user-perceived mean search latency mostly fluctuated between 5 ms with no merge and 15 ms during background StreamingMerge, with Ls=100 maintaining always >92% 5-recall@5.The insertions took around three days to reach 800M points.Source: §6.2 · p. 11, Figure 5 · p. 11
• FreshDiskANN maintained an 800M-point index in steady state while processing equal cycles of 30M inserts and deletes, with about 1,800 of each update per second.The merge took about 16,277 seconds per cycle; insertions and deletions were throttled to avoid backlogging.Source: §6.2 · pp. 10–11
• With 64 search threads and no concurrent inserts, deletes, or merges, throughput reached about 6,500 queries/sec, with mean and 99% latency below 10 and 12 ms.Search throughput scaled almost linearly with the number of search threads when the index was not processing updates.Source: §6.2 · p. 12
• A 40-thread StreamingMerge incorporated 30M inserts and deletes into an 800M-point index in about 16,000 seconds, 8.5% of a comparable full rebuild time.The merged change was 7.5% of the index.Source: §6.2 · p. 12, Figure 7 · p. 12
• Increasing merge threads speeds updates but raises SSD contention and can hurt search throughput and latency predictability; 40 threads supported 3,600 updates/sec, while 10 threads could serve 1,000 updates/sec with more predictable search latency.The merge scales near-linearly overall, though its Patch and Insert phases scale sub-linearly due to intensive SSD I/O.Source: §6.2 · pp. 11–12

7 Conclusion

• FreshVamana reflects updates with compute proportional to update size while keeping index quality similar to a fresh rebuild, and StreamingMerge brings updates into an SSD-resident index with minimal write amplification.Together, they support a dynamic billion-point index on a commodity machine with concurrent inserts, deletes, and searches at millisecond-scale latencies.Source: §7 · p. 13

A Recall Stability of FreshVamana Indices

• After ramp-up to one million points, FreshVamana's final recall was at least as good as a batch-built Vamana index with the same search parameters.The experiment grew the index from 100K points through cycles of 12K insertions and 10K deletions.Source: A Recall Stability of FreshVamana… · p. 16, Figure 9 · p. 16

B Index build times

• For a 800M index, reflecting 30M inserts and deletes with FreshDiskANN took less than one-seventh the time of a DiskANN rebuild, despite the rebuild using more than twice the resources.FreshVamana updates also took a fraction of the time required to rebuild with Vamana.Source: B Index build times · p. 16

C Effect of 𝛼on recall stability

• For α>1, average degree increased over repeated update cycles while recall stabilized around its initial value.The trends were measured on SIFT1M and DEEP1M during cycles inserting and deleting 5% of the index.Source: C Effect of 𝛼on recall stability · p. 16, Figure 12 · p. 17
• For static Vamana indices, search latency at the same recall improved as α rose from 1 to 1.2, with no noticeable further improvement beyond 1.2.The recall-versus-latency comparison used indices built with different α values.Source: C Effect of 𝛼on recall stability · p. 16, Figure 13 · p. 17
• The authors chose α=1.2 to combine the best search performance with the lowest average degree among the considered settings.They selected this value to minimize index memory footprint.Source: C Effect of 𝛼on recall stability · p. 16

D Amortized Cost of Delete Phase in StreamingMerge

• For a random delete set of fraction β, expected delete-phase work is proportional to NR(1−β)^2(1+Rβ), assuming pruning is linear in candidate-list size.Here N is the index size and R is the maximum graph degree.Source: D Amortized Cost of Delete Phase in… · p. 17
• When β is around 5%–10% and R is 64–128, Rβ≫1, so expected delete-phase time is directly proportional to the delete-list size.For large β, the (1−β)^2 factor makes the deletion phase quick.Source: D Amortized Cost of Delete Phase in… · p. 17
• The authors empirically tested Algorithm 3's linear time complexity by deleting 10% of a SIFT1M index while increasing candidate-list size.Figure 14 plots the algorithm's runtime against candidate-list size.Source: D Amortized Cost of Delete Phase in… · p. 17, Figure 14 · p. 17

• FreshVamana build parameters are adjusted to match Vamana’s build time for the latency comparison.Source: §E.1.1 · p. 17
• For 1-recall@1 and 10-recall@10, the comparison covers 95%, 98%, and 99% recall.Source: §E.1.1 · p. 17
• For 100-recall@100, the comparison covers 98% and 99% recall because the lowest search-list parameter L gives 98% recall.Source: §E.1.1 · p. 17

E.1.1 Search Latency vs Recall.

• For k=1, FreshVamana’s post-insertion 1-recall@1 is reported stable at 95% and 99.9% recall.Source: §E.1.1 · p. 17
• For k=10, post-insertion 10-recall@10 is reported stable at 95% and 99% recall.Source: §E.1.1 · p. 17
• For k=100, post-insertion 100-recall@100 is examined at 98% and 99% recall, since the lowest valid L gives 98%.Source: §E.1.1 · p. 17

E.2 FreshDiskANN

• The steady-state experiment tracks mean 100-recall@100 and 10-recall@10 search latency over one merge cycle on an 800M FreshDiskANN index.Source: §E.2.1 · p. 17

E.2.1 Search latencies over one merge cycle.

• Figures 15–17 compare Vamana and build-time-normalized FreshVamana query latency for 1-, 10-, and 100-recall@k targets at the stated recall levels.The 100-recall@100 comparison uses 98% and 99%; the other two use 95%, 98%, and 99%.Source: Figure 15 · p. 18, Figure 16 · p. 18, Figure 17 · p. 18

F Search latency of FreshDiskANN

• Figure 21 examines how varying the number of search threads affects mean search latency for an 800M index when no merge is running.Source: F Search latency of FreshDiskANN · p. 18

G Concurrency during StreamingMerge

• The concurrent-merge experiments cover 30M insertions and deletions into an 800M FreshDiskANN index; Figure 18 tracks post-insertion k-recall across 50 deletion and reinsertion cycles.The Figure 18 rows use deletion and reinsertion of 5%, 10%, and 50% of a SIFT1M index.Source: G Concurrency during StreamingMerge · p. 18, Figure 18 · p. 18

G.1 Search threads fixed - varying merge threads

• A 40-thread merge takes approximately half the time of a 20-thread merge, while search latencies are consistently higher during its Delete and Insert phases.Source: §G.1 · pp. 18–19
• The experiments track mean search latency at 95% recall on an 800M SIFT index across different thread counts, with batches of 10,000 queries.Source: Figure 21 · p. 19

G.2 Merge threads fixed - varying search threads

• With merge threads fixed at 40, the study increases search-thread counts and observes latency trends over a merge cycle.Source: §G.2 · p. 19