Billion-scale Similarity Search Using a Hybrid Indexing Approach with Advanced Filtering

• URL: http://arxiv.org/abs/2501.13442v1
• Date: Thu, 23 Jan 2025 07:47:00 GMT
• Title: Billion-scale Similarity Search Using a Hybrid Indexing Approach with Advanced Filtering
• Authors: Simeon Emanuilov, Aleksandar Dimov,
• Abstract summary: This paper presents a novel approach for similarity search with complex filtering capabilities on billion-scale datasets, optimized for CPU inference. Our method extends the classical IVF-Flat index structure to integrate multi-dimensional filters. The proposed algorithm combines dense embeddings with discrete filtering attributes, enabling fast retrieval in high-dimensional spaces.
• Score: 49.1574468325115
• License:
• Abstract: This paper presents a novel approach for similarity search with complex filtering capabilities on billion-scale datasets, optimized for CPU inference. Our method extends the classical IVF-Flat index structure to integrate multi-dimensional filters. The proposed algorithm combines dense embeddings with discrete filtering attributes, enabling fast retrieval in high-dimensional spaces. Designed specifically for CPU-based systems, our disk-based approach offers a cost-effective solution for large-scale similarity search. We demonstrate the effectiveness of our method through a case study, showcasing its potential for various practical uses.

Related papers

• Large-scale Multi-objective Feature Selection: A Multi-phase Search Space Shrinking Approach [0.27624021966289597]
  Feature selection is a crucial step in machine learning, especially for high-dimensional datasets. This paper proposes a novel large-scale multi-objective evolutionary algorithm based on the search space shrinking, termed LMSSS. The effectiveness of the proposed algorithm is demonstrated through comprehensive experiments on 15 large-scale datasets.
  arXiv  Detail & Related papers  (2024-10-13T23:06:10Z)
• Retrieval with Learned Similarities [2.729516456192901]
  State-of-the-art retrieval algorithms have migrated to learned similarities. We show that Mixture-of-Logits (MoL) can be realized empirically to achieve superior performance on diverse retrieval scenarios.
  arXiv  Detail & Related papers  (2024-07-22T08:19:34Z)
• Decomposed Guided Dynamic Filters for Efficient RGB-Guided Depth Completion [46.04264366475848]
  RGB-guided depth completion aims at predicting dense depth maps from sparse depth measurements and corresponding RGB images. Guided dynamic filters generate spatially-variant depth-wise separable convolutional filters from RGB features to guide depth features. We propose to decompose the guided dynamic filters into a spatially-shared component multiplied by content-adaptive adaptors at each spatial location.
  arXiv  Detail & Related papers  (2023-09-05T08:37:58Z)
• Gotta match 'em all: Solution diversification in graph matching matched filters [13.841897638543033]
  We present a novel approach for finding multiple noisily embedded template graphs in a very large background graph. Our method builds upon the graph-matching-matched-filter technique proposed in Sussman et al.
  arXiv  Detail & Related papers  (2023-08-25T15:53:30Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Efficient Joint-Dimensional Search with Solution Space Regularization for Real-Time Semantic Segmentation [27.94898516315886]
  We search an optimal network structure that can run in real-time for this problem. A novel Solution Space Regularization (SSR) loss is first proposed to effectively encourage the supernet to converge to its discrete one. A new Hierarchical and Progressive Solution Space Shrinking method is presented to further achieve high efficiency of searching.
  arXiv  Detail & Related papers  (2022-08-10T11:07:33Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering [59.349057602266]
  Variational AutoEncoder (VAE) has been extended as a representative nonlinear method for collaborative filtering. We propose to decompose the inner-product-based softmax probability based on the inverted multi-index. FastVAE can outperform the state-of-the-art baselines in terms of both sampling quality and efficiency.
  arXiv  Detail & Related papers  (2021-09-13T08:31:59Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. We present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. We show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets.
  arXiv  Detail & Related papers  (2020-03-06T00:06:20Z)

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.