Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing

• URL: http://arxiv.org/abs/2604.04603v1
• Date: Mon, 06 Apr 2026 11:46:47 GMT
• Title: Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing
• Abstract summary: In this work, we address the problem of cardinality estimation for similarity search in high-dimensional spaces.<n>We leverage locality-sensitive hashing (LSH) to partition the vector space while preserving distance proximity.<n>We employ progressive sampling to reduce the number of distance computations and utilize asymmetric distance computation in product quantization to accelerate distance calculations in high-dimensional spaces.
• Score: 9.718824826201201
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this work, we address the problem of cardinality estimation for similarity search in high-dimensional spaces. Our goal is to design a framework that is lightweight, easy to construct, and capable of providing accurate estimates with satisfying online efficiency. We leverage locality-sensitive hashing (LSH) to partition the vector space while preserving distance proximity. Building on this, we adopt the principles of classical multi-probe LSH to adaptively explore neighboring buckets, accounting for distance thresholds of varying magnitudes. To improve online efficiency, we employ progressive sampling to reduce the number of distance computations and utilize asymmetric distance computation in product quantization to accelerate distance calculations in high-dimensional spaces. In addition to handling static datasets, our framework includes updating algorithm designed to efficiently support large-scale dynamic scenarios of data updates.Experiments demonstrate that our methods can accurately estimate the cardinality of similarity queries, yielding satisfying efficiency.

Related papers

• Efficient Identification of High Similarity Clusters in Polygon Datasets [0.0]
  We propose a framework that reduces the number of clusters requiring verification, thereby decreasing the computational load on these systems.<n>The framework integrates dynamic similarity index thresholding, supervised scheduling, and recall-constrained optimization.<n>Our approach achieves substantial reductions in computational cost without sacrificing accuracy.
  arXiv  Detail & Related papers  (2025-09-28T15:39:15Z)
• Radial Neighborhood Smoothing Recommender System [0.0]
  Radial Neighborhood Estimator (RNE) is proposed to construct neighborhoods based on overlapped and partially overlapped user-item pairs.<n>RNE achieves superior performance compared to existing collaborative filtering and matrix factorization methods.
  arXiv  Detail & Related papers  (2025-07-14T06:01:58Z)
• Efficient Computation of Sparse and Robust Maximum Association Estimators [0.4588028371034406]
  Robust statistical estimators offer empirical precision but are often computationally challenging in high-dimensional sparse settings.<n>Modern association estimator techniques are utilized for outliers without imposing resilience against other robust methods.
  arXiv  Detail & Related papers  (2023-11-29T11:57:50Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• UNETR++: Delving into Efficient and Accurate 3D Medical Image Segmentation [93.88170217725805]
  We propose a 3D medical image segmentation approach, named UNETR++, that offers both high-quality segmentation masks as well as efficiency in terms of parameters, compute cost, and inference speed. The core of our design is the introduction of a novel efficient paired attention (EPA) block that efficiently learns spatial and channel-wise discriminative features. Our evaluations on five benchmarks, Synapse, BTCV, ACDC, BRaTs, and Decathlon-Lung, reveal the effectiveness of our contributions in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2022-12-08T18:59:57Z)
• ECO-TR: Efficient Correspondences Finding Via Coarse-to-Fine Refinement [80.94378602238432]
  We propose an efficient structure named Correspondence Efficient Transformer (ECO-TR) by finding correspondences in a coarse-to-fine manner. To achieve this, multiple transformer blocks are stage-wisely connected to gradually refine the predicted coordinates. Experiments on various sparse and dense matching tasks demonstrate the superiority of our method in both efficiency and effectiveness against existing state-of-the-arts.
  arXiv  Detail & Related papers  (2022-09-25T13:05:33Z)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  We propose a Shapley value based method to evaluate operation contribution (Shapley-NAS) for neural architecture search. We show that our method outperforms the state-of-the-art methods by a considerable margin with light search cost.
  arXiv  Detail & Related papers  (2022-06-20T14:41:49Z)
• Featurized Density Ratio Estimation [82.40706152910292]
  In our work, we propose to leverage an invertible generative model to map the two distributions into a common feature space prior to estimation. This featurization brings the densities closer together in latent space, sidestepping pathological scenarios where the learned density ratios in input space can be arbitrarily inaccurate. At the same time, the invertibility of our feature map guarantees that the ratios computed in feature space are equivalent to those in input space.
  arXiv  Detail & Related papers  (2021-07-05T18:30:26Z)
• ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions [34.576469570537995]
  We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity.
  arXiv  Detail & Related papers  (2021-06-23T08:24:36Z)
• Learning Optical Flow from a Few Matches [67.83633948984954]
  We show that the dense correlation volume representation is redundant and accurate flow estimation can be achieved with only a fraction of elements in it. Experiments show that our method can reduce computational cost and memory use significantly, while maintaining high accuracy.
  arXiv  Detail & Related papers  (2021-04-05T21:44:00Z)
• Improving Approximate Optimal Transport Distances using Quantization [23.319746583489763]
  Optimal transport is a popular tool in machine learning to compare probability measures geometrically. Linear programming algorithms for computing OT scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access.
  arXiv  Detail & Related papers  (2021-02-25T08:45:06Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Scalable Distributed Approximation of Internal Measures for Clustering Evaluation [5.144809478361603]
  Internal measure for clustering evaluation is the silhouette coefficient, whose computation requires a quadratic number of distance calculations. We present the first scalable algorithm to compute such a rigorous approximation for the evaluation of clusterings based on any metric distances. We also prove that the algorithm can be adapted to obtain rigorous approximations of other internal measures of clustering quality, such as cohesion and separation.
  arXiv  Detail & Related papers  (2020-03-03T10:28:14Z)

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.