DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries

10/27/2022
by   Joshua Engels, et al.
0

We study the problem of vector set search with vector set queries. This task is analogous to traditional near-neighbor search, with the exception that both the query and each element in the collection are sets of vectors. We identify this problem as a core subroutine for many web applications and find that existing solutions are unacceptably slow. Towards this end, we present a new approximate search algorithm, DESSERT (DESSERT Effeciently Searches Sets of Embeddings via Retrieval Tables). DESSERT is a general tool with strong theoretical guarantees and excellent empirical performance. When we integrate DESSERT into ColBERT, a highly optimized state-of-the-art semantic search method, we find a 2-5x speedup on the MSMarco passage ranking task with minimal loss in recall, underscoring the effectiveness and practical applicability of our proposal.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset