Talk by Alexandr Andoni: Near Neighbor Search under General Symmetric Distances

On 17 August 2017, Alexandr Andoni, Associate Professor in the Department of Computer Science at Columbia University, will give a talk at DIKU.

Near Neighbor Search under General Symmetric Distances

We show an efficient approximate nearest neighbor search (ANN) algorithm over any arbitrary high dimensional symmetric norm. Traditionally, the ANN problem in high dimensions has been studied over the Manhattan and Euclidean distances, with only a few exceptions.

This new result is a (modest) step towards a unified theory of similarity search. At a very high level, the algorithm proceeds by mapping an arbitrary symmetric norm into a carefully crafted "simpler" space, which we can handle via a combination of classic and new tools. The resulting data structure achieves doubly-logarithmic approximation using sub-polynomial query time and near-linear space.

Joint work with Huy Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten (STOC'17).


Alexandr Andoni is an Associate Professor in the Department of Computer Science at Columbia University with a broad interest in algorithmic foundations of massive data. His particular research interests include sublinear algorithms (streaming and property testing), high-dimensional computational geometry, metric embeddings, and machine learning.

Professor Andoni graduated from MIT in 2009, under the supervision of Professor Piotr Indyk. His PhD thesis was on the "Nearest Neighbor Search: the Old, the New, and the Impossible". In 2009-2010, he was a postdoc at the Center for Computational Intractability at Princeton, and a visitor at NYU and IAS. He was also a researcher at Microsoft Research Silicon Valley lab, from 2010 until its closure in 2014. Afterwards, he was a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley.