Reproduce “JUNO: Optimizing High-Dimensional Approximate Nearest Neighbour Search with Sparsity-Aware Algorithm and Ray-Tracing Core Mapping” 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
Zihan Liu, Wentao Ni, Jingwen Leng, Yu Feng, Cong Guo, Quan Chen, Chao Li, Minyi Guo and 1 more
Researchers developed JUNO, a system that significantly enhances high-dimensional Approximate Nearest Neighbor (ANN) search by integrating a sparsity-aware algorithm with a novel mapping to GPU Ray Tracing and Tensor cores, demonstrating throughput improvements of 2.1x to 8.5x over state-of-the-art methods like FAISS.
Key insights
- L2-LUT construction and distance calculation are the dominant time consumers (90-99.9%) in IVFPQ-based ANN search pipelines.
- Only a small fraction (25-30%) of codebook entries are relevant for top-k nearest neighbors, and these entries exhibit spatial locality around query projections within subspaces.
- Ray Tracing (RT) cores, traditionally for graphics, can be re-purposed for high-dimensional ANN by mapping proximity checks to ray-sphere intersections, providing logarithmic complexity for selective pruning.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.