Practical Near Neighbor Search via Group Testing
Authors: Joshua Engels
Benjamin Coleman
Anshumali Shrivastava
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: group testing
locality sensitive hashing
near neighbor search
index

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.

Practical Near Neighbor Search via Group Testing
Joshua Engels" Department Computer Science Rice University Houston, Texas, USA jae4@rice edu
Benjamin Coleman"
Electrical and Computer Engineering Rice University Houston, Texas, USA ben. www.commmmee...eeee....ee edu
Anshumali Shrivastava
Department of Computer Science
Rice University & ThirdAl Corp.
Houston, Texas, USA anshumalion weaemaa@@riieeeee edu
Abstract
We present new algorithm for the approximate near neighbor problem that com- bines classical ideas from group testing with locality-sensitive hashing (LSH). We reduce the near neighbor search problem nating neighbors as "positives," non non-neighbors as "negatives," " and approximate membership queries group tests. We instantiate this framework using distance- sensitive Bloom Filters to Identify Near-Neighte that FLINNG has sub-linear query time and show that algorithm comes with a variety practical advantages. For example, FL.NNG 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 tigh-dimmnsional 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.
group testing problem by desig-
Groups (FLINNG). We prove
1 Introduction
Nearest neighbor search is a fundamental problem with many applications in machine learning systems. Informally, the task is as follows. Given dataset D (I1, 22 ...IN), we wish to build data structure that can be queried with any point 9 to obtain a small set of points x; E that have high similarity (low distance) to the query. This structure is called index. Near neighbor indices form the backbone of production models in recommendation systems, social networks, genomics, computer vision and many other application domains.
Applications: In this paper, we focus on algorithms for approximate near neighbor search over high- dimensional large scale datasets. Such tasks frequently arise in genomics, web-scale data mining, machine learning, and other large-scale applications. Consider the Yahoo Flickr Creative Commons dataset (YFCC100M) which consists of 100 million media embeddings that are derived from the neuron activations for a convolutional neural network (2I). Each embedding is 4096-dimensional vector. The dataset is about ITB in size and presents substantial challenge for even the most popular algorithms, which struggle with memory, index construction, and query time. Similar issues occur
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

in genomics, where the task is to identify genome sequences with high Jaccard similarity to the query. Modern genomic datasets can contain millions of reads with billions of possible n-gram sequences [17]. Many algorithms work well when there are few hundred dimensions but are inappropriate for such applications. Our experiments demonstrate that for the datasets of interest in this paper, popular indices like HNSW and FAISS can take days to build, require gigabytes of RAM and have a suboptimal precision- recasiooo--callqueeey time tradeoff.
Since our goal is to perform approximate search, dimensionality reduction is a reasonable strategy. However, dimensionality reduction is costly for ultra-high dimensional data. In genomics applications, n n-gram sizes are typically very large (n > 18). Thus, the one-hot encoding of each sequence can require billions of dimensions (4 18 68B), making it intractable to learn an embedding model. For embedding applications such as YFCC100M or product search, a large embedding dimension can lead to performance improvements [S]. Dimensionality reduction can incur performance penalty, so we may wish to perform the near neighbor search over the original metric space.
Ideally, we would choose an algorithm that did not store data points in RAM, evaluate the distance function many times, employ iterative and non-streaming processes such as k-means, or construct complicated structures such as graphs. which are hard parallelize and distribute. Recent algorithms such as FLASH [22] provide the ability to search based on aggregate LSH count statistics without computing distances, but these methods are heuristics that do not have theoretical guarantees. On the other hand, algorithms such as LSH, which have a well-established theoretical grounding, tend to perform poorly in practice because of their prohibitive hash table size and post filtering stage. which needs many (No in theory) distance computations. In this paper, we present an algorithm having all the practical advantages of a system like FLASH while also being more accurate, theoretically sound, and provably sub-linear.
1.1 Our Contribution
In this paper, we address the computational challenges of high-dimensional similarity search by presenting an index with fast construction time, low memory requirement, and zero query-time distance computations. Our approach to transform a near neighbor search problem into a group testing problem by designing test that outputs "positive" when group of points contains a near neighbor to a query. That is, each test answers an approximate membership query over its group. Given a query, our algorithm produces B x R array of group test results that can be efficiently decoded to identify the nearest neighbors. This is more efficient than statistical aggregation algorithms like FLASH because each test filters out entire groups of non-neighbors with single test operation.
We develop a concrete example of such an algorithm by using Filters to Identify Near Neighbor Groups (FLINNG). We use standard non-adaptive group testing design with distance-sensitive Bloom filters as tests. We prove that FLINNG solves the randomized nearest neighbor problem in O (log(()) log (NV) time, where 7 is query-dependee
parameter that characterizes
query stability. We also implement FLINNG in C++ and conduct experiments on real-world high- dimensional datasets from genomics, embedding search, and URL analysis, where FLINNG achieves up to a 10x query speedup over existing indices with faster construction time and lower memory.
2 Related Work
The near neighbor problem has been the focus of more than four decades of intense research activity. The low dimensional problem is particularly well-understood, with space partitioning trees that can efficiently find the exact k-nearest neighbors. However, exact search in high dimensions is intractable due to the curse of dimensionality the computational resources needed to solve the exact problem scale exponentially with dimensions. This has led to a diverse set of algorithms to solve the approximate near neighbor problem, which we now describe.
Locality Sensitive Hashing:
LSH was the first approximate near neighbour algorithm to break the curse of dimensionality. At their core, LSH algorithms use an LSH function to partition the dataset into buckets. The hash function is selected so that the distance between points in the same bucket likely to be small. To find the near neighbors of query, we hash the query and compute the distance to every point in the corresponding bucket. Query performance can be improved with replication, which queries multiple independent hash tables, multi-probe methods [13), which examine multiple

---

buckets in the hash table, and data- data-dependent LSH B3, which tunes the hash function to the dataset. Recent work shows that machine learning algorithms can also construct effecttvve LSH partitions [6].
Count-Based I LSH: There are several recent algorithms which identify neighbors by counting the number of LSH collisions rather than explicitly computing distances. For example, the algorithm from [22] uses the count values to quickly identify potential neighbors. The algorithm from [S] applies compressed sensing techniques the counts compress the dataset, and popular technique in genomics is to simply replace each data point with its hash values 17.
Graph- braph methods are another successful family of algorithms. Graph algorithms locate near neighbors by walking the edges of a graph where each point is (approximately) connected to its k nearest neighbors. The focus in this area has been to improve graph properties using diversification, pruning, hierarchical structures, and other heuristics [4]. Graph indices perform well on industry- standard benchmarks but not theoretically well-understood, despite recent progress [88] Graph indices also suffer from long construction times and bloated memory consumption.
Graphs:
Sample Compression: A large number of practical methods are based quantization. Such methods replace points in the dataset with compressed versions of the points. Methods such as scalar quantization, vector quantization and product quantization alias each point to collection of k-means centroids. One can also use machine learning to obtain learned Hamming codes for the dataset and perform efficient distance computations using bit operations. Advances in quantization to most other algorithms, but have been particularly effective when combined with brute force search on GPU hardware and partetion-based search over billion-scale datasets [11]
applicable
We are not the first algorithm to apply group testing to near neighbor search. However, existing algorithms have key limitations that prevent effective practical implementations and rigorous theoretical analysis. The authors of [0] propose a group-based filtering algorithm based on group representative vectors, the vector average of group entries. To query the index, [IO] explicitly compute the distances to points where the distance between the representative and query exceeds threshold. The algorithm of (20) uses the same group representatives, but applies online backpropagation algorithm to estimate the individual similarities.
Group Testing:
This work has two shortcomings. First, the methods require many distance calculations against the group representatives ([10 requires N/10 distances), resulting poor query time. Second, the average vector can be similar to the query even when all points are far from the query, precluding theoretical analysis except under restrictive distribution assumptions. In this work, we analyze methods where only the group tests are used to identify the neighbors, forming expensive distance computations. Unsurprisingyy, our method is theoretically and practically superior.
goal is to avoid per-
Theoretical Comparison: In high dimensions. most methods require conditions that depend on the data and query to prove efficient search time. Table[]]shwws some representative theoretical results for the classes of algorithms described previously.
3 Background
Formal Problem Statement: In this paper, we solve the randomized nearest neighbor problem. Definition] D is stronger version of the well-studied (R, c)-aprroxemate near neighbor problem. In particular, any algorithm which solves the randomized nearest neighbor problem also solves the approximate near neighbor problem with 1 and any R the distance to the nearest neighbor.
Definition 1. Randomized Nearest neighbor: Given dataset D, distance metric d(-:)) and failure probability 8 E [0. 1], construct a data structure which, given a query point y, reports the point D with the smallest distance d(z, y) with probability greater than 1 8.
3.1 Group Testing
Suppose we are given set D of N items, i of which are positive ("hits") and N - k of which are negative ("misses"). The group testing problem to identify the hits by grouping items and using small collection of group tests. A group test is positive if and only if any item from the group is positive. The objective of group testing is to reliably identify the positive items using fewer than N group tests. The problem is noisy if the tests make i..dd. mistakes with some false positive and false
3

