Hub labels とは

コンピュータ科学では、ハブ・ラベルまたはハブ・ラベリング・アルゴリズムは、ルックアップ・テーブルよりもはるかに少ないリソースを消費するが、道路ネットワークなどのグラフ内のノード間の最短経路を見つけるためには非常に高速な方法である。
この方法では、最大で2つのSELECT文と2つの文字列を分析して、グラフの2つの頂点間の最短経路を計算することができます。道路グラフのような向きのグラフの場合、この手法では、縮小階層の方法を使用して構築された構造から2つのテーブルを事前に計算する必要があります。最後に、これら2つの計算テーブルは、グラフ内に存在するノードと同じ数の行を持ちます。各行(各ノード)に対して、ラベルが計算されます。
ラベルは、現在のノード(行のノード)と相対マルチレベル構造上で昇順検索で到達できる他のすべてのノードとの間の距離情報を含む文字列です。これらの距離の利点は、すべてが最短経路を表すことです。
したがって、将来のクエリでは、最短パスの検索は、最初のテーブルのソースと2番目のテーブルの宛先から開始し、関連する距離情報を持つ共通ノードのラベル内で検索されます。最短経路の結果として最小の距離の和しか保持されません。