論文の概要: Optimal Oblivious Algorithms for Multi-way Joins

• arxiv url: http://arxiv.org/abs/2501.04216v2
• Date: Thu, 09 Jan 2025 03:02:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-10 10:39:54.347533
• Title: Optimal Oblivious Algorithms for Multi-way Joins
• Title（参考訳）: マルチウェイ結合のための最適省略アルゴリズム
• Authors: Xiao Hu, Zhiang Wu,
• Abstract要約: 我々は,ORAMシミュレーションや他のセキュリティ仮定に頼らずに動作するマルチウェイ結合処理のためのソートに基づく新しいアルゴリズムを提案する。 我々のアルゴリズムは、安全でない最悪ケースの最適結合アルゴリズムと対数係数を一致させる時間的複雑さを持つ、基本的なプリミティブの非自明で明白な構成である。
• 参考スコア（独自算出の注目度）: 2.8151472703172398
• License:
• Abstract: In cloud databases, cloud computation over sensitive data uploaded by clients inevitably causes concern about data security and privacy. Even when encryption primitives and trusted computing environments are integrated into query processing to safeguard the actual contents of the data, access patterns of algorithms can still leak private information about the data. Oblivious Random Access Memory (ORAM) and circuits are two generic approaches to address this issue, ensuring that access patterns of algorithms remain oblivious to the data. However, deploying these methods on insecure algorithms, particularly for multi-way join processing, is computationally expensive and inherently challenging. In this paper, we propose a novel sorting-based algorithm for multi-way join processing that operates without relying on ORAM simulations or other security assumptions. Our algorithm is a non-trivial, provably oblivious composition of basic primitives, with time complexity matching the insecure worst-case optimal join algorithm, up to a logarithmic factor. Furthermore, it is cache-agnostic, with cache complexity matching the insecure lower bound, also up to a logarithmic factor. This clean and straightforward approach has the potential to be extended to other security settings and implemented in practical database systems.
• Abstract（参考訳）: クラウドデータベースでは、クライアントがアップロードした機密データに対するクラウド計算が、データセキュリティとプライバシに関する懸念を必然的に引き起こす。 暗号化プリミティブと信頼性の高いコンピューティング環境がクエリ処理に統合され、実際のデータ内容が保護されたとしても、アルゴリズムのアクセスパターンはデータに関するプライベート情報を漏洩させる可能性がある。 ORAM(Oblivious Random Access Memory)とサーキットは、この問題に対処するための2つの一般的なアプローチであり、アルゴリズムのアクセスパターンがデータに無関心であることを保証する。 しかし、特にマルチウェイ結合処理において、これらの手法を安全でないアルゴリズムにデプロイすることは、計算コストが高く、本質的に困難である。 本稿では,ORAMシミュレーションやセキュリティ仮定に頼らずに動作するマルチウェイ結合処理のためのソートに基づく新しいアルゴリズムを提案する。 我々のアルゴリズムは、安全でない最悪ケースの最適結合アルゴリズムと対数係数を一致させる時間的複雑さを持つ、基本的なプリミティブの非自明で明白な構成である。 さらに、キャッシュに依存しないため、安全でない低いバウンダリと一致するキャッシュの複雑さが、対数係数にまで達する。 このクリーンで簡単なアプローチは、他のセキュリティ設定にまで拡張され、実用的なデータベースシステムで実装される可能性がある。

関連論文リスト

• Sublinear-Overhead Secure Linear Algebra on a Dishonest Server [3.8105803634609483]
  我々は、高速、遠隔、およびデータ公開線形代数に対する自然効率性とセキュリティデシラタを述べる。 我々は、満足なアルゴリズムを暗示する行列とベクトル族の存在を予想し、共通暗号仮定に基づくそのようなアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2025-02-18T17:05:17Z)
• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
  論文  参考訳（メタデータ） (2025-02-13T01:27:11Z)
• Encrypted system identification as-a-service via reliable encrypted matrix inversion [0.0]
  暗号化された計算は、多数のアプリケーションドメインにわたる有望な道を開く。 特に、算術的同型暗号化はクラウドベースの計算サービスに自然に適合する。 本稿では,少なくとも2乗問題に対する信頼性の高い暗号化ソリューションにより,暗号化されたシステム識別サービスを提案する。
  論文  参考訳（メタデータ） (2024-10-27T20:00:04Z)
• Encoding of data sets and algorithms [0.0]
  多くの高インパクトアプリケーションにおいて、機械学習アルゴリズムの出力品質を保証することが重要である。 我々は、ある指標の観点から、どのモデルが互いに近いかを決定するために、数学的に厳密な理論を開始した。 このグリッドに作用する所定のしきい値メートル法は、それぞれのアルゴリズムと関心のデータセットから、任意のアプリケーションに近接性(または統計的距離)を表現します。
  論文  参考訳（メタデータ） (2023-03-02T05:29:27Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。 本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。 各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
  論文  参考訳（メタデータ） (2020-06-17T18:14:30Z)
• Safeguarded Learned Convex Optimization [106.81731132086851]
  解析最適化アルゴリズムは、反復的な方法で問題を確実に解くために手作業で設計することができる。 データ駆動アルゴリズムは、汎用最適化アルゴリズムと同様のイテレーション当たりのコストと、はるかに少ないイテレーションで"L2O"を最適化する。 我々はこれらのアプローチの利点を融合させるSafe-L2Oフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-04T04:01:15Z)

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

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