Fast Filtering by Conjunctive Enumeration of Sketches for Nearest Neighbor Search
摘要
Sketches are compact bit-strings that represent points in a metric space while preserving their distance relationships. Traditionally, the Hamming distance from a query’s sketch has been used to prioritize the selection of solution candidates for the nearest neighbor search. We introduced an asymmetric distance, named \(\widetilde{D}_1\) , which achieves higher recall rates for prioritization. Additionally, we introduced fast filtering by sketch enumeration. However, enumeration in \(\widetilde{D}_1\) order is challenging to parallelize, unlike enumeration in Hamming distance order. Recently, we proposed conjunctive enumeration \( CE \) to address the lower recall rates of Hamming distance and at the same time to be speeded up through parallelization, but the number of solution candidates generated by \( CE \) was still too large. In this paper, we present an enhanced conjunctive enumeration method \( CE+ \) with post-selection. This method reselects candidates with high \(\widetilde{D}_1\) priority from those filtered by \( CE \) , achieving \(\widetilde{D}_1\) -level recall rates with comparable candidate sizes. Despite the additional reselection costs, \( CE+ \) filtering outperforms \(\widetilde{D}_1\) filtering overall. Experimental validation on large-scale datasets confirms the effectiveness of our enhanced method.