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 and OdinANN while controlling latency degradation.
hub
FreshDiskANN: A fast and accurate graph-based ANN index for streaming similarity search.arXiv preprint arXiv:2105.09613
19 Pith papers cite this work. Polarity classification is still indexing.
19
Pith papers citing it
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.
hub tools
citation-role summary
background 3
dataset 1
citation-polarity summary
representative citing papers
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-sphere inner-product bound.
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.
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.
At matched consolidation count, navigability-signal-triggered local repair of graph ANN indexes yields no tail-recall gain over fixed-cadence repair; the prior positive result was an interpolation artifact on a concave budget curve.
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 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 on five datasets.
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 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 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 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 query latency under mixed workloads.
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 with higher recall, lower latency, and over 66% memory reduction.
Akashic’s MemAttention plus locality-aware placement improves agent task accuracy by up to 10.2 points and throughput by up to 1.21× over prior memory systems across four long-horizon workloads.
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 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 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 latency, and epsilon 4.25 at delta 10^-6.
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.
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 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.
citing papers explorer
-
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 and OdinANN while controlling latency degradation.
-
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-sphere inner-product bound.
-
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.
-
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.
-
When to Repair a Graph ANN Index: A Matched-Budget Negative Result, and the Interpolated-Baseline Trap That Hid It
At matched consolidation count, navigability-signal-triggered local repair of graph ANN indexes yields no tail-recall gain over fixed-cadence repair; the prior positive result was an interpolation artifact on a concave budget curve.
-
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 on five datasets.
-
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 query latency under mixed workloads.
-
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 with higher recall, lower latency, and over 66% memory reduction.
-
Akashic: A Low-Overhead LLM Inference Service with MemAttention
Akashic’s MemAttention plus locality-aware placement improves agent task accuracy by up to 10.2 points and throughput by up to 1.21× over prior memory systems across four long-horizon workloads.
-
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 latency, and epsilon 4.25 at delta 10^-6.
-
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.