Fast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs

• URL: http://arxiv.org/abs/2008.02002v1
• Date: Wed, 5 Aug 2020 08:50:21 GMT
• Title: Fast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs
• Authors: Xiaozheng Jian, Jianqiu Lu, Zexi Yuan, Ao Li
• Abstract summary: 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.
• Score: 1.5828697880068703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore the use of GPU for accelerating large scale nearest neighbor search and we propose a fast vector-quantization-based exhaustive nearest neighbor search algorithm that can achieve high accuracy without any indexing construction specifically designed for cosine similarity. This algorithm uses a novel XOR-friendly binary quantization method to encode floating-point numbers such that high-complexity multiplications can be optimized as low-complexity bitwise operations. 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 when high accuracy is needed.

Related papers

• Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
  We analyze generalizations of algorithms based on the short-path framework first proposed by Hastings. Under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups. We conclude the paper with a numerical analysis that guides the choice of parameters for short path algorithms.
  arXiv  Detail & Related papers  (2024-10-30T17:52:56Z)
• Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search [14.821492155733555]
  We propose a graph-based ANNS algorithm for dense-sparse hybrid vectors. We show that our algorithm achieves 8.9x$sim$11.7x throughput at equal accuracy compared to existing hybrid vector search algorithms.
  arXiv  Detail & Related papers  (2024-10-27T09:12:51Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• 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)
• Locality-aware Qubit Routing for the Grid Architecture [1.4459640831465588]
  We introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain "grid-like" architectures.
  arXiv  Detail & Related papers  (2022-03-21T20:46:39Z)
• Nearest neighbor search with compact codes: A decoder perspective [77.60612610421101]
  We re-interpret popular methods such as binary hashing or product quantizers as auto-encoders. We design backward-compatible decoders that improve the reconstruction of the vectors from the same codes.
  arXiv  Detail & Related papers  (2021-12-17T15:22:28Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Fast Search on Binary Codes by Weighted Hamming Distance [38.50174794945964]
  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.
  arXiv  Detail & Related papers  (2020-09-18T02:24:44Z)
• 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)
• Hybrid divide-and-conquer approach for tree search algorithms [0.0]
  We study the hybrid divide-and-conquer method in the context of tree search algorithms. We provide conditions for speedups for the well known algorithm of DPLL. We briefly discuss the limitations of hybrid methods in providing speed-ups for larger problems.
  arXiv  Detail & Related papers  (2020-07-14T13:57:12Z)
• 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.