NAVER LABS Europe seminars are open to the public. This seminar is virtual and requires registration
Date: 28th March 2023, 10:00 am (CEST)
Sketching and topological organization of sparse vectors for probably approximately correct maximum inner product search
About the speaker: Sebastian Bruch completed his Ph.D. in Computer Science at the University of Maryland, College Park in 2013. His research since has centered around probabilistic data structures, streaming algorithms for maximum inner product search, and learnt stochastic ranking policies. He has published in and served on the program committees and senior program committees of premier IR conferences like SIGIR, WSDM, SIGKDD, and the Web Conference. He is a Staff Research Scientist at Pinecone in the United States, and a Visiting Scholar at Università Ca’ Foscari in Venice, Italy.
Abstract: Maximum Inner Product Search (MIPS) over the space of sparse, extremely high-dimensional real vectors is a beast of its own. In their most general form, such vectors lack a compact representation, making a collection of them expensive to store and retrieve. They have very little in the way of geometrical structure, rendering their space hard to navigate efficiently. But it’s not all bad news if you stop insisting on exactness and instead accept probably approximately correct results, and take on a topological perspective instead of looking for geometrical properties. In this talk, I will first introduce a sketching algorithm that approximates sparse vectors and facilitates efficient inner product computation in streaming collections with quantifiable error. I will then show how we can define a topology of sparse vectors to organize their space, and how to efficiently explore this topology by obliviously embedding it into a lower dimensional space.