  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.
