論文の概要: O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2611.03415v1
• Date: Mon, 02 Nov 2026 16:38:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 04:43:42.43977
• Title: O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search
• Title（参考訳）: O2N2: 効率の良い2倍近い近似的隣人検索
• Abstract要約: O2N2は、ランダムに回転した$k$dの木林において、シングルパス探索を中心に構築された、二重に曖昧なANNフレームワークである。 ポインタベースのCircuit ORAMは、検索構造を格納し、コンパクトな内部ノードとベクトルを持つ葉を別々に格納する。 10-NNと100-NNで指定されたハイリコールターゲットを検索すると、最大2倍のベースラインで$mathrmO(log2 N)$のスピードアップが達成される。
• 参考スコア（独自算出の注目度）: 7.851195946612678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Privacy-preserving approximate nearest neighbor (ANN) search allows clients to search from an untrusted server without revealing sensitive queries, and is useful in scenarios like medical diagnostics and credit scoring. Among the various privacy-preserving primitives, trusted execution environments (TEEs) have much lower overhead than heavy cryptographic ones, yet they leak memory access patterns, enabling adversaries to infer query contents. Oblivious RAM (ORAM) can be used to hide those access patterns at $\mathrm{O}(\log N)$ asymptotic cost, but existing high-performance ANN search algorithms (e.g., IVF or HNSW) exhibit complex, data-dependent access patterns that are unfriendly for ORAM. Furthermore, standard ORAM constructions typically assume there exists a small amount of trusted storage, which weakens the security guarantees and is not always feasible. Solutions that eliminate such trusted storage (known as {\em double obliviousness}) typically degrade performance further to $\mathrm{O}(\log^2 N)$. We introduce O2N2, a doubly oblivious ANN framework built around single-path search in randomly rotated $k$-d tree forests. A pointer-based Circuit ORAM stores the search structure, with separate storage for compact internal nodes and vector-bearing leaves. Each visited leaf is processed by an oblivious selection network, and fixed-schedule duplicate removal and selection combine the local results into the final top-$k$. We evaluate O2N2 on real-world datasets and further test its scalability on 100 million vectors. For 10-NN and 100-NN search at the specified high-recall targets, it achieves a $9.8$--$125.9\times$ speedup over the fastest doubly oblivious baselines.
• Abstract（参考訳）: プライバシ保存に近づいた近接検索(ANN)により、クライアントは機密性の高いクエリを明らかにすることなく、信頼できないサーバから検索することが可能になり、医療診断やクレジットスコアリングといったシナリオで有用である。 さまざまなプライバシ保護プリミティブの中で、信頼できる実行環境(TEE)は重い暗号化環境よりもオーバーヘッドがはるかに低いが、メモリアクセスパターンをリークし、敵がクエリ内容を推測できるようにする。 ORAM(Oblivious RAM)は、これらのアクセスパターンを$\mathrm{O}(\log N)$ asymptotic costで隠すために使用できるが、既存の高性能ANN検索アルゴリズム(例:IVF、HNSW)はORAMに不都合な複雑なデータ依存アクセスパターンを示す。 さらに、標準的なORAM構成では、セキュリティ保証を弱め、常に実現可能であるとは限らない、少量の信頼できるストレージが存在すると仮定することが多い。 このような信頼されたストレージを排除したソリューション(「ダブル・オブリビエンスネス」と呼ばれる)は、通常、性能を$\mathrm{O}(\log^2 N)$に下げる。 O2N2は、ランダムに回転した$k$dの木林において、シングルパス探索を中心に構築された、二重に曖昧なANNフレームワークである。 ポインタベースのCircuit ORAMは、検索構造を格納し、コンパクトな内部ノードとベクトルを持つ葉を別々に格納する。 訪問した各葉は、不可解な選択ネットワークによって処理され、固定スケジュールの重複除去と選択は、ローカルの結果を最終トップ-k$に組み合わせる。 我々は,実世界のデータセット上でO2N2を評価し,そのスケーラビリティを1億ベクトル上でさらに検証する。 10-NNと100-NNで指定されたハイリコールターゲットを検索すると9.8$-125.9\times$のスピードアップが達成される。

関連論文リスト

• HNSecW: A Logarithmic-Time MPC Protocol for Approximate Nearest Neighbor Search [17.883596486426637]
  HNSecWは、ANN検索のための新しいMPCプロトコルであり、初めて$O(log N)$検索時間を達成する。 完全にデータに依存しない実行を実現するために、オフラインのリシャッフルと部分的なデータベース重複を使用します。 実験の結果,HNSecWは100万規模データセットの事前処理よりも20倍以上の効率向上を実現していることがわかった。
  論文  参考訳（メタデータ） (2026-10-25T12:22:21Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• 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)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues [0.0]
  我々は,メモリアクセスのシーケンスを事前に把握している,いわゆるオフラインORAMについて検討する。 我々は、時間フォワード処理により、不要な優先度待ち行列から完全なセキュリティを備えた、最初の最適オフラインORAMを得る。 我々の構築に基づいて、我々はまた、不明瞭で完全にセキュアな構成の効率的な外部メモリインスタンス化を提示する。
  論文  参考訳（メタデータ） (2024-09-18T14:31:33Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
  論文  参考訳（メタデータ） (2024-05-07T15:57:39Z)
• Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search [57.18075258042082]
  このコンペティションは、ANNSアルゴリズムをハードウェアコスト、精度、性能で数十億ドル規模で比較する。 このコンペティションのために新たに4つの、60億の多様なデータセットをまとめました。
  論文  参考訳（メタデータ） (2022-05-08T02:41:54Z)
• SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search [39.361122198195076]
  本稿では,SPANNというメモリディスクハイブリッドインデックスと検索システムを提案する。 ポストリストのセントロイドポイントをメモリに、大きなポストリストをディスクに格納する。 リコール@1とリコール@10はわずか1ミリ秒で、メモリは32GBだ。
  論文  参考訳（メタデータ） (2021-11-05T06:28:15Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)

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

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