Reproduce “Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram, Jakub Lacki

A distributed Approximate Nearest Neighbor Search (ANNS) framework leverages balanced graph partitioning and novel combinatorial routing methods to improve performance on large-scale datasets. This approach achieves up to 2.14x higher query throughput compared to existing methods on billion-scale benchmarks.

Key insights

  • Rough approximate k-NN graphs are sufficient for high-quality balanced partitioning, enabling fast graph construction for billion-scale datasets.
  • Balanced graph partitioning (GP) preserves local neighborhood structure more effectively than traditional methods like k-means, leading to a higher concentration of ground-truth neighbors within top-ranked shards.
  • Well-designed combinatorial routing algorithms like K-Means Tree Routing (KRT) can achieve performance comparable to theoretical optimums and outperform complex neural methods while being significantly faster to train for distributed ANNS.
  • The primary source of routing loss is from representing shards with a subset of points (coarsening) rather than from the approximate search within routing indices, indicating efficient HNSW-based retrieval.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.