Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search
Tobias Christiani


Reinforcement Mechanism Design for e-commerce
    Yiwei Zhang
    December 30, 2023
=============================================




The Indyk-Motwani Locality-Sensitive Hashing (LSH) framework (STOC 1998) is a general technique for constructing a data structure to answer approximate near neighbor queries by using a distribution  over locality-sensitive hash functions that partition space.
For a collection of n points, after preprocessing, the query time is dominated by O(n^ρlog n) evaluations of hash functions from  and O(n^ρ) hash table lookups and distance computations where ρ∈ (0,1) is determined by the locality-sensitivity properties of . 
It follows from a recent result by Dahlgaard et al. (FOCS 2017) that the number of locality-sensitive hash functions can be reduced to O(log^2 n), leaving the query time to be dominated by O(n^ρ) distance computations and O(n^ρlog n) additional word-RAM operations.
We state this result as a general framework and provide a simpler analysis showing that the number of lookups and distance computations closely match the Indyk-Motwani framework, making it a viable replacement in practice. 
Using ideas from another locality-sensitive hashing framework by Andoni and Indyk (SODA 2006) we are able to reduce the number of additional word-RAM operations to O(n^ρ).




§ INTRODUCTION


The approximate near neighbor problem is the problem of preprocessing a collection P of n points in a space (X, ) into a data structure such that, for parameters r_1 < r_2 and given a query point q ∈ X, if there exists a point x ∈ P with (q, x) ≤ r_1, then the data structure is guaranteed to return a point x' ∈ P such that (q, x') < r_2.

Indyk and Motwani <cit.> introduced a general framework for constructing solutions to the approximate near neighbor problem using a technique known as locality-sensitive hashing (LSH). 
The framework takes a distribution over hash functions  with the property that near points are more likely to collide under a random h ∼. 
During preprocessing a number of locality-sensitive hash functions are sampled from  and used to hash the points of P into buckets. 
The query algorithm evaluates the same hash functions on the query point and looks into the associated buckets to find an approximate near neighbor.

The locality-sensitive hashing framework of Indyk and Motwani has had a large impact in both theory and practice (see surveys <cit.> and <cit.> for an introduction), and many of the best known solutions to the approximate near neighbor problem in high-dimensional spaces, such as Euclidean space <cit.>, the unit sphere under inner product similarity <cit.>, and sets under Jaccard similarity <cit.> come in the form of families of locality-sensitive hash functions that can be plugged into the Indyk-Motwani LSH framework. 


Let (X, ) be a distance space and let  be a distribution over functions h  X → R.
We say that  is (r_1, r_2, p_1, p_2)-sensitive if for x, y ∈ X and h ∼ we have that:


  * If (x, y) ≤ r_1 then [h(x) = h(y)] ≥ p_1.

  * If (x, y) ≥ r_2 then [h(x) = h(y)] ≤ p_2.



The Indyk-Motwani framework takes a (r_1, r_2, p_1, p_2)-sensitive family  and constructs a data structure that solves the approximate near neighbor problem for parameters r_1 < r_2 with some positive constant probability of success. 
We will refer to this randomized approximate version of the near neighbor problem as the (r_1, r_2)-near neighbor problem, where we require queries to succeed with probability at least 1/2 (see Definition <ref>).  
To simplify the exposition we will assume throughout the introduction, unless otherwise stated, that 0 < p_1 < p_2 < 1 are constant, that a hash function h ∈ can be stored in n / log n words of space, and for ρ = log(1/p_1) / log(1/p_2) ∈ (0,1) that a point x ∈ X can be stored in O(n^ρ) words of space.
The assumption of a constant gap between p_1 and p_2 allows us to avoid performing distance computations by instead using the 1-bit sketching scheme of Li and König <cit.> together with the family  to approximate distances (see Section <ref> for details).
In the remaining part of the paper we will state our results without any such assumptions to ensure, for example, that our results hold in the important case where p_1, p_2 may depend on n or the dimensionality of the space <cit.>.  


Let  be (r_1, r_2, p_1, p_2)-sensitive and let ρ = log(1/p_1)/log(1/p_2), then there exists a solution to the (r_1, r_2)-near neighbor problem using O(n^1+ρ) words of space and with query time dominated by O(n^ρlog n) evaluations of functions from .


The query time of the Indyk-Motwani framework is dominated by the number of evaluations of locality-sensitive hash functions. 
To make matters worse, almost all of the best known and most widely used locality-sensitive families have an evalution time that is at least linear in the dimensionality of the underlying space <cit.>.
Significant effort has been devoted to the problem of reducing the evaluation complexity of locality-sensitive hash families <cit.>, while the question of how many independent locality-sensitive hash functions are actually needed to solve the (r_1, r_2)-near neighbor problem has received relatively little attention <cit.>.  

