ハブラベル

コンピュータサイエンスにおいて、ハブラベルまたはハブラベリングアルゴリズムは、ルックアップテーブルよりもはるかに少ないリソースを消費しながらも、道路網などを表すグラフ内のノード間の最短経路を非常に高速に見つけることができる高速化技術です。 ^[1]

この方法では、最大 2 つの SELECT ステートメントと 2 つの文字列の分析で、グラフの 2 つの頂点間の最短経路を計算できます。道路グラフのような方向のグラフの場合、この手法では、収縮階層法を使用して構築された構造から 2 つのテーブルを事前に計算する必要があります。最終的に、計算されたこれらの 2 つのテーブルには、グラフ内に存在するノードと同じ数の行が含まれます。各行 (各ノード) に対して、ラベルが計算されます。

ラベルは、現在のノード (行のノード) と、相対的なマルチレベル構造の昇順検索で到達できる他のすべてのノードとの間の距離情報を含む文字列です。これらの距離の利点は、すべてが最短パスを表すことです。

したがって、今後のクエリでは、最短パスの検索は最初のテーブルのソースと 2 番目のテーブルの宛先から開始され、そこからラベル内で関連する距離情報を持つ共通ノードが検索されます。最短パスの結果として保持されるのは、距離の合計が最小のものだけです。

参照

参考文献

^ Ittai Abraham、Daniel Delling、Andrew V. Goldberg、Renato F. Werneck、「道路ネットワーク上の最短経路のためのハブベースのラベリングアルゴリズム」、Microsoft Research Silicon Valley、1065 La Avenida、Mountain View、CA 94043、USA、2010 年。

[1] Ittai Abraham、Daniel Delling、Andrew V. Goldberg、Renato F. Werneck、「道路ネットワーク上の最短経路のためのハブベースのラベリングアルゴリズム」、Microsoft Research Silicon Valley、1065 La Avenida、Mountain View、CA 94043、USA、2010 年。