Data-Dependent hashing via nonlinear spectral gaps

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¹+^ε, 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 ℓ₂. 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 ℓ₁. Our new generic reduction proceeds differently from both of these approaches using a novel partitioning method.