数十億エッジのグラフにおける経路探索をWormHoleがどのように高速化するか

リンク一覧

概要と1. はじめに

1.1 私たちの貢献

1.2 設定

1.3 アルゴリズム

1. 関連研究

2. アルゴリズム

   3.1 構造分解フェーズ

   3.2 ルーティングフェーズ

   3.3 WormHoleのバリエーション

3. 理論的分析

   4.1 前提条件

   4.2 内部リングのサブリニア性

   4.3 近似誤差

   4.4 クエリ複雑性

4. 実験結果

   5.1 WormHole𝐸、WormHole𝐻とBiBFS

   5.2 インデックスベースの手法との比較

   5.3 基本要素としてのWormHole：WormHole𝑀

参考文献

1.1 私たちの貢献

私たちは、多くのソーシャルネットワークや情報ネットワークの典型的な構造を活用して、複数の最短経路の問い合わせに答えることができるデータ構造を作成する新しいアルゴリズム、WormHoleを設計しました。WormHoleはシンプルで実装が容易であり、理論的にも裏付けられています。私たちはさまざまな設定に適した複数のバリエーションを提供し、様々なネットワークデータセットで優れた実証結果を示しています。以下はその主な特徴です：

\ • パフォーマンスと精度のトレードオフ。 私たちの知る限り、これは大規模ネットワークにおける初めての近似サブリニア最短経路アルゴリズムです。小さな加算誤差を許容することで、前処理時間/空間と問い合わせごとの時間のトレードオフが生じ、効率的な前処理と高速な問い合わせ時間を持つ解決策を提供することができます。

\

\ 特に、最も精度が高い（しかし最も遅い）バリエーションであるWormHole𝐸は、ほぼ完璧な精度を持っています：問い合わせの90%以上が加算誤差なしで回答され、すべてのネットワークで問い合わせの99%以上が最大でも2の加算誤差で回答されます。詳細については表3をご覧ください。

\ • 非常に高速なセットアップ時間。 10億エッジのグラフでも、最長のインデックス構築時間はわずか2分でした。参考として、テストしたネットワークの半分でPLLとMLLはタイムアウトし、PLLとMLLが実行を完了した中規模のグラフでは、WormHoleのインデックス構築は100倍速かったです。つまり、WormHoleは数秒で完了したのに対し、PLLは数時間かかりました。表4と表5をご覧ください。この高速なセットアップ時間は、サブリニアサイズのインデックスを使用することで達成されています。私たちが検討した最大のネットワークでは、小さな平均加算誤差を得るためにノードの約1%のインデックスを取るだけで十分です - 表1をご覧ください。小さなネットワークでは、最大6%になる場合があります。

\ • 高速な問い合わせ時間。 BiBFSと比較して、バニラバージョンのWormHole𝐸（インデックスベースの最適化なし）はほぼすべてのグラフで2倍速く、テストした3つの最大グラフでは4倍以上速いです。シンプルなバリエーションであるWormHole𝐻は、精度を犠牲にして桁違いの改善を達成しています：ほぼすべてのグラフで一貫して20倍速く、私たちが持つ最大のグラフでは180倍以上速いです。完全な比較については表3をご覧ください。インデックスベースの手法は通常、マイクロ秒単位で問い合わせに回答します。前述の両方のバリエーションはまだミリ秒の領域にあります。

\ • WormHoleと最先端技術の組み合わせ。WormHoleは、正確な最短経路を計算する頂点の小さなサブセットを保存することで機能します。任意の問い合わせに対して、私たちはこのサブセット（コアと呼ぶ）を通じて経路をルーティングします。この洞察を活用して、コア上で最短経路の最先端技術であるMLLを実装することで、第3のバリエーションであるWormHole𝑀を提供します。これにより、セットアップコストの一部でMLL（WormHole𝐻と同じ精度保証を持つ）に匹敵する問い合わせ時間を達成し、MLLが終了しない巨大なグラフでも実行できます。この組み合わせたアプローチについては§5.3で探求し、表6で統計を提供しています。

\ • サブリニアクエリ複雑性。 クエリ複雑性とは、アルゴリズムによって照会される頂点の数を指します。ノードへの照会によってその隣接リストが明らかになる限定的なクエリアクセスモデル（§1.2参照）では、私たちのアルゴリズムのクエリ複雑性は、行われる距離/最短経路の問い合わせの数に対して非常によくスケールします。5000の近似最短経路の問い合わせに答えるために、私たちのアルゴリズムはほとんどのネットワークでノードの1%から20%しか観察しません。比較すると、BiBFSは数百の最短経路の問い合わせに答えるためにグラフの90%以上を見ています。比較については図2と図5をご覧ください。

\ • 誤差とパフォーマンスに関する証明可能な保証。 §4では、実証的なパフォーマンスを補完し説明する一連の理論的結果を証明しています。以下に非公式に述べられた結果は、べき乗則の次数分布を持つChung-Luランダムグラフモデル[15-17]に対して証明されています。

\ 定理1.1（非公式）。𝑛頂点上のべき乗則指数𝛽∈(2,3)を持つChung-Luランダムグラフ𝐺において、WormHoleは高い確率で以下の保証を持ちます：

\

\

:::info 著者：

(1) Talya Eden, バル・イラン大学 (talyaa01@gmail.com);

(2) Omri Ben-Eliezer, MIT (omrib@mit.edu);

(3) C. Seshadhri, カリフォルニア大学サンタクルーズ校 (sesh@ucsc.edu).

:::

:::info この論文は arxivで入手可能 であり、CC BY 4.0ライセンスの下で提供されています。

:::

\