Probabilistic analysis of data structures for locality-sensitive hashing functions

For the nearest neighbor search problem in high-dimensional spaces, Locality-Sensitive Hashing (LSH)has shown excellent performance in terms of query cost and disk space utilization. Under the traditional analysis model, LSH is considered a randomized algorithm, with the only uncertainty being the choice of the hash function. In this research, the collision probability obtained under this model is referred to as the hash-function-based collision probability. In this paper, a different analysis model is used to conduct a theoretical analysis of LSH. The motivation for this work is twofold:1) Under the existing analysis model, users must generate random data structures for each query point to achieve the theoretical effect, which is impractical in real applications.2) The performance metric that users are concerned with is the expected collision probability of a random query point in a single data structure. Based on this, this paper derives the collision probability of random point pairs under the Hamming distance for any single hash function. The collision probability derived under this model is referred to as the query-based collision probability. It is also proven that in the Hamming space, the two types of collision probabilities are identical.