Dense and sparse vector search

Vector retrieval without an index is “dense” because you need to retrieve the entire candidate in order to make a comparison. Such a “brute force” scan must take , where is the dimension of the vectors and is the number of vectors to be compared.

By contrast, predicated search (such as a relational database query) is “sparse,” even without an index, because only a portion of the data must be retrieved.

Vector retrieval can be made sparse by adding an index. However, there is no natural sorting principle for vectors. Hence, vector indexing always involves some kind of vector partitioning. Note that, after a first-pass selection of vectors based on an index, a brute force scan of the remaining candidates is typically still required.