論文の概要: Amora: Communication-Efficient Private Approximate Nearest Neighbors Search

• arxiv url: http://arxiv.org/abs/2610.21174v1
• Date: Thu, 15 Oct 2026 03:30:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:16.160621
• Title: Amora: Communication-Efficient Private Approximate Nearest Neighbors Search
• Title（参考訳）: Amora: 通信効率のよいプライベート近似の隣人検索
• Abstract要約: プライベートANNS(PANNS)は、クライアントがクエリを公開することなく、最も近い隣人を検索することを可能にする。 分割グラフインデックスにSimplePIRを適用する通信効率の高いPANNSシステムであるAmoraを提案する。 96から1024の次元と最大1000万のベクトルからなる5つのデータセット上でAmoraを評価する。
• 参考スコア（独自算出の注目度）: 9.309450370285534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate nearest neighbors search (ANNS) over cloud-hosted vector databases raises a critical privacy concern: the query vector, which often encodes sensitive user intent, is exposed to the server. Private ANNS (PANNS) allows a client to retrieve nearest neighbors without revealing its query. The state-of-the-art single-server scheme, Pacmann (ICLR'25), achieves high accuracy via graph-based search with private information retrieval (PIR), but incurs substantial communication overhead because each PIR query retrieves only a single vertex. We present Amora, a communication-efficient PANNS system that applies SimplePIR to a partitioned graph index so that one PIR query is amortized over many vertices. To retrieve as much of the distance and neighbor information the search needs under a limited communication budget, Amora adopts a dual-PIR split layout with two heterogeneous PIR matrices that stay balanced in dimension: VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal. This layout shifts the cost model of PIR query from per-vertex to per-partition, which significantly reduces the communication overhead. To further improve efficiency by reducing the number of scans and query rounds in the PIR database, Amora introduces batch PIR to pack multiple queries into one matrix multiplication, centroid-based pruning to filter unpromising partitions, and TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition. We evaluate Amora on five datasets spanning 96 to 1024 dimensions and up to 10 million vectors. Compared to Pacmann, Amora reduces online communication by 93--99% while achieving higher search accuracy.
• Abstract（参考訳）: クラウドにホストされたベクトルデータベース上での近似近傍検索(ANNS)は、重要なプライバシー上の懸念を提起する。 プライベートANNS(PANNS)は、クライアントがクエリを公開することなく、最も近い隣人を検索することを可能にする。 最先端のシングルサーバ方式であるPacmann (ICLR'25) は、プライベート情報検索(PIR)を用いたグラフベースの検索によって高い精度を達成するが、各PIRクエリが単一の頂点のみを取得するため、かなりの通信オーバーヘッドが発生する。 Amoraは、SimplePIRを分割グラフインデックスに適用し、多くの頂点上で1つのPIRクエリが償却される通信効率の高いPANNSシステムである。 限られた通信予算の下で、探索に必要な距離と近隣情報を検索するために、Amoraは2つの不均一なPIR行列を持つ二重PIR分割レイアウトを採用する: VecPIRは頂点の分割全体に対する内部積を同時に取得し、NbrPIRはグラフトラバーサルのサブグループ粒度で必要な隣接リストを検索する。 このレイアウトは、PIRクエリのコストモデルを頂点単位から分割単位にシフトし、通信オーバーヘッドを大幅に削減する。 PIRデータベースのスキャン数とクエリラウンド数を削減して効率をさらに向上するため、AmoraはバッチPIRを導入して、複数のクエリを1つの行列乗算にまとめる。 96から1024の次元と最大1000万のベクトルからなる5つのデータセット上でAmoraを評価する。 Pacmannと比較して、Amoraは検索精度を高めながら、オンラインコミュニケーションを93-99%削減する。

関連論文リスト

• Cascaded Retrieval with Cross-Modal Query Refinement for Efficient Visual Document Search [54.48124421246385]
  現在の視覚言語レトリバーは、コーパスサイズとともに成長し、スケールすることができないクエリ時間コストを発生させる。 本稿では,検索性能を徹底検索から分離する2トラック検索フレームワークSCOUTを提案する。 SCOUTを4つの主要なベンチマークで評価し、最高のベースラインに対して80.7倍(平均28.8倍)のクエリ時間遅延改善を観測した。
  論文  参考訳（メタデータ） (2026-10-14T15:40:27Z)
• PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval [6.4584274993673105]
  Retrieval-augmented Generation (RAG) は、ユーザのクエリをコーパスをホストする人に渡す。 プライベート情報検索(PIR)に基づくプライバシ保護RAG(PPRAG)システムであるPILLARを提案する。 PILLARを2つのプロトコルでインスタンス化し、検索品質とレイテンシを交換します。
  論文  参考訳（メタデータ） (2026-09-28T21:59:04Z)
• Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search [22.644268689842377]
  距離フィルタ近似近傍探索(RFANNS)はベクトルデータベースにとって重要なプリミティブである。 我々は、外部ソースの暗号化ベクタデータベース上でのプライバシー保護RFANNSを定式化し、評価する。 提案手法は,既存のRFANNSアプローチのセキュアな適応に対するQPS-リコールトレードオフを改善する。
  論文  参考訳（メタデータ） (2026-08-17T12:28:25Z)
• Lower Bounds for PIR with Preprocessing from Blackbox Cryptography [57.20693707878285]
  プリプロセッシングによるシングルサーバプライベート情報検索(PIR)の限界について検討する。 本研究は,プリプロセッシングを伴うシングルサーバPIRに対して,計算の低いバウンダリを提示する。
  論文  参考訳（メタデータ） (2026-07-07T16:12:48Z)
• GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
  GONDORはGreedy Best-First Search(GBFS)の拡張である GONDORは、アンカー状態のスパースセットを保持しながら周期的に探索木を圧縮し、ゴールに達するとスパース状態間の再探索によって経路を再構築する。 実験により、GONDORは標準のGBFSと比較して、低メモリ予算下でのカバレッジを一貫して改善することが示された。
  論文  参考訳（メタデータ） (2026-05-27T13:20:58Z)
• VLM2GeoVec: Toward Universal Multimodal Embeddings for Remote Sensing [59.73939718087177]
  シングルエンコーダの視覚言語モデルは、統合ベクトル空間にインターリーブされた入力を埋め込むために対照的に訓練された。 VLM2GeoVecは、領域レベルの空間推論とスケーラブルな検索を統合し、リモートセンシングにおける凝集性多モード解析を可能にする。
  論文  参考訳（メタデータ） (2025-12-12T11:39:35Z)
• Panorama: Fast-Track Nearest Neighbors [22.201421121801218]
  本稿では,機械学習によるアプローチであるPANORAMAを提案する。 PANORAMAは、2-30$times$ end-to-end speedupをリコールロスなしで利用できることを示す。
  論文  参考訳（メタデータ） (2025-10-01T06:38:45Z)
• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [13.809692299886715]
  この研究は、クラスタリングに基づく最大内部積探索におけるルーティングを研究することによってギャップを埋める。 各シャード内の内積分布のモーメントを組み込んで最大内積を推定する枠組みを提案する。
  論文  参考訳（メタデータ） (2024-05-20T17:47:18Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)

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

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