Fast Filtering for Similarity Search Using Conjunctive Enumeration of Sketches in Order of Hamming Distance

TY - GEN

T1 - Fast Filtering for Similarity Search Using Conjunctive Enumeration of Sketches in Order of Hamming Distance

AU - Higuchi, Naoya

AU - Imamura, Yasunobu

AU - Mic, Vladimir

AU - Shinohara, Takeshi

AU - Hirata, Kouichi

AU - Kuboyama, Tetsuji

PY - 2024

Y1 - 2024

N2 - Sketches are compact bit-string representations of points, often employed for speeding up searches through the effects of dimensionality reduction and data compression. In this paper, we propose a novel sketch enumeration method and demonstrate its ability to realize fast filtering for approximate nearest neighbor search in metric spaces. Whereas the Hamming distance between the query’s sketch and sketches of points to be searched has been used for sketch prioritization traditionally, recent research has introduced asymmetric distances, enabling higher recall rates with fewer candidates. Additionally, sketch enumeration methods that speed up the filtering such that high-priority solution candidates are selected based on the priority of the sketch to the given query without the need for direct sketch comparisons have been proposed. Our primary goal in this paper is to further accelerate sketch enumeration through parallel processing. While Hamming distance-based enumeration can be parallelized relatively easily, achieving high recall rates requires a large number of candidates, and speeding up the filtering alone is insufficient for overall similarity search acceleration. Therefore, we introduce the conjunctive enumeration method, which concatenates two Hamming distance-based enumerations to approximate asymmetric distance-based enumeration. Then, we validate the effectiveness of the proposed method through experiments using large-scale public datasets. Our approach offers a significant acceleration effect, thereby enhancing the efficiency of similarity search operations.

AB - Sketches are compact bit-string representations of points, often employed for speeding up searches through the effects of dimensionality reduction and data compression. In this paper, we propose a novel sketch enumeration method and demonstrate its ability to realize fast filtering for approximate nearest neighbor search in metric spaces. Whereas the Hamming distance between the query’s sketch and sketches of points to be searched has been used for sketch prioritization traditionally, recent research has introduced asymmetric distances, enabling higher recall rates with fewer candidates. Additionally, sketch enumeration methods that speed up the filtering such that high-priority solution candidates are selected based on the priority of the sketch to the given query without the need for direct sketch comparisons have been proposed. Our primary goal in this paper is to further accelerate sketch enumeration through parallel processing. While Hamming distance-based enumeration can be parallelized relatively easily, achieving high recall rates requires a large number of candidates, and speeding up the filtering alone is insufficient for overall similarity search acceleration. Therefore, we introduce the conjunctive enumeration method, which concatenates two Hamming distance-based enumerations to approximate asymmetric distance-based enumeration. Then, we validate the effectiveness of the proposed method through experiments using large-scale public datasets. Our approach offers a significant acceleration effect, thereby enhancing the efficiency of similarity search operations.

KW - Approximate Nearest Neighbor Search

KW - Asymmetric Distance

KW - Conjunctive Enumeration

KW - Hamming Distance

KW - Similarity Search

KW - Sketch

UR - http://www.scopus.com/inward/record.url?scp=85190700915&partnerID=8YFLogxK

U2 - 10.5220/0012322700003654

DO - 10.5220/0012322700003654

M3 - Article in proceedings

SN - 9789897586842

VL - 1

SP - 499

EP - 510

BT - Proceedings of the 13th International Conference on Pattern Recognition Applications and Methods - ICPRAM

A2 - Castrillon-Santana, Modesto

A2 - De Marsico, Maria

A2 - Fred, Ana

PB - SCITEPRESS Digital Library

T2 - The International Conference on Pattern Recognition Applications and Methods

Y2 - 24 February 2024 through 26 February 2024

ER -