---

Table 1:
Asymptotic query times for several types of near neighbor algorithms. Where possible, adapt the guarantees we report the time needed to succeed with constant probability this may be boosted to an arbitrary failure rate ó in polylog(1 time using standard techniques.
notation to apply to our problem statement. For randomized algorithms,
Method
Query Time
Notes
LSH 9
ON logN) N) p
log 1/
Many improvements to reduce p.
log 1/8
Only for dense uniform data on the unit sphere.
O VaNt Md) and M is problem-dependent.
Graphs 18
t depends on the query and can be arbitrarily close to 1.
Random Trees 19
dog N 0 Dog 4F
((1))
dist(g.zz)
dist(g.2")
2, Z,
FLINNG [this work]
O N + log" (N)
7
log K| log K|K]
log K|
can be < 0.5 (query-dependent).
negative rate. The group testing problem may also be adaptive, where we allowed design test based on the results of tests {1, .n. . - J. or non-adaptive, where we must perform all tests at once.
Since the problem's introduction in 1943, there has been considerable work toward the construction of test designs under various constraints. For a recent review, see M. In this paper we develop near neighbor search algorithms using the noisy group testing framework. For simplicity, mainly consider the doubly regular design, where we evenly distribute items among B tests, and we independently repeat this process R times to obtain B x R grid of group tests (Figure IT. This block testing design is similar to that of RAMBO R. but with different filtering and inference algorithms. However, algorithmic framework is compatible with any non-adaptive testing design.
3.2 Locality-Sensitive Hashing
hash function l((x) + (1, R} function that maps an input æ to an integer in the range R). R). An LSH family H is set of hash functions with the following property: Under the hash mapping. nearby points have a high probability of having the same hash value. The two points x and y are said to collide if f(x))
h(y). We will use the notation s(x, 2) to refer to the collision probability Pr+[h(x) = h(y)]. The original definition of LSH given by [9] establishes lower bounds on s(x, 2) when d(æ,, y) is small (i.e. we want high probability that æ and y collide) and upper bounds when d(x, y) is large (i.e. we do not want x and to collide). For our analysis, we will assume slightly different notion of LSH. Specifically, we suppose that s(x, y) is exactly equal to the similarity between x and y. That is, s(x, y) = sim(x, y). The vast majority of LSH functions in the literature satisfy this property see 77 for review.
We also introduce the concatenation trick. For any positive integer I., we may transform an LSH family H with collision probability s(z, y) into a new family having s(ar, y)² by sampling I. hash functions from H and concatenating the values to obtain a new hash code [/1 (x)), (22x)), .... ft (x)]. If the original hash family had the range [1, RJ.. the new hash family has the range [1, R2).
3.3 Distance-Sensitive Bloom Filters
The distance-sensitive Bloom filter 12 data structure which solves the approximate set member- ship problem.
Definition 2. Approximate Set Membership: Given a set D of points and similarity thresholds S1 and SH, construct data structure which, given query point y, has:
True Positive Rate: If there is x E D with sim(x: (x, y) > SH. the structure returns true w.p. 2 P False Positive Rate: If there is no I E D with sim xr v) > St. the structure returns true w.p. q
The distance-sensitive Bloom filter solves this problem using LSH functions and a 2D bit array. The structure consists of binary arrays that are each indexed by an LSH function. There are three

---

parameters: the number of arrays m, positive threshold t S m, and the number of concatenated hash functions L used within each array, The length of each array set to be the range of the LSH family and is therefore not a parameter.
To construct the filter, we insert elements E D by setting the bit located at arra index [m, hm (1:) to 1. To query the filter, we determine the m hash values of the query y. If at least t of the corresponding bits are set, we return true. Otherwise, we return false. For our group testing analysis, we need explicit bounds on the error rates p and q. We obtain these bounds using a straightforward extension of Proposition 2.1 from I2 and provide proof in the supplementary materials.
Theorem 1. Assuming the existence of LSH family with collision probability s(x,, y) sim(a, v). the distance-sensitive Bloom fittrr solves the approximate membership query problem with
p 1 -1-en exp (-2m (-t+ s4))
q S exp (-2m (-t+NS)) NSS)
(1)
Algorithm 1 Index Construction
Algorithm 2 Index Query
Input:
Dataset D of size N. positive inte- gers B and R. similarity threshold S Output: A FLINNG search index consist- ing of membership sets Mr, and group tests C..
Input: A FLINNG index and a query y Output: Approximate set K of neighbors with similarity greater than the threshold S K [1.....N) .N}
for r = 0 to R 1 do
for 0 to Rt- do
Y= 0
Let IT be a random permutation of D Define M,. {T)();; mod B = b}
for b = to B- - do
if Cr,((y) 1 then
y=Y Mr
for r 0 to R 1 do
k=k
for = 0 to B - do
Construct a classifier Gr,6 for member- ship set M, with true positive rate and false positive rate q
4 Algorithm
We will now describe our algorithm for high- dighh-dimenional near neighbor search. We begin by reducing the near neighbor search problem to group testing problem. Suppose we are given an N N-point dataset D and are asked to return points which are similar to a query y. we apply a similarity
threshold to the dataset, we obtain a near neighbor set K = {x D D)sim(z; y) 2 S). We consider K to be the set of "positives" in the group testing problem. We can solve the similarity search problem by finding the |K| positives among the N - K negatives using group testing.
In order to do so, we split the dataset D) into set of groups, which we visualize as B x R grid of cells. Each cell has a group of items My and a corresponding group test Cr.B. To assign items to cells, we evenly distribute the N points among the B cells in each column of the grid, and we independently repeat this assignment process R times.
To identify groups that contain positives, need testing procedure that outputs "true" when the group contains a point similar to and "false" otherwise. That is, we require a binary classifier &r that solves the approximate membership testing problem for Mr (Definition 2). For group testing to be effective, the true positive rate and false positive rate q of the classifier Cr.b should be good enough to reliably identify positive and negative cells, respectively.
Algorithm shows how to construct the index. We begin by randomly distributing the points across the B cells in each row, that each cell has the same number of points. This can be done by randomly permuting the elements of D and assigning blocks of B elements to each cell using modulo hashing. Then, construct classifiers (group tests) solve the approximate membership problem in each cell.
N
To query the index with point y, we begin by querying each classifier. If Cv. = 1, then at least one of the points in Mr has high similarity to y. We collect all of these "candidate points" by taking the union of the M, sets for which Cy,( 1. We repeat this process for each of the R repetitions
5

---

Dataset
R
Bloom Filter Test
O
01110100001111110000111011111111
O
B
00001 01001111111000000001011111111111
01000111111111101111111111111111
00010100000000000000000000000000
Tests
Array of Tests
S1
$2
SynS2
vs Neighbors
Figure 1: Intuition behind our approach. We mark the neighbors (black dots) of query (blue X) as "positives" for group lesting and construct a B x R array of tests. Based on the test results, we obtain sets Si, S2,, RR.S of candidates, which we intersect identify the neighbors. In general, the tests can be any classifier that detects neighbors. In this paper, we use distance-sensitive Bloom filters.
to obtain R candidate sets, one for each column in the grid. With high probability, each candidate set contains the neighbors, but it may also have some non-neighbors that were included in M, by chance. To filter out these points, we intersect the candidate sets to obtain our approximate near neighbor set K. Algorithm explains this process in greater detail.
Intuition: In each repetition, we partition N points into B groups, where B << N. To understand why this strategy leads to good performance, suppose we are only interested in finding the nearest neighbor TNN (i.e. |K] 1). If the tests have high true positive rate p, then the R cells that contain INN will have (B) = 1. If the tests have a low false positive rate then the cells that do not contain INS will have Cr,( 0 with high probability.
In the first repetition, our tests identify the group Mo.s that contains 2NN each point Ma. is wear-neighbor candidate. Thus, with only B calls to the classifier Cro(y), we have reduced the number of candidates from N to B
N If we repeat this process, we find another candidate set MI,,. Our overall set of candidates is now the intersection Mo.s M1,s. whose expected size B In general, each repetition reduces the number of candidates by factor of z. which decreases exponentially with the number of repetitions. We progressively rule out more and more candidates until we are left with only the near neighbors.
In practice, this process is efficient because we can construct tests with reasonable and that are very fast to query. For example, when Cr,6 is distance-sensitive Bloom filter, the testing process can be implemented using constant memory with bit operations or efficient integer lookup tables. The set union and intersection operations can also be implemented using cheap integer operations. The result is an algorithm that identifies the near neighbors using group testing, without explicitly storing the data or performing any distance computations.
Theory
Proof Sketch: We defer full proofs the supplementary materials; what follows high-level description our theory. To obtain theoretical guarantees, we first assume that the tests have a universal fixed false positive and false negative rate. Under this assumption, the query time and eиror rates of the FLINNG algorithm. Next, we show how to construct distance- sensitive Bloom filters with a given eиror rate that satisfies these conditions. Here, the main technical difficulty is to bound the query time necessary to achieve the correct testing error rate. To do this, we introduce data-dependent sparsity measure y that is small when the query has only few close neighbors. To prove our main theorem, we set the test error rates so that the group design solves the randomized nearest neighbor problem.
derive bounds
5.1 Group Testing: Runtime and Accuracy
We first derive bounds on the error rates our index. To find the probability of correctly reporting points neighbors, assume that each group test has fixed false positive and negative rate.

---

Lemma 1. Suppose we have a dataset D of points, where subset K C D is "positive" " and the rest are "negative." Construct a B x R grid of tests. where each test has ii.d. false positive rate p and false negative rate q. Then Algorithm reports points as "positive" with probability:
Pr Report x/1 E 2 n"
[ - B(N - (
(1-(N( -1 (BB(N- - (
[K]
I
Pr(Report.z/r & K]
+p
(3)
The cost of group testing inference (Algorithm is the cost to do all B X R tests, plus the cost of intersecting the positive groups. We bound this cost by bounding the number positive groups.
Theorem 2. Under the assumptions in Lemma 7 suppose that each test runs in time O Then
with probability
- [BTT+ +
RN (p|K) qB) (og(188) N )
lquery =
(4)
B
5.2 Bounding the Test Cost
Our next step find the runtime and error rates of specific binary classifier: distance-sensitive Bloom filter. To distinguish between the K nearest neighbors and the rest of the dataset, we construct filter using Theorem with S (im(
k| y) S| and S sim [#]K]+1 y) $ | where N a is y's Ktth nearest neighbor. We also assume that the filter contains B points and B = 2v Our goal in this section is to select threshold number of bit arrays m, and LSH parameter L to obtain a specified value of and q. Once we have a test with the required error rates, we will bound the test time T.
Without imposing additional requirements on the query and dataset, it is impossible to design a filter for arbitrary p and q, observed by [12). However, this limitation is not serious. We can obtain the error rates provided that the query has K clearly-defined neighbors and the non-neighbor points easily distinguished from the neighbors (i.e. 8 S|K++1 & $1K)). This is closely related to the stability condition from [4] so we refer to such queries as stable. We formally define 7ystable query as:
log(s18()
Definition 3. 7-stable Query: We say that a query is 7-stable if 1og(s1K(+1) log(s181) S
We are now ready to design the classifier. Our classifier achieves the error rates p and q for any ytstable query and has bounded query time, fulfilling the conditions from Theorem 2
Theorem 3. Given true positive rate false positive rale and stubility parameter is possible to choose m. Li and so that the resulting distance-sensine Bloom filter has false positive rute p and false negative rate 9 for all yt-stale queries. The query time is
((mL) O (- l--oommmnn(g 1 p))NN log(N))
(5)
5.3 Query Time Analysis
In this section, we initialize the group testing framework using Bloom filter tests solve the randomized nearest neighbor problem. First, we consider the query time of a 2VN x R grid of Bloom filter classifiers. Lemma is is straightforward substitution of the query time from Theorem 3 into Theorem [] with = mL.
Lemma 2. Under the assumptions in Lemma 7 we can use distance-sensitee Bloom filters as tests to achieve the following query time tquery of Algorithm with probability 1
lquery O(RN log(N) max(- log(g), log(1 (1- - p)) + RNV log" (N)(K) + g log(118))
There are two ways that Algorithm 2 can fail solve the nearest neighbor problem (i.e. |K| 1). We may fail to return the nearest neighbor, but we may also return any point in D that is not the nearest neighbor. We determine the values of and q needed to achieve an overall failure rate 8 by requiring that both events occur with probability < & and applying the union bound.
7

---

Lemma 3. Under the assumptions in Lemma 7 we can build a data structure that solves the randomized nearest neighbor problem for sufficiently large N and small ö, where
5 2R
log(#)
p
N=
R
(6)
1og(4.80N') log(222 3.44Nz)
We obtain main theorem by using the values from Lemma with the query time from Lemma Note that the query time sublinear when the (data-dependent) stability parameter ? < 2
2
Theorem 4. (Main Theorem) Under the assumptions of Lemma we solve the randomized nearest neighbor problem for ytsbbl queries in time Equery.
lquery O ( log (N) (N) (1
8) )))
[K s have sub-linear query time (? < 0.5). In practice, this means that the [K] neighboring points should have high similarity to the query and the non-neighboring points should be far away. The high-dimensional Gaussian mixture model is simple example of favorable data distribution, where queries are 7-stable the Gaussians are sufficiently well-spaced to produce tight clusters. Real datasets also happen satisfy the y-stable condition for many queries. For example, 15% the queries for the RefSeqG dataset satisfy 7 < 0.5 with K 1. If we consider 1 < K < 100, 35% of queries satisfy the sub-linearity condition for some in this range. We provide additional results in the supplementary materials.
Practical Implications: We must have 1+7
Finally, the size of the index O(NmBR) O(N (N), leading to two concerns. First, the space is asymptotically super-linear. However, the practical index size scales much better than expected because the Bloom filter space overhead involves very small constant factors (often a few bits). This leads to practical index sizes that are much smaller than other methods even those with superior asymptotic behavior. Second, the size depends on the range m of the LSH function l(()). However,
While some LSH families have small constant m, others have infinite use a univeral hash function to rehash the infinite output space to range m in such cases. The penalty is a minor distortion the collision probability that does not substantially affect results.
may simply
Algorithm 3 Threshold Relaxation Algorithm
PromethION: Top- 10 Nearest Neighbours
Input: A: Array of cells, sorted in descending order by hash collisions, k: number of neighbors to return
Prectsion
Output: Approximate neighbors of the query Counts +- Array of length N, initialized to
Result +- Empty list of IDs for i = 0 to B x R - do cell Ali] do increment Counts[2]] if Counts]r] R then append z to Result if [Result] le then return Result
TUNNGG (20ms) HNSW (23msl
for point
PLASH (20ml)
67 Recall
Figure Precision recall tradeoff Prome- thION with query time limit of 20 ms. Up and to the right is better.
6 Implementation
Several nontrivial implementation tricks are needed to achieve good practical performance. First, we use the same m LSS functions for all of the filters, allowing us hash the query only one time. Second, we represent the distance-sensinn sensitive Bloom filters as lists of hash codes rather than bit arrays. This allows us to represent the FLINNG structure as a reverse index from hash values
We require N > 150 and small enough that R 10 log N

---

to cells. The reverse index is lookup table that, given a hash value h, returns list of cells whose distance-sensitive Bloom filters contain h. We keep reverse index for each of the m LSH functions.
To query the index, we use the reverse index to count the number of times that each cell collides with the query across the LSH functions. This results in an array of B R count values, one for each cell. To obtain the classifier outputs, we mark all cells with count values larger than threshold t as "true." In Theorem 3 we used a global value of f for all queries. However, this does not work in practice because different queries require different similarity thresholds. To address this issue, we use Algorithm 3 which relaxes t until enough cells return "true" so that & neighbors are returned. This process is equivalent to running Algorithm 2 with decreasing thresholds until & points are returned.
We implemented FLINNG in C++, compiled with the highest level of optimization with GCC, and used OpenMP to parallelize index construction. We implemented the reverse index as an m x 2 table of pointers to vectors, where each vector contains list of cells. To reduce index space, we store cell identifiers as short integers when possible. Finally, note that Algorithm (3) requires an array of length V to store the count values associated with each point. For large datasets, this can exceed the CPU cache size leading to a slowdown from RAM access. However, we can avoid this issue if R = 2 (which is often sufficient for many applications). By storing the counts as bit array of N/8 bytes, we can fit N < 240 million into a 30 MB CPU cache. We make this substitution where appropriate.
7 Experiments
We tested FLINNG on high-dimensional genomics, web-scale data mining, and embedding search datasets. We list the datasets in Table and briefly describe them here. RefSeqG and RefSeqP are sets of reference genome and proteome sequences for approximately 88k species [7]. The sequences are represented sets of 21-grams (k-mers) and are compressed via MinHash. Similarity search is relevant to RefSeq because we can answer basic scientific questions by clustering genomes. PromethION is stream of raw metagenomic sequence reads from the latest sequencing machine by Oxford Nanopore [16). which generates 4TB of data per day. We preprocess the reads into 16-grams. Here, similarity search is important for read de-duplication and other pre- assembly applications. The URL dataset and Webspam datasets are from the libsvm repository. The YFCC100M dataset consists of embeddings derived from neural network activations for 100M videos and images 21
Datasets:
Datasct
N
d
d
Description
Memory
Indexing
RefSeqG
117k
1.4T
lk
Compressed genomes
FLINNG
3.5 GB
40 sec
RefSeyP
117k
1.4T
lk
Compressed proteins
FAISS
3.7 GB
12 hr
PromethlON
3.7M
4.3B
286
Raw sequencer data
HNSW
>1 TB
>5 days
URL
2.4M
3.2M
116
n-gram features
FLASH
4.3 GB
80 sec
Webspam
340k
16.6M
3.7k
n-gram features
Table 3: Index characteristics for YFCC100M.
YFCCI0OM
97M
4096
4096
Neural embeddings
Table 2: Datasets: We selected data from genomics, text and embedding problems. Datasets have N points and d' dimen- sions, with an average d nonzero entries per point.
Baselines: We compare FLINNG against popular implementations of graph algorithms, LSH, and quantization-ban bassea search. FALCONN is a fast implementation of the traditional LSH algorithm that supports multi-probe LSH in various metric spaces [2]. FLAASH is a recent LSH algorithm that uses aggregate LSH count statistics to avoid distance computations [22]. HNSW is a multi-level industry-standarr benchmarks [14. We
graph search algorithm with exceptional performance use the hnswlib library and extended it to work on genomic datasets. FAISS is a highly optimized quantization caatt library used for billion-scale similarity search at Facebook compare against a simple inverted index approach for sparse data when feasible, as well as our implementation (GROUPS) of the other group testing algorithm from (2)..
[T]. Finally, we
We construct indices in parallel but query using a single core. Due to limitations of baseline algorithms, we were unable to evaluate all algorithms on all tasks. Due to space constraints, we provide information about hyperparameters, experiment setup, and computing hardware in the supplementary materials.
Experiment setup:
9

---

RefSeqG
RefSeq
PromethION
Quertes per second (log 10)
Queries per second (log 10)
Querles per second (log 10)
12
R1@100
R1@100
R1@100 YFCC100M
URL
Webspam
Querles per second [og 10)
Queries: per second [log 10)
Querles per second [lo 10)
FLIMSS BL.COM INSW
FLAING
FLASH
R1@100
R1.1000
1900
Figure 3: Time recall tradeoff for each dataset (Pareto frontier across hyperparameter configurations). Up and to the right better. We report R1 @101 except for YFCC100M, where we report R1 @1.
Figure 2 shows the precision recsal curve for the top 10 neighbors on the PromethION dataset when we constrain the query time 20ms. We find that FLINNG obtains between a 2-10x speedup on many search tasks. For example, FLINNG was 3.4 times faster than FAISS at the 0.99 recall level on YFCC100M and was 4x faster than HNSW on PromethION the 0.8 recall level. FLINNG also has small index size and construction time when compared with baselines (Table
Results:
We show the recall-query time tradeoff for all algorithms in Figure 3
Discussion
FLINNG is theoretically sound algorithm with attractive practical properties that lead to a fast implementation. Our theory shows that FLINNG has sublinear query time when the query has a relatively small number of highly similar neighbors, and our experiments show that FLINNG is efficient for many real-world problems. This is particularly true in genomics, where FLINNG can outperform algorithms like HNSW by substantial 4x margin. Existing algorithms often require expensive iterative algorithms such as k-means clustering or graph construction. In contrast, FLINNG relies simple lookup table structure that be constructed in single pass.
We believe that FLINNG could be particularly effective for situations where is hard to reduce the high-dimensional similarity search to a medium-dimensional problem. In genomics, this problem difficult because the k-mer distribution contains billions items and often has heavy-tailed distribution. The situation may also arise for embedding tasks such as YFCC100M, where it is known that dimensionality reduction can hurt performance. In these scenarios, where we prefer to search over the original metric space, FLINNG provides fast and scalable solution.
Limitations and Ethical Considerations: We do not foresce any ethical problems. The main limitation of our method is that it works best on high-dimensional search tasks where the neighbors are all above (relatively high) similarity threshold. For this reason, FLINNG is likely not the best choice for problems such as k-NN classification, where cow-siilarrity results may be important.
Acknowledgements
This work was supported by National Science Foundation IIS- 165213,,, BIGDATA--138177 RI- 1718478, AFOSR- YIP FA9550-18-1-01522 18-1-115, Amazon Research Award, and the ONR BRC grant on Randomized Numerical Linear Algebra.
10

---

References
[1] Matthew Aldridge, Oliver Johnson, Jonathan Scarlett, et al. Group testing: An information theory perspective. Foundations and Trends in Communications and Information Theory, 15(-4)):19-392, 2019.
[2] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. C. Cortes, Lawrence, D. Lee, M. Sugiyama, and R. Gareett, editors, Advances in Neural Information Processing Systems, volume 28, pages
1223-1233. Curran Associates, Inc., 2015.
[3] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the ferty-seventh annual ACM symposium on Theory of computing. pages 793-801, 2015.
[4] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. When is "nearest neighbor" meaningful? In International conference on database theory, pages 217-235. Springer, 1999.
[5] Benjamin Coleman, Richard Baraniuk, and Anshumali Shrivastava. Sub-linear memory sketches for near neighbor search on streaming data. In International Conference on Machine Learning, pages 2089-2099. PMLR, 2020.
[6] Yihe Dong, Piotr Indyk. Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2019.
[7] Aristides Gionis, Piotr Indyk, and Rajeev Motwaniz. Similarity search in high dimensions via hashing. In Proceedings of the 25th International Conference on Very Large Data Base, 1999, 1999.
[8] Gaurav Gupta, Minghao Yan, Benjamin Coleman, Bryce Kille, R. A. Leo Elworth, Tharun Medini, Todd Treangen, and Anshumali Shrivastava. Fast processing and querying of 170tb of genomics data via repeated and merged bloom filter (ramboo.. In Proceedings of the 2021 International Conference on Management of Data, SIGMOD/PODS '21, page 2226-2234, New York, NY, USA, 2021. Association for Computing Machinery.
[9] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604-614 613, 1998.
[10] Ahmet Iscen, Teddy Furon, Vincent Gripon, Michael Rabbat, and Hervé Jégou. Memory vectors for similarity search in high-dimensional spaces. IEEE transactions on big data, 4(1):65-77, 2017.
[11] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. arXiv preprint arXiv: 1702.08734, 2017.
[12] Adam Kirsch and Michael Mitzenmacher. Distance-sensitive bloom filters. In 2006 Proceedings of the Eighth Workshop on Algorithum Engineering and Experiments (ALENEX), pages 41-50. SIAM, 2006.
[13] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe Ish: efficient indexing for nigh-dimensional similarity search. In 33rd International Conference on Very Large Data Bases, VLDB 2007, pages 950-961. Association for Computing Machinery, Inc. 2007.
[14] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, (2(4):824-836. 2018.
[15] Tharun Medini, Beidi Chen, and Anshumali Shrivastava. Solar: Sparse orthogonal learned and random embeddings. In International Conference on Learning Representations, 2021.
[16] Samuel M Nicholls, Joshua C Quick, Shuiquan Tang, and Nicholas Loman. Ultra-decy long- read nanopore sequencing of mock microbial community standards. Gigascience, 8(5).giz043, 2019.
[17] Brian D Ondov, Todd J Treangen, Páll Melsted, Adam B Mallonee, Nicholas H Bergman, Sergey Koren, and Adam Phillippy. Mash: fast genome and metagenome distance estimation using minhash. Genome biology, 17(1):1-14, 2016.

---

[18] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based based nearest neighbor search: From practice theory. In International Conference on Machine Learning, pages 7803-7813. PMLR, 2020.
[19] Parikshit Ram and Kaushik Sinha. Revisiting kd-tree for nearest neighbor search. In Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining, pages 1388, 2019.
[20] Miaojing Shi, Teddy Furon, and Hervé Jégou. A group testing framework for similarity search in high-dimensional spaces. In Proceedings of the 22nd ACM international conference Multimedia, pages 407-416, 2014.
[21] Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. Yfec100m: The new data in multimedia research. Communications of the ACM, 59(2):64-33, 2016.
[22] Yiqiu Wang, Anshumali Shrivastava, Jonathan Wang. and Junghee Ryu. Randomized algorithms accelerated over cpu-gpu for ultra-high dimensional similarity search. In Proceedings of the 2018 International Conference Management of Data, pages 889-903, 2018.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The 10x query speedup shown Figure ?? and the theoretical results (sub-linear query time) proven in Section 5]:
(b) Did you describe the limitations of your work? [Yes] The main limitation that our method - like most LSH based algorithms - is not good for finding neighbors with low
similarity to the query. If the nearest points are far from the query, other algorithms
will be better. See Section g for more.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We do not foresee any negative consequences from this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The main assumption is 7-ttability, which is defined in Section 5.2
(b) Did you include complete proofs of all theoretical results? [Yes] There is proof sketch in the paper, but the full proof' are in the supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL.? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the supplementary materials.
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [No] We report the average of 10,000 queries. One option is to re-issue the set of 10,000 queries multiple times and compute the standard devia- tion. This results in a very small value. Another option is to individually measure the query latency 10,000 times, but this requires lots of instrumentation which affects the performance.
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] We used two machines: one with 88 Intel Xeon E5-2699A v4 processors and one with 96 Intel Xeon Gold 5220R processors. There is more information in the supplementary materials.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the FAISS, FALCONN and HNSW implementations.
(b) Did you mention the license of the assets? [Yes] FAISS and FALCONN are released
under the MIT license. HNSW is released under the Apache-2.0 license.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
We include code, which is not yet released under any license.
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nLaesMD2Rs", "reviewer": "Reviewer_eTUm", "summary": "The paper develops a new algorithm for approximate near neighbor search by combining ideas from group testing and bloom filters. The proposed algorithm called FLINNG casts the problem of finding the near neighbor of a query point in a high-dimensional dataset, as the problem of finding a few number of \"positive\" groups in a group testing problem where each group captures the absence or presence of at least one near neighbor of the query in a small random subset of data points. The paper provides theoretical justifications of the sublinear query time of the algorithm in number of data points and provides empirical evidence on real-world data sets which demonstrates comparable to superior near neighbor query performance compared to some to some baseline algorithms.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides a novel method for the approximate near neighbor problem. The main advantages is that the query time (under some data-dependent assumptions) is sublunar (and therefore fast) and also the implementation is easy and in particular alleviates the need for clustering scheme or graph algorithms. However, the simplicity is highly conditioned on the data-dependent assumption. Therefore, the main limitation is on the gamma-stability requirement of the algorithms which states that the query point should be much more similar to a small subset of size |K| of the data points and be sufficiently far from the rest. This is needed to do the analysis since such data-dependent criteria ensures some notion of sparsity both in the group testing and Bloom filtering stage. My detailed comments are as follows:\n\nTheoretical comparisons. A comparison table containing the theoretical bounds in terms of (at least) the query time and (ideally) the memory and indexing time can be shown to compare FLINNG with other baseline algorithms (including the LSH). This will strengthen the paper and clarify the theoretical contributions. Is there any other sublinear time near neighbor algorithm that employs the stability condition in its bound?\n\nUtility of gamma-stable condition. To ensure the sublinearity claim gamma needs to be smaller than ½ in equation (7); enforcing this condition in Definition 3 yields the condition that s_{|K|+1} < 1/s_{|K|}. For large values of s_{|K|} this will results in very small values for s_{|K|+1}. To convince the utility of the gamma-stable condition it would be helpful to plot the empirical distribution of gamma (if obtainable) for practical values of |K| (e.g., |K| \\in {5,10,50,100}) in a few (maybe small) datasets. This is important since the sublinearity bound highly depends on that. Data that are highly clustered clearly pass the condition; an empirical analysis of the datasets listed in the paper can validate that for the real-world datasets in the paper. Also is there any faster way to check if the stability condition is satisfied for a dataset?\n\nDisparity across datasets.  It would be helpful if the authors can explain conditions under which HNSW can significantly outperform FLINNG, see e.g., Figure 5 in the appendix (Webspam Top-1 NN and RL10@10).\n\nLemma 1. In lemma 1 does increasing R decrease the lower bound for true positive rate? \n\nIndex characteristic. It would be important to add the Index characteristic of Table 2 for other data sets to the appendix.\n\nF-score. Since both precision and recall are critical in these tasks is it possible to add the time against F1 score in Figure 3?\n\nSmall typos: line 271: “to achieve good practical”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "Non.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "jhS8FFOJzTU", "reviewer": "Reviewer_557Q", "summary": "In this paper, the authors presented an algorithm coined Flinters to Identify Near-Neighbor Groups (FLINNG) to solve the approximate near neighbor search problem. Given a dataset $D$, FLINNG is capable of constructing an {\\it index} which, when given a {\\it query} $y$, outputs a set of points $x_i \\in D$ with high similarity to $y$.\n\nThe near neighbor search is a problem with extensive research and a wide range of applications, including recommendation systems, social networks, computer vision, and genome sequencing. While the problem is particularly well-understood in low dimensions, with efficient algorithms to identify exact k-neighbors, but large-scale applications on big datas with high dimentionality often challenges existing algorithms and data structures.\n\nThe authors address this need by showing that FLINNG is an index with efficient construction time, query time, simple structure, and low memory requirement. FLINNG utilizes many previously developed techniques, most notably a reduction from approximate near neighbor search to approximate set membership, and solving the latter using distance-sensitive Bloom filters, with a lower bound on the true positive rate and a upper bound on the false positive rate.\n\nTo construct the index, FLINNG randomly distributes all data points in $D$ evenly among $B$ groups, and repeats $R$ times to create $R$ such independent instances. For each of the $B \\cdot R$ groups created this way, FLINNG constructs a classifier using distance-sensitive Bloom Filters with appropriate error guarantees, which solves the approximate set membership problem on this group.\n\nWhen a query on point $y$ arrives, FLINNG queries each of the $B \\cdot R$ classifiers on whether the corresponding group contains a near neighbor of $y$. If the classifier of a group returns an affirmative result, that group is likely to contain a near neighbor of $y$, and is considered a {\\it candidate group}. FLINNG then first takes the union of all candidate groups within the same instance, then eliminates noises and amplifies accuracy exponentially by taking the intersection of the unions across all $R$ instances. The resulting intersection is returned as the near neighbor set of $y$.\n\nThe authors show that FLINNG can be highly efficient due to the properties of distance-sensitive bloom filters, which allows queries to have constant memory allocation and sublinear time complexity. An implementation is designed and compared with other status-quo near neighbor search algorithms like FLASH, HNSW, and FAISS, on the PromethION data set. These experiments show that indices constructed with FLINNG exhibit a 2x to 10x speed up in queries, as well as decreased index size and construction time.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall, I believe that the article is well-written, well-thought, and of significance. The authors explained in detail the background, prior work, and significance of the problem and their solution, and provided theoretical and empirical evidence of the effectiveness. Although the main body of the article only stated the important theorems and lemmas vital to the analysis, a full proof is indeed provided in the appendix, complementing and completing the authors' argument.\n\n2.1 Originality\n\nThe authors did a great job outlining the prior works done on the near neighbor search problem, with adequate citations. FLINNG utilizes the idea of group testing, which differs from a lot of status quo algorithms based on locality sensitive hashing, sample compression, or graph-based methods. Although there are prior works which apply group testing to near neighbor search, these methods are limited in feasiblity and effectiveness. The authors utilized distance-sensitive Bloom filters to circumvent the aforementioned limitations, resulting in an algorithm that performs better than its predecessors.\n\n2.2 Quality\n\nThe work is technically sound to my best knowledge. The authors claimed that FLINNG is an algorithm that solves the approximate near neighbor search problem efficiently and effectively, and is comparable and competitive against all the status quo algorithms on near neighbor search. The authors then indeed supported these claims by theoretical analysis as well as empirical data. Theoretically, the overall structure of their analysis is sound, and their results are supportive of their claim: FLINNG can support queries with sublinear time complexity, and the error rate is exponentially small. Following these analysis, the authors provided experimental results, comparing the runtime and accuracy of FLINNG to other status quo algorithms including FLASH, FAISS, and HNSW. Their results show that FLINNG obtains a significant speed up and a decrease in data structure size compared to other algorithms. To my best knowledge, the authors' analysis and experimental setup is correct and sound. While the authors did not discuss the weaknesses of their algorithms except a brief argument in the conclusion, I am unable to identify any characteristic that requires any lengthy analysis.\n\n2.3 Clarity\n\nThe article is clearly written with reasonable structure. The authors separated the theorem and lemma statements and the actual analysis, putting the outline of the analysis in the main article, while delaying the proofs to the appendix. This is a common practice, but it is arguable that structuring the proof, perhaps an abridged version under the statements, can better faciliate understanding.\n\nAnother critique is that many of the article's stated lemmas and theorems involves many variables and complicated mathematical expressions. While this complexity is justified by itself, there may be a lack of explanation around these statements to compensate for the complexity. This is especially relevant when the details of the proof are delayed to a later section. As a result, I find the lemmas and statements hard to comprehend without scrutiny. It would be better if the authors can append a sentence or two after statements with complex mathematical expressions, Theorem 2, 3, and 4 in the article, for example, to briefly explain the significance and meaning of these statements.\n\n2.4 Significance\n\nIt is clear both from the authors' narration and the implications of their results that this article is of significance. Near neighbor search is a problem with many applications in various fields, and any improvement to methods solving the problem will imply more efficient and effective algorithms for all such fields. The authors clearly stated the improvements of FLINNG over other status quo algorithms and supported their claims with sound arguments, both theoretical and empirical. Their algorithms are also quite simplistic in nature, and although I am not experienced enough to immediately identify any potential extensions, no doubt future researchers can build upon this article for further improvements to near neighbor search or other significant problems.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ULzbs1ht_xn", "reviewer": "Reviewer_e9ca", "summary": "Near Neighbor Search (NNS) is one of the most fundamental problems in machine learning. This paper proposes an efficient NNS method for high-dimensional data by transforming the original problem into a group testing problem. The authors provide a detailed theoretical analysis of the distance-sensitive Bloom Filters for group testing to demonstrate how the query time and the quality are bounded with proper parameters settings. Experiments validate the performance of FLINNG.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. I appreciate the idea of using group testing to shortlist the nearest neighbour candidate and use repetition to remove false positives. \n\n2. FLINNG enjoys a provable bound for query time and quality.\n\n3. This work provides a detailed theoretical analysis to guide parameter settings in the experiments.\n\n4. The paper is easy to follow, and Figure 1 is clear to show the general workflow of the proposed method.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall, I like this paper. However, I still have some questions about this paper, and some limitations justify my current rating.\n\n1. The $\\gamma$-stable query condition is a relatively strong requirement for the query. As pointed out by the authors, FLINNG works better for genomes data such as RefSeqG and RefSeqP that have ultra-high dimensions. However, for other ultra-high dimensional datasets such as Webspam and URL, the performance of FLASH is better than that of FLINNG, which might be due to this strong query condition. This limit this work to be applied to other applications. Or could you further analyse whether there is any mathematical condition to indicate a dataset as suitable for this method? You can assume the query and data are from the same distribution.\n\n2. For the $m$ hash tables used for the distance-sensitive Bloom filter, the bound of the hash code $h(x)$ is not clearly explained. Since the FLINNG structure is an inverted index (as indicated in Section 6) from hash code to cell, the range of $h(x)$ would greatly affect the space requirement of the index structure. This may need to explain more clearly.\n\n3. The hash functions and distance metrics used for each dataset are not specified. For example, the authors only mentioned some of the datasets are compressed via MinHash, but they did not specify the LSH for the distance-sensitive Bloom filter. I suppose MinHash and Jaccard similarity is applied for the sparse datasets, but what about the dense dataset YFCC100M? And FAISS do not support Jaccard similarity.\n\n4. In the experiments, some necessary information is missing. \n(1) The index construction time comparison with FAISS lack details such as whether the GPU support of FAISS is enabled. Also, since there are plenty of parameter combinations, what exactly is the trade-off between search performance and index constructions. \n(2) The number of queries is not specified for each dataset. For query time, since FAISS can support batch queries so whether the comparison is under maximum query batch size or just one query at a time would greatly affect the query efficiency. \n\n5. The paper presentation can be further improved. For example, In Section 5, some of the references are clearly wrong and get mixed up with the proof in Appendix, e.g., In Lemma 2 (Line 258), they claim \"Under the assumptions in Lemma 2...\" Additionally, there is a reference to Figure 4 in the Appendix but Figure 4 is missing.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "0sG44X3KdG1", "reviewer": "Reviewer_sLDs", "summary": "The paper tackles the problem of near-neighbor (and nearest-neighbor) search in high-dimensional spaces. The authors propose to use group-testing on top of distance-sensitive Bloom filters: to simplify, the returned set is the intersection of the union of small sets, each of these small sets being a hash bucket that the query falls into. The authors derive the theoretical properties of their method FLINNG (sublinear query time), and show the superiority of their method compared to the state of the art (FAISS, HNSW, FLINNG) through extensive experiments on genome, URL and embedding data.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting and well-written, and tackles an important problem. \nThe construction of the algorithm is smooth to follow at a high-level, even though the meat resides in being able to construct a classifier with given true and false positive rates: to do this in a reasonable time, the authors have to assume gamma-stability which is a strong hypothesis. I was very positively surprised by the very strong empirical performance of the algorithm. I wonder if it is biased compared to other methods that operate on embeddings, because the datasets considered are mostly long sequences which means very high-dimensional data. \nI have a couple of questions for the authors:\n- Did you try other embedding datasets that YFCC100M, like Deep1B or BigANN1B?\n- How do you go from near- to nearest-neighbor search? In the paper, you mention running Algorithm 3 with various thresholds but Algorithm 3 doesn’t seem to take a threshold as input.\n- What setting of FAISS did you use? FAISS is a library implementing multiple quantization-based algorithms, I am assuming this is IMI (Inverted Multi Index)?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission was deemed significant, well-executed, and that it will have impact. While some reviewers had some reservations, the author rebuttals addressed the concerns.
Decision: Accept (Spotlight)