MINT: Multi-Vector Search Index Tuning

Vector search plays a crucial role in many realworld applications. In addition to single-vector search, multivector search becomes important for multi-modal and multifeature scenarios today. In a multi-vector database, each row is an item, each column represents a feature of items, and each cell is a high-dimensional vector. In multi-vector databases, the choice of indexes can significantly impact the performance of vector search. Although index tuning for relational databases has been extensively studied, index tuning for multi-vector search remains unclear and challenging. In this paper, we define multivector search index tuning and propose a framework to solve it. Specifically, given a multi-vector search workload, we develop algorithms to find indexes that minimize latency and meet storage and recall constraints. Compared to the baseline, our techniques achieve a 2.1× to 8.3× speedup in latency.