The Geometry of Similarity Search
- Speaker
-
Alexandr Andoni, Ph.D.Columbia University
Presidential Lectures are a series of free public colloquia spotlighting groundbreaking research across four themes: neuroscience and autism science, physics, biology, and mathematics and computer science. These curated, high-level scientific talks feature leading scientists and mathematicians and are designed to foster discussion and drive discovery within the New York City research community. We invite those interested in these topics to join us for this weekly lecture series.
How does one efficiently search for similar items in a large dataset, say, of images? This is a classic algorithmic task that arises when dealing with massive datasets. Its applications span many areas, including information retrieval, machine learning, data mining, computer vision, signal processing, bioinformatics, etc. For example, this task underlies the classic ‘nearest neighbor’ classification rule in machine learning. The natural solution for similarity search — to scan the entire dataset, comparing a given item to each item in the dataset — is prohibitively slow for modern datasets.
Alexandr Andoni will describe how efficient solutions for similarity search benefit from the tools and perspectives of high-dimensional geometry. The latter emerged as the natural language of similarity search: e.g., a 20 x 20 pixel image naturally corresponds to a 400-dimensional vector, one coordinate per pixel. Andoni will show how geometric tools such as dimension reduction and randomized space partitions enable efficient similarity search algorithms.
About the Speaker
Alexandr Andoni is associate professor of computer science at Columbia University and a member of its Data Science Institute. Previously, Andoni performed research at the Massachusetts Institute of Technology, the Center for Computational Intractability (Princeton University, New York University and the Institute for Advanced Study), Microsoft Research in Silicon Valley, California, and the Simons Institute for the Theory of Computing at the University of California, Berkeley. Andoni focuses on advancing algorithmic foundations of massive data, studying topics such as sublinear algorithms, high-dimensional geometry, metric embeddings and theoretical machine-learning.