Tag-Filtered Approximate Nearest Neighbor Search

Approximate Nearest Neighbor Search (ANNS) plays an important role in the search and recommendation of objects represented with high-dimensional vectors. For objects that are associated with tags such as the origin location, color, and type, it is common to perform ANNS with tag constraints, i.e., conduct search on objects that carry the query tags. We call such search Tag-Filtered Approximate Nearest Neighbor Search (TFANNS). The state-of-the-art TFANNS method Filtered-DiskANN is a graph-based method which suffers from a low recall for queries with low-to-medium frequent tags. Pre-filtering on these tags could boost the recall but lead to a large memory footprint. To address this issue, we propose three strategies in constructing a graph that strikes a balance between the performance and memory footprint; note that we are the first work on tag-frequency-aware graph-based indexing for TFANNS. Our extensive experiments show the superiority of our proposed methods over existing baselines: under$\geq 0.9$recall, our QPS is up to 13 times that of the best baseline.