IC Colloquium : Algorithmic design via efficient data representations
Event details
| Date | 09.03.2015 |
| Hour | 10:15 › 11:30 |
| Location | |
| Category | Conferences - Seminars |
By : Alexandr Andoni - UC Berkeley
IC Faculty candidate
Abstract :
Modern datasets are at scales that would be unthinkable just a decade ago. This demands rethinking the principles of algorithmic design used to handle such datasets. In this talk, I will describe how such principles emerge from the methods of efficient data representations.
The first illustration will be the Nearest Neighbor Search (NNS) problem -- an ubiquitous massive datasets problem that is of key importance in machine learning and other areas. A central technique for tackling this problem is Locality Sensitive Hashing (LSH), a data representation method that has seen a lot of success in both theory and practice. I will present the best possible LSH-based algorithm for NNS under the Euclidean distance. Then, I will show a new method that, for the first time, provably outperforms the LSH-based algorithms.
Taking a broader perspective, I will also describe how the lens of "efficient data representation" leads to new fast algorithms for other longstanding questions. Specifically, I will discuss a classic dynamic programming problem (edit distance) and a Linear Programming problem (earth-mover distance). Finally, I will briefly mention how the above ideas enable an algorithmic framework for parallel computation systems such as MapReduce.
Bio :
Alexandr Andoni is a computer scientist focused on advancing algorithmic foundations of massive data. His research interests broadly revolve around sublinear algorithms, high-dimensional geometry, and theoretical machine learning. Alexandr graduated from MIT in 2009, with a PhD thesis on Nearest Neighbor Search, under the supervision of Piotr Indyk. During 2009--2010, he was a postdoc at the Center for Computational Intractability at Princeton, as well as a visitor at NYU and IAS. Alexandr then joined Microsoft Research Silicon Valley, where he was a researcher until 2014. Currently, Alexandr is a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley.
More information
IC Faculty candidate
Abstract :
Modern datasets are at scales that would be unthinkable just a decade ago. This demands rethinking the principles of algorithmic design used to handle such datasets. In this talk, I will describe how such principles emerge from the methods of efficient data representations.
The first illustration will be the Nearest Neighbor Search (NNS) problem -- an ubiquitous massive datasets problem that is of key importance in machine learning and other areas. A central technique for tackling this problem is Locality Sensitive Hashing (LSH), a data representation method that has seen a lot of success in both theory and practice. I will present the best possible LSH-based algorithm for NNS under the Euclidean distance. Then, I will show a new method that, for the first time, provably outperforms the LSH-based algorithms.
Taking a broader perspective, I will also describe how the lens of "efficient data representation" leads to new fast algorithms for other longstanding questions. Specifically, I will discuss a classic dynamic programming problem (edit distance) and a Linear Programming problem (earth-mover distance). Finally, I will briefly mention how the above ideas enable an algorithmic framework for parallel computation systems such as MapReduce.
Bio :
Alexandr Andoni is a computer scientist focused on advancing algorithmic foundations of massive data. His research interests broadly revolve around sublinear algorithms, high-dimensional geometry, and theoretical machine learning. Alexandr graduated from MIT in 2009, with a PhD thesis on Nearest Neighbor Search, under the supervision of Piotr Indyk. During 2009--2010, he was a postdoc at the Center for Computational Intractability at Princeton, as well as a visitor at NYU and IAS. Alexandr then joined Microsoft Research Silicon Valley, where he was a researcher until 2014. Currently, Alexandr is a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Rachid Guerraoui