Abstract | ||
---|---|---|
We present a n ovel Locality-Sensitive Hashing scheme for the Ap-proximate 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 l2 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 (lo 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 re-sulting 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-tree. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1145/997817.997857 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
case po,p-stable distribution,earlier algorithm,synthetic data set,query time,lp norm,earlier scheme,efficient approximate nn algorithm,data structure,novel locality-sensitive hashing scheme,lsh scheme,performance,kd tree,locality sensitive hashing,satisfiability,synthetic data,nearest neighbor,stable distribution,data structures,design,euclidean space,locally sensitive hashing | Locality-sensitive hashing,k-nearest neighbors algorithm,Discrete mathematics,Combinatorics,Universal hashing,K-independent hashing,2-choice hashing,Dynamic perfect hashing,Nearest neighbor search,Mathematics,Open addressing | Conference |
ISBN | Citations | PageRank |
1-58113-885-7 | 1218 | 63.85 |
References | Authors | |
23 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mayur Datar | 1 | 4999 | 283.72 |
Nicole Immorlica | 2 | 1636 | 100.87 |
Piotr Indyk | 3 | 10925 | 918.34 |
VAHAB S. MIRROKNI | 4 | 4309 | 287.14 |