論文の概要: HNSecW: A Logarithmic-Time MPC Protocol for Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2610.34248v1
• Date: Sun, 25 Oct 2026 12:22:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.566216
• Title: HNSecW: A Logarithmic-Time MPC Protocol for Approximate Nearest Neighbor Search
• Title（参考訳）: HNSecW: 近似近傍探索のための対数時間MPCプロトコル
• Abstract要約: HNSecWは、ANN検索のための新しいMPCプロトコルであり、初めて$O(log N)$検索時間を達成する。 完全にデータに依存しない実行を実現するために、オフラインのリシャッフルと部分的なデータベース重複を使用します。 実験の結果,HNSecWは100万規模データセットの事前処理よりも20倍以上の効率向上を実現していることがわかった。
• 参考スコア（独自算出の注目度）: 17.883596486426637
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: As a core component of modern RAG systems, approximate nearest neighbor (ANN) search has been extensively studied for decades. In practice, deploying ANN often requires symmetric privacy, where the querier's query and the database owner's data must remain hidden from each other, necessitating a secure multi-party computation (MPC) solution. So far, most MPC-based ANN protocols follow a cluster-based approach: they evaluate distances for the query over a large candidate set and rely on heavyweight primitives such as distributed ORAM to hide access patterns. As a result, each search typically requires $O(\sqrt{N})$ time. We propose HNSecW, a novel MPC protocol for ANN search that achieves the $O(\log N)$ search time for the first time. We first study the single-query setting. Starting from HNSW, the state-of-the-art ANN algorithm, we redesign its control flow and data structures to achieve fully data-independent execution. To further achieve logarithmic search time, we employ offline reshuffling and partial database duplication. Furthermore, we extend our protocol to support multiple sequential queries by introducing a "double visited" caching structure that eliminates redundant cross-query memory accesses, thereby avoiding per-query online shuffling. In addition, we develop a batch-query protocol that exploits higher parallelism to reduce both round complexity and the circuit's critical path. Our experiments show that HNSecW preserves the high accuracy of plaintext HNSW ($\geq 90\%$ recall) and delivers over a $20\times$ efficiency improvement over prior work on million-scale datasets.
• Abstract（参考訳）: 現代のRAGシステムの中核的な構成要素として、近接近接探索(ANN)が数十年にわたって広く研究されてきた。 実際には、ANNのデプロイは対称的なプライバシを必要とすることが多く、クエリーのクエリとデータベース所有者のデータは互いに隠さなければならないため、セキュアなマルチパーティ計算(MPC)ソリューションが必要になる。 これまでのところ、ほとんどのMPCベースのANNプロトコルはクラスタベースのアプローチに従っており、大きな候補セットよりもクエリの間隔を評価し、アクセスパターンを隠すために分散ORAMのような重いプリミティブに依存している。 その結果、各検索は通常$O(\sqrt{N})$timeを必要とする。 我々は,ANN検索のための新しいMPCプロトコルであるHNSecWを提案し,初めて$O(\log N)$検索時間を実現する。 最初はシングルクエリの設定を研究します。 最先端のANNアルゴリズムであるHNSWから始まり、制御フローとデータ構造を再設計し、完全にデータに依存しない実行を実現する。 さらに対数探索時間を達成するために、オフラインのリシャッフルと部分的なデータベース重複を用いる。 さらに、冗長なクロスクエリメモリアクセスを排除し、クエリごとのシャッフルを回避する「ダブルビジター」キャッシュ構造を導入することで、複数のシーケンシャルクエリをサポートするプロトコルを拡張した。 さらに,高い並列性を利用して,ラウンド複雑性と回路臨界経路の両方を低減するバッチクエリプロトコルを開発した。 実験の結果,HNSecW は平文 HNSW (\geq 90\%$ recall) の精度を保ち,100万規模のデータセットに対する以前の作業よりも20ドル以上の効率向上を実現していることがわかった。

関連論文リスト

• MESS: Fast and Private Semantic Search on Multi-Graph HNSW [11.990611521434944]
  プライバシ,正確性,効率性の3つの特性を持つ検索システムであるMESSを紹介する。 元のベクトルをバイナリコードにマッピングし、ローカリティ・センシティブなハッシュ(LSH)とランダムな応答を適用し、多グラフ階層ナビゲート可能な小型世界(HNSW)インデックスを摂動コード上に構築する。 MESSは、最先端のベースラインよりも最大15.08タイムのレイテンシを実現する。
  論文  参考訳（メタデータ） (2026-07-31T03:53:24Z)
• δ-EMG: A Monotonic Graph Index for Approximate Nearest Neighbor Search [33.62724124122037]
  本稿では,クエリ時における近似精度を制御する誤り境界付きANN探索アルゴリズムを提案する。 0.99のリコール条件下では、SIFT1Mデータセット上で19,000QPSを達成し、他の手法よりも40%以上性能が向上する。
  論文  参考訳（メタデータ） (2025-11-21T03:20:54Z)
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations [20.944914202453962]
  グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
  論文  参考訳（メタデータ） (2023-10-29T19:25:48Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。 我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。 提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
  論文  参考訳（メタデータ） (2021-12-05T06:42:48Z)
• OPANAS: One-Shot Path Aggregation Network Architecture Search for Object Detection [82.04372532783931]
  近年、ニューラルアーキテクチャサーチ (NAS) が特徴ピラミッドネットワーク (FPN) の設計に活用されている。 本稿では,探索効率と検出精度を大幅に向上させる,ワンショットパス集約ネットワークアーキテクチャ探索(OPANAS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-08T01:48:53Z)
• Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations [21.68175843347951]
  本稿では,ユーザとイテムのインタラクションデータを用いて,検索可能な構造を直接学習するために,Deep Retrieval(DR)を提案する。 DRは、産業レコメンデーションシステムのために数億のアイテムをスケールで展開した最初の非ANNアルゴリズムの1つである。
  論文  参考訳（メタデータ） (2020-07-12T06:23:51Z)

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

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