Fall 2013

Beyond Locality-Sensitive Hashing

Monday, Aug. 26, 2013 4:20 pm4:45 pm

Add to Calendar

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R^d, our algorithm achieves O(dn^{ ho}) query time and O(n^{1 + ho} + nd) space, where ho <= 7/(8c^2) + O(1 / c^3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ITCS 2011). By a standard reduction we obtain a data structure for the Hamming space and ell_1 norm with ho <= 7/(8c) + O(1/c^{3/2}) + o(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

Joint work with Piotr Indyk, Huy L. Nguyen, Ilya Razenshteyn.