About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2017
Conference paper
Optimal hashing-based time-space trade-offs for approximate near neighbors
Abstract
We show tight upper and lower bounds for time-space trade-offs for the c-approximate Near Neighbor Search problem. For the d-dimensional Euclidean space and n- point datasets, we develop a data structure with space n1+pu+°(1) + O(dn) and query time npq +o(1) + dno(1) for every pu, pq > 0 with: c2√pq +(c2 - 1)√pU- In particular, for the approximation c = 2 we get: Space n1.77....." and query time no(1), significantly improving upon known data structures that support very fast queries [IM98, KOR00]; Space n1.14 and query time n0.14 , matching the optimal data-dependent Locality-Sensitive Hashing (LSH) from [AR15] Space n1+o(1) and query time n0.43 , making significant progress in the regime of near-linear space, which is arguably of the most interest for practice [LJW+07]. This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor c > 1, improving upon [Kap15]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [BDGL16] and data- dependent hashing [AINR14, AR15]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole trade-off (0.1) in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match (0.1) for pq = 0, improving upon the best known lower bounds from [PTW10]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.