### Abstract

We establish a generic reduction from nonlinear spectral gaps of metric spaces to data-dependent Locality-Sensitive Hashing, yielding a new approach to the high-dimensional Approximate Near Neighbor Search problem (ANN) under various distance functions. Using this reduction, we obtain the following results: For general d-dimensional normed spaces and n-point datasets, we obtain a cell-probe ANN data structure with approximation O(^{log} _{ε2} ^{d}), space d^{O}(1)n^{1}+^{ε}, and d^{O}(1)n^{ε} cell probes per query, for any > 0. No non-trivial approximation was known before in this generality other than the O(d) bound which follows from embedding a general norm into ℓ_{2}. For ℓ_{p} and Schatten-p norms, we improve the data structure further, to obtain approximation O(p) and sublinear query time. For ℓ_{p}, this improves upon the previous best approximation 2^{O}(p) (which required polynomial as opposed to near-linear in n space). For the Schatten-p norm, no non-trivial ANN data structure was known before this work. Previous approaches to the ANN problem either exploit the low dimensionality of a metric, requiring space exponential in the dimension, or circumvent the curse of dimensionality by embedding a metric into a “tractable” space, such as ℓ_{1}. Our new generic reduction proceeds differently from both of these approaches using a novel partitioning method.

Original language | English (US) |
---|---|

Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |

Publisher | Association for Computing Machinery |

Pages | 685-698 |

Number of pages | 14 |

ISBN (Electronic) | 9781450355599 |

DOIs | |

State | Published - Jun 20 2018 |

Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: Jun 25 2018 → Jun 29 2018 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|

Country | United States |

City | Los Angeles |

Period | 6/25/18 → 6/29/18 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Locality-sensitive hashing
- Nearest neighbor search
- Nonlinear spectral gaps
- Randomized space partitions

## Fingerprint Dive into the research topics of 'Data-Dependent hashing via nonlinear spectral gaps'. Together they form a unique fingerprint.

## Cite this

*STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 685-698). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188846