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.
The Curse of Dimensionality in Nearest Neighbor Search
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:
- 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.
- Quantization methods (like FAISS): These are more memory-efficient but still require significant compute for index construction and distance calculations.
- 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.
- 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