Practical Near Neighbor Search via Group Testing

Joshua Engels, Benjamin Coleman, Anshumali Shrivastava

This paper, presented at NeurIPS 2021, introduces FLINNG (Filters to Identify Near-Neighbor Groups), a novel approach to the Approximate Near Neighbor (ANN) search problem. By reframing similarity search as a "group testing" problem, the authors achieve massive speedups in indexing and querying while drastically reducing memory overhead compared to industry standards like HNSW and FAISS.

Nearest neighbor search—finding the most similar items to a query in a massive dataset—is the engine behind recommendation systems, genomic search, and image recognition. However, as datasets scale to billions of points and thousands (or millions) of dimensions, systems hit the "curse of dimensionality."

Existing state-of-the-art methods face a three-way trade-off between speed, memory, and accuracy:

  1. Graph-based methods (like HNSW): These offer extremely fast queries but require massive amounts of RAM and can take days to build an index for terabyte-scale data.
  2. Quantization methods (like FAISS): These are more memory-efficient but still require significant compute for index construction and distance calculations.
  3. LSH-based methods: While theoretically sound, Locality-Sensitive Hashing (LSH) is often slow in practice because it requires a "re-ranking" step involving thousands of expensive distance computations.

The authors sought an algorithm that could handle ultra-high-dimensional data (like genomic sequences) without storing the original data in RAM or performing any distance calculations during the query phase.

Methodology: Search as Group Testing

The core innovation of FLINNG is treating near-neighbor search as a Group Testing problem. In classical group testing (like pool testing for a virus), samples are combined to identify "positives" using as few tests as possible. FLINNG applies this logic to high-dimensional data points.

FLINNG Methodology Overview
  • The Setup: The dataset is partitioned into $B$ groups across $R$ different repetitions.
  • The Test: Each group is represented by a distance-sensitive Bloom filter. A Bloom filter is a space-efficient bit array used to test set membership. Here, it is "distance-sensitive" because it uses LSH to determine if a query point is close to any point in the group.
  • The Query: When a query $y$ arrives, FLINNG checks all group tests. If a test returns "positive," every point in that group becomes a candidate.
  • The Intersection: By intersecting the candidate sets from the $R$ repetitions, the algorithm exponentially filters out non-neighbors.

Crucially, FLINNG performs zero distance computations at query time. It relies entirely on bitwise operations and integer lookups, making it incredibly hardware-friendly. Traditional LSH counts "collisions" and uses statistical thresholds, whereas FLINNG uses group testing to logically rule out entire blocks of the dataset with a single bitwise operation.

Experimental Results

The authors evaluated FLINNG on several challenging, high-dimensional datasets, including YFCC100M (100 million media embeddings, approx. 1TB), RefSeqG & RefSeqP (genomic and proteomic sequences with billions of dimensions), PromethION (raw metagenomic sequencer data), and large-scale web mining datasets (URL & Webspam).

The performance gains on the 100-million-point YFCC100M dataset are particularly striking:

  • Indexing Speed: Unlike graph-based methods that require complex, iterative builds, FLINNG can be constructed in a single pass through the data. It took just 40 seconds to build the index. In comparison, FAISS took 12 hours, and HNSW took over 5 days.
  • Memory Footprint: FLINNG required only 3.5 GB of RAM. HNSW required over 1 TB (the size of the dataset itself).
  • Query Throughput: FLINNG achieved up to a 10x speedup over existing indices on genomic search tasks while maintaining high precision and recall. This is largely due to its "distance-free" advantage, bypassing the CPU-heavy floating-point math that slows down other indices.

Limitations and Future Work

While FLINNG is a powerhouse for high-dimensional data, the authors note some constraints:

  • High-Similarity Focus: The algorithm is optimized for finding "near" neighbors (points with high similarity). It is less effective for $k$-NN classification tasks where the "nearest" neighbors might actually be quite far from the query in absolute terms.
  • Stability Dependency: The theoretical sub-linear query time depends on a "stability" parameter ($\gamma$). If a query is surrounded by many points that are "almost" neighbors but not quite, the filtering efficiency can drop.
  • Index Size: Theoretically, the index size could grow super-linearly ($O(N^{1.5})$), though the authors show that in practice, the constant factors are so small that it remains much smaller than competing methods for current scales.

Ultimately, FLINNG represents a significant step toward making billion-scale, high-dimensional search accessible on commodity hardware without the need for massive RAM clusters.

Summary updated

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.
BibTeX
@inproceedings{engels2021practical,
  author = {Joshua Engels and Benjamin Coleman and Anshumali Shrivastava},
  title = {{Practical Near Neighbor Search via Group Testing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=ebIORrYImx},
}
Figure