This paper aims to bring attention to, strengthen, generalize, and simplify results that reduce the number of locality-sensitive hash functions used to solve the (r_1, r_2)-near neighbor problem. In particular, we will extract a general framework from a technique introduced by Dahlgaard et al. <cit.> in the context of set similarity search under Jaccard similarity, showing that the number of locality-sensitive hash functions can be reduced to O(log^2 n) in general. 
We further show how to reduce the word-RAM complexity of the general framework from O(n^ρlog n) to O(n^ρ) by combining techniques from Dahlgaard et al. and Andoni and Indyk <cit.>.
Reducing the number of locality-sensitive hash functions allows us to spend time O(n^ρ / log^2 n) per hash function evaluation without increasing the overall complexity of the query algorithm — something which is particularly useful in Euclidean space where the best known LSH upper bounds offer a tradeoff between the ρ-value that can be achieved and the evaluation complexity of the locality-sensitive hash function <cit.>.



 §.§ Related work




    Indyk-Motwani.

The Indyk-Motwani framework uses L = O(n^ρ) independent partitions of space, each formed by overlaying k = O(log n) random partitions induced by k random hash functions from a locality-sensitive family .
The parameter k is chosen such that a random partition has the property that a pair of points x,y ∈ X with (x, y) ≤ r_1 has probability n^-ρ of ending up in the same part of the partition, while a pair of points with (x, y) ≥ r_2 has probability n^-1 of colliding. 
By randomly sampling L = O(n^ρ) such partitions we are able to guarantee that a pair of near points will collide with constant probability in at least one of them. 
Applying these L partitions to our collection of data points P and storing the result of each partition of P in a hash table we obtain a data structure that solves the (r_1, r_2)-near neighbor problem as outlined in Theorem <ref> above. 
Section <ref> and <ref> contains a more complete description of LSH-based frameworks and the Indyk-Motwani framework.



    Andoni-Indyk.

As previously mentioned, many locality-sensitive hash functions happen to have a super-constant evaluation time. 
This motivated Andoni and Indyk to introduce a replacement to the Indyk-Motwani framework in a paper on substring near neighbor search <cit.>.  
The key idea is to re-use hash functions from a small collection of size m ≪ L by forming all combinations of mt hash functions. 
This technique is also known as tensoring and has seen some use in the work on alternative solutions to the approximate near neighbor problem, in particular the work on locality-sensitive filtering <cit.>.
By applying the tensoring technique the Andoni-Indyk framework reduces the number of hash functions to O(exp(√(ρlog n loglog n))) = n^o(1) as stated in Theorem <ref>.


	Let  be (r_1, r_2, p_1, p_2)-sensitive and let ρ = log(1/p_1)/log(1/p_2), then there exists a solution to the (r_1, r_2)-near neighbor problem using O(n^1+ρ) words of space and with query time dominated by O(exp(√(ρlog n loglog n))) evaluations of functions from  and O(n^ρ) other word-RAM operations.



The paper by Andoni and Indyk did not state this result explicitly as a theorem in the same form as the Indyk-Motwani framework; the analysis made some implicit restrictive assumptions on p_1, p_2 and ignored integer constraints. 
Perhaps for these reasons the result does not appear to have received much attention, although it has seen some limited use in practice <cit.>.
In Section <ref> we present a slightly different version of the Andoni-Indyk framework together with an analysis that satisfies integer constraints, providing a more accurate assessment of the performance of the framework in the general, unrestricted case.   



    Dahlgaard-Knudsen-Throup.

The paper by Dahlgaard et al. <cit.> introduced a different technique for constructing the L hash functions/partitions from a smaller collection of m hash functions from . 
Instead of forming all combinations of subsets of size t as the Andoni-Indyk framework they instead sample k hash functions from the collection to form each of the L partitions.
The paper focused on a particular application to set similarity search under Jaccard similarity, and stated the result in terms of a solution to this problem. 
In Section <ref> we provide a simplified and tighter analysis to yield a general framework:


	Let  be (r_1, r_2, p_1, p_2)-sensitive and let ρ = log(1/p_1)/log(1/p_2), then there exists a solution to the (r_1, r_2)-near neighbor problem using O(n^1+ρ) words of space and with query time dominated by O(log^2 n) evaluations of functions from  and O(n^ρlog n) other word-RAM operations.


The analysis of <cit.> indicates that the Dahlgaard-Knudsen-Thorup framework, when compared to the Indyk-Motwani framework, would use at least 50 times as many partitions (and a corresponding increase in the number of hash table lookups and distance computations) to solve the (r_1, r_2)-near neighbor problem with success probability at least 1/2. 
Using elementary tools, the analysis in this paper shows that we only have to use twice as many partitions as the Indyk-Motwani framework to obtain the same guarantee of success.



    Number of hash functions in practice.

To provide some idea of what the number of hash functions H used by the different frameworks would be in practice, Figure <ref> shows the value of log_2 H that is obtained by actual implementations of the Indyk-Motwani (IM), Andoni-Indyk (AI), and Dahlgaard-Knudsen-Thorup (DKT) frameworks according to the analysis in Section <ref> for p_1 = 1/2 and every value of 0 < p_2 < 1/2 for a solution to the (r_1, r_2)-near neighbor problem on a collection of n = 2^30 points.

