論文の概要: Private Aggregate Queries to Untrusted Databases
- arxiv url: http://arxiv.org/abs/2403.13296v1
- Date: Wed, 20 Mar 2024 04:35:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 17:58:10.560697
- Title: Private Aggregate Queries to Untrusted Databases
- Title(参考訳): 信頼できないデータベースへのプライベートアグリゲートクエリ
- Authors: Syed Mahbub Hafiz, Chitrabhanu Gupta, Warren Wnuck, Brijesh Vora, Chen-Nee Chuah,
- Abstract要約: プライベート情報検索(Private Information Search, PIR)は、プライバシ保護のための暗号ツールである。
ほとんどのPIRプロトコルは、クライアントが意図したデータベースアイテムの正確な行インデックスを知る必要がある。
我々は、ユーザが集約された結果を取得することができる新しい情報理論PIRフレームワークを構築した。
- 参考スコア(独自算出の注目度): 3.6209090009720155
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Private information retrieval (PIR), a privacy-preserving cryptographic tool, solves a simplified version of this problem by hiding the database item that a client accesses. Most PIR protocols require the client to know the exact row index of the intended database item, which cannot support the complicated aggregation-based statistical query in a similar setting. Some works in the PIR space contain keyword searching and SQL-like queries, but most need multiple interactions between the PIR client and PIR servers. Some schemes support searching SQL-like expressive queries in a single round but fail to enable aggregate queries. These schemes are the main focus of this paper. To bridge the gap, we have built a general-purpose novel information-theoretic PIR (IT-PIR) framework that permits a user to fetch the aggregated result, hiding all sensitive sections of the complex query from the hosting PIR server in a single round of interaction. In other words, the server will not know which records contribute to the aggregation. We then evaluate the feasibility of our protocol for both benchmarking and real-world application settings. For instance, in a complex aggregate query to the Twitter microblogging database of 1 million tweets, our protocol takes 0.014 seconds for a PIR server to generate the result when the user is interested in one of 3K user handles. In contrast, for a much-simplified task, not an aggregate but a positional query, Goldberg's regular IT-PIR (Oakland 2007) takes 1.13 seconds. For all possible user handles, 300K, it takes equal time compared to the regular IT-PIR. This example shows that complicated aggregate queries through our framework do not incur additional overhead if not less, compared to the conventional query.
- Abstract(参考訳): プライバシを保存する暗号ツールであるプライベート情報検索(PIR)は、クライアントがアクセスするデータベースアイテムを隠すことで、この問題の簡易バージョンを解決する。
ほとんどのPIRプロトコルは、クライアントが意図したデータベースアイテムの正確な行インデックスを知る必要がある。
PIRの分野での作業にはキーワード検索とSQLライクなクエリが含まれるが、ほとんどの場合、PIRクライアントとPIRサーバ間の複数のインタラクションが必要である。
一部のスキームはSQLライクな表現型クエリを1ラウンドで検索するが、集約型クエリを有効にすることができない。
これらのスキームが本論文の主な焦点である。
このギャップを埋めるために、我々は、ユーザが集約された結果を取得し、ホスティングPIRサーバから複雑なクエリのすべてのセンシティブなセクションを1ラウンドのインタラクションで隠蔽する、汎用的な新しい情報理論PIR(IT-PIR)フレームワークを構築した。
言い換えれば、サーバはどのレコードがアグリゲーションに寄与しているかを知らない。
次に、ベンチマークと実世界のアプリケーション設定の両方において、プロトコルの有効性を評価します。
例えば、Twitterのツイート100万件のマイクロブログデータベースへの複雑な集約クエリでは、PIRサーバが3Kユーザの処理に興味がある場合に結果を生成するのに0.014秒かかります。
対照的に、集約ではなく位置クエリである非常に単純化されたタスクでは、ゴールドバーグの通常のIT-PIR (Oakland 2007) は1.13秒かかる。
可能なすべてのユーザハンドラ、300Kでは、通常のIT-PIRと同等な時間を要する。
この例は、我々のフレームワークによる複雑な集約クエリは、従来のクエリと比較して、追加のオーバーヘッドを発生しないことを示している。
関連論文リスト
- Multi-Hop Table Retrieval for Open-Domain Text-to-SQL [55.2326738851157]
我々はリライトとビームサーチによるマルチホップテーブル検索を提案する(Murre)。
我々はSpiderUnionとBirdUnion+の実験を行い、6.38%の平均的な改善で新しい最先端の結果を得た。
論文 参考訳(メタデータ) (2024-02-16T13:14:35Z) - Fast Interactive Search with a Scale-Free Comparison Oracle [17.38671584773247]
比較ベースの検索アルゴリズムにより、ユーザはフォームのクエリに応答してデータベース内のターゲットアイテム$t$を見つけることができる。
そのような類似性三重項に対して$(i,j;t)$に対して$gamma$-CKLと呼ばれるスケールフリー確率オラクルモデルを提案する。
我々は,バックトラッキング戦略により,$gamma$-CKL のオラクルの下で,指数関数的に収束率の高い探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-06-02T09:33:19Z) - Context-Aware Query Rewriting for Improving Users' Search Experience on
E-commerce Websites [47.04727122209316]
電子商取引のクエリはしばしば短く曖昧である。
ユーザーは購入する前に複数の検索を入力し、それをコンテキストと呼ぶ。
本稿では,エンド・ツー・エンドのコンテキスト認識型クエリ書き換えモデルを提案する。
論文 参考訳(メタデータ) (2022-09-15T19:46:01Z) - Integrating connection search in graph queries [6.948362325254044]
SPARQLやCypherといったグラフクエリ言語に接続ツリーパターン(CTP)を統合する方法を示す。
非常に大きな探索空間に対処するため,我々は効率的な刈り込み手法を提案し,我々のアルゴリズムMOLESPがプルーニングでも完備しているケースの集合を正式に確立する。
論文 参考訳(メタデータ) (2022-08-09T14:27:57Z) - Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。
回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。
埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
論文 参考訳(メタデータ) (2022-04-27T11:16:08Z) - Graph Enhanced BERT for Query Understanding [55.90334539898102]
クエリ理解は、ユーザの検索意図を探索し、ユーザが最も望まれる情報を発見できるようにする上で、重要な役割を果たす。
近年、プレトレーニング言語モデル (PLM) は様々な自然言語処理タスクを進歩させてきた。
本稿では,クエリコンテンツとクエリグラフの両方を活用可能な,グラフ強化事前学習フレームワークGE-BERTを提案する。
論文 参考訳(メタデータ) (2022-04-03T16:50:30Z) - Parallel Instance Query Network for Named Entity Recognition [73.30174490672647]
名前付きエンティティ認識(NER)は自然言語処理の基本課題である。
最近の研究は、名前付きエンティティ認識を読み取り理解タスクとして扱い、エンティティを抽出するためにタイプ固有のクエリを手動で構築している。
本稿では,グローバルかつ学習可能なインスタンスクエリを並列に抽出するParallel Instance Query Network (PIQN)を提案する。
論文 参考訳(メタデータ) (2022-03-20T13:01:25Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳(メタデータ) (2021-10-05T20:15:35Z) - Counting Query Answers over a DL-Lite Knowledge Base (extended version) [14.504450881786214]
知識ベース(KB)上での問合せ応答の複雑さについて検討する。
我々はPTIMEとcoNPの下位境界と、PTIMEとLOGSPACEの上位境界を提供することで既存の結果を改善する。
論文 参考訳(メタデータ) (2020-05-12T16:01:09Z) - Don't Parse, Generate! A Sequence to Sequence Architecture for
Task-Oriented Semantic Parsing [0.0]
Amazon Alexa、Apple Siri、Google Assistantといったバーチャルアシスタントは、ユーザーが話す発話に対してどのアクションを実行するかを理解するために意味解析コンポーネントに依存することが多い。
本稿では,単純なクエリと複雑なクエリの両方を扱うために,Sequence to SequenceモデルとPointer Generator Networkに基づく統一アーキテクチャを提案する。
論文 参考訳(メタデータ) (2020-01-30T17:11:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。