論文の概要: Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems
- arxiv url: http://arxiv.org/abs/2507.17736v1
- Date: Wed, 23 Jul 2025 17:51:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-24 22:33:15.117776
- Title: Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems
- Title（参考訳）: グラフベースレプリケーションシステムにおけるSPIR(Symmetric Private Information Retrieval)
- Authors: Shreya Meel, Sennur Ulukus,
- Abstract要約: 単純なグラフでモデル化された複製されたデータベース上の対称プライベート情報検索。
本研究では,SPIRを実現するのに必要なサーバ側の共通乱数性も,そのグラフに従ってサーバに複製されるような設定について考察する。
- 参考スコア（独自算出の注目度）: 35.16231062731263
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs.
- Abstract（参考訳）: 簡単なグラフでモデル化した複製データベース上での対称プライベート情報検索(SPIR)の問題を紹介する。
このモデルでは、各頂点がサーバに対応し、メッセージが2つのサーバで複製される。
本研究では,SPIRを実現するのに必要なサーバ側の共通乱数性も,そのグラフに従ってサーバに複製されるような設定について検討し,これをメッセージ固有の共通乱数性と呼ぶ。
この設定では、達成可能なSPIRスキームを提案し、SPIR容量、すなわち一般グラフの最大ダウンロード率を低く設定する。
次に、任意のSPIRスキームが実現可能であるためには、メッセージ固有のランダムネスの最小サイズがメッセージのサイズに等しいことを証明する。
最後に、一致する上限を提供することにより、経路と正則グラフのクラスに対する正確なSPIR容量を導出する。
関連論文リスト
- New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage [39.51026717015587]
グラフベースおよびマルチグラフベースの複製システムにおけるプライベート情報検索(PIR)の問題について検討する。
このような系に対するPIR容量の上限を導出し、これらの境界に近づくPIRスキームを構築する。
論文 参考訳（メタデータ） (2025-04-29T16:05:42Z) - Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
多重グラフを用いた複製システムにおけるプライベート情報検索問題について考察する。
我々の目標は、$r$-multigraphのPIR容量の上下境界を確立することです。
論文 参考訳（メタデータ） (2025-01-29T18:48:22Z) - Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
共有インタラクション(SI)は、複数のノード間のノードのコントリビューションとインタラクションを定量化する。
GNNアーキテクチャを利用して、ノード埋め込みにおける相互作用の構造がグラフ予測のために保存されていることを示す。
任意の順序SIを正確に計算するための効率的なアプローチであるGraphSHAP-IQを導入する。
論文 参考訳（メタデータ） (2025-01-28T13:37:44Z) - Signed Diverse Multiplex Networks: Clustering and Inference [4.070200285321219]
本稿では,エッジを肯定的あるいは否定的に得るSGRDPG(Signed Generalized Random Dot Product Graph)モデルを提案する。
設定は多重バージョンに拡張され、すべてのレイヤが同じノードのコレクションを持ち、SGRDPGに従う。
本稿では,新しい手法を用いることで,階層の強い一貫したクラスタリングと高精度な部分空間推定を実現する。
論文 参考訳（メタデータ） (2024-02-14T19:37:30Z) - FedRA: A Random Allocation Strategy for Federated Tuning to Unleash the
Power of Heterogeneous Clients [50.13097183691517]
実世界のフェデレーションシナリオでは、様々な計算と通信資源を持つ多種多様なクライアントが存在することが多い。
本稿では,新しいフェデレーションチューニングアルゴリズムであるFedRAを提案する。
各通信ラウンドにおいて、FedRAはランダムにアロケーション行列を生成する。
アダプタを用いてアロケーション行列とファインチューンに基づいて、元のモデルから少数のレイヤを再編成する。
論文 参考訳（メタデータ） (2023-11-19T04:43:16Z) - Graph Federated Learning for CIoT Devices in Smart Home Applications [23.216140264163535]
G-Fedfilt'と呼ばれるグラフフィルタリングに基づく新しいグラフ信号処理(GSP)に基づく集約ルールを提案する。
提案するアグリゲータは,グラフのトポロジに基づく情報の流れを構造化することができる。
モデルの一般化をテストする場合、FedAvgよりも2.41%$高い精度が得られる。
論文 参考訳（メタデータ） (2022-12-29T17:57:19Z) - EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
埋め込みによるグラフリファインメントクラスタリングネットワーク (EGRC-Net) という新しいグラフクラスタリングネットワークを提案する。
EGRC-Netは学習した埋め込みを利用して初期グラフを適応的に洗練し、クラスタリング性能を向上させる。
提案手法はいくつかの最先端手法より一貫して優れている。
論文 参考訳（メタデータ） (2022-11-19T09:08:43Z) - Multi-Granularity Graph Pooling for Video-based Person Re-Identification [14.943835935921296]
ビデオサンプルの時間的特徴と空間的特徴を集約するためにグラフニューラルネットワーク(GNN)が導入された。
STGCNのような既存のグラフベースのモデルは、グラフ表現を得るためにノード機能でtextitmean/textitmaxプールを実行する。
ビデオ検索のための多粒度グラフ表現を学習するためのグラフプーリングネットワーク(GPNet)を提案する。
論文 参考訳（メタデータ） (2022-09-23T13:26:05Z) - Long Range Graph Benchmark [32.317725340138104]
単にワンホップメッセージパッシングに頼るMP-GNNは、既存のグラフベンチマークでよく使われる。
ベースラインのGNNとGraph Transformerネットワークの両方をベンチマークし、長距離依存をキャプチャするモデルがこれらのタスクにおいて著しく優れていることを検証した。
論文 参考訳（メタデータ） (2022-06-16T13:33:22Z) - Jointly Cross- and Self-Modal Graph Attention Network for Query-Based
Moment Localization [77.21951145754065]
本稿では,共同グラフを渡る反復的メッセージのプロセスとして,このタスクをリキャストするクロスモーダルグラフ注意ネットワーク(CSMGAN)を提案する。
CSMGANは2つのモード間の高次相互作用を効果的に捉えることができ、より正確な局所化を可能にします。
論文 参考訳（メタデータ） (2020-08-04T08:25:24Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。