Figure <ref> reveals that the number of hash functions used by the Indyk-Motwani framework exceeds 2^30, the size of the collection of points P, as p_2 approaches p_1. 
In addition, locality-sensitive hash functions used in practice such as Charikar's SimHash <cit.> and p-stable LSH <cit.> have evaluation time O(d) for points in ℝ^d. 
These two factors might help explain why a linear scan over sketches of the entire collection of points is a popular approach to solve the approximate near neighbor problem in practice <cit.>.
The Andoni-Indyk framework reduces the number of hash functions by several orders of magnitude, and the Dahlgaard-Knudsen-Thorup framework presents another improvement of several orders of magnitude. 
Since the word-RAM complexity of the DKT framework matches the the number of hash functions used by the IM framework, the gap between the solid line (DKT) and the dotted line (IM) gives some indication of the time we can spend on evaluating a single hash function in the DKT framework without suffering a noticeable increase in the query time. 



 §.§ Contribution




    Improved word-RAM complexity.

In addition to our work on the Andoni-Indyk and Dahlgaard-Knudsen-Thorup frameworks as mentioned above, we show how the word-RAM complexity of the DKT framework can be reduced by a logarithmic factor. 
The solution is a simple combination of the DKT sampling technique and the AI tensoring technique: 
First we use the DKT sampling technique twice to construct two collections of √(L) partitions.
Then we use the AI tensoring technique to form L = √(L)×√(L) pairs of partitions from the two collections. 
Below we state our main Theorem <ref> in its general form where we make no implicit assumptions about  (p_1 and p_2 are not assumed to be constant and can depend on for example n) or about the complexity of storing a point or a hash function, or computing the distance between pairs of points in the space (X, ).


	Let  be (r_1, r_2, p_1, p_2)-sensitive and let ρ = log(1/p_1) / log(1/p_2), then there exists a solution to the (r_1, r_2)-near neighbor with the following properties:

	
  * The query complexity is dominated by O(log_1/p_2^2(n)/p_1) evaluations of functions from , O(n^ρ) distance computations, and O(n^ρ / p_1) other word-RAM operations.
	
  * The solution uses O(n^1 + ρ /p_1) words of space in addition to the space required to store the data and O(log_1/p_2^2(n)/p_1) functions from .




Under the same simplifying assumptions used in the statements of Theorem <ref>, <ref>, and <ref>, our main Theorem <ref> can be stated as Theorem <ref> with the word-RAM complexity reduced by a logarithmic factor to O(n^ρ). 
This improvement in the word-RAM complexity comes at the cost of a (rather small) constant factor increase in the number of hash functions, lookups, and distance computations compared to the DKT framework.
By varying the size m of the collection of hash functions from  and performing independent repetitions we can obtain a tradeoff between the number of hash functions and the number of lookups.
In Section <ref> we remark on some possible improvements in the case where p_2 is large.



    Distance sketching using LSH.

Finally, we combine Theorem <ref> with the 1-bit sketching scheme of Li and König <cit.> where we use the locality-sensitive hash family to create sketches that allow us to leverage word-level parallelism and avoid direct distance computations. 
This sketching technique is well known and has been used before in combination with LSH-based approximate similarity search <cit.>, but we believe there is some value in the simplicity of the analysis and in a clear statement of the combination of the two results as given in Theorem <ref>, for example in the important case where 0 < p_2 < p_1 < 1 are constant.

	Let  be (r_1, r_2, p_1, p_2)-sensitive and let ρ = log(1/p_1) / log(1/p_2), then there exists a solution to the (r_1, r_2)-near neighbor with the following properties:

	
  * The complexity of the query operation is dominated by O(log^2(n)/(p_1 - p_2)^2) evaluations of hash functions from  and O(n^ρ/(p_1 - p_2)^2) other word-RAM operations.
	
  * The solution uses O(n^1 + ρ/p_1 + n/(p_1 - p_2)^2) words of space in addition to the space required to store the data and O(log^2(n)/(p_1 - p_2)^2) hash functions from .





§ PRELIMINARIES




    Problem and dynamization.

We begin by defining the version of the approximate near neighbor problem that the frameworks presented in this paper will be solving:

Let P ⊆ X be a collection of |P| = n points in a distance space (X, ).
A solution to the (r_1, r_2)-near neighbor problem is a data structure that supports the following query operation:
Given a query point q ∈ X, if there exists a point x ∈ P with (q, x) ≤ r_1, 
then, with probability at least 1/2, return a point x' ∈ P such that (q, x') < r_2.  

