Content available in repository
Content available in repository
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, Erik Waingarten
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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.
Original language | English |
---|---|
Title of host publication | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |
Editors | Philip N. Klein |
Publisher | Society for Industrial and Applied Mathematics (SIAM) |
Pages | 47-66 |
Number of pages | 20 |
ISBN (Electronic) | 978-1-61197-478-2 |
DOIs | |
Publication status | Published - 4 Jan 2017 |
Event | 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 Conference number: 28 |
Conference | 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) |
---|---|
Abbreviated title | SODA 2017 |
Country/Territory | Spain |
City | Barcelona |
Period | 16/01/17 → 19/01/17 |
Research output: Contribution to journal › Article › Academic
Research output: Contribution to journal › Article › Academic
Research output: Contribution to journal › Article › Academic