Topic: Nearest-neighbor search

Worst-case bounds described as optimal can remain loose for the data encountered in practice. This talk develops distribution-specific analyses for local, nonparametric methods, focusing on nearest neighbors. The statistical results give closely matching upper and lower bounds for classification convergence for each data distribution, characterize metric measure spaces supporting universal consistency, and motivate a smoothness concept adapted to nearest-neighbor methods. The algorithmic results characterize the performance of tree-based nearest-neighbor search through the configuration of the

Maximum inner-product search ranks candidate vectors by their unnormalized dot product with a query. This similarity creates difficulties for conventional locality-sensitive hashing. The talk introduces an asymmetric hashing framework in which queries and stored vectors undergo different transformations, turning approximate MIPS into a standard approximate nearest-neighbor problem. An explicit construction provides provably sublinear search and a simple implementation. Experiments on recommendation tasks using Netflix and MovieLens data compare the method with sign random projection and p-stab

Spectral methods for high-dimensional nearest-neighbor search can perform well in practice even when random projections appear preferable under worst-case theory. This talk studies that difference in a semi-random model: points lie in an unknown low-dimensional subspace and are then perturbed by Gaussian noise in the full ambient space. The algorithms repeatedly compute a leading principal component or subspace and achieve query times polynomial in the ambient dimension and logarithm of the number of points over substantial parameter ranges. They can remain effective when noise is much larger