Locality-sensitive hashing scheme based on p-stable distributions

TLDR

We present a novel Locality‑Sensitive Hashing scheme for the Approximate Nearest Neighbor Problem under the lp norm, based on p‑stable distributions. The scheme uses p‑stable distributions to hash points directly in Euclidean space, achieving faster running time than previous algorithms and enabling exact near‑neighbor search in O(log n) for data with bounded growth. The algorithm is the first provably efficient approximate NN method for p<1, achieves a simple query time bound without large factors, finds exact near neighbors in O(log n) for bounded‑growth data, and is up to 40 × faster than a kd‑tree in experiments.

Abstract

We present a novel Locality-Sensitive Hashing scheme for the Approximate Nearest Neighbor Problem under lp norm, based on p-stable distributions.Our scheme improves the running time of the earlier algorithm for the case of the lp norm. It also yields the first known provably efficient approximate NN algorithm for the case p<1. We also show that the algorithm finds the exact near neigbhor in O(log n) time for data satisfying certain "bounded growth" condition.Unlike earlier schemes, our LSH scheme works directly on points in the Euclidean space without embeddings. Consequently, the resulting query time bound is free of large factors and is simple and easy to implement. Our experiments (on synthetic data sets) show that the our data structure is up to 40 times faster than kd-tree.