We aim for solutions with a failure probability that is upper bounded by 1/2.
The standard trick of using η independent repetitions of the data structure allows us to reduce the probability of failure to 1/2^η.
For the sake of simplicity we restrict our attention to static solutions, meaning that we do not concern ourselves with the complexity of updates to the underlying set P, although it is simple to modify the static solutions presented in this paper to dynamic solutions where the update complexity essentially matches the query complexity <cit.> 



    LSH powering.

The Indyk-Motwani framework and the Andoni-Indyk framework will make use of the following standard powering technique described in the introduction as “overlaying partitions”.
Let k ≥ 1 be an integer and let  denote a locality-sensitive family of hash functions as in Definition <ref>. 
We will use the notation ^k to denote the distribution over functions h'  X → R^k where

    h'(x) = (h_1(x), …, h_k(x))

and h_1, …, h_k are sampled independently at random from .
It is easy to see that ^k is (r_1, r_2, p_1^k, p_2^k)-sensitive.
To deal with some special cases we define ^0 to be the family consisting of a single constant function.



    Model of computation.

We will work in the standard word-RAM model of computation <cit.> with a word length of Θ(log n) bits where n denotes the size of the collection P to be searched in the (r_1, r_2)-near neighbor problem.
During the preprocessing stage of our solutions we will assume access to a source of randomness that allows us to sample independently from a family  and to seed pairwise independent hash functions <cit.>. 
The latter can easily be accomplished by augmenting the model with an instruction that generates a uniformly random word in constant time and using that to seed the tables of a Zobrist hash function <cit.>.



§ FRAMEWORKS




    Overview.

We will describe frameworks that take as input a (r_1, r_2, p_1, p_2)-sensitive family  and a collection P of n points and constructs a data structure that solves the (r_1, r_2)-near neighbor problem.
The frameworks described in this paper all use the same high-level technique of constructing L hash functions g_1,…,g_L that are used to partition space such that a pair of points x, y with (x, y) ≤ r_1 will end up in the same part of one of the L partitions with probability at least 1/2. 
That is, for x, y with (x, y) ≤ r_1 we have that [∃ l ∈ [L]  g_l(x) = g_l(y)] ≥ 1/2 where [L] is used to denote the set {1,2,…,L}.
At the same time we ensure that the expected number of collisions between pairs of points x,y with (x, y) ≥ r_2 is at most one in each partition.



    Preprocessing and queries.

During the preprocessing phase, for each of the L hash functions g_1, …,g_L we compute the partition of the collection of points P induced by g_l and store it in a hash table in the form of key-value pairs (z, { x ∈ P | g_l(x) = z }).
To reduce space usage we store only a single copy of the collection P and store references to P in our L hash tables.
To guarantee lookups in constant time we can use the perfect hashing scheme by Fredman et al. <cit.> to construct our hash tables.
We will assume that hash values z = g_l(x) fit into O(1) words. 
If this is not the case we can use universal hashing <cit.> to operate on fingerprints of the hash values.

We perform a query for a point q as follows: for l = 1, …, L we compute g_l(q), 
retrieve the set of points { x ∈ P | g_l(x) = g_l(q) }, and compute the distance between q and each point in the set.
If we encounter a point x' with (q, x') < r_2 then we return x' and terminate.
If after querying the L sets no such point is encountered we return a special symbol ∅ and terminate.

We will proceed by describing and analyzing the solutions to the (r_1, r_2)-near neighbor problem for different approaches to sampling, storing, and computing the L hash functions g_1, …, g_L, resulting in the different frameworks as mentioned in the introduction.



 §.§ Indyk-Motwani


To solve the (r_1, r_2)-near neighbor problem using the Indyk-Motwani framework we sample L hash functions g_1, …,g_L independently at random from the family ^k where we set k = ⌈log(n) / log(1/p_2) ⌉ and L = ⌈ (ln 2)/p_1^k ⌉.
Correctness of the data structure follows from the observation that the probability that a pair of points x, y with (x,y) ≤ r_1 does not collide under a randomly sampled g_l ∼^k is at most 1 - p_1^k. 
We can therefore upper bound the probability that a near pair of points does not collide under any of the hash functions by (1-p_1^k)^L ≤exp(-p_1^k L) ≤ 1/2 using a standard bound stated as Lemma <ref> in Appendix <ref>.

In the worst case, the query operation computes L hash functions from ^k corresponding to Lk hash functions from . 
For a query point q the expected number of points x' ∈ P with (q, x') ≥ r_2 that collide with q under a randomly sampled g_l ∼^k is at most np_2^k ≤ np_2^log(n) / log (1/p_2) = 1.
It follows from linearity of expectation that the total expected number of distance computations during a query is at most L.
The result is summarized in Theorem <ref> from which the simplified Theorem <ref> follows.

Given a (r_1, r_2, p_1, p_2)-sensitive family  we can construct a data structure that solves the (r_1, r_2)-near neighbor problem such that for
k = ⌈log(n) / log(1/p_2) ⌉ and L = ⌈ (ln 2)/p_1^k ⌉ the data structure has the following properties:


  * The query operation uses at most Lk evaluations of hash functions from , 
	expected L distance computations, and O(Lk) other word-RAM operations.

  * The data structure uses O(nL) words of space in addition to the space required to store the data and Lk hash functions from .


