2021/06/22 by Joshua Engels, Benjamin Coleman, Engels, Joshua +3
Computer Science · Immunology and Microbiology · Medicine · #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #HIV Research and Treatment #SARS-CoV-2 detection and testing
paper · pdf · doi:10.48550/arxiv.2106.11565
openalex publication_date 2021/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.