論文の概要: Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search

• arxiv url: http://arxiv.org/abs/2405.12207v1
• Date: Mon, 20 May 2024 17:47:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-21 12:25:40.564361
• Title: Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search
• Title（参考訳）: クラスタリングに基づく最大内積探索における最適クエリルーティング
• Authors: Sebastian Bruch, Aditya Krishnan, Franco Maria Nardini,
• Abstract要約: クラスタリングに基づく最大内部積探索(MIPS)におけるルーティングの問題について検討する。 最大内積を楽観的に推定するために,各シャード内の内積分布のモーメントを組み込んだ新しい枠組みを提案する。
• 参考スコア（独自算出の注目度）: 9.01394829787271
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering-based nearest neighbor search is a simple yet effective method in which data points are partitioned into geometric shards to form an index, and only a few shards are searched during query processing to find an approximate set of top-$k$ vectors. Even though the search efficacy is heavily influenced by the algorithm that identifies the set of shards to probe, it has received little attention in the literature. This work attempts to bridge that gap by studying the problem of routing in clustering-based maximum inner product search (MIPS). We begin by unpacking existing routing protocols and notice the surprising contribution of optimism. We then take a page from the sequential decision making literature and formalize that insight following the principle of ``optimism in the face of uncertainty.'' In particular, we present a new framework that incorporates the moments of the distribution of inner products within each shard to optimistically estimate the maximum inner product. We then present a simple instance of our algorithm that uses only the first two moments to reach the same accuracy as state-of-the-art routers such as \scann by probing up to $50%$ fewer points on a suite of benchmark MIPS datasets. Our algorithm is also space-efficient: we design a sketch of the second moment whose size is independent of the number of points and in practice requires storing only $O(1)$ additional vectors per shard.
• Abstract（参考訳）: クラスタリングに基づく近接探索は、データポイントを幾何学的シャードに分割してインデックスを形成し、クエリ処理中に数個のシャードのみを探索して、上位$k$ベクトルの近似集合を見つけるという、単純で効果的な方法である。 探索の有効性は探索するシャードの集合を識別するアルゴリズムの影響を強く受けているが、文献ではほとんど注目されていない。 本研究は,クラスタリングに基づく最大内積探索(MIPS)におけるルーティング問題を研究することにより,そのギャップを埋めようとするものである。 まず、既存のルーティングプロトコルをアンパックして、楽観主義の驚くべき貢献に気づきます。 次に、逐次的意思決定の文献からページを取得し、不確実性に直面した「最適化」の原則に従ってその洞察を定式化する。 特に、各シャード内の内積分布のモーメントを組み込んで、最大内積を楽観的に推定する新たな枠組みを提案する。 次に、我々のアルゴリズムの単純な例を示し、ベンチマークMIPSデータセットのスイートで最大50ドル以下のポイントを探索することにより、最初の2つのモーメントのみを使用して、 \scannのような最先端ルータと同じ精度に達する。 我々のアルゴリズムは空間効率も高い:我々は、点数に依存しない第2モーメントのスケッチを設計し、実際にはシャード毎に$O(1)$のベクトルのみを格納する必要がある。

関連論文リスト

• Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
  共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。 我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。 本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
  論文  参考訳（メタデータ） (2024-02-02T13:31:24Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
  論文  参考訳（メタデータ） (2021-04-18T07:46:28Z)
• Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects [0.0]
  Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。 この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。 本稿では,本手法の計算的側面について考察する。
  論文  参考訳（メタデータ） (2021-02-02T10:39:27Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。