Theorem <ref> gives a bound on the expected number of distance computations while the simplified version stated in Theorem <ref> uses Markov's inequality and independent repetitions to remove the expectation from the bound by treating an excessive number of distance computations as a failure.



 §.§ Andoni-Indyk


In 2006 Andoni and Indyk, as part of a paper on the substring near neighbor problem, introduced an improvement to the Indyk-Motwani framework that reduces the number of locality-sensitive hash functions <cit.>.
Their improvement comes from the use of a technique that we will refer to as tensoring: setting the hash functions g_1, …, g_L to be all t-tuples from a collection of m functions sampled from ^k/t where m ≪ L.
The analysis in <cit.> shows that by setting m = n^ρ/t and repeating the entire scheme t! times, the total number of hash functions can be reduced to O(exp(√(ρlog n loglog n))) when setting t = √(ρlog n/loglog n).
This analysis ignores integer constraints on t, k, and m, and implicitly place restrictions on p_1 and p_2 in relation to n (e.g. 0 < p_2 < p_1 < 1 are constant).
We will introduce a slightly different scheme that takes into account integer constraints and analyze it without restrictions on the properties of .

Assume that we are given a (r_1, r_2, p_1, p_2)-sensitive family .
Let η, t, k_1, k_2, m_1, m_2 be non-negative integer parameters.
Each of the L hash functions g_1, …, g_L will be formed by concatenating one hash function from each of t collections of m_1 hash functions from ^k_1 and concatenating a last hash function from a collection of m_2 hash functions from ^k_2.
We take all m_1^t m_2 hash functions of the above form and repeat η times for a total of L = η m_1^t m_2 hash functions constructed from a total of H = η(m_1 k_1 t + m_2 k_2) hash functions from .
In Appendix <ref> we set parameters, leaving t variable, and provide an analysis of this scheme, showing that L matches the Indyk-Motwani framework bound of O(1/p_1^k) up to a constant where k = ⌈log(n) / log(1/p_2) ⌉ as in Theorem <ref>.



    Setting t.

It remains to show how to set t to obtain a good bound on the number of hash functions H.
Note that in practice we can simply set t = _t H by trying t = 1,…,k. 
If we ignore integer constraints and place certain restrictions of  as in the original tensoring scheme by Andoni and Indyk we want to set t to minimize the expression t^t n^ρ/t. 
This minimum is obtained when setting t such that t^2 log t = ρlog n.
We therefore cannot do much better than setting t = √(ρlog(n) / loglog n) which gives the bound H = O(exp(√(ρlog(n) loglog n))) as shown in <cit.>. 
To allow for easy comparison with the Indyk-Motwani framework without placing restrictions on  we set t = ⌈√(k)⌉, resulting in Theorem <ref>. 

Given a (r_1, r_2, p_1, p_2)-sensitive family  we can construct a data structure that solves the (r_1, r_2)-near neighbor problem such that for k = ⌈log(n) / log(1/p_2) ⌉, H = k(√(k)/p_1)^√(k), and L = ⌈ 1/p_1^k ⌉ the data structure has the following properties:

	
  * The query operation uses O(H) evaluations of functions from , O(L) distance computations, and O(L + H) other word-RAM operations.
	
  * The data structure uses O(nL) words of space in addition to the space required to store the data and O(H) hash functions from .


Thus, compared to the Indyk-Motwani framework we have gone from using O(k(1/p_1)^k) locality-sensitive hash functions to O(k(√(k)/p_1)^√(k)) locality-sensitive hash functions. 
Figure <ref> shows the actual number of hash functions of the revised version of the Andoni-Indyk scheme as analyzed in Appendix <ref> when t is set to minimize H.



 §.§ Dahlgaard-Knudsen-Thorup


In a recent paper Dahlgaard et al. <cit.> introduce a different technique for reducing the number of locality-sensitive hash functions.
The idea is to construct each hash value g_l(x) by sampling and concatenating k hash values from a collection of km pre-computed hash functions from .
Dahlgaard et al. applied this technique to provide a fast solution the the approximate near neighbor problem for sets under Jaccard similarity.
In this paper we use the same technique to derive a general framework solution that works with every family of locality-sensitive hash functions, reducing the number of locality-sensitive hash functions compard to the Indyk-Motwani and Andoni-Indyk frameworks.

Let [n] denote the set of integers {1,2,…,n}.
For i ∈ [k] and j ∈ [m] let h_i,j∼ denote a hash function in our collection.
To sample from the collection we use k pairwise independent hash functions <cit.> of the form f_i  [L] → [m] and set

    g_l(x) = (h_1,f_1(l)(x), …, h_k,f_k(l)(x)).

