arXiv Open Access 2016

Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors

Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn Erik Waingarten

Lihat Sumber

Abstrak

We show tight lower bounds for the entire trade-off between space and query time for the Approximate Near Neighbor search problem. Our lower bounds hold in a restricted model of computation, which captures all hashing-based approaches. In articular, our lower bound matches the upper bound recently shown in [Laarhoven 2015] for the random instance on a Euclidean sphere (which we show in fact extends to the entire space $\mathbb{R}^d$ using the techniques from [Andoni, Razenshteyn 2015]). We also show tight, unconditional cell-probe lower bounds for one and two probes, improving upon the best known bounds from [Panigrahy, Talwar, Wieder 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than for one probe. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.

Topik & Kata Kunci

cs.DS cs.CC cs.CG cs.IT

Penulis (4)

Alexandr Andoni

Thijs Laarhoven

Ilya Razenshteyn

Erik Waingarten

Format Sitasi

APA MLA BibTeX

Andoni, A., Laarhoven, T., Razenshteyn, I., Waingarten, E. (2016). Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. https://arxiv.org/abs/1605.02701

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2016
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