Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search
Authors: Ninh Pham
Tao Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Approximate nearest neighbor search
locality-sensitive
recall-speed tradeoff

Abstract: We present Falconn++, a novel locality-sensitive filtering (LSF) approach for approximate nearest neighbor search on angular distance. 
Falconn++ can filter out potential far away points in any hash bucket before querying, which results in higher quality candidates compared to other hashing-based solutions. Theoretically, Falconn++ asymptotically achieves lower query time complexity than Falconn, an optimal locality-sensitive hashing scheme on angular distance. Empirically, Falconn++ achieves a higher recall-speed tradeoff than Falconn on many real-world data sets. Falconn++ is also competitive with HNSW, an efficient representative of graph-based solutions on high search recall regimes.

Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search
Ninh Pham School of Computer Science University of Auckland ninh. pwwm@auckl nz
Tao Liu School of Computer Science University of Auckland tliul37@aucklandde ac.nz
Abstract
We present Falconn+++, novel locality- sensitive filtering approach for approximate nearest neighbor search on angular distance. Falconn++ can filter out potential far away points in any hash bucket before querying, which results in higher quality candidates compared other hashing- bashing-based solutions. Theoretically, Falconn++ asymptotically achieves lower query time complexity than Falconn, an optimal Secality-sensitivv hashing scheme on angular distance. Empirically, Falconn++ achieves higher recall-speed tradeoff's than Falconn on many real-world data sets. Falconn++ also competitive with HNSW, an efficient representative of graph- based solutions on high search recall regimes.
Introduction
Nearest neighbor search (NNS) unit sphere is the task of, given a point set X 8d-1 of size and a query point Sd-1, finding the point p E X such that p = arg minxex ||x qll- Since both data set X and query q are unit sphere, NNS angular distance (i.c. = arg maxxex x q). NNS and its variant top-k NNS on angular distance the fundamental problems in computer science, e.g. web search recommender system (2]. machine learning 77. and computer vision [22].
Euclidean distance is identical to NNS on
NNS dates back Minsky and Papert 11.. who studied the tradeoff between query time and indexing space in high dimensions. Due to the "curse of dimensionality" linear scan outperforms space/data partitioning solutions solving exact NNS given linear indexing space (24. Given polynomial indexing space n (1)), there is known algorithm to solve exact NNS in truly sublinear time. If there exists such an algorithm, the Strong Exponential Time Hypothesis (SETH) (12), a fundamental
conjecture in computational complexity theory, is wrong 3 25
Due the hardness of exact NNS, researchers study efficient solutions for approximate NNS (ANNS). Given an approximation factor c' > 1, ANNS aims at finding the point p' E X within distance ||p qll. Since we can reduce ANNS to its "decision version". called (c. aaapprxximaee near neighbor ((c, r)-NN) for an approximation factor e >> 1 and radius [10]. solving ANNS boils down to (c, rNNN. The problem (c, r)-NN that asks to return any point within distance or to q there is a point within distance to is the key algorithmic component of many ANNS solvers. Locality-sensitie hashing (LSH) [13 is the first provable sublinear query time solution using a subquadratic indexing space for (c, r)NN in high dimensions.
In principle, LSH hashes "close" points, i.e. within radius r to q. into the same bucket with q with high probability, and hashes "far away" points, i.e. outside radius or to into the same bucket with low probability. Given parameter 0 < p < 1, LSH answers (c. r)-N in (dn") time and uses O (nd + nd*+)) space. Since the exponent governs the complexity of LSH, it is desirable to have LSH families with the smallest p. LSH families with optimal values p Rs 1 1/c² on Euclidean
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

distance are well studied in theory [1 In practice. to our knowledge, only Falconn 2 with the cross-polytope LSH family asymptotically achieves p = 1/c² on the Euclidean unit sphere.
Despite provable sublinear query time guarantees, the indexing space of LSH is a primary bottleneck. Since different queries require different values of practical I-SH-based solutions often use hundreds of hash tables to guarantee the querying performance. To overcome this bottleneck, Lv et al. [15] propose a multi-probbnn trick that sequentially checks nearby buckets of the query's ' bucket. This is because the hash values of the nearest neighbors of tend to be close to the hash value of on the hashing space [9]. Therefore, multi-pu multi-probe LSH achieves a similar success probability with a smaller number of hash tables than the standard LSH.
We observe that LSH and its multi-prode probe schemes do not efficiently answer ANNS on high recall regimes. Since the distance gaps between the nearest neighhors are tiny in many real-world data sets, need very small approximation factor c, e.g. c 1.01. This requirement degrades the perfor- mance of LSH-based solutions as + 1. In this case, multi-probe LSH has to increase the number of probes and the number of candidates. That significantly reduces the querying performance since the probed buckets different from the query bucket tend to have more far away points. Empirically, multi-probe Falconn [2] with L 100 hash tables on the Glove300 data set needs 4,000 probes and computes more than 0.1 n number of distances to achieve 90% recall. This is the rationale that LSH- solutions are less favorable for ANNS on high recall regimes than the recent graph-based solutions (6,, e.g. HNSW [16].
To further facilitate LSH-based solutions for ANNS, we propose a filtering mechanism that can efficiently filter out the far away points in any bucket before querying. Our proposed mechanism is also locality-sensitfie
in the sense that far away points will be filtered out with high probability and close points will be pruned with low probability. Therefore, we can safely remove far away points while building the index improve the query time and reduce the indexing space simultaneously. This feature significantly increases the performance of multi-probe LSH since it dramatically reduces the number of distance computations while preserving the search recall.
We implement the proposed filtering mechanism for angular distance based on the asymptotic property of the concomitant of extreme order statistics O 20). Similar to Falconn 22. our approach utilizes many random projection vectors and only considers specific vectors r; that are closest or furthest to the query q- The key difference is that we use the random projection value r, estimate x q by leveraging the asymptotic behavior of these projection values. This feature makes our filtering mechanism locality-sensitive.
Theoretically, our proposed locality- filtering (LSF) scheme, named Falconn++, asymptoti- cally achieves smaller p. parameter governing the query time complexity, than Falconn. Empirically, Falconn+ with a new add-on that applies multi-probing on both querying and indexing phases achieves significantly higher recall-speed tradeoffs than Falconn many real- world data sets. We further innovate Falcomn+ with several heuristics that make it competitive with HNSW [16) a recent efficient graph-basel solution for ANNS on high recall regimes.
Preliminary
2.1 Locality- hashing (LSH)
Since 1998, LSH [13] has emerged as an algorithmic primitive of ANNS in high dimensions. LSH provably guarantees sublinear query time for ANNS by solving the (c.r)-NN over Ô (logn) different radii Given a distance function dist(:,)), the LSH definition is as follows.
Definition 1 (LSH), For positive reals r, c, Pı, P2. and 0 < P2 < Pi I 1, c > 1. a family of functions H is (r, cr, PL, P1) if for uniformly chosen h E H and all x,y, q E Rd:
dist(x, q) S r, then Pr [h(x) = h((q)) 2 P1: If distyyy q) 2 cr, then Pr [h(y) h(q)) S P2
To simplify notations, we call x as a "close" point if (x, q) < r and y as "far away" point if dist(y, q) 2 cr. To minimize the collision probability of far away points, we combine / = O (logn) different LSH functions together to form new (r, cr. pf pb. -sensitivee LSH family, and set p/ = 1/n. Since the combination also decreases the collision probability of close points from p1 to p/. we need

---

2.45
Falconn++ Falconn
5
0:35
0.05
0.3
Falconn++
Falconn
0.2
C=1.5
cr= /2
(a) An illustration of Falconn with rı, 12, h(x) h(2)
(b) A comparison of hetween Falconn++ and Falconn while fixing and varying ri and fixing or v2 and varying
h(q)- rı, b,y -2.
L= O (1/r4) hash tables to ensure that we can find a close point with constant probability. Given the setting 2l2 1/'n and denote by p p= (n(1/p1)/ (n(1/p2) /p2). LSH needs L. O (n²) tables and compute O (n²) distances in (dn²) time to answer (c, r)-N with a constant probability.
The exponent / governing the complexity of an (r, cr, Pl, (2l pen-siiiiiive LSH algorithm depends on the distance function and c. O' D'nnelll et al. [18] show that 2 1/c² - o(1) on Euclidean distance given p2
1/n. However, it is difficult to implement the LSH families with optimal p in practice.
2.2 Falconn: An optimal LSH on angular distance
Andoni et al. 2 introduce Falconn that uses a cross-por coos-pooyytope LSH family on angular distance (i.e. cosine similarity). Given D random vectors r; Rd, E [D] whose coordinates are randomly selected from the standard normal distribution (0, 1), and (-) is the sign function, the cross- polytope LSH family uses the index of the random vector the hash value. In particular, w.l.o.g. assume that arg max,, lq rsl. then h(q) is calculated as follows:
M(q) = [r sgn q (r) 2 0,
-r, otherwise.
geometric intuition of Falconn that (())) rı (or l((q) -r) indicates that q closest (or furthest) to the random vector ri among D random vectors, as shown in Figure Ta Falconn uses D random vectors r; to partition the sphere into 2D wedges centered by the 2D random vectors =;; If x and q are similar, they tend to be closest or furthest to the same random vector, and hence are hashed into the same wedge corresponding to that random vector. The following lemma states the asymptotic collision probability between two points x, when D is sufficiently large.
Lemma 1. 12 Theorem l] Given two points E Sd-1 such that ||x qll = r where 0 <r < 2 Then, we have
Pr [h(x) h(g)) D ス/-
4/63,3_1 4/1--1 1/22.
Given small c, Equation indicates that Falconn has optimal exponent p
Multi-probe Falconn. To reduce the number of hash tables L, multi-probe Falconn considers the next closest or furthest random vectors to generate the probing sequence in hash table. For example, in Figure Ia| since q is next closest to -r2, the bucket corresponding to the blue wedge will be the next probe. Given a fixed total number of query probes Probbe for a query, ranking the buckets across tables challenging. Falconn heuristically uses the distance between the projection values of q random vectors to construct the probing sequence. For example, in the table corresponding
to Figure Ia the ranking score of the blue wedge for probing is q -Tr rr| - |q r2)- Even though
multi-probe Falconn can significantly reduce the number of hash tables, it demands a significantly large q &robes and candidate sizes to solve ANN on high recall regimes due to the small distance gaps among nearest neighbors.
3

---

2.3 CEOs: An optimal dimensionality reduction on unit sphere
Pham proposes CEOs [20, an optimal dimensionality reduction for ANN on angular distance. While CEOs shares the same spirit that utilizes random projections as Falconn, it is similarity estimation technique rather than hashing. In particular, CEOs randomly projects X and q onto D Gaussian random vectors and considers the projection values specific random vectors that are closest or furthest to q. e-g. arg max,, |q T r:/- Asymptotically, given a sufficiently large D, the following lemma states the projection values on few specific random vectors preserve the inner product.
Lemma 2. [20) Given two points X, q Sd-1 and significantly large D random vectors w.l.o.g we assume that 1 = arg max,, 1q r:/. Then, we have
x x ~ N (gn((TTr.) r1)) x V- (x]]))
(3)
Among random vectors, if r1 is closest or furthest to q, the projection values of all points in X preserve their inner product order in expectation. In Figure Ia| since q is closest ri, the order of projection values onto Ii, c.g. x r1 > z rı, preserves the inner product order, e.g. x > z q.
Importantly, given a constant > 0, Lemma also holds for the top-8o closest vectors and top-8o furthest random vectors to q due to the asymptotic property of extreme normal order statisties (9. For example, in Figure we can see that the inner product order is also preserved on -r1,
Connection to Falconn. From Equations I and 3 we can see that Falconn uses the top-1 closest or furthest random vector (i.e. rı) as the hash value of q while CEOs uses the projection values over this random vector as inner product estimates. Furthermore, the multi-probe Falconn likely probes buckets corresponding to the 2sg random vectors closest or furthest to q. Since the inner product order is well preserved on the projections onto these 2sg vectors, thanks the CEOs property. we can keep a small fraction of number of points with the largest projection values in Falconn's 's buckets. This filtering approach will significantly save the indexing space and improve the query time while maintaining the same recall as multi-probs Falconn. The next section will theoretically analyze this approach and deseribe its practical implementation.
Falconn++: A locality-sensitive filtering approach
3.1 A lecality-sensitive filtering (LSF)
Let 0 < 92 < F1 S 1, we define an LSF mechanism that can keep in any bucket ht(q) any close point with probability at least 91 and any far away point y with probability at most q2 follows.
Definition 2 (LSF). For positive reals v, C, qu Q2. and 0 < Q2 91 S L, 1, given x,y in the bucket ((q) where h is randomly chosen from a LSH family, an LSF mechanism is a filter that have the following properties:
If dist(x, q) S r, then Pr (x not filtered| 2 91 * If dislly. q) 2 cr, then Pr (y is not filtered & Q2
Applying the LSF mechanism on each bucket of the hash table constructed by any (r, cr, sensitive LSH, the new collision probabilities among x, y, q after hashing and filtering are:
Pr [h(x) = h()),, is not filtered] 2 41P1 Pr [hy) = hı(q) y is not filtered| S 92P2
Assume that LSF has the property In (1 (1/g1)/ln (1/g2) S p. applying hashing and filtering, we can solve (c, with the new exponent pf S
Benefits of LSF. Given the condition In (1/q1)/ In (1/q2) - p of LSF, combining filtering and hashing mechanisms leads to faster LSH-based (c,r)-NN solver since p' < p. We note that the number of required tables is now O (1/q1P1) whereas the standard LSH only needs O (1/p1). ). Since the number of close points is often much smaller than the number of far away points in real-world data sets, an LSF table contains substantially less than nę points in practice. Therefore, the combination of L.S and LSH improves both query time and indexing space compared to LSH.
Challenges. The challenge is how to design an LSF mechanism with In (1/q1)/ (1/g2) S 1/c2 since Falconn has asymptotically optimal 1/c². If this condition does not hold, the LSF

---

mechanism will increase the exponent p and degrade the querying performance. For example, randomly discarding a point in bucket will increase p. Next, we will instantiate the LSF mechanism based on the CEOs property, which leads to an evolution of Falconn for angular distance.
3.2 LSF with CEOs
Given sufficiently large D random vectors r,, w.l.o.g. assumee h(q) rı arg max, qrr, We denote by random variables X =x
R ri, Y.
y'r r corresponding to x. in the bucket h(q)) From
Lemma 2 we have X N x 2 D, (x) (xTq)²)
N (y" 2yTqv22m (y 9/9 ))²
Exploiting this property, we propose the filtering mechanism as follows:
r1 2 t and Given a threshold = (1 -1-11 11--r//0 (22-222) in each bucket, we keep any point x if TTrr discard any point y y rı
The following theorem shows that our mechanism is locality-sensitive.
Theorem 1. Given sufficiently large D random vectors and 1, the proposed filtering mechanism asymptotically has the following properties:
If < T, then Pr (x is not filtered, 2 41 = 1/22;
1f ly q 2 cr, then Pr ly is not filtered S q2 7v22 exp(->2//2) < q1 where
7 er(1-/fe Dn
v4-c*,²
The proof uses classical tail bound on normal variables Y over é (see the supplementary materials for details). Given a sufficiently large D, we can make In ///////n (1/92) arbitrarily smaller than 1/c². Hence, the proposed LSF mechanism can be used to improve Falconn for ANNS.
3.3 Falconn++: A locality-sensitive filtering approach
Falconn++ an essential combination between the proposed LSF and the cross-polytope LSH of Falconn using sufficiently large 1) random vectors. For each bucket, simply filter out potential far away points if its projection value is smaller than (1 - /2/ In D. From Theorem
have: In (1/q1) = In 2 and In (1/92) = In (V2m) + In + /// where = vI-c²p / D.
cr(1-1/c*)
For a large D, we have In (1/42) 72/2 -111/211² カ/25 In D. The new exponent p' of Falconn++ on
answering (c,r)-NN is strictly smaller than the exponent of Falconn since
p' In (1/(2P2)
In (1/q1P1)
111// N/---I
In
4/
1+ 11-111180 1/2)2
1
4/0²,2 -
4/72 11 p.
4/6-1=1
For small p 1/c² and = 1/(22² - 2 1/c2). Figure lb shows clear gap between p compared to p on various settings of r and c.
Discussion on the lower bounds. The lower bound > 1/e² o(1) 18 Theorem 4. 4.1] for data- independent (r, cr, P1. P2) -ee-siesee LSH families on Euclidean space requires P2 1/n to yield an O (P) space and O (n²) distance computations. Given the setting p242 1/n, have:
11-1/29) 4/c2,2
4/22,2 In D = Inn = D 1 n 14/+2-1)
4/62,2 -1
To ensure Falconn++ has an O (dree) query time, we need D = O n2e)) and hence r 2 /2. We emphasize that the theoretical improvement of Falconn++ over the lower bound is only in certain range of r. Note that this condition also necessary for Falconn. Since nearest neighbors tend to be orthogonal, i.e. r zs /2, in high dimensions, and distance computation often dominates hash use significantly large D to boost the practical performance of Falconn variants.
evaluation,
Connection to recent LSF frameworks. Our proposed LSF mechanism combined with Falconn can be seen as a practical instance of the asymmetric I LSF frameworks recently studied in theory 4 g These frameworks use different filtering conditions on the data and query points govern the space- time tradeoff of ANNS. In particular, given two thresholds tu, tg. over the random choice of r,, the
5

---

Algorithm Falconn++ with multi-probe indexing
1:
procedure MULTI-PROBE INDEXING(X, a, D random vectors ri, iProbes)
2:
for each x E X do
3:
Compute top-iProbes vectors s.t. |x r. is largest.
4: Add x into the iProbes buckets corresponding to these iProbes vectors.
5: end for
6: For each bucket of size B corresponding to r;, keep top- points with largest
absolute projection values on r;-
7:
end procedure
LSF frameworks study the probability where both x and q pass the filter corresponding to r,, i.e. Pr ixrr; 2 lus q r, 2 1z] Indeed, Falcona++ can be seen as specific design of the asymmetric LSF framework where we utilize cross-polytope LSH to implement the filtering condition for queries and the asymptotic property of CEOs to implement the filtering condition for data points. We believe that our approach is much simpler in terms of thcoretical analysis and practical implementation. Empirically, we observe that Falconn++ with practical add-ons provides higher search recall than the corresponding instantiation of the theoretical LSF frameworks.
3.4 Practical implementation and add-ons of Falconn++
In the previous section, we prove that there exists threshold so that Falconn++ runs faster and uses less indexing space on answering (c,N than Falconn. Since the nearest neighbor distance different from different queries in practice, it difficult to find an optimal for all queries. We simplify the process of selecting f by introducing scaling factor 0 < < to control the fraction of number of points in bucket. In particular, for any bucket of size corresponding to the random vector ri, we keep only the top-(a points x where [x r: is largest. Hence, the total number of points one hash table is scaled to an.
Selecting an a fraction of points in a bucket is similar to selecting different values of I on different density areas. In particular, we tend use larger for large buckets covering dense areas, and a smaller & for small buckets covering sparse areas. This simple scheme can be seen as data-dependent LSF without any training phase.
Multi-probing for indexing: A new add-on. We note that multi-probing is motivated by the observation that randomly perturbing q generates many perturbed objects that tend to be close q and to be hashed into the same bucket with q's nearest neighbors [9]. This observation also true in the reverse case where we perturb q's nearest neighbors form new perturbed objects that tend to be hashed into the q's bucket. Hence, multi-probing can be used for indexing where we hash one point into multiple buckets. However, the downside of this approach is an increase of the table size from n to i irobes n. points where iProbes 2 1 is the number of indexing probes for one data point. Therefore, multi-probing for indexing has not been used in practice.
We note that the key feature of Falconn++ is the capacity to rank and filter out the points in any bucket based their projection values to govern the space complexity. Given this mechanism, Falconn++ can utilize multi-probe indexing to improve the query performance without increasing the indexing space. Particularly, after executing D random projections, buckets corresponding to the top-iProbes random vector r; closest or furthest to x, as shown in Algorithm 1 Since we further scale each bucket by iProbes times, the number of points in table is still on. Empirically, a large iProbes does not improve the performance of Falconn++ since we likely keep points closest to the random vector r,, When q is not close enough to r,, we will get all false positive candidates.
add x into the iProbes
Multi-probing for querying: A new criteria. Among D random vectors, the CEOs property asymptotically holds for the 2sg closest and furthest random vectors to q for a constant so > 0. Hence, +alconn++ can probe up to 2so buckets each table. Unlike Falconn, rank the probing sequences based on |q ral where r; is the random vector corresponding to the probing bucket.
New heuristics makes Falconn++ more efficient. Besides the Structured Spinners (2) that exploit the fast Hadamard transform (FHT) to simulate Gaussian random projections in (Dlog D) time, we propose other heuristics to improve the performance of Falconn++.

---

L 500, g=0.1
1-500 a=0.1
iProbes=1 Probea=3 i iProhes-9
L-250, o=0.
L-250, a=0.2
Time mn5
100, a-0.5
50, os1 (Falconn)
Dot products
L-100, a-0.5
500 es1 (Falconn)
Time ms
Recall 1Probes-1
Recall
Recall
(b) iProbes-1
L-500, ow0.1
Figure 2: The recall-time tradeoff's of Falconn++ with various settings on Glove200.
(1) Centering the data points. We observe that when the data set distribution is skewed on specific area of the sphere, Falconn variants do not perform well. This is because most data points will be hashed into a few buckets. To handle this issue, we center the data set before building the index. Denote by c = >. x:/n the center of X, we map x; + x = X; - c. This mapping can diverge X to the whole sphere and hence increases the performance of Falconn variants. We note that after centering, arg m x q = arg max x' q. Although ||>|| * 1, it does not affect the performance of +alconn++ since the CEOs property holds for the general inner product (20).
(2) Limit scaling. We observe that we do need scale small buckets since they might already contain high quality candidates. While we are scaling the bucket size on I Line 6, Algorithm|] I we keep mar(k: oB/ / /robes)) points. Note that this trick will increase space usage in practice. However, achieves a better recall- seeeed-peedd tradeoff given the same space complexity configuration.
4 Experiment
We implement Falconn and Falconn++ in C++ and compile with g++ -03 -std=c++17 -fopenmp march-native. We conduct experiments Ubuntu 20.04.4 with an AMD Ryzen Threadripper 3970X CPU 2.2 MHz, 128GB of RAM using 64 threads. We present empirical evaluations on top-k NNS to verify our claims, including:
Falconn++ with multi-probe indexing and querying provides higher search recall-speed tradeoffs than FalconnL.bb[ given the same amount of indexing space.
Falconn++ builds index faster and achieves competitive recall-speed tradeoffss compared to HNSW. recent efficient graph-based based solution for ANNS high search recall regimes.
We set k 20 for all experiments. We use the average number of queries per second and Recall @20 to measure recall-speed tradeoffs. A better solution will give the recall- -peed curve towards the top right corner. We conduct experiments on three popular data sets, including Glove200 (n 1, 183, 514, d 200), Glove300 (n 2, 196, 017, d 300), and NYTimes (n 290, 000, d = 256). We extract 1000 points to form the query set. All results are the average runs of the algorithms.
Our implemen- tation uses std: :eccorr to store hash tables and the Eigen library for SIMD vectorization. We use boost: socyyamic_biteee to remove duplicated candidates. For muuti-threading. we add #pragma omp parallel directive on the for loop over 1000 queries. Compared the released FalconnLib and HnswLib, our implementation is rather straightforward and lacks many optimized routines, such as prefetching instructions, optimized multi-threading primitives, and other hardware-speciffe optimizations. Given the same configuration, our Falconn's 's indexing time is 3 times slower than FalconnLib. Though Falconn++ still provides higher search-recall tradeoffs than these two highly optimized libraries, we believe there are rooms to engineer Falconn++ for further improvements.
A note on our implementation /https://githieii
Falconn++ and FalconnL.ib parameter settings. FalconnLib uses the number of bits to control the number of buckets in hash table, which implicitly governs the number of concatenating hash functions l. In the experiment, our Falconn and Falconn++ use ( and explicitly set the number of buckets via the number of random projections D. Since each hash function returns 2D different hash
We use the latest version 1.3.1 3 from http:/ghhaaccm//AA...oonIIAAAAA We use the released version on Dee 28, 2021 from http://githhh..com//mssi/////// https://eigen..uxfaaii...
7

---

Heshing Procinn Lookup
Falconnes canterFalconn Falconn
Distance
Cualios per 500
SPabbes 6.50
Otherss
Dot
Caaa Times in mis
1000
sPrdeee 5000
chrdee 4003
Falconn
Recall Speed-reese tradeaft
Recal Dat products recult tradectt
Fal.
contorFal.
Fall-
Query time components
Figure 3: The performance of Falconn++ (L 500, 0.1, irobes 3) with new heuristics and
its query cost components.
values, Falconn++ has 4D buckets on a hash table. For example, on Glove200 where d = 200, the setting D 256 2 of Falconn++ leads to the suggested configuration of FalconnLib using 18 bits. Regarding the indexing space, both Falconn++ and Falconn use roughly the same memory footprint contain the same number of points in a hash table.
4.1 An ablation study on Glove200
This subsection measures the performance of our implemented Falconn++ and Falconn. We show the advantage of functionalities of Falconn++, including multi-pros mulli-probe indexing and proposed heuristics for improving the recall-time time tradeoff.
conduct the experiments on Glove200 using 64 threads. Both Falconn variants use D 256. To have the same indexing space, Falconn uses L hash tables and Falconn++ uses L/a where a is scaling factor. Falconn+ with index probing iProbes uses L/(a iProbes). Note that Falconn is Falconn++ with iProbes 1,
Falconn++ with multi-probing Figure 2 shows the recall-time tradeoff's of Falconn++ with various settings of L. and such that the total number of points in all tables is onL. Falconn uses q gProbes= 11000.... 10000) and Falconn++ uses g gProbes/ a to have a similar number of candidates.
Without index probing, i.c. iProbes = 1, Figure 2a shows that Falconn++ has lower query time than Falconn given the same recall rate. Falconn++ achieves better recall-time tradeoff's when is smaller. 2p explains the superiority of Falconn++. Given q &Probes/ a probes, smallest candidate sizes for the same recall though Falconn++'s indexing time is increased by 1/a.
0.1 leads to the
With the index probing, Falconn++ with L = 500, a 0.1 improves the performance with iProbes = 3 in Figure Zc. Larger iProbes values are not helpful since Falconn++ tends to keep points closest or furthest to the random vectors only.
Falconn++ with heuristics. Figure 3 shows the performance of Falconn++ with the centering and limit scaling heuristics. Given
500, a = 0.1, iProbes = 3. the limit scaling that keeps mar(k, aB/ /iPoobes) points in any bucket increases the number of points in a table from 0.1n to 2.42n points. This because many empty or small buckets tend to contain more points (up to k = 20) with index probing. However, such increased number of points in table pay off. Each bucket has sufficient high quality candidates and hence we do not need large q Probes to get high recalls. In this case, one hash table of +alcomn++ can be
"merged version" of 3 hash tables of Falconn.
Figure 3 shows the recall-speed comparison between Falconn++ with centering and limit scaling heuristics and Falconn variants given the same 2.42 nz points in the index. Though Falconn with the centering hcuristic achieves higher tradcoffs than standard Falconn, both of them with = 1210 tables inferior to Falconn++. Figure 3 shows that the centering heuristic provides better candidates as Falconn++ and centering Falconn use a similar number of inner product computations to achieve the same recall. Figure 3e shows the query time breakdown components. Since Falconn+ uses less and qProbes, it has less hashing and probing time and hence less total query time compared to the centering Falconn given the same 95% recall ratio.
Falconn++ parameter settings. Falconn++ has several parameters, including L, D, i iProbes, a, gProbes. Since increasing i iProbes will degrade the performance (see Figure 2 we need i irobes large enough to ensure that each bucket has approximately & candidates. Note that Falconn+ uses 2 LSH functions and hence has 2 buckets. With index probing, expect the number
8

---

Falconn conter FalconnLib
Falconn++
Falcorme+
center FalconnLib FalconnLib
Our Falconn
FalconnLib
a Querr ress per 580
Cluer fess per S8C
Qusrris par
Recall
Recell
(a) NYTimes
(b) Glove300
(6) Glove200
Figure 4: The recall-speed comparison between Falconn++ and FalconnLib on 3 data sets.
of points a table, i.e. n iProbes, will be distributed uniformly into 4D buckets and each bucket has iPProess/aa /422 points in expectation. We heuristically select iProbes and D such that & R n iProbes/ D For instance, on Glove200: n = 1M, D 256, 20, choice of i iProbes = 3, D 256 leads to 1M 3//2 2 16 k 20 points in bucket in expectation. and a depend on the available memory footprint, and q Probes depends on the required recall ratio.
4.2 Comparison between Falconn++ and FalconnLib
This subsection compares our implemented Falconn++ with the released FalconnLib 2 given the same number of points in the index. Since FalconnLib does not support multi-threading for querying, Falconn++ uses thread for a sake comparison.
Falconn++ uses = 50, a = 0.1, iProbes = 10 on NYTimes, L 500, a = 0.1, iProbes = on Glove300, and L = 500,
0.1, iPobee 3 on Glove200. iProbes are set based the above heuristic. For each data set, FalconnLib uses the corresponding scaled tables I, = {200, 50, 1210). respectively, ensure the bits for the corresponding data sets to yield the highest performance. For Falconn++, we set D {128, 256, 256} accordingly. For all approaches, we select qProbes {1000, 20000}.
space usage. We observe that FalconnLib needs {16, 18, 18)
Figure f shows recall-speed comparison between Falconn++ and FalconnLib on these data sets. Since the center e R 0 on NYTimes, the centering trick is not necessary. Instead, we plot our own implemented Falconn, which has lower recall-speed tradcoffs than FalconnLib. This again shows that our implementation is not well-optimized. Nevertheless, Falconn++ shows superior performance compared to FalconnLib on the 3 data sets. The significant improvement is from Glove300 and Glove200 where Falconn++ gains substantial advantages from better quality candidates and less number query probes.
4.3 Comparison between Falconn++ and HNSW on high search recall regimes
This subsection compares Falconn++ with the released HnswLib (16), and kniss-Hnsw [14 highly op- timized libraries for ANNS using 64 threads. HNSW has two parameters to control the indexing space and time, including e inder and M. We set _indeer 200 and use M (1024, 512, 512] for NYTimes, Glove300, and Glove200, respectively, to achieve high recalls with fast query time. Falconn++ uses 500, a 0.01, iProbes 10 on NYTimes, on Glove300. L = 350, 0.01, Probes 3 on Glove200 to have the same space as HNSW.
900. a 0.01, &Pobes
Figure 5 shows the recall-speed tradeoff's of Falconn++ and HNSW libraries using 1 and 64 threads on NYTimes and Glove200. Falconn++ uses &Probes = {1000,..- 20000} and HNSW sets ef eu_eur {100.... ... 2000). Though Falconn++ not competitive with HnswLib, it outperforms Faiss-Hnsw with thread at the recall of 97%. With 64 threads, Falconn+ surpasses both HnswLib and Faiss-Hnsw from recall ratios of 0.97 and 0.94, respectively, on both data sets.
We observe that the speedup of Falconn+ comes from its simplicity and scalability on multi- threading CPUs. Table that Falconn++ achieves higher threading scales than both HnswLib and Haiss-Hnsw when increasing the number threads on NYTimes and Glove200. Both HNSW libraries suffer sufficiently suboptimal scales when the number of threads is larger than 16.
T the recall-speed comparison between Falconn++,, HnswLib, and brute force with the above parameter settings. Falconn++ provides higher recall-speed tradcoff' than HnswLib when

---

Rocall
NYTimes,
Ihread
(b) NYTimee, Fioedd
10) Glove200 Uhread
(6) Glove200 threads
Figure 5: The recall-speed comparison between Falconn++,, Faiss- and HnswLib on thread and 64 threads.
Falconne+
000
Hnsw
@Cuaries per
Queries per sec
100
1:3
Querles
F Falconn++
8
Falconn++
8
BF
BF
07
Recall
Recall Glove300
Recall
(a) NYTimes
Glove200
Figure 6: The recall-speed comparison between Falconn++ and HnswLib data sets.
the recall is least 97% the data sets. Regarding the indexing space, they nearly the same amount of RAM, as shown Table 2 However, Falconn++ builds indexes at least 5 times faster than HNSW and hence can be better for streaming ANNS applications (33
Due to the space limit, we present the comparison of recall-speed tradeoffs between Falconn++, the theoretical LSF frameworks, and other competitive ANNS solvers in the supplementary materials.
5 Conclusion
We present Falconn++, practical locality-sensitive filtering scheme for ANNS angular distance. Theoretically, Falconn++ asymptotically has lower query time complexity than Falconn, an optimal LSH scheme. Though our implementation of Falconn++ lacks many optimized routines, Falconn+ with several heuristic add-ons gives higher secall-speed tradeoff's than Falconn. It is also competitive with HNSW, an efficient representative of graph-based solutions high search recall regimes.
Table The average scale of Falconn++, Faiss-Hnsw, and HnswLib on different number of threads on NYTimes. Similar suboptimal scales of Hnsw libraries are also observed on Glove200.
Threads
16
32
64
HnswLib
1.9
3.6
6.2
10.0
10.3
10.5
Faiss-Hnsw
3.7
6.9
10.9
14.6
15.1
Falconn++
1.9
3.7
6.4
11.4
18.5
24.8
Table Indexing space and time comparison between Falconn++ and HNSW on data sets.
NYTimes
Glove300
Glove200
Algorithms
Space
Time
Space
Time
Space
Time
Hnsw
2.5 GB
7.8 mins
10.9 GB
26.7 mins
5,4 GB
13.7 mins
Falconn++
GB
0.6 mins
10.8 GB
5.4 mins
5.3 GB
1.1 mins
10

---

References
[1] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS, pages 459-468, 2006.
[2] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, llya Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. In NIPS, pages 1225-1233, 2015.
[3] Alexandr Andoni, Piotr Indyk, and Ilya P. Razenshteyn. Approximate nearest neighbor search in high dimensions. CoRR, abs/ 10211806.9990 09823, 2018.
[4] Alexandr Andoni, Thijs Laarhoven, Ily P. Razenshteyn, and Erik Waingarten. Optimal hashing- based time-space trade-offs for approximate near neighbors. In SODA, pages 47-66, 2017.
[5] Alexandr Andoni and Ilya P. Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In STOC, pages 793-801, 2015.
[6] Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst., 87, 2020.
[7] George H. Chen and Devavrat Shah. Explaining the success of nearest neighbor methods in prediction. Found. Trends Mach. Learn., 10(5-6):337-588, 2018.
[8] Tobias Christiani. A framework for similarity search with space-time tradeoffss using locality- sensitive filtering. In SODA, pages 31-46, 2017.
[9] H. A. David and Galambos. The asymptotic theory of concomitants of order statistics. Journal of Applied Probability, 11(4):762-770, 1974.
[10] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 8(1):321-350, 2012.
[11] Monika Rauch Henzinger. Finding near-duplicate web pages: large-scale evaluation of algorithms. SIGIR, pages 284-291, 2006.
[12] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Comput. Syst. Sci., 63(4), 2001.
[13] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pages 604-613, 1998.
[14] Faiss Library. Faiss. https:/ffaiss.ai/
[15] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH:: efficient indexing for high-dimensional similarity search. In VLDB, pages 950-961, 2007.
[16] 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, 42(4):824-836, 2018.
[17] Marvin Minsky and Seymour A Papert. Perceptrons: An introduction computational geometry. MIT press, 1969.
[18] Ryan O'Donnell, Yi Wu, and Yuan Zhou. Optimal lower bounds for locality hashing (except when q is tiny). ACM Trans. Comput. Theory, 6(1):5:1-5:13, 2014.
[19] Rina Panigrahy, Entropy based nearest neighbor search in high dimensions. In SODA, pages 1186-1195, 2006.
[20] Ninh Pham. Simple yet efficient algorithms for maximum inner product search via extreme order statistics. In KDD,, pages 1339-1347, 2021.
[21] Badrul Munir Sarwar, George Karypis, Joseph A. Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In WWW, pages 285-295, 2001.

---

[22] Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-neighbor methods in learning and vision. IEEE Trans. Neural Networks, 19(2):777, 2008.
[23] Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish, Todd Mostak, Piotr Indyk. Samuel Madden, and Pradeep Dubey. Streaming similarity search over one billion tweets using parallel locality-sensitive hashing. PVLDB, 6 6(14):1930-19) 2013.
[24] Roger Weber, Hans-Jörg Schek, and Stephen Blott. quantitative analysis and performance study for similarity-sean search methods in Sigh-dimessionl spaces. In VLDB, pages 194-205, 1998.
[25] Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In SODA, pages 1867-1877, 2014.
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] See Section 3 for theoretical results and Section 5 for empirical results.
(b) Did you describe the limitations of your work? [Yes] Currently, our implementaion of Falconn++ is not optimized compared to other competitors, especially HNSW. We plan to integrate our work into the released FalconnLib to utilize its optimized routines. Another issue is the increase of indexing time of Falconn++. However, it just takes few minutes to build the index compared to a half of hour of HNSW on Glove300.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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 theoretical results? [Yes] The asymptotic results of both Falconn and Falconn++ require sufficiently large D) random vectors.
Indeed, Falconn++ built on the CEOs property that requires - co. Nevertheless, observe that D > 100 works very well in practice.
(b) Did you include complete proofs of all theoretical results? [Yes] Please see the supplementary material for the detailed proof of the main theorem.
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 or as URL)? [Yes] Please see the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [No] We do not use any training phase.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] The recall-speed deviations of studied algorithms are very tiny. Hence, we do not report them.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Please see Section 4.
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 used the released FalconnLib and HnswLib, and public data sets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [Ys]]
Falconn+ implementation is htttt:://// /ttp://///tttbbb/// www.Ninhhha...mmmmmmmmmmmm FaanaPaamaFlllaa Faam connLSF Ponppo/asaa//nlonnFSF
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
12

---

(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, 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": "z_mAxrU3Ky", "reviewer": "Reviewer_spwu", "summary": "This paper investigated a fundamental problem of approximate nearest neighbor search on angular distance. The authors developed a practical LSF approach called Falconn++ that combines the LSF property with the LSH to achieve a lower query time complexity beyond the vanilla LSH schemes such as Falconn. Extensive experiments validated the superior performance of Falconn++.\n", "questions": "Q1. Followed by W1, can they conduct more experiments for parameter settings? Or provide more theoretical (or empirical) analysis for the impact of the parameters. \n\nQ2. Followed by W2, can they compare Falconn++ with FalconnLib and HNSW for different values of k (e.g., from 1 to 100)? \n\nQ3. Can they discuss the possibility of extending the pattern of LSF + LSH to support the ANNS on other similarity/distance measures? ", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nS1. The pattern of LSF + LSH is very interesting to me. Even though the two key components (i.e., CEO and Falconn) of Falconn++ come from existing work, they discover a promising way to combine them together and provide a comprehensive theoretical analysis.  \n\nS2. They conducted a systematic comparison of Falconn++ with Falconn and HNSW. Extensive results justify their theoretical analysis and validate the superior performance of Falconn++.\n\nS3. The paper is well organized and easy to follow.\n\nWeaknesses\n\nW1. The proposed Falconn++ contains many parameters, such as D, L, $\\alpha$, iProbes, qProbes. In the experiments (Subsections 4.2 and 4.3), they config different values of L, $\\alpha$, iProbes for Falconn++ when comparing with different methods even for the same datasets. Thus, it might be more comprehensive and beneficial for practitioners if they could make a discussion for the parameter settings. \n\nW2. The experiments might be more convincing if they could study the sensitivity of k for Falconn++. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "d8VDGTXLud1", "reviewer": "Reviewer_1qZS", "summary": "The author proposed a locality-sensitive filtering approach with an asymptotically lower query time algorithm than Falconn and competitive to efficient indices like HNSW. Falconn++ keeps only the top-($\\alpha B/iProbes$) points (closest to the hyperplane $r_i$) in each bucket. The closeness is defined by the threshold on the inner product distance $t = (1 − r 2 /2) 2 log D$, from the $r_i$. A limit scaling strategy is added for more balanced buckets and higher query-recall performance.", "questions": "Questions:\n1) Where are the significant query time improvements (empirical) coming from compared to Falconnlib? Is it due to filtered far-away points in buckets or the heuristics? \n2) I am not able to locate the metric. Everywhere it is mentioned as a recall. Is it Recallk@k where k is 20 or something else?\n3) How does Falconn++ compares with Fast cross polytope LSH*?\n\n*Kennedy, Christopher, and Rachel Ward. \"Fast cross-polytope locality-sensitive hashing.\" arXiv preprint arXiv:1602.06922 (2016).", "limitations": "The authors have addressed their work's limitations and potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1) Theoretical analysis is adequate and conveys the proposed approach's correctness.\n\n2) The paper is well written. The preliminary ideas and the state of art methods are thoroughly discussed.\n\n3) Experiments with SOTA ANN approaches: The work has compared Falconn++ with Falconnlib, HNSW, FAISS, ScANN, and coCEOs over Million scale datasets. Falconn++ beats these state-of-the-art approaches in the high recall region.\n\n4) New heuristics have shown improvement over the proposed LSF approach.\n\nWeakness\n\n1) It is great to see the comment on the comparison with other LSFs[4][8].  It will be good to see the experimental comparison as well for thorough evaluation. (citations from the paper)\n\n2) No performance evaluation in lower recall regime- especially for HNSW and ScANN; however, comparison with coCEOs covers almost the entire spectrum. ScANN is really good in the high recall region, and it is great to see that Falconn++ is very close to it and even beats it on smaller-scale datasets. However, it will be helpful to analyze how Falconn++ performs against them in the mid-recall region (0.5-0.8), as the near neighbors in mid-recall are also useful for many practical search systems. Same argument for FAISS and HNSW. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5DJAVbprO8I", "reviewer": "Reviewer_y5Sd", "summary": "The paper proposes an interesting extension of the special LSH scheme for angular distance (and cosine similarity) nearest neighbor search. Specifically it proposes a filtering mechanism and proves that it leads to asymptotically better retrieval times. Empirically, the approach is competitive with the graph-based retrieval algorithm HNSW for high recall values. \n\nNearest neighbor search is a backbone of many recommender and retrieval systems. Clearly, it is important to be able to do this task well. There has been historically a competition of several approaches including LSH, randomized trees, quantization approaches, and graph-based retrieval methods with sometimes comparable outcomes. It has been a useful competition, because different methods have different strengths and applicability. In my opinion, this is an important line of research.\n\nThe paper proposes an interesting trick to index-time filtering of unpromising data points. This is possible, because the inner product between a bucket \"pivot\" and a query is quite close to the *SCALED* inner product between the query and data points in a bucket (BTW it's nice to point out that scaling arises from the fact that data/query are normalized but \"pivot\"/sampled vectors are not). Authors further show this property can be exploited both theoretically and practically to improve upon FALCON.\n\nIn terms of theory, they show it for a c-approximate nearest neighbor search. For practical purposes, one has to resort to theory-inspired heuristics. I think it's totally fine, but the paper should be clear about it. \n\nEmpirically, the method improves upon the original FALCON and claims to be comparable to HNSW, but only in high-recall zone when the number of threads are large. Although this was not in the original version of the paper, additional experiments revealed that HNSW implementations seems to scale poorly with the number of threads, at least for the specific architecture used in the paper.\n\nSo, potentially HNSW can work better, but we don't know this for sure. This is unfortunate, but resolving this issue may require a separate paper. I personally think that the most important baseline in this work is FALCON. Plus, if the approach is more scalable (with the number of threads), this is certainly a plus.\n", "questions": "**Some detailed comments:**\n\n25-27, please give a clearer definition of a decision version of the problem.\n\n34 citation is needed.\n\n45-46 not only that but old-style random-projection LSH often performs no better than a VP-tree modified for approximate search. They are also typically outperformed by random-projection trees. If I remember correctly authors of FLANN have some comparison points.\n\n123-124 how is it different from the original FALCON ordering of buckets in line 115? In lines 234-237 you remove the absolute value, is this actually the difference?\n\n126 a significantly large NUMBER of vectors ??? Same issue in line 169.\n\n127 Eq (3) can possibly be accurate for x == q, because we get zero variance. I guess it should have some error term diminishing with D.   \n\nAlso lines 128-129 We can see that, among D random vectors, if r1 is closest (or furthest) to q, then the projection values of *ALL* points in X preserves their inner product order expectation -> I feel this is a very inaccurate description. First of all, the equation doesn't say anything about expectation of *ALL* points. It does say that the distance is preserved with a high probability P for a given pair of points. If you have three points, the full order preservation is going to be only P^2, etc... for a large enough set it's going to be close to zero IMHO. However, I believe the expected number of preserved distances should be high.\n\n135-143 This is confusing. If the filtering heuristic is used at indexing time, it is not related to multi-probing. It should improve performance of a regular single-probe LSH as well, because unlikely candidates are going to be pruned. \n\n173-174  If this is index-time filtering why does it depend on the query q? I think I understand what you are talking about, but some explanation won't harm. \n\n241 The centering approach is not new and it was in fact used in FALCON when FALCON was still present in ANN-BENCHMARK. Please, see, e.g., the code here:\n\nhttps://github.com/erikbern/ann-benchmarks/blob/406574ef659338accb6a926a097099c1691ef8f3/ann_benchmarks/algorithms/falconn.py#L29\n\n\n", "limitations": "1. negative societal impact discussion isn't really applicable.\n2. authors discuss limitations of their implementation as well as limitations of approximate nearest neighbor search in general.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n1. The paper is a bit messy and many explanations are confusing. Although with some effort the paper is understandable, but the presentation can be improved substantially.\n2. The centering trick is NOT NEW and it was used in FALCON when it was incorporated into ANN BENCHMARKS. Please see a reference below. \n\nGenerally, math makes sense to me, but I did not check very fine details. In particular, I have to trust the derivation of the Eq. (3) from prior work, but I haven't checked this derivation myself.\n\nhttps://github.com/erikbern/ann-benchmarks/blob/406574ef659338accb6a926a097099c1691ef8f3/ann_benchmarks/algorithms/falconn.py#L29\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept