Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review
The algorithm has expected query time bounded by O(t(n/t)ρ), where t is the number of points to report and ρ∈(0,1) depends on the data distribution and the strength of the LSH family used. We further present a parameter-free way of using multi-probing, for LSH families that support it, and show that for many such families this approach allows us to get expected query time close to O(nρ+t), which is the best we can hope to achieve using LSH. The previously best running time in high dimensions was Ω(tnρ). For many data distributions where the intrinsic dimensionality of the point set close to q is low, we can give improved upper bounds on the expected query time.
|Title of host publication||Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms|
|Number of pages||18|
|Publisher||Society for Industrial and Applied Mathematics|
|Publication status||Published - 2017|