Optimal Data-Dependent Hashing for Nearest Neighbor Search
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Claims a concrete improvement over LSH: using data-dependent hashing and a tree of partitions that alternates dense-cluster extraction and cap carving, worst-case nearest-neighbor reduces to an average-case on a sphere and achieves a strictly smaller exponent rho (e.g., for approximation c=2 Euclidean query time improves from n^{1/4} to about n^{1/3}). Construction replaces many hash tables, needs repetitions for success, and supports near-linear preprocessing via careful down-sampling.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:45Nearest Neighbor Search (NNS)
- 1:13Motivation
- 3:04Curse of Dimensionality All exact algorithms degrade rapidly with the dimension
- 4:00Approximate NNS
- 5:57NNS algorithms
- 6:34Locality-Sensitive Hashing
- 10:19LSH Algorithms
- 12:03Detour: Closest Pair Problem
- 16:17Beyond Locality Sensitive Hashing
- 19:07A look at LSH lower bounds LSH lower bounds in Hamming space Fourier analytic
- 21:54Construction of hash function Two components
- 23:07Average-case: nicer structure
- 26:54Reduction to nice structure
- 30:20Hash function Described by a tree like a hash table
- 35:54Dense clusters Current dataset: radius R A dense cluster
- 38:02Tree recap
- 40:47Fast preprocessing How to find the dense clusters fast!
- 43:14Data-dependent hashing: beyond LSH