論文の概要: 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シミュレーションやセキュリティ仮定に頼らずに動作するマルチウェイ結合処理のためのソートに基づく新しいアルゴリズムを提案する。 我々のアルゴリズムは、安全でない最悪ケースの最適結合アルゴリズムと対数係数を一致させる時間的複雑さを持つ、基本的なプリミティブの非自明で明白な構成である。 さらに、キャッシュに依存しないため、安全でない低いバウンダリと一致するキャッシュの複雑さが、対数係数にまで達する。 このクリーンで簡単なアプローチは、他のセキュリティ設定にまで拡張され、実用的なデータベースシステムで実装される可能性がある。

関連論文リスト

• Encrypted system identification as-a-service via reliable encrypted matrix inversion [0.0]
  暗号化された計算は、多数のアプリケーションドメインにわたる有望な道を開く。 特に、算術的同型暗号化はクラウドベースの計算サービスに自然に適合する。 本稿では,少なくとも2乗問題に対する信頼性の高い暗号化ソリューションにより,暗号化されたシステム識別サービスを提案する。
  論文  参考訳（メタデータ） (2024-10-27T20:00:04Z)
• An Algorithm for Streaming Differentially Private Data [7.726042106665366]
  我々は、特に空間データセットに対して計算された、微分プライベートな合成ストリーミングデータ生成のためのアルゴリズムを導出する。 本アルゴリズムの有効性は実世界とシミュレーションデータセットの両方で検証される。
  論文  参考訳（メタデータ） (2024-01-26T00:32:31Z)
• 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)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Safeguarded Learned Convex Optimization [106.81731132086851]
  解析最適化アルゴリズムは、反復的な方法で問題を確実に解くために手作業で設計することができる。 データ駆動アルゴリズムは、汎用最適化アルゴリズムと同様のイテレーション当たりのコストと、はるかに少ないイテレーションで"L2O"を最適化する。 我々はこれらのアプローチの利点を融合させるSafe-L2Oフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-04T04:01:15Z)

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

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