Topic: Approximate nearest neighbors

Nearest-neighbor indexes usually rely on a single distance function, but accurate comparisons can be expensive. This talk proposes a bi-metric framework: a cheap proxy metric builds the index, while the query procedure uses a limited number of evaluations of both the proxy and an expensive ground-truth metric. The theory applies to DiskANN and Cover Tree. When the proxy approximates the ground-truth metric within a bounded factor, the resulting structure can achieve arbitrarily good approximation guarantees under the accurate metric. Experiments on text retrieval using models with very differe

This talk establishes a general reduction from nonlinear spectral gaps of metric spaces to data-dependent space partitions in the form of locality-sensitive hashing. The reduction yields an approach to high-dimensional approximate near-neighbor search and a data structure for any d-dimensional norm whose query algorithm makes a sublinear number of probes. Its approximation factor is O(log d), improving on the square-root-of-d factor available from the generic approach based on John’s ellipsoid. The presentation connects spectral properties, geometric partitions, and efficient approximate searc