論文の概要: Private Information Retrieval for Graph-based Replication with Minimal Subpacketization
- arxiv url: http://arxiv.org/abs/2601.09957v1
- Date: Thu, 15 Jan 2026 00:34:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-16 19:43:18.932608
- Title: Private Information Retrieval for Graph-based Replication with Minimal Subpacketization
- Title（参考訳）: 最小部分パッケージ化によるグラフベースレプリケーションのためのプライベート情報検索
- Authors: Vayur Shanbhag, Prasad Krishnan,
- Abstract要約: グラフベース複製データベースにおける情報理論的プライベート情報検索のための最小サブパッケージ化方式を新たに設計する。
グラフベースのレプリケーションでは、システムは$N$サーバ間で複製された$K$ファイルで構成され、グラフには$N$ verticesと$K$ edgeがある。
クライアントは、クエリ応答プロトコルを介して、各サーバから所望のファイルのインデックスをプライベートに保ちながら、1つの所望のファイルを検索したい。
- 参考スコア（独自算出の注目度）: 3.795745240553126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We design new minimal-subpacketization schemes for information-theoretic private information retrieval on graph-based replicated databases. In graph-based replication, the system consists of $K$ files replicated across $N$ servers according to a graph with $N$ vertices and $K$ edges. The client wants to retrieve one desired file, while keeping the index of the desired file private from each server via a query-response protocol. We seek PIR protocols that have (a) high rate, which is the ratio of the file-size to the total download cost, and (b) low subpacketization, which acts as a constraint on the size of the files for executing the protocol. We report two new schemes which have unit-subpacketization (which is minimal): (i) for a special class of graphs known as star graphs, and (ii) for general graphs. Our star-graph scheme has a better rate than previously known schemes with low subpacketization for general star graphs. Our scheme for general graphs uses a decomposition of the graph via independent sets. This scheme achieves a rate lower than prior schemes for the complete graph, however it can achieve higher rates than known for some specific graph classes. An extension of our scheme to the case of multigraphs achieves a higher rate than previous schemes for the complete multi-graph.
- Abstract（参考訳）: グラフベース複製データベースにおける情報理論的プライベート情報検索のための最小サブパッケージ化方式を新たに設計する。
グラフベースのレプリケーションでは、システムは$N$サーバ間で複製された$K$ファイルで構成され、グラフには$N$ verticesと$K$ edgeがある。
クライアントは、クエリ応答プロトコルを介して、各サーバから所望のファイルのインデックスをプライベートに保ちながら、1つの所望のファイルを検索したい。
我々は、PIRプロトコルを求めます。
(a)ファイルサイズとダウンロード総コストの比率であるハイレート、及び
b) プロトコルを実行するファイルのサイズの制約として機能する低サブパッケージ化。
ユニットサブパッケージ化(最小限)を持つ2つの新しいスキームを報告する。
(i)スターグラフと呼ばれる特殊なグラフのクラスに対して、
(ii) は一般グラフである。
我々の星グラフスキームは、一般的な星グラフのサブパッケージ化が低い既知のスキームよりも優れている。
一般グラフに対する我々のスキームは、独立集合によるグラフの分解を利用する。
このスキームは、完備グラフの以前のスキームよりも低いレートを達成するが、特定のグラフクラスで知られているよりも高いレートを達成することができる。
マルチグラフの場合への我々のスキームの拡張は、完全マルチグラフの以前のスキームよりも高いレートを達成する。
関連論文リスト
- Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
データベースの複製を単純なグラフでモデル化した環境で、対称なプライベート情報検索の問題を再考する。
メッセージとは独立して、すべてのサーバに共通するランダム性を共有させます。
所望シンボル数とダウンロードシンボル数の最大比であるSPIR容量の改善を定量化する。
論文 参考訳（メタデータ） (2025-10-29T17:40:40Z) - 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) - MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。
最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。
本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
論文 参考訳（メタデータ） (2024-01-10T07:58:44Z) - Graph Generation with $K^2$-trees [13.281380233427287]
K2$-tree表現を利用した新しいグラフ生成手法を提案する。
また、プルーニング、フラットニング、トークン化プロセスを組み込んだシーケンシャルな$K2$-treerepresentationを提示する。
グラフ生成の優位性を確認するため,本アルゴリズムを4つの一般および2つの分子グラフデータセット上で広範囲に評価した。
論文 参考訳（メタデータ） (2023-05-30T15:36:37Z) - EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
埋め込みによるグラフリファインメントクラスタリングネットワーク (EGRC-Net) という新しいグラフクラスタリングネットワークを提案する。
EGRC-Netは学習した埋め込みを利用して初期グラフを適応的に洗練し、クラスタリング性能を向上させる。
提案手法はいくつかの最先端手法より一貫して優れている。
論文 参考訳（メタデータ） (2022-11-19T09:08:43Z) - Variational Graph Generator for Multi-View Graph Clustering [51.89092260088973]
マルチビューグラフクラスタリング(VGMGC)のための変分グラフ生成器を提案する。
この生成器は、複数のグラフに対する事前仮定に基づいて、信頼性のある変分コンセンサスグラフを推論する。
推論されたビュー共通グラフとビュー固有のグラフを機能と一緒に埋め込む。
論文 参考訳（メタデータ） (2022-10-13T13:19:51Z) - Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
ノードがグラフのインスタンスである階層グラフにおけるノード分類問題について検討する。
本稿では階層グラフ相互情報(HGMI)を提案し,理論的保証をもってHGMIを計算する方法を提案する。
本稿では,この階層グラフモデリングとSEAL-CI法がテキストおよびソーシャルネットワークデータに与える影響を実証する。
論文 参考訳（メタデータ） (2022-06-11T04:05:29Z) - Scaling R-GCN Training with Graph Summarization [71.06855946732296]
リレーショナルグラフ畳み込みネットワーク(R-GCN)のトレーニングは、グラフのサイズに合わない。
本研究では,グラフの要約手法を用いてグラフを圧縮する実験を行った。
AIFB, MUTAG, AMデータセットについて妥当な結果を得た。
論文 参考訳（メタデータ） (2022-03-05T00:28:43Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。
AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。
本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
論文 参考訳（メタデータ） (2021-05-22T07:05:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。