論文の概要: Cluster with Auctions for Vector Search
- arxiv url: http://arxiv.org/abs/2607.13728v1
- Date: Wed, 15 Jul 2026 11:42:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-16 16:39:12.752424
- Title: Cluster with Auctions for Vector Search
- Title（参考訳）: ベクトル探索のためのオークション付きクラスタ
- Abstract要約: 大規模に近い近接探索は、インデックス化の分割によく依存する。
クエリプローブ関数とデータベースパーティションは、分離されたエンティティとして扱われることは滅多にありません。
本稿では、バランスの取れたデータベース分割とニューラルファンクションを共同で学習することで、この制限に対処するCwAを紹介する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: データベースベクトルはクラスタに分割され、各クエリに対して、探索関数はスキャン対象のクラスタを選択する。
ほとんどのテクニックは、特にデータベースとクエリの分布が異なる場合に、データベースベクトルと同じ割り当て関数でクエリを割り当てます。
本稿では、バランスの取れたデータベース分割とニューラル・プロービング関数を共同で学習することで、この制限に対処するCwA(Cluster with Auctions)を紹介する。
CwAはクエリ分布に対して直接検索性能を最適化する。
2つのステップを交互に行うことで目的を最小化する。
一 探索関数のニューラルネットワーク上の勾配降下、及び
(II)データベースベクトルに対するクラスタ割り当ての大規模な組合せ最適化。
設計による分割のバランスをとる並列化可能なオークションアルゴリズムで後者を解く。
CwAをさらにスケールするために、分割の粒度を増大させるクラスタのカルテアン積にメソッドを拡張します。
データベースとクエリの分散が異なる場合、CwAは同等のリコールで4.7$\times$スループットを達成する。
In-distribution (ID)設定では、CwAで訓練された単純な線形プローブ関数でさえ、競合するディープニューラルメソッドより優れている。
関連論文リスト
- Imputation Meets Clustering: Exploiting Latent Subgroup Structure for Missing Data Recovery [52.29866804948133]
本稿では、クラスタリングと命令を相互に強化する共最適化プロセスとして再構築するフレームワークであるCAGI(Cluster-Aware Generative Imputation)を提案する。
14のベンチマークデータセットと15の代表的なベースラインの実験は、CAGIの優位性を実証している。
論文 参考訳（メタデータ） (2026-07-08T02:50:02Z) - Hyperdimensional computing for structured querying on tabular data embeddings [2.260258863997296]
タブラルデータ埋め込みは、データプロファイリングとデータ統合パイプラインの基盤となっている。
既存のアプローチでは、行、列、またはテーブル全体をベクトル空間に埋め込んで、最も近い隣の検索を使って候補マッチングを検索する。
現在の埋め込み法の基本的な制限は、解釈可能な類似性スコアの欠如である。
論文 参考訳（メタデータ） (2026-06-11T19:54:11Z) - LIRA: A Learning-based Query-aware Partition Framework for Large-scale ANN Search [14.354312183838642]
クエリフェーズでは、クエリの距離ランクに基づいてパーティションを探索し、セントロイドをパーティションする方法が一般的である。
パーティション構築フェーズでは、すべてのパーティションベースのメソッドは、クエリの最も近い隣人を複数のパーティションに分離する境界問題に直面します。
我々はLearnIngベースのqueRy-aware pArtitionフレームワークであるLIRAを提案する。
論文 参考訳（メタデータ） (2025-03-30T12:03:57Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - SQLNet: Scale-Modulated Query and Localization Network for Few-Shot Class-Agnostic Counting [67.97870844244187]
CAC(class-agnostic counting)タスクは、最近、任意のクラスの全てのオブジェクトを、入力画像にいくつかの例を付与してカウントする問題を解くために提案されている。
我々は、スケール変調クエリーおよびローカライズネットワーク(Net)と呼ばれる、新しいローカライズベースのCACアプローチを提案する。
クエリとローカライゼーションの段階において、模範者のスケールを完全に探求し、各オブジェクトを正確に位置付けし、その近似サイズを予測することで、効果的なカウントを実現している。
論文 参考訳（メタデータ） (2023-11-16T16:50:56Z) - Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。
本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。
本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
論文 参考訳（メタデータ） (2023-11-05T06:12:03Z) - Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。
IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - funLOCI: a local clustering algorithm for functional data [0.0]
funLOCIは、分割階層クラスタリングに基づく3段階のアルゴリズムである。
大量のローカルクラスタを扱うために、結果の最小化のために余分なステップが実装されている。
論文 参考訳（メタデータ） (2023-05-22T12:51:58Z) - A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。
機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。
実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
論文 参考訳（メタデータ） (2022-04-21T11:24:55Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳（メタデータ） (2021-03-17T23:13:25Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。