Fast Search On Binary Codes By Weighted Hamming Distance

Abstract

Weighted Hamming distance, as a similarity measure between binary codes and binary queries, provides superior accuracy in search tasks than Hamming distance. However, how to efficiently and accurately find \(K\) binary codes that have the smallest weighted Hamming distance to the query remains an open issue. In this paper, a fast search algorithm is proposed to perform the non-exhaustive search for \(K\) nearest binary codes by weighted Hamming distance. By using binary codes as direct bucket indices in a hash table, the search algorithm generates a sequence to probe the buckets based on the independence characteristic of the weights for each bit. Furthermore, a fast search framework based on the proposed search algorithm is designed to solve the problem of long binary codes. Specifically, long binary codes are split into substrings and multiple hash tables are built on them. Then, the search algorithm probes the buckets to obtain candidates according to the generated substring indices

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyweng2020fast

Related papers

• Fast Cosine Similarity Search In Binary Space With Angular Multi-index Hashing (2016)8.60
• Constant Sequence Extension For Fast Search Using Weighted Hamming Distance (2023)0.00
• Polysemous Codes (2016)11.49
• Nearest Neighbor Search With Compact Codes: A Decoder Perspective (2021)3.58
• Fast And Exact Nearest Neighbor Search In Hamming Space On Full-text Search Engines (2019)5.24
• Online Hashing With Efficient Updating Of Binary Codes (2019)8.09
• Query-adaptive Hash Code Ranking For Large-scale Multi-view Visual Search (2019)13.74
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00