Fast Search on Binary Codes by Weighted Hamming Distance

• URL: http://arxiv.org/abs/2009.08591v2
• Date: Tue, 10 Aug 2021 07:36:22 GMT
• Title: Fast Search on Binary Codes by Weighted Hamming Distance
• Authors: Zhenyu Weng, Yuesheng Zhu, Ruixin Liu
• Abstract summary: A fast search algorithm is proposed to perform the non-exhaustive search for $K$ nearest binary codes by weighted Hamming distance. A fast search framework based on the proposed search algorithm is designed to solve the problem of long binary codes.
• Score: 38.50174794945964
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, and a merging algorithm is proposed to find the nearest binary codes by merging the candidates. Theoretical analysis and experimental results demonstrate that the search algorithm improves the search accuracy compared to other non-exhaustive algorithms and provides orders-of-magnitude faster search than the linear scan baseline.

Related papers

• Structured search algorithm: A quantum leap [0.0]
  Grover's quantum search algorithm showcases the prowess of quantum algorithms. This letter advances Grover's algorithm using a structured search method to attain an unbounded search speed.
  arXiv  Detail & Related papers  (2025-04-04T13:16:53Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
  arXiv  Detail & Related papers  (2024-07-17T21:26:27Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Accelerating Code Search with Deep Hashing and Code Classification [64.3543949306799]
  Code search is to search reusable code snippets from source code corpus based on natural languages queries. We propose a novel method CoSHC to accelerate code search with deep hashing and code classification.
  arXiv  Detail & Related papers  (2022-03-29T07:05:30Z)
• A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in Peafowls [0.0]
  Simplistic methods such as exhaustive search become computationally expensive and unreliable as the solution space for search algorithms increase. This research proposes an Infrasonic Search Algorithm, inspired from the Gravitational Search Algorithm and the mating behaviour in peafowls.
  arXiv  Detail & Related papers  (2021-06-28T09:04:51Z)
• Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples [10.993342896547691]
  We study the behavior of several black-box search algorithms used for generating adversarial examples for natural language processing (NLP) tasks. We perform a fine-grained analysis of three elements relevant to search: search algorithm, search space, and search budget.
  arXiv  Detail & Related papers  (2020-09-09T17:04:42Z)
• Faster Person Re-Identification [68.22203008760269]
  We introduce a new solution for fast ReID by formulating a novel Coarse-to-Fine hashing code search strategy. It uses shorter codes to coarsely rank broad matching similarities and longer codes to refine only a few top candidates for more accurate instance ReID. Experimental results on 2 datasets show that our proposed method (CtF) is not only 8% more accurate but also 5x faster than contemporary hashing ReID methods.
  arXiv  Detail & Related papers  (2020-08-16T03:02:49Z)
• Fast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs [1.5828697880068703]
  This algorithm uses a novel XOR-friendly binary quantization method to encode floating-point numbers. Experiments show that, our quantization method takes short preprocessing time, and helps make the search speed of our exhaustive search method much more faster than that of popular approximate nearest neighbor algorithms.
  arXiv  Detail & Related papers  (2020-08-05T08:50:21Z)
• A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing [0.0]
  We present an approach based on hash tables that focuses on both minimizing the number of comparisons performed during the search and minimizing the total collection size. The paper results show that near-perfect hashing is faster than binary search, yet uses less memory than perfect hashing.
  arXiv  Detail & Related papers  (2020-07-16T12:57:15Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.