Cluster with Auctions for Vector Search

• URL: http://arxiv.org/abs/2607.13728v1
• Date: Wed, 15 Jul 2026 11:42:07 GMT
• Title: Cluster with Auctions for Vector Search
• Abstract summary: Large-scale approximate nearest neighbor search commonly relies on partitions for indexing.<n> query probing function and the database partition are rarely treated as separate entities.<n>This paper introduces CwA, which addresses this limitation by jointly learning a balanced database partition and a neural function.
• Score: 18.098804415480696
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large-scale approximate nearest neighbor search commonly relies on partitions for indexing: database vectors are partitioned into clusters, and for each query a probing function selects the clusters to be scanned. The query probing function and the database partition are rarely treated as separate entities: most techniques assign queries with the same assignment function as the database vectors, which is suboptimal especially when database and query distributions differ. This paper introduces CwA (Cluster with Auctions), which addresses this limitation by jointly learning a balanced database partition and a neural probing function. CwA optimizes search performance directly for the query distribution. It minimizes its objective by alternating two steps: (i) gradient descent on the neural network of the probing function, and (ii) a large-scale combinatorial optimization of the cluster assignment for the database vectors. We solve the latter with a parallelizable auction algorithm that balances the partition by design. To further scale CwA, we extend the method to a Cartesian product of clusters that increases the partition's granularity. When database and query distributions differ, CwA achieves up to 4.7$\times$ throughput over the state-of-the-art at equal recall. In the in-distribution (ID) setting, even a simple linear probing function trained with CwA outperforms competing deep neural methods.

Related papers

• Imputation Meets Clustering: Exploiting Latent Subgroup Structure for Missing Data Recovery [52.29866804948133]
  We propose CAGI (Cluster-Aware Generative Imputation), a framework that reformulates clustering and imputation as a mutually reinforcing co-optimization process.<n>Experiments on 14 benchmark datasets with 15 representative baselines demonstrate the superiority of CAGI.
  arXiv  Detail & Related papers  (2026-07-08T02:50:02Z)
• Hyperdimensional computing for structured querying on tabular data embeddings [2.260258863997296]
  Tabular data embeddings have become a cornerstone of data profiling and data integration pipelines.<n>Existing approaches embed rows, columns, or entire tables into a vector space and rely on nearest-neighbor search to retrieve candidate matches.<n>A fundamental limitation of current embedding methods is the lack of interpretable similarity scores.
  arXiv  Detail & Related papers  (2026-06-11T19:54:11Z)
• LIRA: A Learning-based Query-aware Partition Framework for Large-scale ANN Search [14.354312183838642]
  In the query phase, a common strategy is to probe partitions based on the distance ranks of a query to partition centroids.<n>In the partition construction phase, all partition-based methods face the boundary problem that separates a query's nearest neighbors to multiple partitions.<n>We propose LIRA, a LearnIng-based queRy-aware pArtition framework.
  arXiv  Detail & Related papers  (2025-03-30T12:03:57Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• SQLNet: Scale-Modulated Query and Localization Network for Few-Shot Class-Agnostic Counting [67.97870844244187]
  The class-agnostic counting (CAC) task has recently been proposed to solve the problem of counting all objects of an arbitrary class with several exemplars given in the input image.<n>We propose a novel localization-based CAC approach, termed Scale-modulated Query and Localization Network (Net)<n>It fully explores the scales of exemplars in both the query and localization stages and achieves effective counting by accurately locating each object and predicting its approximate size.
  arXiv  Detail & Related papers  (2023-11-16T16:50:56Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  This work presents an adaptive group testing framework for the range-based high dimensional near neighbor search problem. Our method efficiently marks each item in a database as neighbor or non-neighbor of a query point, based on a cosine distance threshold without exhaustive search. We show that, using softmax-based features, our method achieves a more than ten-fold speed-up over exhaustive search with no loss of accuracy.
  arXiv  Detail & Related papers  (2023-11-05T06:12:03Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• funLOCI: a local clustering algorithm for functional data [0.0]
  funLOCI is a three-step algorithm based on divisive hierarchical clustering. To deal with the large quantity of local clusters, an extra step is implemented to reduce the number of results to the minimum.
  arXiv  Detail & Related papers  (2023-05-22T12:51:58Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMS is proposed to use data clustering and pivot-based data transformation techniques to build learned indexes. Machine learning models are developed to approximate the position of each data record on the disk. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes.
  arXiv  Detail & Related papers  (2022-04-21T11:24:55Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.