To show correctness of this scheme we will use make use of an elementary one-sided version of Chebyshev's inequality stating that for a random variable Z with mean μ > 0 and variance σ^2 < ∞ we have that [Z ≤ 0] ≤σ^2 / (μ^2 + σ^2). 
For completeness we have included the proof of this inequality in Lemma <ref> in Appendix <ref>.
We will apply this inequality to lower bound the probability that there are no collisions between close pairs of points.
For two points x and y let Z_l = {g_l(x) = g_l(y)} so that Z = ∑_l = 1^L Z_l denotes the sum of collisions under the L hash functions. 
To apply the inequality we need to derive an expression for the expectation and the variance of the random variable Z.
Let p = _h ∼[h(x) = h(y)] then by linearity of expectation we have that μ = [Z] = L p^k.
To bound σ^2 = [Z^2] - μ^2 we proceed by bounding [Z^2] where we note that Z_l = Π_i = 1^k Y_l, i for Y_l, i = 1{h_i,f_i(l)(x) = h_i,f_i(l)(x)} and make use of the independence between Y_l,i and Y_l', i' for i ≠ i'.

    [Z^2]    = ∑_l, l' ∈ [L] 
     l ≠ l'[Z_l Z_l'] + ∑_l = 1^L [Z_l] 
       = (L^2 - L) [Z_l Z_l'] + μ
       ≤ L^2 [ Π_i = 1^k Y_l, i Y_l', i] + μ
       = L^2 ( [Y_l, i Y_l', i] )^k + μ.

We have that [Y_l, i Y_l', i] = [f_i(l) = f_i(l')] p + [f_i(l) ≠ f_i(l')] p^2 = (1/m)p + (1-1/m)p^2 which follows from the pairwise independence of f_i. 
Let ε > 0 and set m = ⌈1-p_1/p_1k/ln(1+ε)⌉ then for p ≥ p_1 we have that ( [Y_l, i Y_l', i] )^k ≤ (1 + ε)p^2k.
This allows us to bound the variance of Z by σ^2 ≤εμ^2 + μ resulting in the following lower bound on the probability of collision between similar points.

 
For ε > 0 let m ≥⌈1-p_1/p_1k/ln(1+ε)⌉, then for every pair of points x, y with (x, y) ≤ r_1 we have that 

    [∃ l ∈ [L]  g_l(x) = g_l(y)] ≥1 + εμ/1 + (1 + ε)μ.



By setting ε = 1/4 and L = ⌈ (2 ln(2))/p_1^k ⌉ we obtain an upper bound on the failure probability of 1/2.
Setting the size of each of the k collections of pre-computed hash values to m = ⌈ 5k/p_1 ⌉ is sufficient to yield the following solution to the (r_1, r_2)-near neighbor problem where provide exact bounds on the number of lookups L and hash functions H:


Given a (r_1, r_2, p_1, p_2)-sensitive family  we can construct a data structure that solves the (r_1, r_2)-near neighbor problem such that for k = ⌈log(n) / log(1/p_2) ⌉, H = k ⌈ 5k / p_1 ⌉, and L = ⌈ (2 ln(2))/p_1^k ⌉ the data structure has the following properties:


  * The query operation uses at most H evaluations of hash functions from , 
	expected L distance computations, and O(Lk) other word-RAM operations.

  * The data structure uses O(nL) words of space in addition to the space required to store the data and H hash functions from .



Compared to the Indyk-Motwani framework we have reduced the number of locality-sensitive hash functions H from O(k (1/p_1)^k) to O(k^2 / p_1) at the cost of using twice as many lookups. 
To reduce the number of lookups further we can decrease ε and perform several independent repetitions.
This comes at the cost of an increase in the number of hash functions H.



§ REDUCING THE WORD-RAM COMPLEXITY
 

One drawback of the DKT framework is that each hash value g_l(x) still takes O(k) word-RAM operations to compute, even after the underlying locality-sensitive hash functions are known. 
This results in a bound on the total number of additional word-RAM operations of O(Lk).
We show how to combine the DKT universal hashing technique with the AI tensoring technique to ensure that the running time is dominated by O(L) distance computations and O(H) hash function evaluations. 
The idea is to use the DKT scheme to construct two collections of respectively L_1 and L_2 hash functions, and then to use the AI tensoring approach to form g_1, …, g_L as the L = L_1 × L_2 combinations of functions from the two collections.
The number of lookups can be reduced by applying tensoring several times in independent repetitions, but for the sake of simplicity we use a single repetition.
For the usual setting of k = ⌈log(n) / log(1/p_2) ⌉ let k_1 =  ⌈ k/2 ⌉ and k_2 = ⌊ k/2 ⌋.
Set L_1 = ⌈ 6 (1/p_1)^k_1⌉ and L_2 = ⌈ 6 (1/p_1)^k_2⌉.
According to Lemma <ref> if we set ε = 1/6 the success probability of each collection is at least 3/4 and by a union bound the probability that either collection fails to contain a colliding hash function is at most 1/2.
This concludes the proof of our main Theorem <ref>.



 §.§ Sketching


The theorems of the previous section made no assumptions on the word-RAM complexity of distance computations and instead stated the number of distance computations as part of the query complexity. 
We can use a (r_1, r_2, p_1, p_2)-sensitive family  to create sketches that allows us to efficiently approximate the distance between pairs of points, provided that the gap between p_1 and p_2 is sufficiently large. 
In this section we will re-state the results of Theorem <ref> when applying the family  to create sketches using the 1-bit sketching scheme of Li and König <cit.>.
Let b be a positive integer denoting the length of the sketches in bits.
The advantage of this scheme is that we can use word level parallelism to evaluate a sketch of b bits in time O(b/log n) in our word-RAM model with word length Θ(log n). 

For i = 1, …, b let h_i  X → R denote a randomly sampled locality-sensitive hash function from  and let f_i  R →{0,1} denote a randomly sampled universal hash function.
We let s(x) ∈{0,1}^b denote the sketch of a point x ∈ X where we set the ith bit of the sketch s(x)_i = f_i(h(x)).
For two points x, y ∈ X the probability that they agree on the ith bit is 1 if the points collide under h_i and 1/2 otherwise. 

    [s(x)_i = s(y)_i] = [h_i(x) = h_i(y)] + (1 - [h_i(x) = h_i(y)])/2 = (1 + [h_i(x) = h_i(y)])/2.

We will apply these sketches during our query procedure instead of direct distance computations when searching through the points in the L buckets, comparing them to our query point q.
Let λ∈ (0,1) be a parameter that will determine whether we report a point or not.
For sketches of length b we will return a point x if s(q) - s(x)_1 > λ b.
An application of Hoeffiding's inequality gives us the following properties of the sketch:

	Let  be a (r_1, r_2, p_1, p_2)-sensitive family and let λ = (1+p_2)/2 + (p_1-p_2)/4, 
	then for sketches of length b ≥ 1 and for every pair points x, y ∈ X:  
	
		
  * If (x ,y) ≤ r_1 then [s(x) - s(y)_1 ≤λ b] ≤ e^b(p_1 - p_2)^2 / 8.
		
  * If (x ,y) ≥ r_2 then [s(x) - s(y)_1 > λ b] ≤ e^b(p_1 - p_2)^2 / 8.
	


If we replace the exact distance computations with sketches we want to avoid two events: 
Failing to report a point with (q,x) ≤ r_1 and reporting a point x with (q, x) ≥ r_2.
By setting b = O(ln(n) / (p_1 - p_2)^2) and applying a union bound over the n events that the sketch fails for a point in our collection P we obtain Theorem <ref>. 



§ THE NUMBER OF HASH FUNCTIONS IN CORNER CASES


When the collision probabilities of the (r_1, r_2, p_1, p_2)-sensitive family  are close to one we get the behavior displayed in Figure <ref> where we have set p_1 = 0.9. 
Here it may be possible to reduce the number of hash functions by applying the DKT framework to the family ^τ for some positive integer τ. That is, instead of applying the DKT technique directly to  we first apply the powering trick to produce the family ^τ.
The number of locality-sensitive hash functions from  used by the DKT framework is given by H = O( (log(n) / log(1/p_2))^2 / p_1).
If we instead use the family ^τ the expression becomes H = O( τ(log(n) / log(1/p_2^τ))^2 / p_1^τ) = O((log(n) / log(1/p_2))^2 / τ p_1^τ). 
Ignoring integer constraints, the value of τ that maximizes τ p_1^τ, thereby minimizing H, is given by τ = 1 / ln(1/p_1).
Discretizing, the resulting number of hash functions when setting τ = ⌈ 1 / ln(1/p_1)⌉ is given by H = O(ρ (log n)^2 / (p_1 log(1/p_2))).
For constant ρ and large p_2 this reduces the number of hash functions by a factor 1/log(1/p_2).

The behavior for small values of p_1 is displayed in Figure <ref> where we have set p_1 = 0.1.




§ CONCLUSION AND OPEN PROBLEMS


We have shown that there exists a simple and general framework for solving the (r_1, r_2)-near neighbor problem using only few locality-sensitive hash functions and with a reduced word-RAM complexity matching the number of lookups.
The analysis in this paper indicates that the performance of the Dahlgaard-Knudsen-Thorup framework is highly competitive compared to the Indyk-Motwani framework in practice, especially when locality-sensitive hash functions are expensive to evaluate, as is often the case.

An obvious open problem is the question of whether the number of locality-sensitive hash functions can be reduced even below O(k^2 / p_1).
Another possible direction for future research would be to obtain similar framework results in the context of solutions to the (r_1, r_2)-near neighbor problem that allow for space-time tradeoffs <cit.>.



    Acknowledgements.


I want to thank Rasmus Pagh commenting on an earlier version of this manuscript and for making me aware of the application of the tensoring technique in <cit.> that led me to the Andoni-Indyk framework <cit.>.





§ INEQUALITIES


We make use of the following standard inequalities for the exponential function. 
See <cit.> for more details.

	Let n, t ∈ℝ such that n ≥ 1 and |t| ≤ n then e^-t(1-t^2 /n) ≤ (1 - t/n)^n ≤ e^-t.


	For t ≥ 0 we have that e^-t≤ 1 - t + t^2 / 2.


We make use of a one-sided version of Chebyshev's inequality to show correctness of the Dahlgaard-Knudsen-Thorup LSH framework. 

Let Z be a random variable with [Z] = μ > 0 and [Z] = σ^2 < ∞ then [Z ≤ 0] ≤σ^2/(μ^2 + σ^2). 


	For every s ∈ℝ we have that 

    [Z ≤ 0] = [-(Z - μ) + s ≥μ + s] ≤[(-(Z - μ) + s)^2 ≥ (μ + s)^2].

Next we apply Markov's inequality 

    [(-(Z - μ) + s)^2 ≥ (μ + s)^2] ≤[(-(Z - μ) + s)^2]/ (μ + s)^2 = (σ^2 + s^2)/ (μ + s)^2

Set s = σ^2 / μ and use that σ^2 = sμ to simplify 

    (σ^2 + s^2)/ (μ + s)^2 = (sμ + s^2)/ (μ + s)^2 = σ^2 / (μ^2 + σ^2).



To analyze the 1-bit sketching scheme by Li and König we make use of Hoeffding's inequality:
 
	Let X_1, X_2, …, X_n be independent random variables satisfying 0 ≤ X_i ≤ 1 for i ∈ [n].
	Define X̅ = (X_1 + X_2 + … + X_n)/n and μ = [X̅], then:
	
		
  - For 0 < ε < 1 - μ we have that [X̅ - μ≥ε] ≤ e^-2nε^2.
		
  - For 0 < ε < μ we have that [X̅ - μ≤ - ε] ≤ e^-2nε^2.
	




§ ANALYSIS OF THE ANDONI-INDYK FRAMEWORK


Let φ denote the probability that a pair of points x, y with (x,y) ≤ r_1 collide in a single repetition of the scheme.
A collision occurs if and only if there there exists at least one hash function in each of the underlying t + 1 collections where the points collide.
It follows that

    φ = (1 - (1-p_1^k_1)^m_1)^t (1 - (1-p_1^k_2)^m_2).

To guarantee a collision with probability at least 1/2 it suffices to set η = ⌈ln(2) / φ⌉.

We will proceed by analyzing this scheme where we let t ≥ 1 be variable and set parameters as followers:

    k    = ⌈log(n) / log(1/p_2) ⌉
    
    	k_1    = ⌊ k/t ⌋
    
    	k_2    = k - tk_1 
    
    	m_1    = ⌈ 1/ t p_1^k_1⌉
    
    	m_2    = ⌈ 1/ p_1^k_2⌉
    η   = ⌈ln(2) / φ⌉.

To upper bound L we begin by lower bounding φ.
The second part of φ can be lower bounded using Lemma <ref> to yield (1 - (1-p_1^k_2)^m_2) ≥ 1 - 1/e.
To lower bound (1 - (1-p_1^k_1)^m_1)^t we first note that in the case where p_1^k_1 > 1/t we have m_1 = 1 and the expression can be lower bounded by p_1^k_1 t = (p_1^k_1 m_1)^t ≥  (p_1^k_1 m_1)^t / 2e.
The same lower bound holds in the case there t = 1.
In the case where p_1^k_1≤ 1/t and t ≥ 2 we make use of Lemma <ref> and <ref> to derive the lower bound. 

    1 - (1-p_1^k_1)^m_1   ≥ 1 - e^-p_1^k_1 m_1
       ≥ 1 - (1 - p_1^k_1 m_1 + (p_1^k_1 m_1)^2/2) 
       ≥ p_1^k_1 m_1 (1 - p_1^k_1(1/t p_1^k_1 + 1)/2) 
       ≥ p_1^k_1 m_1 (1 - 1/t).

Using the bound (p_1^k_1 m_1 (1 - 1/t))^t ≥ (p_1^k_1 m_1)^t / 2e we have that 

    φ≥ (p_1^k_1 m_1)^t / 4e ≥ (1/t)^t / 4e.

We can then bound the number of lookups and the expected number of distance computations

    L = η m_1^t m_2 ≤ (4e / (p_1^k_1 m_1)^t + 1) m_1^t (1/p_1^k_2 + 1) ≤ 16e (1/p_1^k).

Note that this matches the upper bound of the Indyk-Motwani LSH framework up to a constant factor.

To bound the number of hash functions from  we use that k_1 ≤ k/t ≤ k and k_2 < t.

    H = η (m_1 k_1 t + m_2 k_2) ≤ 8e t^t (k/t p_1^k/t + t-1/p_1^t-1).





