Reproduce “BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU” 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

Karthik V., Saim Khan, Somesh Singh, Harsha Vardhan Simhadri, Jyothi Vedurada

The BANG method enables billion-scale Approximate Nearest Neighbour Search (ANNS) with high recall and throughput using a single GPU. It demonstrates 50x to 400x higher throughput on 1-billion point datasets compared to competing methods while maintaining high accuracy.

Key insights

  • Achieving high recall and throughput for billion-scale Approximate Nearest Neighbour Search (ANNS) on a single GPU is feasible by judiciously balancing workloads and data between CPU and GPU.
  • Overlapping CPU-GPU data transfer with computation through asynchronous operations and eager prefetching effectively mitigates the PCIe bottleneck inherent in large datasets exceeding GPU memory.
  • Combining a robust graph index (Vamana) with a hybrid memory approach (compressed data on GPU, index on CPU) and optimized GPU kernels can overcome memory limitations while maintaining search accuracy for massive datasets.

Summary by alphaXiv.

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