Advances in Vector Search

Whether a text document is freed from the rules of grammar, stripped of word order, and thereby turned into a bag of words, or whether its semantic nuances learnt and condensed into an embedding space, its final representation is the same mathematical object: a vector. In fact, vectors represent much more than just text documents. Any object, be it a document or query, that contains text, images, speech, or a mix of these modalities, is often represented as a vector. Collect a large enough quantity of these vectors and the fundamental question of retrieval from the Information Retrieval (IR) discipline becomes urgently relevant: Finding k vectors that are more similar to a query. This full-day tutorial is concerned with the question above and intends to cover foundational concepts and advanced algorithms for vector retrieval or vector search. The tutorial begins with a focus on foundational concepts, including a brief history from space partitioning, to locality-sensitive hashing, graph-based, and clustering-based methods. As we discuss each class of solutions, we show failure scenarios and explain why they prove insufficient. We conclude the tutorial by turning our attention in the second half to recent developments for maximum inner product search over dense and sparse vectors, as well as open questions that need further research. Through this tutorial, we wish to recap the fascinating topic of retrieval in modern IR for the community, lower barriers of entry into this rich area of research, and inspire interest in conducting research on the underlying theoretical and empirical questions that are specific to IR.