Baselines.
We have two baseline algorithms in the experiments: Vanilla and product quantization (PQ) [1]}. Vanilla, which uses the same code base of [2]}, is an adaption of HNSW [3]} to our constrained similarity search problem. We add the query constraint filter before pushing top-k results into the result heap. All our proposed AIRSHIP optimizations are built on top of the vanilla solution. PQ is one of the most popular quantization-based similarity search algorithms. It quantizes the high-dimensional vector to a limited number of integers to accelerate the distance computation. For the PQ comparison, we go over all vectors and check whether they meet the query constraint. Then, top-k similar vectors are chosen by the distances on the quantized vectors instead of the original data vector.
