publication . Other literature type . Conference object . 2004

Locality-sensitive hashing scheme based on p-stable distributions

Mayur Datar; Nicole Immorlica; Piotr Indyk; Vahab S. Mirrokni;
  • Published: 01 Jan 2004
  • Publisher: Association for Computing Machinery (ACM)
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 impl...
Subjects
free text keywords: Dynamic perfect hashing, Mathematics, Locality-sensitive hashing, Universal hashing, K-independent hashing, Combinatorics, k-nearest neighbors algorithm, Hopscotch hashing, Feature hashing, Discrete mathematics, Nearest neighbor search
Related Organizations
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Other literature type . Conference object . 2004

Locality-sensitive hashing scheme based on p-stable distributions

Mayur Datar; Nicole Immorlica; Piotr Indyk; Vahab S. Mirrokni;