 |
 |
Universite Paris Cite Seminar Series on Data Analytics Invited Seminar Talk |
 |
|
Prof Ke Li, Simon Fraser University (Canada) when: 3 October 2023, 1pm where: online (email the organizer for connection details), and in-person: room Turing Reunion, 7th floor, Universite Paris Cite, 45 Rue Des Saints Peres, Paris 75006 Abstract Nearest neighbour search is a classical problem that arises in machine learning, databases, statistics and computational geometry. Many attempts have been made over four decades to devise efficient algorithms, but they all suffered from an exponential dependence on dimensionality, a phenomenon known as the “curse of dimensionality”. Approximation algorithms can overcome this curse by expanding the set of acceptable solutions exponentially; however, the quality of approximation degrades significantly in high dimensions. In this talk, I will give an overview of Dynamic Continuous Indexing (DCI), a family of exact algorithms we developed that improves the dependence on intrinsic dimensionality from exponential to sublinear, which matches the lower bound on search with range queries. Empirically, DCI achieves the fastest construction and retrieval at all levels of recall on the approximate nearest neighbour (ANN) benchmark compared to 35 algorithms that have been developed to date. Short Bio Ke Li is an Assistant Professor and Visual Computing Chair in the School of Computing Science at Simon Fraser University. He is interested in a broad range of topics in machine learning, computer vision, NLP and algorithms. He is particularly passionate about tackling long-standing fundamental problems that cannot be tackled with a straightforward application of conventional techniques. He was previously a Member of the Institute for Advanced Study (IAS), and received his Ph.D. from UC Berkeley and B.Sc. from the University of Toronto. Hosted by: Themis Palpanas List of past seminars |