ANN indexes

The goal of the index is to prevent scanning the whole database to retrieve the answer. In the case of k-ANN search, that means performing distance computation between the query and each object in the database. Performing distance computation is the most expensive operation in k-ANN search (LI in VDBMS).

Therefore, we use an index that tries to minimize the number of these operations. ANN indexing algorithms can be categorized roughly into three groups: partition-based (e.g. IVF-PQ), hash-based (e.g. LSH) and graph-based (e.g. HNSW). Almost all vector databases use graph-based algorithms nowadays. More specifically, they employ the Hierarchical Navigable Small Worlds (HNSW) algorithm.

• Partition-based
• Hash-based
• Graph-based