Abstract
We present a new algorithm for the approximate near neighbor problem that combines classical ideas from group testing with locality-sensitive hashing (LSH). We reduce the near neighbor search problem to a group testing problem by designating neighbors as "positives," non-neighbors as "negatives," and approximate membership queries as group tests. We instantiate this framework using distance-sensitive Bloom Filters to Identify Near-Neighbor Groups (FLINNG). We prove that FLINNG has sub-linear query time and show that our algorithm comes with a variety of practical advantages. For example, FLINNG can be constructed in a single pass through the data, consists entirely of efficient integer operations, and does not require any distance computations. We conduct large-scale experiments on high-dimensional search tasks such as genome search, URL similarity search, and embedding search over the massive YFCC100M dataset. In our comparison with leading algorithms such as HNSW and FAISS, we find that FLINNG can provide up to a 10x query speedup with substantially smaller indexing time and memory.
Introduction
Finding the "nearest neighbor" to a query point in a massive dataset is a cornerstone of modern AI, powering everything from product recommendations to genomic sequence matching. However, as datasets grow into the billions of points and millions of dimensions (the "curse of dimensionality"), traditional methods stumble. Graph-based methods like HNSW require massive amounts of RAM and days to build an index, while quantization methods like FAISS struggle with ultra-high-dimensional sparse data. Standard LSH often requires expensive distance computations to filter out false positives at query time.
Researchers from Rice University have unveiled FLINNG, a new algorithm that seeks a practical middle ground: an algorithm that is fast to build, memory-efficient, and requires zero distance computations during the search.
The FLINNG Framework
The core innovation is the transformation of search into Group Testing. In medical group testing, samples from multiple people are combined into one test to quickly find the few infected individuals. FLINNG applies this to data by designating actual neighbors as "positives" and non-neighbors as "negatives." Instead of checking points one by one, it performs "group tests" on clusters of points.
FLINNG (Filters to Identify Near-Neighbor Groups) uses distance-sensitive Bloom filters as the "tests." The algorithm partitions the dataset into $B$ groups across $R$ different random repetitions. For each group, it builds a classifier that can detect if a neighbor is present based on LSH collision counts. When a query comes in, FLINNG checks which groups return a "positive" result. By intersecting these groups across the $R$ repetitions, the algorithm rapidly narrows down the candidates to the true nearest neighbors. The entire process uses simple integer operations and bitwise logic, avoiding the need to store original high-dimensional vectors in memory.
Experimental Results
The authors evaluated FLINNG on a diverse set of massive, high-dimensional benchmarks, including genomics (RefSeqG, RefSeqP), web-scale sparse data (URL, Webspam), and the YFCC100M dataset (100 million media embeddings).
On the 100-million-point YFCC100M dataset, the performance gains were striking:
- Indexing Speed: FLINNG took only 40 seconds to index YFCC100M. In comparison, FAISS took 12 hours, and HNSW failed to finish even after 5 days.
- Memory Footprint: FLINNG required only 3.5 GB of RAM for the index, whereas HNSW would have required over 1 TB.
- Query Speed: FLINNG achieved up to a 10x speedup over baselines on genomic and embedding search tasks while maintaining high accuracy.
Discussion and Limitations
While powerful, FLINNG's efficiency relies on "query stability," where neighbors are clearly distinguishable from non-neighbors. It may perform less effectively on noisy datasets where every point is roughly the same distance from the query. Additionally, it is optimized for finding highly similar neighbors and might not be the best choice for $k$-NN classification tasks where low-similarity points still carry important information.
References
Engels, J., Coleman, B., & Shrivastava, A. (2021). Practical Near Neighbor Search via Group Testing. arXiv:2106.11565v1 [cs.DS].
Summary updated