Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search

Yang Shi, Yiping Sun, Jiaolong Du, Xiaocheng Zhong, Zhiyong Wang, Yao HuWWW 2025 · DOI · OpenReview

TL;DR

This paper introduces SOGAIC, a novel system for building massive Approximate Nearest Neighbor (ANN) search indexes for billions of vectors. It tackles the scalability and efficiency bottlenecks of existing methods by proposing an "overload-aware" data partitioning strategy and a distributed, load-balanced subgraph construction framework, enabling faster index creation for real-world industrial applications.

What Problem Does This Paper Address?

Modern applications like recommendation systems, web search, and AI-powered content generation rely heavily on efficiently finding similar items within enormous datasets of vectors (e.g., embeddings from images, text, or audio). Approximate Nearest Neighbor Search (ANNS) algorithms are crucial for this, and graph-based methods like HNSW have shown great promise. However, building these graph indexes for datasets with billions of vectors is incredibly slow and resource-intensive, making it difficult to update them frequently. Existing methods struggle with:

  1. Scalability of Index Construction: Building indexes on such massive scales is computationally expensive and time-consuming, hindering real-time or frequent updates.
  2. Distributed Processing Challenges: Effectively partitioning data and distributing the workload for subgraph construction across many machines without introducing significant overhead or bottlenecks is complex.
  3. Overload Issues: When partitioning data for distributed processing, some subsets can become overloaded with vectors, exceeding resource limits and causing failures or performance degradation.

Methods

SOGAIC addresses these challenges with a two-stage approach:

  1. Overload-Aware Adaptive Data Partitioning:
    • Dynamic Overlaps: Instead of fixed data partitions, SOGAIC uses an adaptive algorithm that introduces overlaps between subsets. This is crucial for maintaining graph connectivity and search quality.
  2. Overload Constraints: The partitioning process is designed to be "overload-aware." It dynamically adjusts assignments to prevent any single subset from exceeding its capacity (e.g., memory limits), using an adaptive relaxation parameter (epsilon) to balance geometric relationships with overload prevention. This is a key departure from methods that might rigidly assign vectors based on distance alone.
  3. Parallel Quantization: Vector quantization (a technique to compress vectors for faster similarity checks) is performed in parallel with data partitioning, further boosting efficiency.
  4. Distributed ANNS Graph Construction with Agglomerative Subgraph Merging:
    • Load-Balancing Scheduler: Subgraph construction tasks are distributed across a cluster using a scheduler that prioritizes larger tasks and assigns them to the least-loaded machines. This ensures efficient utilization of computational resources and prevents bottlenecks.
  5. Agglomerative Merging: Completed subgraphs are merged in a hierarchical, "agglomerative" fashion. This allows for efficient in-memory merging at each stage, reducing I/O overhead and enabling faster access to vector data for more precise merging decisions. This is contrasted with on-disk merging strategies that can be slower.

Datasets

The paper evaluates SOGAIC on several real-world datasets:

  • SIFT1M: A standard benchmark for image embeddings.
  • SIFT1B: A larger version of the SIFT dataset, pushing the boundaries of scale.
  • GloVe: Word embeddings.
  • ISD3B: An image search dataset with high local intrinsic dimensionality (LID), indicating data complexity.
  • VDD10B: A video de-duplication dataset, representing a very large-scale, high-dimensional benchmark.

The paper does not introduce new datasets but uses existing, large-scale benchmarks to demonstrate the system's capabilities.

Key Insights and Ideas

  • "Overload-Awareness" is Key for Scalability: The core innovation is treating "overload" not just as an error to avoid, but as a constraint to manage adaptively during data partitioning. This allows for more flexible and efficient distribution of work.
  • Dynamic Overlaps Improve Connectivity: By intelligently introducing overlaps between data partitions, SOGAIC ensures that the resulting subgraphs can be merged into a highly connected global graph, which is essential for accurate ANNS.
  • Parallelism and Load Balancing are Synergistic: The combination of an adaptive partitioning strategy and a smart load-balancing scheduler is what unlocks true scalability. It allows the system to effectively utilize many low-cost workers instead of relying on a few powerful ones.
  • In-Memory Merging is Faster and Better: The agglomerative merging strategy, prioritizing in-memory operations, significantly speeds up the process and can lead to higher quality merged graphs compared to disk-based approaches.

Key Results

  • Significant Speedup: SOGAIC achieves an average 47.3% reduction in construction time compared to existing methods across various datasets.
  • Scalability: The system exhibits near-linear scalability with the addition of computational resources (CPUs), making it highly adaptable to different cluster sizes.
  • Handles Ultra-Large Datasets: It successfully constructs indexes for datasets exceeding 10 billion vectors.
  • Outperforms Baselines: On large datasets like SIFT1B and ISD3B, SOGAIC was able to complete construction where other methods (like Faiss HNSW and DiskANN) failed due to memory or data imbalance issues.
  • Real-World Deployment: The system has been successfully deployed in a production environment, handling over 10 billion daily updated vectors and serving millions of users.

Limitations and Future Work

  • Parameter Tuning: While the adaptive relaxation parameter (epsilon) is a strength, its optimal tuning might still require some experimentation for highly diverse datasets.
  • Future Work: The paper implies that further optimizations in scheduling and merging strategies could yield even greater performance gains. The successful deployment suggests a path towards broader adoption and integration into industrial search systems.

Summary updated

BibTeX
@inproceedings{shi2025scalable,
  author = {Yang Shi and Yiping Sun and Jiaolong Du and Xiaocheng Zhong and Zhiyong Wang and Yao Hu},
  title = {{Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search}},
  booktitle = {The Web Conference},
  year = {2025},
  doi = {10.1145/3701716.3715576},
}
Figure