WANを介して効率的なグラフデータ構造を送信

Question

私はWAN経由でプロパティグラフを送信する効率的な方法を探しています。レイテンシと帯域幅のために、できるだけ効率的にする必要があります。 1つの解決策は、グラフのデータ構造をシリアライズし、それをソケット上に小さなサイズのチャンクで送ることです。このアプローチは、異なる方法で実施することができる。おそらく最も明白な実装は、すべてのエッジに対してトリプル（頂点 - エッジ - 頂点）の直列化されたリスト内にグラフを送り、すべての切断された頂点に対して直列化された頂点を送ることでしょう。しかし、頂点は複数回送信され、多くの帯域幅を使用できるため、このソリューションは効率的ではありません。

私はグラフデータ構造を知るには、隣接リストと隣接行列を使用して転送することができますが、私は直列化の道をそれを把握し、これらのフォームにWANを介していることを送信することはできません。誰かが効率的なソリューションを手伝ってくれたら本当に感謝しています。

Answer 1

隣接行列を使用する場合は、n^2個の頂点接続を指定する必要があるため、不要なデータを送信する問題があります。そのため、非常に疎結合のグラフがある場合は、少なくともn^2ビットの情報を送信する。

n^2ビット+ 1バイトの情報しか使用しない単純な解決策の1つは、暗黙的に隣接行列を送信することです。

nの頂点があるとします。 1...nから任意に番号を付けてください。次に、n x n隣接行列Aを作成します。この場合、そのような接続が存在しない場合は、i〜jと0のエッジが存在する場合、A(i,j)==1が作成されます。ご覧のように、隣接行列を指定するにはn^2ビット（バイトではありません）だけが必要です。

最初に1バイト（32ビット）、つまりintを使用して、マトリックスのサイズを指定します（n）。次に、次のn^2ビットは隣接行列でなければなりません。

デシリアライズするには、最初のバイトを読み取って隣接行列のサイズを調べ、エッジ接続の次のn^2ビットを読み出します。

注：概念的に考えるのが簡単になるようにここで用語マトリックスを使用していますが、データを明示的にマトリックス形式で構成する必要はなく、線形に格納することができます。その後、行ijにアクセスするには、単にA(i*n+j)を実行します。

明らかに、このソリューションはグラフ構造を送信するだけで、グラフに含まれる実際のデータは送信しません。しかし、グラフに含まれている実際のデータを送信しなければならない場合でも、これはまだ良い考えですと思っています。グラフ構造があれば、残りのデータをシリアル化して、違った終わり方。