(57)【要約】      （修正有）【課題】Ｋ個の最短経路発見法を提供する。【解決手段】エッジによって相互接続された頂点から構成されるグラフにおける源頂点と行き先頂点との間の経路のうちで、どの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数である。方法は、主プロセスを実行することを含み、主プロセスは計算手順を実行することを含み、また、主プロセスと同時に一つまたは複数の並列プロセスを実行することを含む。並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を第一の頂点として、並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を特定の頂点として計算手順を実行することを含み、並列プロセス開始頂点および並列プロセス終了頂点はいずれも源頂点から行き先頂点までの経路上にある。【選択図】図１
2015169654.tif 000002
【特許請求の範囲】
【請求項１】
エッジによって相互接続された頂点から構成されるデータ・グラフにおける源頂点と行き先頂点との間の諸経路のうちでk個の最短経路長を見出すコンピュータ実装される方法であって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数であり、当該方法は、主プロセスを実行することを含み、前記主プロセスは計算手順を実行することを含み、頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点の直前であると定義され、前記計算手順は、
特定の頂点の直前の唯一のまたは各頂点について：
前記直前の頂点について前記計算手順が完了しているという通知を受け取り；
前記直前の頂点から前記特定の頂点までのエッジに帰属させられた長さ値を、前記第一の頂点から前記直前の頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含み、
前記計算手順はさらに：
前記特定の頂点について計算されたk個の最短経路長の記録を維持し；
前記直前の頂点のうちの前記唯一のまたは各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含み；
前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、
当該方法はさらに、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行することを含み、前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある、
コンピュータ実装される方法。
【請求項２】
当該方法が、各反復での同じ頂点および各反復での異なる行き先頂点を用いて少なくとも一回反復される、請求項１記載のコンピュータ実装される方法。
【請求項３】
当該方法がさらに：
前記主プロセスの一部として、前記一つまたは複数の並列プロセス開始頂点のうちのある並列プロセス開始頂点について前記計算手順が完了したという通知が発されたのち、および前記並列プロセスの一部として、対応する並列プロセス終了頂点について前記計算手順が完了したという通知が発されたのち、前記並列プロセスの一部として前記計算手順が実行された各頂点において記録された並列プロセス開始頂点からのk個の最短経路長を、その並列プロセス開始頂点において記録されている源頂点からのk個の最短経路長を加えることによって修正することを含む、
請求項１記載のコンピュータ実装される方法。
【請求項４】
前記データ・グラフが領域に分割されて二つ以上のデータ記憶ユニットにまたがって分散して記憶され、各データ記憶ユニットが前記領域の少なくとも一つを記憶し、専用の計算処理ユニットをもち、前記計算手順が前記特定の頂点が記憶されているデータ記憶ユニットに専用の計算処理ユニットによって実行される、請求項１記載のコンピュータ実装される方法。
【請求項５】
唯一の並列プロセス開始頂点または各並列プロセス開始頂点および対応する並列プロセス終了頂点は同じ領域からのものであり、前記並列プロセス開始頂点はその領域の境界頂点であり、前記予備的な計算手順は、やはり同じ領域内にある頂点から構成される任意の経路上の各頂点について実行される、
請求項４記載のコンピュータ実装される方法。
【請求項６】
唯一の並列プロセスまたは各並列プロセスは、各反復での同じ並列プロセス開始頂点および各反復での異なる並列プロセス終了頂点を用いて少なくとも一度繰り返される、
請求項４記載のコンピュータ実装される方法。
【請求項７】
各領域について、当該領域の境界にある各頂点について、該頂点を該頂点から当該領域の前記一つまたは複数の同定された中央頂点またはそのそれぞれまでの最短経路長と関連付けて記憶し；
前記並列プロセス開始頂点を選択することをさらに含む、請求項４記載の方法であって、前記並列プロセス開始頂点の選択は：
源頂点を含む領域内の、異なるデータ記憶ユニット上に記憶されている隣接領域にエッジによって接続されている境界頂点のうちから、同定された中央頂点までの最短経路長をもつまたは前記二つ以上の同定された中央頂点までの最小の平均最短経路長をもつ境界頂点を同定し；
同定された境界頂点またはエッジによって該同定された境界頂点に接続されている前記隣接領域内の境界頂点のいずれかを、前記並列プロセス開始頂点として選択することによって行なわれる、
方法。
【請求項８】
領域の前記中央頂点は、中間性中心性指標に基づいて同定される、請求項７記載の方法。
【請求項９】
最短経路長の記録を維持することが、前記経路長を、それぞれの経路上の前記一つまたは複数の先行する頂点を同定する情報に関連付けて記憶することを含む、
請求項１記載の方法。
【請求項１０】
前記記録を維持することが：
その特定の頂点において、k個の最短経路のそれぞれの先行する頂点を、それぞれのk個の最短経路長をインデックス付け値とするヒープ・フォーマットで記憶することを含む、
請求項９記載の方法。
【請求項１１】
前記k個の最短経路のそれぞれの先行する頂点を記憶することが、最短経路上の先行する各頂点の同定情報を記憶し、残りのk−1個の最短経路については前記最短経路からの差の同定情報を記憶することを含む、
請求項９記載の方法。
【請求項１２】
前記計算手順において、前記特定の頂点についての新たな経路長を計算することは、直前の各頂点のために順次：
前記特定の頂点について計算されたk個の最短経路長の記録へのアクセスを一時的にロックし；
直前の頂点において記録されている、記録されたk個の最短経路長のそれぞれに、直前の頂点から前記特定の頂点までのエッジに帰属させられている長さ値を加えることによって、前記特定の頂点についての新たな経路長を計算し；
前記特定の頂点について計算されたk個の最短経路長の記録を更新して、計算された新たな経路長およびロックされた記録されているk個の最短経路長のうちのk個の最短経路長を含むようにし；
k個の最短経路長の記録へのアクセスをロック解除することによって実行される、
請求項１ないし１１のうちいずれか一項記載の方法。
【請求項１３】
前記特定の頂点について前記計算手順が完了しているという通知を発することが、前記特定の頂点が源頂点から行き先頂点までの経路上の直前の頂点であるような頂点または各頂点に、前記特定の頂点についてのk個の最短経路長の記録を送信することを含み、
前記計算手順において、
前記特定の頂点についての新たな経路長を計算することは、前記直前の頂点から前記特定の頂点までのエッジに帰属させられている長さ値を、前記直前の頂点から受領された記録に含まれるk個の最短経路長のそれぞれに加えることを含む、
請求項１記載の方法。
【請求項１４】
前記主プロセスが、諸頂点が、前記計算手順が実行される前記特定の頂点となる順序を決定することを含み、前記特定の頂点となるのは、前記計算手順がまだ完了しておらず、前記計算手順が唯一の直前の頂点または各直前の頂点については完了している頂点のうちから、前記直前の頂点が源頂点への最短経路長をもつとして記録されている頂点を、次の特定の頂点として選択することによる、
請求項１記載の方法。
【請求項１５】
エッジによって相互接続された頂点から構成されるデータ・グラフにおける源頂点と行き先頂点との間の諸経路のうちでk個の最短経路長を見出す装置であって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数であり、当該装置は、主プロセスを実行するよう構成されており、前記主プロセスは計算手順を実行することを含み、頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点の直前であると定義され、前記計算手順は、特定の頂点の直前の唯一の頂点または各頂点について：
前記直前の頂点について前記計算手順が完了しているという通知を受け取り；
前記直前の頂点から前記特定の頂点までの前記エッジに帰属させられている長さ値を、前記第一の頂点から前記直前の頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含み、
前記計算手順はさらに：
前記特定の頂点について計算されたk個の最短経路長の記録を維持し；
直前の唯一の頂点または直前の各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含み、
前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、
当該装置は、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行するよう構成されており、前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある、
装置。
【請求項１６】
コンピューティング装置によって実行されたときに、前記コンピューティング装置に、エッジによって相互接続された頂点から構成されるデータ・グラフにおける源頂点と行き先頂点との間の諸経路のうちでk個の最短経路長を見出すプロセスを実行させるコンピュータ・プログラムであって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数であり、前記プロセスは、主プロセスを実行することを含み、前記主プロセスは計算手順を実行することを含み、頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点の直前であると定義され、前記計算手順は、
特定の頂点の直前の唯一のまたは各頂点について：
前記直前の頂点について前記計算手順が完了しているという通知を受け取り；
前記直前の頂点から前記特定の頂点までのエッジに帰属させられた長さ値を、前記第一の頂点から前記直前の頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含み、
前記計算手順はさらに：
前記特定の頂点について計算されたk個の最短経路長の記録を維持し；
前記直前の頂点のうちの前記唯一のまたは各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含み；
前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、
前記プロセスはさらに、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行することを含み、前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある、
コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ・データベースのためのアルゴリズムおよび処理方法の分野に属する。詳細には、本発明はグラフ・データベースにおいて二つの頂点の間のk個の最短経路を見出すための方法に関する。
【背景技術】
【０００２】
最短経路解析は根本的なグラフ処理操作である。これは、単一の源頂点からグラフ内の他のすべての頂点への最短経路、指定された一対の頂点の間の最短の経路またはグラフ頂点のあらゆる対の間で最短の経路を計算する。最短経路は通常、有向の重み付けされたグラフ上で計算される。ここで、エッジ重みは等しくても異なっていてもよく、正でも負でもよい（負のループが存在しなければ）。最短経路解析は、無向グラフにおいても実行できる。グラフ・データベースにおいて二つの頂点の間の最短経路を見出すためのアルゴリズムが存在する。たとえば、ダイクストラ・アルゴリズムは良好な理論的および実際的結果を呈する。
【０００３】
実際上は、最短経路の発見は常に最も有用な操作ではなく、実際には応用は二番目に短い、三番目に短いなどの経路を発見することを必要とすることがある。たとえば、最短経路が常に理想的または利用可能ではないシナリオがあることがある。したがって、k個の最短経路を見出すための操作が存在している。
【０００４】
一つの既存のk最短経路アルゴリズムはイェン・アルゴリズムである。イェン・アルゴリズムは、まずたとえばダイクストラ・アルゴリズムを使って最短経路Pを計算する。次いで、分岐点を定義してP上のエッジを最適でないエッジで置き換えることによって、Pから逐次反復的に離れていく。次いで、最終的な上位K個の代替経路が問題への解であると考えられる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
イェン・アルゴリズムの性質（処理されるべき次の頂点の中央集中された待ち行列の維持、K反復工程がK−1反復工程の状態に基づくこと、グローバル変数の監視など）のため、これは並列化するのが難しく、よって計算上、高価である。システム・パフォーマンス上のボトルネックが生じうる。
【課題を解決するための手段】
【０００６】
本発明の実施形態は、エッジによって相互接続された頂点から構成されるデータ・グラフにおけるある源頂点とある行き先頂点との間の諸経路のうちでk個の最短の経路長を見出すコンピュータ実装された方法であって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられ、kは2以上の整数であり、当該方法は、主プロセスを実行することを含み、主プロセスは計算手順を実行することを含む、方法を含む。頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点に先行すると定義され、前記計算手順は、特定の頂点に先行する唯一のまたは各頂点について：前記先行する頂点について前記計算手順が完了しているという通知を受け取り；前記先行する頂点から前記特定の頂点までのエッジに帰属させられた長さ値を、前記第一の頂点から前記先行する頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含む。前記計算手順はさらに：前記特定の頂点について計算されたk個の最短経路長の記録を維持し；前記先行する頂点のうちの前記唯一のまたは各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含む。前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含む。本方法はさらに、前記主プロセスと同時に、一つまたは複数の並列プロセスを実行することを含む。前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から前記並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある。
【０００７】
有利なことに、本発明の諸実施形態は、源頂点から計算手順が実行される頂点までのk個の最短経路長を確立するために、計算手順が実行される頂点において局所的に利用可能なデータを使う主プロセスを提供する。本方法の結果として、源頂点から行き先頂点までのk個の最短経路長を計算する際に、源頂点から該源頂点と行き先頂点との間の経路上のあらゆる頂点までのk個の最短経路長も計算される。
【０００８】
本方法は、主プロセスと同時並行して実行される一つまたは複数の並列プロセスを含む。たとえば、前記主プロセスを実行することに携わるCPU（単数または複数）に対する前記並列プロセスまたは前記並列プロセスのそれぞれを実行することに複数の別個のCPUが携わってもよい。
【０００９】
並列プロセス開始頂点からいくつかの他の頂点のそれぞれまでのk個の最短経路長を計算することによって、前記計算手順がある並列プロセスの一部として実行された頂点について前記計算手順を実行するときに必要とされる計算を軽減する何らかの予備的な計算が実行される。該計算の一部を並列化することによって、前記方法によって引き起こされる全体的なシステム・ボトルネックが軽減または緩和される。事実上、前記並列プロセスは、前記主プロセスに関わる経路長の計算に寄与するいくつかの経路長部分を計算する。
【００１０】
ある方法は、前記源頂点が、前記手順が前記源頂点について完了しているという通知（または前記主プロセス開始頂点が先行する頂点となるような頂点について前記計算手順が始まるよう前記諸頂点をトリガーするよう構成された通知）を発することによって開始されてもよい。本方法は、少なくとも前記源頂点を特定し、任意的にはさらに一つまたは複数の行き先頂点を特定する、あるアプリケーションの要求に際して実行されてもよい。
【００１１】
主プロセス開始頂点から特定の頂点までのk個の最短経路（経路長およびそれぞれの経路上でのそれまでの頂点を同定するデータ）が、前記特定の頂点において記憶されてもよい。
【００１２】
本方法は、単一の源頂点から多数の行き先頂点の仕方で実装されてもよい。たとえば、本方法は、各反復での同じ頂点および各反復での異なる行き先頂点を用いて少なくとも一回反復されうる。
【００１３】
任意的に、行き先頂点が未指定で、処理が、指定された源頂点からデータ・グラフ中の任意の他の頂点へのk個の最短経路長を見出すことであってもよい。行き先頂点は逐次反復的に変更でき、それにより前記主プロセスは結果的にはデータ・グラフ中の源頂点以外のすべての頂点について実行される。主プロセスがある頂点について実行／実施／執行されると言われる場合、それは、問題の頂点が前記主プロセスの一部をなす前記計算手順のある反復工程についての前記特定の頂点であることを意味するものと了解される。
【００１４】
本方法を固定したまたは一定の源頂点を用いて、毎回行き先頂点を変えながら（たとえばデータ／グラフの境界にある各頂点を行き先頂点として選んでいく）逐次反復的または反復的に実行することによって、本方法は、「一対多」型のk最短経路長処理を実行できるようにする。単一源頂点から多数行き先頂点の処理では、本方法は、固定した単一の源頂点と、多数の行き先頂点のそれぞれとを用いて逐次反復的に実行されてもよい。本方法の結果として、一つの行き先頂点について本方法を実行することが、源頂点から、該源頂点から前記一つの行き先頂点までの経路上のすべての頂点までのk個の最短経路長が計算され、記憶される結果となる。したがって、一対多の処理のための前記方法を完了させるためには、前記主プロセスが一つの行き先頂点について実行されたのち、前記主プロセスは、源頂点からその行き先頂点までの経路上にない頂点について実行されるだけでよい。換言すれば、主プロセス開始頂点が変わらない限り、現在の行き先と共通の経路または経路部分をもつ他のプロセス終了頂点についてすでに実行された計算が記憶されており、新たな計算手順は、主プロセス開始頂点から他のプロセス終了頂点までの経路上に現われない、源頂点から現在の行き先頂点までの経路上の頂点（もしあれば）について実行されるだけでよい。並列プロセスの一部としての前記計算手順は、前記行き先頂点または各行き先頂点について、および源頂点から前記行き先頂点または各行き先頂点までの経路上の各頂点について、一度、源頂点から、前記行き先頂点もしくは各行き先頂点および源頂点と行き先頂点との間の経路上の各頂点までのk個の最短経路長を計算するために、実行されるだけでよい。
【００１５】
主プロセスの一部をなす計算手順は、頂点ごとにCPUにおいて（またはCPUノードにおいて）処理スレッドとして実行される。唯一のまたは各並列プロセスの一部をなす計算手順も、頂点ごとに、主プロセスの一部をなす計算手順が実行されるCPU（またはCPUノード）とは異なるCPU（またはCPUノード）において実行される。前記一つまたは複数の並列プロセスの一部として計算されたk個の最短経路長は、主プロセスの一部として計算されたk個の最短経路と組み合わされて、源頂点から、並列プロセスの一部として計算手順が実行された諸頂点へのk個の最短経路長についての予備的な値を得ることができる。
【００１６】
前記予備的な計算が実行された頂点において記憶されたk個の最短の予備的な経路は、前記計算手順が実行された諸頂点について計算されたk個の最短経路と組み合わされることができる。たとえば、主プロセスの一部として、前記一つまたは複数の並列プロセス開始頂点のうちのある並列プロセス開始頂点について前記計算手順が完了したという通知が発されたのち、および並列プロセスの一部として、対応する並列プロセス終了頂点について前記計算手順が完了したという通知が発されたのち、並列プロセスの一部として前記計算手順が実行された各頂点において記録された並列プロセス開始頂点からのk個の最短経路長が、その並列プロセス開始頂点において記録された源頂点からのk個の最短経路長を加えることによって修正される。
【００１７】
このように結果を組み合わせることによって、並列プロセスの一部として前記計算手順がすでに実行されているが、主プロセスの一部としては前記計算手順がまだ実行されていない頂点において、有用な結果が得られる。つまり、それらの結果は、源頂点から、前記並列プロセス開始頂点を含む諸経路に沿って問題の頂点までのk個の最短経路である。このように、源頂点から問題の頂点までの絶対的なk個の最短の経路ではないものの、並列プロセスにおいて計算されたk個の最短経路を修正することによって得られるk個の最短経路長は、いくらかの意義をもち、応用にとって有用であることがありうる。
【００１８】
データ・グラフが領域に分割されて二つ以上のデータ記憶ユニットにまたがって分散して記憶され、各データ記憶ユニットが前記領域の少なくとも一つを記憶し、専用の計算処理ユニットをもち、前記計算手順が特定の頂点が記憶されているデータ記憶ユニットに専用の計算処理ユニットによって実行される実施形態では、並列のための格別な機会がありうる。特に、唯一のまたは各並列プロセス開始頂点および対応する並列プロセス終了頂点は同じ領域からのものであり、並列プロセス開始頂点はその領域の境界頂点であり、前記予備的な計算手順は、やはり同じ領域内にある頂点から構成される任意の経路上の各頂点について実行される。
【００１９】
本方法の計算手順および予備的計算手順への分割は、源頂点を記憶しているデータ記憶ユニットにおいて実行される計算手順と並列に、源頂点を記憶しているデータ記憶ユニット以外のデータ記憶ユニット上に記憶されている領域について、手順が実行されることができるようにすることが理解できる。一つまたは複数の他の領域も、並列に実行される予備的計算手順を有していてもよい。各インスタンスにおいて、並列プロセス開始頂点はその領域の任意の境界頂点として選択されてもよく、あるいは源頂点が記憶されている領域への、他の境界頂点より短い経路をもつことが知られている境界頂点であってもよい。そのような知識は、たとえばキャッシュされている結果に基づくものであってもよい。
【００２０】
境界頂点は、ある領域内の頂点であって、別の領域内の頂点とエッジによって接続されているものである。
【００２１】
並列プロセスにおいてk個の最短経路が計算される頂点の数が増すよう、並列プロセスは反復的または逐次反復的に実行されてもよい。たとえば、唯一のまたは各並列プロセスは、各反復での同じ並列プロセス開始頂点および各反復での異なる並列プロセス終了頂点を用いて少なくとも一度繰り返される。並列プロセス終了頂点は、領域の他の境界頂点のそれぞれとして選択され、特定の領域について、並列プロセスは、並列プロセス開始頂点に経路を介して接続されている当該領域内の各頂点について予備的計算手順が実行されたときに、完了してもよい。
【００２２】
データ・グラフの各領域について諸中央頂点が決定されてもよい。有利なことに、中央頂点は、本発明を具現する諸方法において有用なツールをなす。他の領域への距離の点で当該領域内の頂点の典型であると想定できるからである。この属性は、並列プロセス開始頂点を選択する際に利用されることができる。たとえば、方法は、各領域について、当該領域の境界にある各頂点について、該頂点を該頂点から当該領域の前記一つまたは複数の同定された中央頂点またはそのそれぞれまでの最短経路長と関連付けて記憶し、並列プロセス開始頂点を選択することを含んでいてもよい。並列プロセス開始頂点の選択は、源頂点を含む領域内の、異なるデータ記憶ユニット上に記憶されている隣接領域にエッジによって接続されている境界頂点のうちから、同定された中央頂点までの最短経路長をもつまたは前記二つ以上の同定された中央頂点までの最小の平均最短経路長をもつ境界頂点を同定し、同定された境界頂点またはエッジによって同定された境界頂点に接続されている前記隣接領域内の境界頂点のいずれかを、前記並列プロセス開始頂点として選択することによって行なわれてもよい。
【００２３】
あるいはまた、各領域の各境界頂点が、他の各領域の中央頂点からの最短経路長（または前記二つ以上の中央頂点からの平均最短経路長）に関連付けて記憶されるのでもよい。このようにして、各データ記憶ユニットにおいて同時に並列プロセスが実行されることができる。特定のデータ記憶ユニットにおいて並列プロセスが実行される領域は、前記特定のデータ記憶ユニット上に記憶された境界頂点のうち、源頂点の領域の中央頂点までの最短経路長をもつ境界頂点をもつ、前記特定のデータ記憶ユニット上に記憶された領域として選択されてもよい。任意の領域についての並列プロセス開始点は、源頂点の領域の中央頂点からの最短経路長（または二つ以上の中央頂点からの平均最短経路長）をもつ、その領域の境界頂点として選択されてもよい。
【００２４】
実装に依存して、データ・グラフが記憶される際、二つの領域の境界にある頂点がそれら二つの領域の両方の一部として記憶されるのでもよい。一対の領域は、対の一方の中のある頂点が対の他方の中のある頂点にエッジによって接続している場合に、隣接している。
【００２５】
ある領域の中央頂点を決定するための例示的な手順として、領域の中央頂点は、中間性中心性（betweenness  centrality）指標に基づいて同定されてもよい。
【００２６】
k個の最短経路長が頂点において記憶される詳しいフォーマットは、実施形態の要求やその特定のデータ・グラフのフォーマットに依存することになる。いくつかの実装では、単に経路長のみが関心対象であることもある。他の実装では、経路長およびk個の最短経路上のそれまでの頂点の両方が必要とされることがありうる。任意的に、最短経路長のレコードは、経路長を、それぞれの経路上での一つまたは複数の先行する〔先に現われる〕頂点を同定する情報と関連付けて記憶することを含む。
【００２７】
経路を記憶する例示的なフォーマットはヒープとして記憶するものである。任意的に、最短経路長の記録を維持することは、その特定の頂点において、k個の最短経路のそれぞれの先行する頂点を、それぞれのk個の最短経路長をインデックス付け値とするヒープ・フォーマットで記憶することを含む。
【００２８】
ヒープ構造は、スペース要件の点で効率的であり、問い合わせするのが迅速で、更新するのが迅速で、ヒープに記憶されていない値との簡単な比較を助ける。諸実施形態において使用されうるヒープの特定の形は、二分最大ヒープ（binary  max  heap）である。有利には、そのようなヒープのルートは最も大きな値であり、よって計算された新たな経路長のうち最短のものが特定の頂点において記憶されている二分最大ヒープのルートより短くない場合、更新が必要ないことがすぐに判別できる。対応して、計算された新たな経路長のうち一つまたは複数が特定の頂点のヒープにおいてすでに記憶されている諸経路長より短い場合、ヒープは更新され、計算された新たな経路長およびヒープにすでに記憶されているk個の経路のうち、k個の最短の経路長（およびその関連付けられた経路）が更新されたヒープに記憶されるようにされる。
【００２９】
前記k個の経路のそれぞれについて前記経路のk個全部の上の頂点全部の同定情報を記憶するのではなく、一つの経路を完全に同定可能なフォーマットで記憶し、次いで残りの経路は最初の経路に依存して記憶することにより、頂点における記憶スペースの点でいくらかの効率性が得られることがありうる。たとえば、k個の最短経路のそれぞれの上の先行する頂点を記憶することは、最短経路上の先行する頂点のそれぞれの同定情報を記憶し、残りのk−1個の最短経路については最短経路からの差の同定情報を記憶することを含む。
【００３０】
特定の頂点について実行される計算手順は、事実上、前記特定の頂点に先行する各頂点について決定／計算／コンピューティングされたk個の最短経路長を、それぞれの先行する頂点から前記特定の頂点までの経路長を加えることによって修正したもののうちから、k個の最短経路長を収集／決定／計算／コンピューティングする。この計算手順を実行するための具体的な技法は、前記特定の頂点について計算されたk個の最短経路長の記録へのアクセスを一時的にロックし；直前の頂点において記録された、記録されたk個の最短経路長のそれぞれに、直前の頂点から前記特定の頂点までのエッジに帰属させられている長さ値を加えることによって、前記特定の頂点についての新たな経路長を計算し；前記特定の頂点について計算されたk個の最短経路長の記録を更新して、計算された新たな経路長およびロックされた記録されているk個の最短経路長のうちのk個の最短経路長を含むようにし；k個の最短経路長の記録へのアクセスをロック解除することによって実行される。
【００３１】
第二の例では、特定の頂点について前記計算手順が完了しているという通知を発することが、前記特定の頂点が源頂点から行き先頂点までの経路上の先行する頂点であるような頂点または各頂点に、前記特定の頂点についてのk個の最短経路長の記録を送信することを含む。前記計算手順において、前記特定の頂点についての新たな経路長を計算することは、前記先行する頂点から前記特定の頂点までのエッジに帰属させられている長さ値を、前記先行する頂点から受領された記録に含まれるk個の最短経路長のそれぞれに加えることを含む。
【００３２】
特定の頂点における前記計算手順は、前記計算手順が先行する頂点すべてについて完了していることに依拠する（本稿で先行するとは、場所的な意味で使われているが、当該方法の性質のため、時間的な意味においても適切である）。したがって、順次の特定の頂点について実行されていくことによって、処理スレッドを定義する前記計算手順は、源頂点（または並列プロセス開始頂点）から外向きに、行き先頂点（単数または複数）につながる経路に沿って漸進的に広がると考えることができる。本方法は、諸計算手順を順序付けるための特定の技法を含んでいてもよい。たとえば、前記主プロセスは、諸頂点が、前記計算手順が実行される特定の頂点となる順序を決定することを含む。特定の頂点となるのはたとえば、前記計算手順がまだ完了しておらず、前記計算手順が前記それぞれの先行する頂点またはそのそれぞれについて完了している頂点のうちから、前記先行する頂点が源頂点への最短経路長をもつとして記録されている頂点を、次の特定の頂点として選択することによる。
【００３３】
別の側面の諸実施形態は、エッジによって相互接続された頂点から構成されるデータ・グラフにおけるある源頂点とある行き先頂点との間の諸経路のうちでk個の最短の経路長を見出す装置であって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられ、kは2以上の整数であり、当該装置は、主プロセスを実行するよう構成されており、主プロセスは計算手順を実行することを含む、装置を含む。頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点に先行すると定義され、前記計算手順は、特定の頂点に先行する唯一のまたは各頂点について：前記先行する頂点について前記計算手順が完了しているという通知を受け取り；前記先行する頂点から前記特定の頂点までの前記エッジに帰属させられた長さ値を、前記第一の頂点から前記先行する頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含む。前記計算手順はさらに：前記特定の頂点について計算されたk個の最短経路長の記録を維持し；前記先行する頂点のうちの前記唯一のまたは各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含む。前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含む。さらに、本装置は、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行するよう構成されている。前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から前記並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある。
【００３４】
たとえば、本装置は、命令をロードされた複数の計算処理資源であってもよいし、あるいは二つ以上の処理スレッドを並行して実行するコンピューティング資源を有するデータ記憶装置であってもよい。
【００３５】
別の側面の諸実施形態は、データ・グラフを記憶するよう構成されたデータ記憶システム内のコンピューティング装置によって実行されたときに、前記コンピューティング装置に本発明を具現する方法を実行させるコンピュータ・プログラムの組を含む。
【００３６】
本発明の好ましい事項について、これから、純粋に例として、付属の図面を参照しつつ述べる。
【図面の簡単な説明】
【００３７】
【図１】本発明を具現する方法を表わすフローチャートである。
【図２】発明実施形態におけるデータ・グラフの断片の図解である。
【発明を実施するための形態】
【００３８】
図１は、本発明を具現する方法を表わすフローチャートである。近似的な意味において、時間は上から下へと増大する。よって、ステップS101が最初に実行され、次いでステップS102およびS103が少なくとも部分的には並列に実行され、次いでステップS103が方法の終わりとなる。
【００３９】
ステップS101において本方法が開始される。本方法は、アプリケーションまたは記憶されているデータ・グラフに対して処理が実行されることを命令することができる他の何らかのエンティティからの要求または命令に応答して開始されてもよい。たとえば、データベース・コントローラが第一の頂点から第二の頂点へのk個の最短経路についての問い合わせを受領してもよい。開始ステップS101はまた、源頂点から、源頂点から行き先頂点への経路上のその後の各頂点に、源頂点において前記計算手順が完了しているという通知を送信する、あるいは他の何らかの仕方で、前記計算手順がそれらその後の頂点において実行されるようトリガーすることを含んでいてもよい。
【００４０】
開始ステップS101は、並列プロセス開始および終了頂点を選択することを含んでいてもよい。S101とS103およびS103とS104の間の複数の線は、二つ以上の並列プロセスがある可能性を表わしている。二つ以上の並列プロセスは必ずしも同時に実行される必要はないことを注意しておくべきである。しかしながら、諸実施形態では、並列プロセスの少なくとも一部が主プロセスS102が実行されている間に実行される。並列プロセスS103は、主プロセスS102が並列プロセス開始頂点から並列プロセス終了頂点への諸経路上の頂点に到達するときに、停止させられてもよい。それにより、並列プロセスが主プロセスをホールドアップすることが防止される。
【００４１】
S102は、主プロセスを表わしている。ここでは、源頂点からその計算手順が実行されている特定の頂点までのk個の最短経路を計算し、維持または記憶する計算手順が、源頂点から行き先頂点への経路上の各頂点について実行される。
【００４２】
経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列である。つまり、経路は自らに交わったり、当該経路上で逆行したり、あるいはループを形成したりすることはできない。経路長は、経路上の頂点を接続するエッジに帰属させられている長さ値の和である。長さ値は正でも負でもよいが、いくつかの実施形態では、長さ値は正の値に限定されてもよい。経路上の頂点を接続するエッジに帰属させられている長さ値の和が小さいほど、経路は短い。経路は、経路長および該経路上の先行する頂点の同定情報であると考えられてもよく、経路は、経路長が同定でき、経路上の先行する頂点が同定できる形で記憶されてもよい。あるいはまた、エッジが個々に同定できる場合、経路は、経路長が同定でき、経路上のエッジが同定できる形で記憶されてもよい。k個の最短経路が、k個の最短経路長の代わりにまたはそれに加えて記録されてもよい。
【００４３】
頂点〔バーテックス〕は、少なくとも一つのエッジによって別のグラフ要素にリンクされるグラフ要素である。頂点のことをいうのに、ノードまたは資源〔リソース〕という用語が使われることもある。頂点は情報を記憶することができる。たとえば、頂点識別子が鍵〔キー〕値〔バリュー〕記憶部における鍵で、値が記憶される情報であってもよい。そのような記憶される情報の例は、主プロセス開始頂点（すなわち、源頂点）から当該頂点までのk個の最短経路の記録および先行する頂点のチェックリストを含む。それにより、先行する頂点のそれぞれについて前記計算手順が完了しているという通知が発されたとき、当該頂点に記憶されている情報から決定できる。
【００４４】
エッジは、二つのエッジの間の相互接続である。エッジは有向であってもよく、それによりエッジ自身が、そのエッジが相互接続する二つの頂点の先行関係を決定する：エッジが出て行く頂点が、エッジがはいってくる頂点より先行するのである。あるいはまた、エッジは無向であってもよく、先行関係は経路の幾何構造によって決定される。エッジは、第一の頂点から第二の頂点へのエッジが第一の頂点と第二の頂点の間の論理的な接続を表わすまたは定義するよう、ラベル付けされてもよい。エッジに割り当てられたラベル付けがその論理的な関係の形を定義するのである。たとえば、第一の頂点は主体（subject）頂点、第二の頂点は客体（object）頂点と考えられてもよい。エッジのラベルは主体頂点の属性を同定し、客体頂点の値が主体頂点に帰属可能な属性の範囲または値を定義する。エッジはあるいは相互接続と称されることもある。エッジに割り当てられたラベルを定義するために述語という用語が使用されてもよい。エッジが同質（homogenous）である、すなわち一つの形のエッジしかなく、よってエッジに帰属させられるラベルがそのエッジを他のエッジから区別する積極的な効果をもたない実施形態では、エッジに帰属させられる長さ値がラベルの代わりに記憶されてもよい。
【００４５】
データ・グラフは、記憶されたデータの表出であり、記憶されているデータをユーザーに対して、またはイベント・ハンドラまたはデータ記憶システム内部の他のプロセスに対して表現する手段である。データ・グラフがトリプル（triple）、たとえばRDFトリプルとしてエンコードされ、資源〔リソース〕が、該資源が主体として指定されるトリプルによって定義されてもよい。代替的または追加的に、データが鍵値記憶部に記憶され、トリプルが、頂点を定義する追加的なデータ（たとえばメタデータ）が記憶されている記憶位置をインデックス付けする鍵のはたらきをする。
【００４６】
本稿では、機能がある頂点またはデータ・グラフの他の何らかの要素において行なわれるとして記述される場合、その機能は実際には、そのグラフ要素をエンコードしているデータを含むデータに対する処理資源において実行されることが想定される。同様に、頂点において記憶されているデータまたは情報は、頂点をエンコードするデータの一部をなして記憶される。
【００４７】
ステップS103は、前記一つまたは複数の並列プロセスを表わす。ここでは、並列プロセス開始頂点からその計算手順が実行されている特定の頂点までのk個の最短経路を計算し、維持または記憶する計算手順が、並列プロセス開始頂点から並列プロセス終了頂点への経路上の各頂点について実行される。
【００４８】
前記並列プロセスまたは各並列プロセスは、主プロセスが実行されている間に実行される、あるいは少なくとも部分的に主プロセスが実行されている間に実行される。各頂点において実行される前記計算手順は、源頂点から前記特定の頂点までの諸経路上の先行する頂点のそれぞれについて前記計算手順が実行済みであることに依拠する。よって、主プロセスはまず源頂点に最も近い諸頂点について実行され、源頂点から遠ざかる諸経路に沿って進行する。こうして、並列プロセス開始頂点（単数または複数）は、源頂点から所定の最小数の頂点より多く隔たった頂点として選択されてもよいし、あるいはデータ・グラフの、源頂点の領域とは別の領域にある頂点として選択されてもよい（データ・グラフが記憶のために諸領域に分割されている実施形態の場合）。並列プロセスは、主プロセスが並列プロセス開始頂点まで達してしまう前に実行されることができる処理の例である。
【００４９】
実施形態は、主プロセスまたは前記並列プロセスもしくは各並列プロセスが単一の処理スレッドとして実行されることに限定されない。利用可能なコンピューティング資源に依存して、主プロセスに関わる何らかの処理が並列化できることがありうる。同様に、特定の並列プロセスに関わる何らかの処理が並列化されてもよい。
【００５０】
ステップS104は、本方法の終わりである。ステップS104は、前記行き先頂点または各行
先頂点に記憶されたk個の最短経路について、問い合わせするエンティティに通知することを含んでいてもよい。
【００５１】
諸実施形態において要求されるまたは望ましい、データ・グラフ（またはグラフ・データベース）ならびに値および情報の記憶のためのフォーマットについてこれから論じる。諸実施形態は、各エッジに経路長を帰属させることができるデータ・グラフにおける実装に好適である。たとえば、各エッジは、長さ値と関連付けられて記憶される。エッジ属性をサポートする一般的なデータ・グラフでは、エッジ重みと称することもできる長さ値が、エッジ属性の要素として記憶されることができる。いくつかのデータ・グラフでは、エッジに帰属させることのできる唯一の値はエッジ・ラベルであることがある。諸実施形態は、そのようなデータ・グラフでも実装されうる。たとえば、この場合、グラフ・データベース（データ・グラフ）を記憶するために、以下の手法の一つが採用できる：
・エッジが同質である（すなわち、エッジがみな同じラベル付けをされる）とき、RDFエッジ・ラベルについてリザーブされた記憶スペースが、エッジに帰属させられた長さ値を記憶するために使用されることができる；あるいは
・長さ値がエッジ・ラベルに連結され、前記計算手順の間に、別個の読み出し動作でラベルをパースすることによって抽出されることができる；あるいは
・XMLタグ付けのような非RDF構造体が使用されることができる。これはパースおよび抽出のために特定の処理が実行されることを要求する；
・相補的なオントロジカル推論（ontological  reasoning）およびグラフ解析手順と組み合わせて特殊な関係概念を使って、長さ値のようなエッジ属性がエミュレートできる。
【００５２】
頂点自身のデータ構造に関し、前記計算手順を容易にする例示的なデータ記憶フォーマットについてこれから論じる。
【００５３】
一例では、各頂点において、以下の情報が記憶される：源頂点Sを与えられたときの、Sから現在頂点までのK個の最短経路。ここで、k個の最短経路というのは、k個の最短経路長と、k個の各最短経路上の先行する頂点の同定情報であると了解される。
【００５４】
上記の情報は対（経路長および対応する先行頂点が一つの対をなす）で記憶される。高速な検索および挿入のために、経路の長さをインデックス付けする値として、ヒープが具体的なデータ・フォーマットとして使われる。ヒープの例示的な形は二分最大ヒープである。二分最大ヒープでは、ルート要素は、頂点に記憶されているK個の最短経路のうちで最も大きな経路長である。任意の時点においてある頂点に記憶されているk個の最短経路は、その時点までに計算された、プロセス開始頂点からのk個の最短経路である。ひとたび前記計算手順がプロセスの一部として、ある頂点について完了したら、すなわち、前記計算手順が各先行頂点について完了し、それらの先行頂点に記憶されているk個の最短経路が、それぞれの先行頂点から問題の頂点までの諸経路に帰属させられているそれぞれの長さ値とともに使われて、問題の頂点に記憶されているk個の最短経路を更新したら、問題の頂点に記憶されているk個の最短経路が、プロセス開始頂点から問題の頂点までの実際のk個の最短経路長であるよう取ることができる。ある頂点に記憶されている二分最大ヒープは、計算手順の実行において下記のように更新される。
【００５５】
p'が特定の頂点において考えられるべき新たな経路長（すなわち、ある先行する頂点に記憶されているk個の最短経路長のうちの一つに、前記先行する頂点からその特定の頂点までのエッジに帰属させられている長さ値を加えたもの）であるとする。h.rootは、ヒープのルート要素を返す関数であり、h.heapify()はヒープを再構築する関数である。
【００５６】
１．If  p'＜h.root  より短い経路がみつかった、goto  ステップ２；else  gotoステップ３
２．h.rootを除去、h.root＝p'と割り当て
h.heapify()新たな最大ヒープ
h.rootはいまだに最大の経路長
３．p'を破棄。
【００５７】
結果がソートされる必要がある場合には、最大ヒープ全体に対してクイックソート・アルゴリズムを使う、あるいは各ステップにおいてルート要素を取って縮小サイズでヒープを再構築することができる。
【００５８】
保存されるべき、ローカルな頂点における第二の要素は、経路上の先行する頂点の形でのk個の最短経路である。1＜i＜kとして、i番目に短い経路は、頂点についての重複のある、最も短い経路の変形である可能性が高い。頂点において記憶されるデータのサイズを減らすために、ストリング圧縮法が適用できる。たとえば、最短経路は、先行する頂点を一つ一つ同定できるようにするフォーマットで記憶されることができる。k個の最短経路のうちの残りのk−1個は、最短経路と問題の経路との間の差分が同定できるようにするフォーマットで記憶されることができる。あるいはまた、問題の頂点でのk個の最短の経路と指定された先行する頂点でのK個の最短の経路との間の差分が記憶されることができる。
【００５９】
グラフの実際の実装に依存して、記憶実装は異なることができる。プロセス開始プロセスからある頂点までのk個の最短経路は、鍵値記憶部の値部分を利用することによって、頂点において記憶されることができる。鍵値記憶部において、当該頂点が主体となっているトリプルが鍵である。エッジ指向のグラフ記憶のためには、上記のデータ構造は、頂点が導入されるときにエッジに記憶されることができる。たとえば、RDFグラフ記憶では、上記の情報は次のフォーマットでRDFトリプルに記憶されることができる：
〈http://foo.bar/someentity,rdf:type,http://foo.bar/sometype〉
ここで、RDF資源が形式的に定義されている。頂点指向のグラフ記憶のためには、そのような情報は（隠された）頂点属性として記憶されることができる。
【００６０】
諸方法は、プロセス開始頂点（プロセス開始頂点は、本稿の他所では第一の頂点と称されている）から特定の頂点までのk個の最短経路を見出すのに、任意の頂点vについて、
【数１】
2015169654.tif 000003
であれば、
【数２】
2015169654.tif 000004
であるという属性を利用する。ここで、SPは所与の二つの頂点の間の最短経路（shortest  path）を表わす。すなわち、源頂点sから行き先頂点tまでの、頂点vを含む最短経路は、sからvまでの最短経路をvからtまでの最短経路に加えることによって得られる。これに基づいて、前記主プロセスまたは前記並列プロセスの一部としての前記計算手順は頂点ごとに進行する。
【００６１】
例示的な方法は以下のステップを含んでいてもよい。
・k個の最短経路長が初期に∞として記憶されているテーブルまたは記憶データの他の何らかの形に、各頂点をエンコードするデータを加えることによって頂点を初期化する；
・源頂点Sから、Sから行き先頂点までの経路上のその後の諸頂点への、前記計算手順がそれらその後の頂点を前記特定の頂点として実行できることをそれらその後の頂点に通知するメッセージをトリガーする；
・前記主プロセスを進める。各頂点はその先行する諸頂点からメッセージを受け取り、ローカルなK個の最短経路を更新する（徐々に∞値を置換し、その後は源頂点から問題の頂点までの新たに計算された経路長より長い経路長があればそれを置換する）；
・各頂点がその先行する頂点のすべてのチェックリストを維持する。先行頂点からその先行頂点において前記計算手順が実行されたというメッセージを受け取り、応答して当該頂点に記憶されているk個の最短頂点を更新した（更新が必要とされる場合）のち、チェックリストの対応する要素がチェックされる。ひとたびチェックリストのすべての要素がチェックされたら、諸経路上の唯一のその後の頂点または各その後の頂点に、当該頂点についての前記計算手順が完了であることを通知する；
・並列プロセスを実行すべきグラフの部分を選択し、並列プロセス開始頂点PISから、PISから並列プロセス行き先頂点までの経路上のその後の諸頂点に、それらその後の頂点を前記特定の頂点として前記計算手順が実行されることができることをそれらその後の頂点に通知するメッセージをトリガーすることによって、前記並列プロセスを開始する；
・前記並列プロセスを進める。各頂点がその諸先行頂点からメッセージを受け取り、PISから当該頂点までのローカルなK個の最短経路を記憶する；
・ひとたび前記主プロセスが前記並列プロセス開始頂点に達したら、前記並列プロセスの一部として前記計算手順が実行された各頂点において、PISから当該頂点までのk個の最短経路に、SからPISまでのk個の最短経路を加えることによって、SからPISを経て当該頂点までのk個の最短経路を見出す。
【００６２】
前記計算手順を実行するための例示的な手順がここで論じられる。図２は、データ・グラフの断片を示している。AからCへのエッジおよびBからCへのエッジは有向エッジである。頂点AおよびBは頂点Cに先行する。長さ値dが頂点Aから頂点Cまでの経路に帰属させられている。長さ値d'が頂点Bから頂点Cまでの経路に帰属させられている。
【００６３】
前記計算手順が前記特定の頂点としての頂点Cについてどのように実行されうるかの第一の例として、頂点Aはロックを取得し、頂点Aに記憶されているK個の最短経路を通じて逐次反復され、頂点Aに記憶されているi番目に短い経路のいずれかについて（ここで、1≦i≦k）、lia＋dが頂点Cにおいて現在維持されているk個の最短経路のうちの最も長いものより短ければ、しかるべく頂点Cに記憶されているk個の最短経路を更新する（ここで、liaは、プロセス開始頂点から頂点aまでのi番目に短い経路の経路長である）。次いでロックが解放されて、頂点Bが同じようにしてCにおいて維持されているk個の最短経路を更新できる。
【００６４】
第二の例では、頂点AおよびBの両方がそのローカルなk個の最短経路を頂点Cにメッセージとして渡す。これはたとえば、それらの頂点としてひとたび前記計算手順が完了されたら行なわれる。次いで、頂点Cについての前記計算手順は、はいってくるデータを経路長に基づいてソートし、m個の（m＝先行する頂点の数×k）受領された経路を、メッセージが受領された受領元の頂点からその特定の頂点までのエッジに帰属されられている長さ値を加えることによって修正したもののうちからk個の最短経路を同定し、次いでそれらk個の同定された経路を使ってローカルな更新を行なうことを含む。
【００６５】
前記主プロセスおよび前記並列プロセスは、同じ計算手順に基づいており、それは次のように要約できる：
・頂点が現在のk個の最短経路の情報をその隣接頂点すべてに渡し、そのような隣接頂点での更新を開始する。
・頂点の現在の状態が、受け取るメッセージに基づいて変化し、よってそのメッセージへの反応が変化する。
【００６６】
グラフがp個の領域に分散しており、各領域が、自分自身の専用の処理資源を有する別個のデータ記憶ユニットに記憶されているとする。前記計算プロセスは、源頂点sにおいてローカルな最短経路キャッシュを更新することによって開始される。更新イベントがトリガーされる。このイベントはsにいる観察者によって捕捉されるであろう。その結果、sは、sから行き先頂点までの諸経路上のその後の諸頂点にメッセージを送る。
【００６７】
分散したデータ・グラフ（複数の領域に分割されたグラフ）は、二つ以上のグラフ・パーティションに存在する多数の境界頂点を有していてもよい（パーティションというのは、データ・グラフのある領域の記憶されたバージョン）。すなわち、境界頂点は、該境界頂点が境界をなしている領域の両方の一部として、複製され、記憶されてもよい。諸方法は、同時並行処理を実行するためにこのデータ記憶構造を利用する。
【００６８】
諸方法は、並列プロセス開始頂点について決定するために何らかの発見法的解析を実行することを含んでいてもよい。並列プロセス開始頂点を選択するための例示的な技法について、ここで論じる。これは、前記主手順がまだ源頂点から行き先頂点までの経路上の各頂点について完了していないときに適用されることを注意しておく。そのような場合、計算は、最も短いまたは最初のK個の最短経路を呈する境界頂点（単数または複数）から続く。
【００６９】
データ・グラフを記憶しているシステムがアイドルであるまたはオフラインであってより多くのコンピューティング資源が利用可能である間に、準備段が実行されることができる。
【００７０】
準備段は、グラフの中間性中心性（betweenness  centrality）を取得することを含む。中間性（betweenness）値が高い頂点がコア集合Sbとして事前選択される。一例では、コア集合Sbは、全体的なデータ・グラフについて最も高い中間性値をもつほうから所定数の頂点（すなわち、グラフ全体のうち最も中央の諸頂点）を含む。別の例では、コア集合Sbは、各パーティションについて最も高い中間性値をもつほうから所定数の頂点（すなわち、そのパーティションのうち最も中央の諸頂点）を含む。パーティションpiについて、諸中央頂点{v|v∈Sb∧v∈pi}とすべての境界頂点との間の距離／経路長が計算され、記憶される。
【００７１】
この例示的な技法は、準備段によって計算されたデータを、源頂点sと行き先頂点tとの間のk個の最短経路を見出すための方法において、利用する。ここで、psはsを含むパーティションであり、
【数３】
2015169654.tif 000005
である。前記主プロセスの一部としての前記計算手順が始まるとき、psのすべての隣接パーティションについて、並列プロセスは次の優先順位をもって始まる。
【００７２】
すべての隣接頂点は、ps内の諸中央頂点からの最も低い平均経路長をもつものを最高ランクとし、他のものは昇順としてランク付けされる。psと境界を共有するパーティションの、同じパーティションからの他のすべての境界頂点に比べてps内の中央頂点から最も低い平均経路長をもつ境界頂点が、並列プロセス開始頂点として選択される。
【００７３】
並列プロセス開始頂点を選択するために他の技法が使われてもよい。たとえば、sからtへの経路上の諸頂点を含む任意のパーティションpjについて、並列プロセス開始頂点は、前記準備段に基づいて、psの中央頂点までの最短経路長（または諸中央頂点までの最短の平均経路長）をもつ境界頂点として選択されてもよい。
【００７４】
さらに、頻繁に更新され、中間性中心性が不安定になるデータ・グラフには、代替的な技法が特に好適であることがある。そのようなさらなる代替的な技法は：
・前記中間性中心性が最後に測定されて以降に更新された諸頂点が高次の（high-degree）ものでなければ、グラフの変化は全体的なグラフ・トポロジーに著しく影響しないであろうとの想定で、もとの中心性（centrality）を使うことができる；あるいは
・前記中間性中心性が最後に測定されて以降に更新された諸頂点が高次の（high-degree）ものであれば、前記並列プロセスは、当該パーティション内の諸頂点についての中間性中心性が再計算されてそれらの中央頂点がしかるべく更新されるあとまで、遅延させられる。
【００７５】
上記で概説したように、ひとたび前記主プロセスが並列プロセス開始頂点に達したら、前記計算手順が前記並列プロセスの一部として実行された各頂点において、並列プロセス開始頂点から当該頂点までのk個の最短経路に、Sから並列プロセス開始頂点までのk個の最短経路を加え、並列プロセス開始頂点を介してのSから当該頂点までのk個の最短経路を見出す。任意のパーティションpyに属する境界頂点が並列プロセス開始頂点として選択される（そしてたとえば、sからtまでの経路上の、py内の残りの境界頂点の一つまたは複数が、並列プロセス終了頂点として選択される）実施形態では、ひとたび、前記並列プロセスの一部として第一群の頂点において前記計算手順が実行され、前記主プロセスの一部として前記並列プロセス開始頂点において前記計算手順が実行されたら、結果の何らかの同期が実行されることができる。Slcが頂点の前記第一群であり、Ssbが並列プロセス開始頂点として選択されている境界頂点の集合であるとする。
【００７６】
あらゆる任意の頂点vx∈Ssbについて：
・vx∈Slcであれば、事前計算された経路をvxにおいて呈される経路長を用いて更新  ・py内の任意の頂点vyについて、これはDis(s,vy)＝Dis(s,vx)＋Dis(vx,vy)として行なわれる。ここで、Dis()は二つのグラフ頂点の間の経路長を呈する。
・
【数４】
2015169654.tif 000006
であり、前記並列プロセス開始頂点からのk個の最短経路がまだ計算されていなければ、当該頂点に記憶されている前記並列プロセス開始頂点からのいかなる経路および経路長も破棄する。
【００７７】
任意的に、k最短経路解析が実行される頻度に対してあまり頻繁に変化しない中央頂点をもつデータ・グラフでは、何らかのキャッシングが適用されれば全体的なパフォーマンスを改善できる。たとえば、履歴データに基づいて、中間性中心性の推定が過去の計算から得られることができる。その際、同一の中央頂点および最短経路がすでに計算されている他のグラフ頂点からの最短経路の長さが、将来重複した計算を回避するためにキャッシュされることができる。これは次のようになされる。
【００７８】
中間性中心（Betweenness  centres）（c1）として同定される頂点のローカルなデータ構造が、きわめて頻繁に問い合わせされるグラフ頂点（行き先頂点としてよく選択される頂点）についてのマップを用いて拡張されることができる。該マップの鍵は、頻繁に問い合わせされるグラフ頂点の諸頂点である。値部分もマップである。
・本発明を具現する方法の一部として(k)個の最短経路が計算されていたら、それぞれの選択された頂点（たとえばvx）の値マップは、c1からvxまでの(k)個の最短経路を入れられる。
・前記主プロセスの一部として前記計算手順を実行するとき、前記主プロセスが中間性中心に達したら、ローカル・マップを検索することによって解がすでにわかっているかどうかをチェックする。
・キャッシュ照合が真を返す。源頂点から中間性中心までのk個の最短経路が、中間性中心からvxまでのk個の最短経路と組み合わされて、予備的な結果、すなわち中間性中心を経てのsからvxへのk個の最短経路を生成する。
・キャッシュ照合が偽を返す。主プロセスの計算が続けられ、コールバック動作にフラグが付けられる。
・前記主プロセスが完了したとき、システムは戻ってすべてのフラグを付けられた中間性中心のキャッシュを更新する。
【００７９】
キャッシング専用とする記憶スペースの量は、実装毎に決定すべきである。キャッシュ照合は単に厳密な一致照合（すなわち、目標頂点がキャッシュ・マップ／テーブル内にあるかどうかをチェックする）またはグラフに基づく照合（すなわち、キャッシュされた頂点が目標頂点への経路上にあるかどうかをチェックする）であることができる。後者は計算上より高価であり、常に全体的なパフォーマンスを改善するとは限らない。多くの場合、厳密な一致照合が十分であるはずである。キャッシュの更新は、頻度および／またはユーザーが定義した基準に基づいていてもよい。重要度の低いまたは使用率の低いキャッシュされた値は削除されてもよい。
【００８０】
諸側面（ソフトウェア／方法／装置）が別個に論じられているが、一つの側面に関連して論じられる特徴および帰結は他の側面にも等しく適用可能であることは理解しておくべきである。したがって、方法特徴が論じられる場合、装置実施形態はその特徴を実行するまたは適切な機能を提供するよう構成されたユニットまたは装置を含み、プログラムは該プログラムが実行されるコンピューティング装置に該装置特徴を実行させるよう構成されることは当然である。
【００８１】
上記の側面のいずれにおいても、さまざまな特徴は、ハードウェアにおいてまたは一つまたは複数のプロセッサ上で走るソフトウェア・モジュールとして実装されうる。ある側面の特徴は、他の側面の任意のものに適用されてもよい。
【００８２】
本発明は、本稿に記載された方法の任意のものを実行するためのコンピュータ・プログラムまたはコンピュータ・プログラム・プロダクトならびに本稿に記載された方法の任意のものを実行するためのプログラムを記憶しているコンピュータ可読媒体をも提供する。本発明を具現するコンピュータ・プログラムは、コンピュータ可読媒体上に記憶されていてもよく、あるいはたとえばインターネット・ウェブサイトから提供されるダウンロード可能なデータ信号のような信号の形であることもでき、あるいは他のいかなる形であることもできる。
【００８３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
エッジによって相互接続された頂点から構成されるデータ・グラフにおける源頂点と行き先頂点との間の諸経路のうちでk個の最短経路長を見出すコンピュータ実装される方法であって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数であり、当該方法は、主プロセスを実行することを含み、前記主プロセスは計算手順を実行することを含み、頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点の直前であると定義され、前記計算手順は、
特定の頂点の直前の唯一のまたは各頂点について：
前記直前の頂点について前記計算手順が完了しているという通知を受け取り；
前記直前の頂点から前記特定の頂点までのエッジに帰属させられた長さ値を、前記第一の頂点から前記直前の頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含み、
前記計算手順はさらに：
前記特定の頂点について計算されたk個の最短経路長の記録を維持し；
前記直前の頂点のうちの前記唯一のまたは各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含み；
前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、
当該方法はさらに、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行することを含み、前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある、
コンピュータ実装される方法。
（付記２）
当該方法が、各反復での同じ頂点および各反復での異なる行き先頂点を用いて少なくとも一回反復される、付記１記載のコンピュータ実装される方法。
（付記３）
当該方法がさらに：
前記主プロセスの一部として、前記一つまたは複数の並列プロセス開始頂点のうちのある並列プロセス開始頂点について前記計算手順が完了したという通知が発されたのち、および前記並列プロセスの一部として、対応する並列プロセス終了頂点について前記計算手順が完了したという通知が発されたのち、前記並列プロセスの一部として前記計算手順が実行された各頂点において記録された並列プロセス開始頂点からのk個の最短経路長を、その並列プロセス開始頂点において記録されている源頂点からのk個の最短経路長を加えることによって修正することを含む、
付記１記載のコンピュータ実装される方法。
（付記４）
前記データ・グラフが領域に分割されて二つ以上のデータ記憶ユニットにまたがって分散して記憶され、各データ記憶ユニットが前記領域の少なくとも一つを記憶し、専用の計算処理ユニットをもち、前記計算手順が前記特定の頂点が記憶されているデータ記憶ユニットに専用の計算処理ユニットによって実行される、付記１記載のコンピュータ実装される方法。
（付記５）
唯一の並列プロセス開始頂点または各並列プロセス開始頂点および対応する並列プロセス終了頂点は同じ領域からのものであり、前記並列プロセス開始頂点はその領域の境界頂点であり、前記予備的な計算手順は、やはり同じ領域内にある頂点から構成される任意の経路上の各頂点について実行される、
付記４記載のコンピュータ実装される方法。
（付記６）
唯一の並列プロセスまたは各並列プロセスは、各反復での同じ並列プロセス開始頂点および各反復での異なる並列プロセス終了頂点を用いて少なくとも一度繰り返される、
付記４記載のコンピュータ実装される方法。
（付記７）
各領域について、当該領域の境界にある各頂点について、該頂点を該頂点から当該領域の前記一つまたは複数の同定された中央頂点またはそのそれぞれまでの最短経路長と関連付けて記憶し；
前記並列プロセス開始頂点を選択することをさらに含む、付記４記載の方法であって、前記並列プロセス開始頂点の選択は：
源頂点を含む領域内の、異なるデータ記憶ユニット上に記憶されている隣接領域にエッジによって接続されている境界頂点のうちから、同定された中央頂点までの最短経路長をもつまたは前記二つ以上の同定された中央頂点までの最小の平均最短経路長をもつ境界頂点を同定し；
同定された境界頂点またはエッジによって該同定された境界頂点に接続されている前記隣接領域内の境界頂点のいずれかを、前記並列プロセス開始頂点として選択することによって行なわれる、
方法。
（付記８）
領域の前記中央頂点は、中間性中心性指標に基づいて同定される、付記７記載の方法。
（付記９）
最短経路長の記録を維持することが、前記経路長を、それぞれの経路上の前記一つまたは複数の先行する頂点を同定する情報に関連付けて記憶することを含む、
付記１記載の方法。
（付記１０）
前記記録を維持することが：
その特定の頂点において、k個の最短経路のそれぞれの先行する頂点を、それぞれのk個の最短経路長をインデックス付け値とするヒープ・フォーマットで記憶することを含む、
付記９記載の方法。
（付記１１）
前記k個の最短経路のそれぞれの先行する頂点を記憶することが、最短経路上の先行する各頂点の同定情報を記憶し、残りのk−1個の最短経路については前記最短経路からの差の同定情報を記憶することを含む、
付記９記載の方法。
（付記１２）
前記計算手順において、前記特定の頂点についての新たな経路長を計算することは、直前の各頂点のために順次：
前記特定の頂点について計算されたk個の最短経路長の記録へのアクセスを一時的にロックし；
直前の頂点において記録されている、記録されたk個の最短経路長のそれぞれに、直前の頂点から前記特定の頂点までのエッジに帰属させられている長さ値を加えることによって、前記特定の頂点についての新たな経路長を計算し；
前記特定の頂点について計算されたk個の最短経路長の記録を更新して、計算された新たな経路長およびロックされた記録されているk個の最短経路長のうちのk個の最短経路長を含むようにし；
k個の最短経路長の記録へのアクセスをロック解除することによって実行される、
付記１ないし１１のうちいずれか一項記載の方法。
（付記１３）
前記特定の頂点について前記計算手順が完了しているという通知を発することが、前記特定の頂点が源頂点から行き先頂点までの経路上の直前の頂点であるような頂点または各頂点に、前記特定の頂点についてのk個の最短経路長の記録を送信することを含み、
前記計算手順において、
前記特定の頂点についての新たな経路長を計算することは、前記直前の頂点から前記特定の頂点までのエッジに帰属させられている長さ値を、前記直前の頂点から受領された記録に含まれるk個の最短経路長のそれぞれに加えることを含む、
付記１記載の方法。
（付記１４）
前記主プロセスが、諸頂点が、前記計算手順が実行される前記特定の頂点となる順序を決定することを含み、前記特定の頂点となるのは、前記計算手順がまだ完了しておらず、前記計算手順が唯一の直前の頂点または各直前の頂点については完了している頂点のうちから、前記直前の頂点が源頂点への最短経路長をもつとして記録されている頂点を、次の特定の頂点として選択することによる、
付記１記載の方法。
（付記１５）
エッジによって相互接続された頂点から構成されるデータ・グラフにおける源頂点と行き先頂点との間の諸経路のうちでk個の最短経路長を見出す装置であって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数であり、当該装置は、主プロセスを実行するよう構成されており、前記主プロセスは計算手順を実行することを含み、頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点の直前であると定義され、前記計算手順は、特定の頂点の直前の唯一の頂点または各頂点について：
前記直前の頂点について前記計算手順が完了しているという通知を受け取り；
前記直前の頂点から前記特定の頂点までの前記エッジに帰属させられている長さ値を、前記第一の頂点から前記直前の頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含み、
前記計算手順はさらに：
前記特定の頂点について計算されたk個の最短経路長の記録を維持し；
直前の唯一の頂点または直前の各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含み、
前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、
当該装置は、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行するよう構成されており、前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある、
装置。
（付記１６）
コンピューティング装置によって実行されたときに、前記コンピューティング装置に、エッジによって相互接続された頂点から構成されるデータ・グラフにおける源頂点と行き先頂点との間の諸経路のうちでk個の最短経路長を見出すプロセスを実行させるコンピュータ・プログラムであって、経路とは、それに沿ってどの単一の頂点も二回以上含まれないような、エッジによって接続された頂点の任意の系列であり、エッジには長さ値が帰属させられており、kは2以上の整数であり、前記プロセスは、主プロセスを実行することを含み、前記主プロセスは計算手順を実行することを含み、頂点が特定の頂点にエッジによって接続され、その頂点が第一の頂点から前記特定の頂点までの経路の一つの上にある場合にその頂点は前記特定の頂点の直前であると定義され、前記計算手順は、
特定の頂点の直前の唯一のまたは各頂点について：
前記直前の頂点について前記計算手順が完了しているという通知を受け取り；
前記直前の頂点から前記特定の頂点までのエッジに帰属させられた長さ値を、前記第一の頂点から前記直前の頂点までの記録されているk個の最短経路長のそれぞれに加えることによって、前記特定の頂点についての新たな経路長を計算することを含み、
前記計算手順はさらに：
前記特定の頂点について計算されたk個の最短経路長の記録を維持し；
前記直前の頂点のうちの前記唯一のまたは各頂点について前記新たな経路長が計算されたのち、前記特定の頂点について前記計算手順が完了しているとの通知を発することを含み；
前記主プロセスは、前記源頂点を前記第一の頂点として、前記源頂点から前記行き先頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、
前記プロセスはさらに、前記主プロセスと並行して、一つまたは複数の並列プロセスを実行することを含み、前記並列プロセスまたは各並列プロセスは、並列プロセス開始頂点を前記第一の頂点として、前記並列プロセス開始頂点から並列プロセス終了頂点までの経路上の各頂点を前記特定の頂点として前記計算手順を実行することを含み、前記並列プロセス開始頂点および前記並列プロセス終了頂点はいずれも前記源頂点から前記行き先頂点までの経路上にある、
コンピュータ・プログラム。
【符号の説明】
【００８４】
S101  開始
S102  源頂点から行先頂点への経路上の各頂点について、源頂点からのk個の最短経路長を計算
S103  並列プロセス開始頂点から並列プロセス終了頂点への経路上の各頂点について、並列プロセス開始頂点からのk個の最短経路長を計算
S104  終了
【図１】
2015169654.tif 000007
【図２】
2015169654.tif 000008