The Geometry of Similarity Search
- Speaker
-
Alexandr Andoni, Ph.D.Columbia University
Presidential Lectures are free public colloquia centered on four main themes: Biology, Physics, Mathematics and Computer Science, and Neuroscience and Autism Science. These curated, high-level scientific talks feature leading scientists and mathematicians and are intended to foster discourse and drive discovery among the broader NYC-area research community. We invite those interested in the topic to join us for this weekly lecture series.
By clicking to watch this video, you agree to our privacy policy.
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.