(57)【要約】グラフデータクエリ方法および装置が開示される。方法は、クエリ頂点の区画番号および層番号を取得するステップと、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用するステップと、その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成するステップと、クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップとを含む。解決法を使用することによって、グラフデータクエリ効率が向上される。
2017509043.tif 000002
【特許請求の範囲】
【請求項１】
グラフデータ全体セットにおけるグラフデータのクエリに適用されるグラフデータクエリ方法であって、前記グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、前記グラフデータ全体セットにおける前記複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が前記頂点の区画番号として使用され、頂点と、前記頂点が置かれている区画の区画境界との間の最短距離が前記頂点の層番号として使用され、前記方法は、
クエリ条件、および前記クエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するステップと、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップ、およびそれらを候補区画番号および候補層番号として使用するステップであって、前記候補頂点は、前記クエリ条件に従ってクエリされる必要がある頂点である、ステップと、
その区画番号および層番号が前記候補区画番号および前記候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するステップと、
前記クエリ条件に従って前記候補セットにおいてグラフデータクエリを行うステップと
を含むことを特徴とする方法。
【請求項２】
頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、前記デフォルト層番号は、前記頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップの前に、前記方法は、
前記クエリ頂点の前記層番号が前記デフォルト層番号であるかどうかを決定するステップ、および、前記決定するステップの結果が、前記クエリ頂点の前記層番号が前記デフォルト層番号でないことである場合、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップをトリガするステップ
をさらに含むか、または、
前記方法は、
前記クエリ頂点の前記層番号が前記デフォルト層番号である場合、その区画番号が前記クエリ頂点の前記区画番号であり、その層番号が前記デフォルト層番号である頂点を使用することによって候補セットを形成するステップと、
前記クエリ条件に従って前記候補セットにおいてグラフデータクエリを行うステップと
をさらに含む
ことを特徴とする請求項１に記載の方法。
【請求項３】
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有する場合、または前記辺のどれもが重みを有しない場合、頂点と前記頂点が置かれている区画の区画境界との間の最短距離は、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最小ホップカウントであり、前記２つの頂点間の距離は、前記２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有するのではない場合、頂点と前記頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最短距離として使用され、２つの頂点間の距離は、前記２つの頂点のうち一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、前記経路に含まれる辺の重みの総和である
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップは、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、および前記クエリ条件によって示される前記候補頂点と前記クエリ頂点との間の距離に従って、前記候補頂点の前記区画番号および前記層番号を決定するステップ
を具体的に含む
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記グラフデータ全体セットにおける前記複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、前記頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
前記クエリ条件が、前記候補頂点と前記クエリ頂点との間の最大距離を示す場合、前記候補頂点の区画番号および層番号を決定する前記ステップは、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定するステップ、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定するステップ、または、
前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定するステップ、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ、および、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定するステップ、および、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定するステップ
を具体的に含む
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記グラフデータ全体セットにおける前記複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、前記区画境界上の前記頂点と、前記頂点が置かれている区画の前記区画境界との間の最短距離がゼロであり、
前記クエリ条件が、前記候補頂点と前記クエリ頂点との間の最大距離を示す場合、前記候補頂点の区画番号および層番号を決定する前記ステップは、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定するステップ、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定するステップ、または、
前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定するステップ、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、およびゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ、および、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算することによって得られる値との間の最小値を決定するステップ、および、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定するステップ
を具体的に含む
ことを特徴とする請求項４に記載の方法。
【請求項７】
クエリ条件、ならびに前記クエリ条件によって示されるクエリ頂点の区画番号および層番号を取得する前記ステップは、
前記クエリ条件を取得し、前記クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、前記第１のクエリ頂点の区画番号および層番号ならびに前記第２のクエリ頂点の区画番号および層番号を取得するステップ
を具体的に含み、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップは、
前記第１のクエリ頂点および前記第２のクエリ頂点が同じ区画に置かれている場合、前記候補頂点の前記区画番号は前記第１のクエリ頂点および前記第２のクエリ頂点の前記区画番号であることを決定するステップ、および、前記第１のクエリ頂点の前記層番号から前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の前記層番号として決定するステップ、または、
前記第１のクエリ頂点および前記第２のクエリ頂点が異なる区画に置かれている場合、前記候補頂点の前記区画番号は前記第１のクエリ頂点の前記区画番号および前記第２のクエリ頂点の前記区画番号であることを決定するステップ、前記第１のクエリ頂点が置かれている区画について、ゼロから前記第１のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第１のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ、および、前記第２のクエリ頂点が置かれている区画について、ゼロから前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第２のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ
を具体的に含む
ことを特徴とする請求項１に記載の方法。
【請求項８】
前記クエリ条件に従って、必要とされるグラフデータが前記候補セットにおいて見出されない場合、拡張された候補セットを得るように前記候補セットに含まれる層番号区間を拡張するステップと、
前記クエリ条件に従って前記拡張された候補セットにおいてグラフデータクエリを実行するステップと
をさらに含む
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記グラフデータ全体セットにおける前記グラフデータがファイルシステムに保存されている場合、前記複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存されることを特徴とする請求項１に記載の方法。
【請求項１０】
前記クエリ条件に従って前記候補セットにおいてグラフデータクエリを行う前記ステップは、
前記候補セットに含まれる頂点のグラフデータをメモリにロードするステップと、
前記クエリ条件に従って、前記候補セットに含まれる前記頂点のグラフデータであり、前記メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うステップと
を具体的に含む
ことを特徴とする請求項１乃至９のいずれか一項に記載の方法。
【請求項１１】
グラフデータ全体セットにおけるグラフデータのクエリに適用されるグラフデータクエリ装置であって、前記グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、前記グラフデータ全体セットにおける前記複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が前記頂点の区画番号として使用され、頂点と、前記頂点が置かれている区画の区画境界との間の最短距離が前記頂点の層番号として使用され、前記クエリ装置は、
クエリ条件、ならびに前記クエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するように構成された取得ユニットと、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用するように構成された第１の決定ユニットであって、前記候補頂点は、前記クエリ条件に従ってクエリされる必要がある頂点である、第１の決定ユニットと、
その区画番号および層番号が前記候補区画番号および前記候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するように構成された第２の決定ユニットと、
前記クエリ条件に従って前記候補セットにおいてグラフデータクエリを行うように構成されたクエリユニットと
を含むことを特徴とするグラフデータクエリ装置。
【請求項１２】
頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、前記デフォルト層番号は、前記頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
前記第１の決定ユニットは、前記クエリ条件によって示される前記候補頂点の前記区画番号および前記層番号を決定する前に、前記クエリ頂点の前記層番号が前記デフォルト層番号であるかどうかを決定し、前記決定することの結果が、前記クエリ頂点の前記層番号が前記デフォルト層番号でないことである場合、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップをトリガするようにさらに構成され、
前記第２の決定ユニットは、前記クエリ頂点の前記層番号が前記デフォルト層番号である場合、その区画番号が前記クエリ頂点の前記区画番号であり、その層番号が前記デフォルト層番号である頂点を使用することによって候補セットを形成するようにさらに構成された
ことを特徴とする請求項１１に記載の装置。
【請求項１３】
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有する場合、または前記辺のどれもが重みを有しない場合、頂点と前記頂点が置かれている区画の区画境界との間の最短距離は、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最小ホップカウントであり、前記２つの頂点間の距離は、前記２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有するのではない場合、頂点と前記頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最短距離として使用され、２つの頂点間の距離は、前記２つの頂点のうち一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、前記経路に含まれる辺の重みの総和である
ことを特徴とする請求項１１に記載の装置。
【請求項１４】
前記第１の決定ユニットは、前記クエリ頂点の前記区画番号および前記層番号に基づいて、および前記クエリ条件によって示される前記候補頂点と前記クエリ頂点との間の距離に従って、前記候補頂点の前記区画番号および前記層番号を決定するように具体的に構成された
ことを特徴とする請求項１１に記載の装置。
【請求項１５】
前記グラフデータ全体セットにおける前記複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、前記頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
前記第１の決定ユニットは、
前記クエリ条件が、前記候補頂点と前記クエリ頂点との間の最大距離を示す場合、前記候補頂点の前記区画番号および前記層番号を以下のように決定するように、すなわち、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定し、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定する、または、
前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定し、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定する
ように具体的に構成された
ことを特徴とする請求項１４に記載の装置。
【請求項１６】
前記グラフデータ全体セットにおける前記複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、前記区画境界上の前記頂点と、前記頂点が置かれている区画の前記区画境界との間の最短距離がゼロであり、
前記第１の決定ユニットは、
前記クエリ条件が、前記候補頂点と前記クエリ頂点との間の最大距離を示す場合、前記候補頂点の前記区画番号および前記層番号を以下のように決定するように、すなわち、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定し、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定する、または、
前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定し、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定する
ように具体的に構成された
ことを特徴とする請求項１４に記載の装置。
【請求項１７】
前記取得ユニットは、前記クエリ条件を取得し、前記クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、前記第１のクエリ頂点の区画番号および層番号ならびに前記第２のクエリ頂点の区画番号および層番号を取得するように具体的に構成され、
前記第１の決定ユニットは、
前記第１のクエリ頂点および前記第２のクエリ頂点が同じ区画に置かれている場合、前記候補頂点の前記区画番号は前記第１のクエリ頂点および前記第２のクエリ頂点の前記区画番号であることを決定し、前記第１のクエリ頂点の前記層番号から前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の前記層番号として決定する、または、
前記第１のクエリ頂点および前記第２のクエリ頂点が異なる区画に置かれている場合、前記候補頂点の前記区画番号は前記第１のクエリ頂点および前記第２のクエリ頂点の前記区画番号であることを決定し、前記第１のクエリ頂点が置かれている区画について、ゼロから前記第１のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第１のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定し、前記第２のクエリ頂点が置かれている区画について、ゼロから前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第２のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定する
ように具体的に構成された
ことを特徴とする請求項１１に記載の装置。
【請求項１８】
前記第２の決定ユニットは、前記クエリユニットが、前記クエリ条件に従って、必要とされるグラフデータを前記候補セットにおいて見出さない場合、拡張された候補セットを得るように前記候補セットに含まれる層番号区間を拡張するようにさらに構成され、
前記クエリユニットは、前記クエリ条件に従って前記拡張された候補セットにおいてグラフデータクエリを行うようにさらに構成された
ことを特徴とする請求項１７に記載の装置。
【請求項１９】
前記グラフデータ全体セットにおける前記グラフデータがファイルシステムに保存されている場合、前記複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存されることを特徴とする請求項１１に記載の装置。
【請求項２０】
前記クエリユニットは、前記候補セットに含まれる頂点のグラフデータをメモリにロードし、前記クエリ条件に従って、前記候補セットに含まれる前記頂点のグラフデータであり、前記メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うように具体的に構成されたことを特徴とする請求項１１乃至１９のいずれか一項に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理技術の分野におけるグラフデータクエリ技術の分野に関し、より詳細には、グラフデータクエリ方法および装置に関する。
【背景技術】
【０００２】
ソーシャルネットワーク、ワールドワイドウェブ、通信ネットワークなどの急速な発展で、グラフデータに基づく組織化およびクエリ技術が出現してきた。データ容量が比較的大きい場合、グラフデータはまた、ビッググラフデータと呼ぶこともできる。
【０００３】
グラフデータのセットは、グラフデータ全体セットと呼ばれることがあり、グラフデータ全体セットは普通、多数の頂点、および接続関係を有する各２つの頂点の間の辺を含む。実際のアプリケーションシナリオによると、頂点は対応する物理的意味を示すことがある。例えば、ソーシャルネットワークでは、頂点はユーザを示し、頂点のグラフデータは、名前、性別、年齢、友人リストなどの、頂点によって示されたユーザの様々な属性データを含むことができ、接続関係を有する２つの頂点では、辺が２つの頂点の間に作り出され、辺は２つの頂点によって示されるユーザが友人であることを示すことができる。別の例では、マップにおいては、頂点は地理的位置を示し、頂点のグラフデータは、位置名、位置座標などの、頂点によって示される地理的位置の様々な属性データを含むことができ、接続関係を有する２つの頂点では、辺は２つの頂点の間に作り出されるのであり、辺は、２つの頂点によって示される地理的位置の間の直接経路があること、すなわち、一方の頂点は、他方の頂点を通過することなく他の頂点から接続され得ることを示すことができる。
【０００４】
グラフデータの実際のアプリケーションでは、グラフデータはしばしば、予測グラフデータを取得するためにクエリされる必要がある。例えば、ソーシャルネットワークでは、特定のユーザの関連グラフデータがクエリされることが可能であり、または特定のユーザとの友人関係を有するユーザが、クエリ条件に従ってクエリされることが可能であり。別の例では、マップにおいて、２つの地理的位置の間の最短経路をクエリすることが可能である。
【０００５】
しかし、グラフデータ全体セットのデータ容量が大きくなると、各グラフデータクエリはグラフデータ全体セットに含まれる全てのグラフデータに基づいているので、クエリ効率が低くなる。
【０００６】
クエリ効率を向上させるために、グラフデータを組織化するいくつかの解決法は、従来技術で生じた。これらの解決法では、区画化アルゴリズムは普通、グラフデータを組織化するために使用される、すなわち、グラフデータ全体セット内の全てのグラフデータは、別個の記憶および計算の多数の区画に分割される。
【０００７】
しかし、区画化はグラフデータ上で行われるが、いくつかのクエリ要件、例えば距離関連クエリ要件では、クエリはまだ、クエリ結果の精度が保証されるように、グラフデータ全体セットに基づいて行われる必要がある。この場合、比較的低いクエリ効率の問題が依然として存在する。
【発明の概要】
【課題を解決するための手段】
【０００８】
本発明の実施形態は、グラフデータクエリ効率が比較的低いという従来技術の問題を解決するように、グラフデータクエリ方法および装置を提供する。
【０００９】
第１の態様によると、グラフデータクエリ方法が提供され、これは、グラフデータ全体セットにおけるグラフデータのクエリに適用され、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用され、方法は、
クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するステップと、
クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップ、およびそれらを候補区画番号および候補層番号として使用するステップであって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である、ステップと、
その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するステップと、
クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップと
を含む。
【００１０】
第１の態様を参照し、第１の可能な実装方式では、頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、デフォルト層番号は、頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップの前に、方法は、
クエリ頂点の層番号がデフォルト層番号であるかどうかを決定するステップ、および、決定するステップの結果が、クエリ頂点の層番号がデフォルト層番号でないことである場合、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップをトリガするステップ
をさらに含むか、または、
方法は、
クエリ頂点の層番号がデフォルト層番号である場合、その区画番号がクエリ頂点の区画番号であり、その層番号がデフォルト層番号である頂点を使用することによって候補セットを形成するステップと、
クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップと
をさらに含む。
【００１１】
第１の態様を参照し、第２の可能な実装方式では、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有する場合、または辺のどれもが重みを有しない場合、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点と頂点が置かれている区画の区画境界との間の最小ホップカウントであり、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有するのではない場合、頂点と頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、頂点と頂点が置かれている区画の区画境界との間の最短距離として使用され、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、経路に含まれる辺の重みの総和である。
【００１２】
第１の態様を参照し、第３の可能な実装方式では、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップは、
クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定するステップ
を具体的に含む。
【００１３】
第１の態様の第３の可能な実装方式を参照し、第４の可能な実装方式では、グラフデータ全体セットにおける複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を決定するステップは、
最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定するステップ、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定するステップ、または、
最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定するステップ、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定するステップ、および、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定するステップ、および、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定するステップ
を具体的に含む。
【００１４】
第１の態様の第３の可能な実装方式を参照し、第５の可能な実装方式では、グラフデータ全体セットにおける複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、区画境界上の頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を決定するステップは、
最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定するステップ、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定するステップ、または、
最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定するステップ、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定するステップ、およびゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定するステップ、および、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算することによって得られる値との間の最小値を決定するステップ、および、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定するステップ
を具体的に含む。
【００１５】
第１の態様を参照し、第６の可能な実装方式では、クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するステップは、
クエリ条件を取得し、クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、第１のクエリ頂点の区画番号および層番号ならびに第２のクエリ頂点の区画番号および層番号を取得するステップ
を具体的に含み、
クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップは、
第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定するステップ、および、第１のクエリ頂点の層番号から第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号として決定するステップ、または、
第１のクエリ頂点および第２のクエリ頂点が異なる区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定するステップ、第１のクエリ頂点が置かれている区画について、ゼロから第１のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第１のクエリ頂点の区画番号と同じグループに属する層番号として、決定するステップ、および、第２のクエリ頂点が置かれている区画について、ゼロから第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第２のクエリ頂点の区画番号と同じグループに属する層番号として、決定するステップ
を具体的に含む。
【００１６】
第１の態様の第６の可能な実装方式を参照し、第７の可能な実装方式では、方法は、クエリ条件に従って、必要とされるグラフデータが候補セットにおいて見出されない場合、拡張された候補セットを得るように候補セットに含まれる層番号区間を拡張するステップと、
クエリ条件に従って拡張された候補セットにおいてグラフデータクエリを行うステップと
をさらに含む。
【００１７】
第１の態様を参照し、第８の可能な実装方式では、グラフデータ全体セットにおけるグラフデータがファイルシステムに保存されている場合、複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存される。
【００１８】
第１の態様、第１の態様の第１の可能な実装方式、第１の態様の第２の可能な実装方式、第１の態様の第３の可能な実装方式、第１の態様の第４の可能な実装方式、第１の態様の第５の可能な実装方式、第１の態様の第６の可能な実装方式、第１の態様の第７の可能な実装方式または第１の態様の第８の可能な実装方式を参照し、第９の可能な実装方式では、クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップは、
候補セットに含まれる頂点のグラフデータをメモリにロードするステップと、
クエリ条件に従って、候補セットに含まれる頂点のグラフデータであり、メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うステップと
を具体的に含む。
【００１９】
第２の態様によると、グラフデータクエリ装置が提供され、これは、グラフデータ全体セットにおけるグラフデータのクエリに適用され、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用され、クエリ装置は、
クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するように構成された取得ユニットと、
クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用するように構成された第１の決定ユニットであって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である、第１の決定ユニットと、
その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するように構成された第２の決定ユニットと、
クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたクエリユニットと
を含む。
【００２０】
第２の態様を参照し、第１の可能な実装方式では、頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、デフォルト層番号は、頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
第１の決定ユニットは、クエリ条件によって示される候補頂点の区画番号および層番号を決定する前に、クエリ頂点の層番号がデフォルト層番号であるかどうかを決定し、決定することの結果が、クエリ頂点の層番号がデフォルト層番号でないことである場合、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップをトリガするようにさらに構成され、
第２の決定ユニットは、クエリ頂点の層番号がデフォルト層番号である場合、その区画番号がクエリ頂点の区画番号であり、その層番号がデフォルト層番号である頂点を使用することによって候補セットを形成するようにさらに構成される。
【００２１】
第２の態様を参照し、第２の可能な実装方式では、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有する場合、または辺のどれもが重みを有しない場合、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点と頂点が置かれている区画の区画境界との間の最小ホップカウントであり、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有するのではない場合、頂点と頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、頂点と頂点が置かれている区画の区画境界との間の最短距離として使用され、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、経路に含まれる辺の重みの総和である。
【００２２】
第２の態様を参照し、第３の可能な実装方式では、第１の決定ユニットは、クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定するように具体的に構成される。
【００２３】
第２の態様の第３の可能な実装方式を参照し、第４の可能な実装方式では、グラフデータ全体セットにおける複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
第１の決定ユニットは、
クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、
最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、
最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定する
ように具体的に構成される。
【００２４】
第２の態様の第３の可能な実装方式を参照し、第５の可能な実装方式では、グラフデータ全体セットにおける複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、区画境界上の頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
第１の決定ユニットは、
クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、
最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、
最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定する
ように具体的に構成される。
【００２５】
第２の態様を参照し、第６の可能な実装方式では、取得ユニットは、クエリ条件を取得し、クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、第１のクエリ頂点の区画番号および層番号ならびに第２のクエリ頂点の区画番号および層番号を取得するように具体的に構成され、
第１の決定ユニットは、第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点の層番号から第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号として決定する、または、
第１のクエリ頂点および第２のクエリ頂点が異なる区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点が置かれている区画について、ゼロから第１のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第１のクエリ頂点の区画番号と同じグループに属する層番号として、決定し、第２のクエリ頂点が置かれている区画について、ゼロから第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第２のクエリ頂点の区画番号と同じグループに属する層番号として、決定する
ように具体的に構成される。
【００２６】
第２の態様の第６の可能な実装方式を参照し、第７の可能な実装方式では、第２の決定ユニットは、クエリユニットが、クエリ条件に従って、必要とされるグラフデータを候補セットにおいて見出さない場合、拡張された候補セットを得るように候補セットに含まれる層番号区間を拡張するようにさらに構成され、
クエリユニットは、クエリ条件に従って拡張された候補セットにおいてグラフデータクエリを行うようにさらに構成される。
【００２７】
第２の態様を参照し、第８の可能な実装方式では、グラフデータ全体セットにおけるグラフデータがファイルシステムに保存されている場合、複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存される。
【００２８】
第２の態様、第２の態様の第１の可能な実装方式、第２の態様の第２の可能な実装方式、第２の態様の第３の可能な実装方式、第２の態様の第４の可能な実装方式、第２の態様の第５の可能な実装方式、第２の態様の第６の可能な実装方式、第２の態様の第７の可能な実装方式または第２の態様の第８の可能な実装方式を参照し、第９の可能な実装方式では、クエリユニットは、候補セットに含まれる頂点のグラフデータをメモリにロードし、クエリ条件に従って、候補セットに含まれる頂点のグラフデータであり、メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うように具体的に構成される。
【００２９】
第３の態様によると、クエリサーバが提供され、これは、グラフデータ全体セットにおけるグラフデータのクエリに適用され、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用され、クエリサーバは、
クエリ条件を受信するように構成されたインターフェースと、
クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得し、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用し、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点であり、その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成し、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたプロセッサと、
グラフデータをグラフデータ全体セットに保存し、複数の頂点の区画番号と層番号をグラフデータ全体セットに保存するように構成された記憶装置と
を具体的に含む。
【００３０】
第３の態様を参照し、第１の可能な実装方式では、頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、デフォルト層番号は、頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
プロセッサは、クエリ条件によって示される候補頂点の区画番号および層番号を決定する前に、クエリ頂点の層番号がデフォルト層番号であるかどうかを決定し、決定することの結果が、クエリ頂点の層番号がデフォルト層番号でないことである場合、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップをトリガし、または、クエリ頂点の層番号がデフォルト層番号である場合、その区画番号がクエリ頂点の区画番号であり、その層番号がデフォルト層番号である頂点を使用することによって候補セットを形成し、クエリ条件に従って候補セットにおいてグラフデータクエリを行うようにさらに構成される。
【００３１】
第３の態様を参照し、第２の可能な実装方式では、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有する場合、または辺のどれもが重みを有しない場合、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点と頂点が置かれている区画の区画境界との間の最小ホップカウントであり、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有するのではない場合、頂点と頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、頂点と頂点が置かれている区画の区画境界との間の最短距離として使用され、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、経路に含まれる辺の重みの総和である。
【００３２】
第３の態様を参照し、第３の可能な実装方式では、プロセッサは、クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定するように具体的に構成される。
【００３３】
第３の態様の第３の可能な実装方式を参照し、第４の可能な実装方式では、グラフデータ全体セットにおける複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
プロセッサは、
クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、
最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、
最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定する
ように具体的に構成される。
【００３４】
第３の態様の第３の可能な実装方式を参照し、第５の可能な実装方式では、グラフデータ全体セットにおける複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、区画境界上の頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
プロセッサは、
クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、
最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、
最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定する
ように具体的に構成される。
【００３５】
第３の態様を参照し、第６の可能な実装方式では、プロセッサは、クエリ条件を取得し、クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、第１のクエリ頂点の区画番号および層番号ならびに第２のクエリ頂点の区画番号および層番号を取得し、第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点の層番号から第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号として決定し、または、第１のクエリ頂点および第２のクエリ頂点が異なる区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点が置かれている区画について、ゼロから第１のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第１のクエリ頂点の区画番号と同じグループに属する層番号として、決定し、第２のクエリ頂点が置かれている区画について、ゼロから第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第２のクエリ頂点の区画番号と同じグループに属する層番号として、決定するように具体的に構成される。
【００３６】
第３の態様の第６の可能な実装方式を参照し、第７の可能な実装方式では、プロセッサは、クエリ条件に従って、必要とされるグラフデータを候補セットにおいて見出さない場合、拡張された候補セットを得るように候補セットに含まれる層番号区間を拡張し、およびクエリ条件に従って拡張された候補セットにおいてグラフデータクエリを行うようにさらに構成される。
【００３７】
第３の態様を参照し、第８の可能な実装方式では、記憶装置は、グラフデータ全体セットにおけるグラフデータをファイルシステムに保存し、複数の頂点の区画番号および層番号を１つのファイルに保存し、同じ区画番号および層番号を有する頂点のグラフデータを１つのファイルに保存し、異なる区画番号および層番号を有する頂点のグラフデータを異なるファイルに保存するように具体的に構成される。
【００３８】
第３の態様、第３の態様の第１の可能な実装方式、第３の態様の第２の可能な実装方式、第３の態様の第３の可能な実装方式、第３の態様の第４の可能な実装方式、第３の態様の第５の可能な実装方式、第３の態様の第６の可能な実装方式、第３の態様の第７の可能な実装方式または第３の態様の第８の可能な実装方式を参照し、第９の可能な実装方式では、プロセッサは、候補セットに含まれる頂点のグラフデータをメモリにロードし、クエリ条件に従って、候補セットに含まれる頂点のグラフデータであり、メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うように具体的に構成される。
【００３９】
本発明の利益となる効果は以下を含む。
【００４０】
本発明の実施形態で提供される解決策において、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用される。グラフデータクエリが頂点の区画番号および層番号に基づいて行われる場合、クエリ頂点の区画番号および層番号が最初に取得され、クエリ条件によって示された候補頂点の区画番号および層番号は、候補区画番号および候補層番号としてクエリ頂点の区画番号および層番号に基づいて決定され、その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成し、グラフデータクエリが、クエリ条件に従って候補セットにおいて行われる。候補セットは、クエリ条件に従って、ならびに頂点の予め分割された区画および層、およびグラフデータ全体セットのデータ容量より少ない候補セットのデータ容量に基づいて、グラフデータ全体セットから選択される。したがって、候補セットにおいてグラフデータクエリを行うことにより、グラフデータクエリ効率が向上する。
【００４１】
このアプリケーションの追加の特性および利点は、以下の明細書に記載され、部分的に、明細書により明らかになる、または本出願の実施により習得される。本出願の目的および追加の利点は、記載された明細書、特許請求の範囲、および添付の図面で特に特定された構造を使用することによって実施され、得ることができる。
【００４２】
添付の図面は、本発明をさらに理解するために使用され、明細書の一部を構成し、本発明の実施形態と共に本発明を説明するために使用され、これは本発明を限定するものではない。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施形態によるグラフデータクエリ方法のフローチャートである。
【図２】本発明の実施形態１によるグラフデータ全体セット内のグラフデータを組織化するフローチャートである。
【図３】本発明の実施形態１による辺切断区画化を行った区画化結果の略図である。
【図４】本発明の実施形態１による頂点切断区画化を行った区画化結果の略図である。
【図５】辺切断区画化が本発明の実施形態１による頂点上で行われた後に、図３の頂点上で階層化を行った結果の略図である。
【図６】頂点切断区画化が本発明の実施形態１による頂点上で行われた後に、図４の頂点上で階層化を行った結果の略図である。
【図７】本発明の実施形態１により頂点が再付番された後に得られた略構造図である。
【図８】本発明の実施形態２によるグラフデータクエリ方法のフローチャートである。
【図９】本発明の実施形態３によるグラフデータクエリ方法のフローチャートである。
【図１０】本発明の実施形態４による候補セットにおいてグラフデータクエリを行うフローチャートである。
【図１１】本発明の実施形態５によるグラフデータクエリ装置の略構造図である。
【図１２】本発明の実施形態６によるクエリサーバの略構造図である。
【発明を実施するための形態】
【００４４】
グラフデータクエリ効率を良くするための実施解決法を与えるために、本発明の実施形態は、グラフデータクエリ方法および装置を提供する。本明細書の添付の図面を参照して、本発明の例示的実施形態を以下に説明する。本明細書に記載された例示的実施形態は、単に本発明を記載および説明するために使用され、本発明を限定することを意図したものではないことを理解されたい。本出願の実施形態、および実施形態における特性は、互いに矛盾しない場合には互いに組み合わせてもよい。
【００４５】
本発明の実施形態は、グラフデータ全体セットにおけるグラフデータのクエリに適用されるグラフデータクエリ方法を提供し、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用される。図１に示すように、方法は以下を含む。
【００４６】
ステップ１０１．クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得する。
【００４７】
ステップ１０２．クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップ、およびそれらを候補区画番号および候補層番号として使用するステップであって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である。
【００４８】
ステップ１０３．その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成する。
【００４９】
ステップ１０４．クエリ条件に従って候補セットにおいてグラフデータクエリを行う。
【００５０】
実際の応用例では、隔離頂点とも呼ばれる、グラフデータ全体セット内にいくつかの遊離頂点がある可能性がある、すなわち、これらの頂点は、頂点が置かれている区画の区画境界に接続することができない。これらの頂点がグラフデータ全体セットに存在する場合、これらの頂点の各層番号はさらに、デフォルト層番号として決定され、デフォルト層番号は、頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なる。
【００５１】
これに応じて、前述の図１に示す方法では、クエリ条件によって示される候補頂点の区画番号および層番号を決定する前述のステップ１０２の前に、クエリ頂点の層番号がデフォルト層番号であるかどうかが最初に決定されることが可能である。クエリ頂点の層番号がデフォルト層番号でない場合、前述のステップ１０２がトリガされる。あるいは、その区画番号がクエリ頂点の区画番号であり、その層番号がデフォルト層番号である頂点を使用することによって候補セットが形成されることが可能であり、クエリ条件に従って候補セットにおいてグラフデータクエリが行われる。したがって、グラフデータ全体セットにおける遊離頂点のグラフデータのクエリが実施される。
【００５２】
本発明の実施形態では、新しいグラフデータ組織化方法が提供される。すなわち、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われ、グラフデータ組織化方法を行った結果に基づいてグラフデータクエリを行うように、各頂点の区画番号および層番号が決定される。
【００５３】
以下にまず、添付の図面を参照して、本発明の実施形態で提供されたグラフデータ組織化方法を詳細に説明する。
【００５４】
実施形態１
図２は、以下の処理ステップを具体的に含む、本発明の実施形態１によるグラフデータ全体セット内のグラフデータを組織化するフローチャートである。
【００５５】
ステップ２０１．グラフデータ全体セットに含まれる複数の頂点で区画化を行う。
【００５６】
区画化アルゴリズムは、辺切断区画化（ｅｄｇｅ−ｃｕｔ）である、または頂点切断区画化（ｖｅｒｔｅｘ−ｃｕｔ）である可能性がある。以下で別に、２つの区画化アルゴリズムを説明する。
【００５７】
辺切断区画化：図３に示すように、区画化は、頂点０から頂点９上で行われる。頂点０から頂点９の頂点間の関係が、図３に示され、２つの頂点間の接続ラインは、２つの頂点間の辺を示す。
【００５８】
図３に示すように、辺切断区画化は、頂点間の辺が区画境界を使用して切断されることを意味する。切断後、頂点０、頂点１、頂点２、頂点６、および頂点７は、区画０とも呼ばれる同じ区画に置かれる、すなわち、区画番号が０である。頂点３、頂点４、頂点５、頂点８、および頂点９は、区画１とも呼ばれる他の区画に置かれる、すなわち、区画番号が１である。
【００５９】
頂点切断区画化：図４に示すように、図３と同じように、頂点０から頂点９上で区画化が行われる。
【００６０】
図４に示すように、頂点切断区画化は、区画境界を使用することによって頂点が切断されることを意味する。切断後、切断される頂点は、切断境界の２側部のあらゆる区画に属することができ、例えば、頂点０、頂点１、頂点２、頂点６、および頂点７は、区画０とも呼ばれる同じ区画に置かれる、すなわち、区画番号が０である。頂点３、頂点４、頂点５、頂点８、および頂点９は、区画１とも呼ばれる他の区画に置かれる、すなわち、区画番号が１である。
【００６１】
ステップ２０２．グラフデータ全体セットに含まれる複数の頂点が区画化された後、各区画に含まれる頂点上で階層化を行い、同じ層で、頂点が置かれている区画の区画境界に対して同じ最短距離を有する頂点を配置し、最短距離は層番号として使用される。
【００６２】
本発明の本実施形態では、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有する場合、または辺のどれもが重みを有しない場合、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点と頂点が置かれている区画の区画境界との間の最小ホップカウントであり得、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有するのではない場合、頂点と頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、頂点と頂点が置かれている区画の区画境界との間の最短距離として使用され、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、経路に含まれる辺の重みの総和である。
【００６３】
実際の応用例、いくつかの応用例シナリオでは、２つの頂点間の関係は、２つの頂点が接続関係を有することを示すだけでよく、この場合、重みは２つの頂点間の辺に対して設定されていないことがあり、または同じ重みが各辺に対して設定されていないことがある。例えば、ソーシャルネットワークでは、辺は、２つの頂点によって示される２人のユーザが友人関係を有することを示すだけであり、重みは設定されないことがある。しかし、いくつかの応用例シナリオでは、２つの頂点が接続関係を有することを示すことに加えて、２つの頂点間の関係はさらに、接続度を示すことがあり、この場合、重みは２つの頂点間の辺に対して設定されること可能であり、異なる重みは異なる接続度を示す。例えば、マップでは、辺は２つの頂点によって示される地理的位置間の直接経路があることを示し、辺のより大きな重みはより長い経路を示す。例えば、対応する重みが経路長さ範囲に従って決定される場合、同じ範囲内の経路長さは、同じ対応する重みを有する。
【００６４】
説明を容易にするため、また本応用例の解決法の明確な理解を容易にするために、ステップでは、接続関係を有する各２つの頂点間の辺に重みがない例は、階層化結果を説明するために使用される。
【００６５】
図５に示すように、図５は、辺切断区画化が頂点０から頂点９上で行われた後に、図３における頂点０から頂点９上で階層化を行った結果の略図である。別の区画を交差する辺を有する頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロである、すなわち、頂点２、頂点７、頂点３、および頂点８の層番号がゼロである。頂点６および頂点９それぞれから区画境界までのホップカウントが１である、すなわち、層番号が１である。頂点０、頂点１、および頂点４それぞれと、区画境界との間のホップカウントが２である、すなわち、層番号が２である。頂点５と区画境界との間のホップカウントが３である、すなわち、層番号が３である。
【００６６】
図６に示すように、図６は、頂点切断区画化が頂点０から頂点９上で行われた後に、図４における頂点０から頂点９上で階層化を行った略構造図である。区画境界上の頂点と、頂点が置かれている区画の区画化境界との間の最短距離がゼロである、すなわち、頂点２と頂点８の層番号が０である。頂点６、頂点７、頂点３、および頂点９それぞれと、区画境界との間のホップカウントが１である、すなわち、層番号が１である。頂点０、頂点１、および頂点４それぞれと、区画境界との間のホップカウントが２である、すなわち、層番号が２である。頂点５と区画境界との間のホップカウントが３である、すなわち、層番号が３である。
【００６７】
ステップ２０３．グラフデータ全体セット内の頂点上で区画化および階層化を行った後に、グラフデータ全体セットに含まれる頂点の区画および層情報、すなわち、各頂点の区画番号および層番号を保存し、任意選択では、区画化および階層化結果に基づいてグラフデータ全体セット内のグラフデータを保存する、すなわち、異なる区画および異なる層にある頂点のグラフデータを別に保存する。
【００６８】
例えば、グラフデータ全体セット内のグラフデータが、分配ファイルシステム（ＨＤＦＳ、Ｈａｄｏｏｐ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）などのファイルシステムに保存された場合、複数の頂点の区画および層情報（区画番号および層番号）は独立したファイルに保存されることが可能であり、同じ区画番号および層番号を有する頂点のグラフデータは独立したファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータは異なるファイルに保存される。
【００６９】
別の例では、グラフデータがグラフデータベースに保存される場合、複数の頂点の区画および層情報は、データベース内にテーブルの形で保存されることが可能である。
【００７０】
別の例では、グラフデータ間の隣接関係を示すためにマトリックスが使用される場合、従来技術におけるＧＢＡＳＥデータベースシステムなどのシステム、すなわち、スケーラブル汎用グラフデータ管理システムは、グラフデータのクエリをマトリックスの演算に変換することができる。この場合、図３または図４に示す未処理オリジナルグラフに対応するマトリックスは、以下の通りに示される。
【００７１】
【数１】
2017509043.tif 000003
【００７２】
要素（ｍ，ｎ）が１であることは、ｍ番目の頂点とｎ番目の頂点との間に接続関係があることを示している。
【００７３】
区画化および階層化が、前述のステップを使用することによって複数の頂点上で行われた後に、頂点は、マトリックス内の同じ層における頂点を連続的に示すように再付番されることが可能である。再付番の方法では、同じ層にある頂点が連続的に付番され、隣接する区画にある頂点が連続して付番される。再付番の結果が、図７に示され、再付番後に得られた対応するマトリックスは、以下のように示される。
【００７４】
【数２】
2017509043.tif 000004
【００７５】
このステップでは、異なる区画および異なる層にある頂点のグラフデータは別に保存され、それによって、その後のグラフデータクエリプロセスでは、候補セットに含まれる頂点のグラフデータがより便利に取得されることが可能である。したがって、グラフデータクエリ効率がさらに向上される。
【００７６】
本発明の実施形態１では、グラフデータ全体セットに含まれる頂点が２つの区画に分割される例が、グラフデータ全体セット内のグラフデータを組織化する解決法を説明するために使用される。実際の応用例では、グラフデータ全体セットに含まれる頂点はまた、より多くの区画に分割されることが可能であり、本発明の本実施形態で提供されるグラフデータクエリ方法にも適用可能である。
【００７７】
本発明の本実施形態では、グラフデータ全体セットのグラフデータが、前述の実施形態１に示す手順を使用することによって組織化された後に、すなわち、区画化および階層化が頂点で行われ、グラフデータが保存された後に、グラフデータクエリが結果に基づいて行われる。
【００７８】
グラフデータクエリが行われる場合、対応するクエリ手順が、異なるクエリ条件に従って使用されることが可能である。例えば、クエリ条件が候補頂点とクエリ頂点との間の距離を示すことができる場合、以下の実施形態２に示した手順を使用して、クエリを行うことができる。
【００７９】
実施形態２
本発明の実施形態２では、グラフデータクエリが行われるクエリ条件は、クエリ頂点、および候補頂点とクエリ頂点との間の距離を示すことができ、候補頂点は、クエリにより、頂点がクエリ条件を満たすかどうかを決定する必要がある頂点である。
【００８０】
例えば、特定の頂点の特定の属性データがクエリされる場合、頂点がクエリ頂点である。別の例では、頂点はユーザを示し、特定の名前の人が特定のユーザの友人の友人であるかどうかがクエリされる。この場合、ユーザに対応する頂点はクエリ頂点であり、候補頂点は、頂点と友人関係を有する頂点、および頂点の友人と友人関係を有する頂点であり、すなわち、候補頂点とクエリ頂点の間の距離が１および２を含む。別の例では、頂点は地理的位置を示し、頂点の属性データがクエリされ、２つの頂点間の距離が予め設定された範囲を満たし、この場合、候補頂点と頂点との間の距離が、予め設定された範囲内の距離を含む。
【００８１】
図８は、以下の処理ステップを具体的に含む、本発明の実施形態２によるグラフデータクエリ方法のフローチャートである。
【００８２】
ステップ８０１．クエリ頂点の区画番号および層番号を取得する。
【００８３】
クエリ頂点の区画番号および層番号は、クエリ条件から取得されることが可能である。
【００８４】
ステップ８０２．クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用し、候補頂点は、クエリ条件に従ってクエリする必要がある頂点である。
【００８５】
このステップでは、クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示すことができる例が、説明のために使用される。この場合、候補頂点の決定した区画番号および層番号は、複数のグループの区画番号および層番号を含むことができ、同じ区画では、層番号は、辺切断区画化および頂点切断区画化に従って、以下に別に記載した層番号区間に含まれる層番号であってもよい。
【００８６】
方法１：この方法では、辺切断区画化がグラフデータ全体セット内の複数の頂点上で行われ、区画境界は頂点を含まず、別の区画と交差する辺を有する頂点と頂点が置かれている区画の区画境界との間の最短距離がゼロである。
【００８７】
この方法は以下のステップを含む。
【００８８】
ステップａ．クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、最大距離Ｋがクエリ頂点の層番号Ｌより大きいかどうかをまず決定する。最大距離Ｋがクエリ頂点の層番号Ｌよりも大きくない場合、ステップｂに進み、最大距離Ｋがクエリ頂点の層番号Ｌよりも大きい場合、ステップｅに進む。
【００８９】
ステップｂ．最大距離Ｋがクエリ頂点の層番号Ｌよりも大きくない場合、候補頂点の区画番号がクエリ頂点の区画番号であることを決定し、ステップｃに進む。
【００９０】
ステップｃ．クエリ頂点が置かれている区画の最大層番号Ｌmaxと、クエリ頂点の層番号Ｌと最大距離Ｋとを加算することによって得られた値との間の最小値、すなわちｍｉｎ（Ｌ＋Ｋ，Ｌmax）を決定し、その後、ステップｄに進む。
【００９１】
ステップｄ．クエリ頂点の層番号Ｌから最大距離Ｋを減算することによって得られた値から最小値ｍｉｎ（Ｌ＋Ｋ，Ｌmax）までの閉区間内の層番号、すなわち、区間内の層番号［Ｌ−Ｋ，ｍｉｎ（Ｌ＋Ｋ，Ｌmax）］を候補頂点の層番号として決定する。
【００９２】
ステップｅ．最大距離Ｋがクエリ頂点の層番号Ｌより大きい場合、候補頂点の区画番号が、クエリ頂点の層番号、およびクエリ頂点が置かれている区画の隣接区画の区画番号であることを決定し、その後、ステップｆに進む。
【００９３】
ステップｆ．クエリ頂点が置かれている区画では、クエリ頂点が置かれている区画内の最大層番号Ｌmaxと、クエリ頂点の層番号Ｌと最大距離Ｋとを加算することによって得られた値との間の最小値、すなわちｍｉｎ（Ｌ＋Ｋ，Ｌmax）を決定し、その後、ステップｇに進む。
【００９４】
ステップｇ．ゼロから最小値（Ｌ＋Ｋ，Ｌmax）までの閉区間内の層番号、すなわち区間内の層番号［０，ｍｉｎ（Ｌ＋Ｋ，Ｌmax）］を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として決定し、その後、ステップｈに進む。
【００９５】
ステップｈ．クエリ頂点が置かれている区画の各隣接区画では、隣接区画の最大層番号Ｌmaxと、最大距離Ｋからクエリ頂点の層番号Ｌを減算し、次いで、１を減算することによって得られた値との間の最小値、すなわちｍｉｎ（Ｋ−Ｌ−１，Ｌmax）を決定し、その後、ステップｉに進む。
【００９６】
ステップｉ．ゼロから最小値ｍｉｎ（Ｋ−Ｌ−１，Ｌmax）までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号、すなわち区間内の層番号［０，ｍｉｎ（Ｋ−Ｌ−１，Ｌmax）］として決定する。
【００９７】
方法２：このように、頂点切断区画化がグラフデータ全体セット内の複数の頂点上で行われ、区画境界は頂点を含み、区画境界上の頂点と頂点が置かれている区画の区画境界との間の最短距離がゼロである。
【００９８】
この方法は、以下のステップを含む。
【００９９】
ステップａ．クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、最大距離Ｋがクエリ頂点の層番号Ｌより大きいかどうかをまず決定する。最大距離Ｋがクエリ頂点の層番号Ｌよりも大きくない場合、ステップｂに進み、最大距離Ｋがクエリ頂点の層番号Ｌよりも大きい場合、ステップｅに進む。
【０１００】
ステップｂ．最大距離Ｋがクエリ頂点の層番号Ｌよりも大きくない場合、候補頂点の区画番号がクエリ頂点の区画番号であることを決定し、ステップｃに進む。
【０１０１】
ステップｃ．クエリ頂点が置かれている区画の最大層番号Ｌmaxと、クエリ頂点の層番号Ｌと最大距離Ｋとを加算することによって得られた値との間の最小値、すなわちｍｉｎ（Ｌ＋Ｋ，Ｌmax）を決定し、その後、ステップｄに進む。
【０１０２】
ステップｄ．クエリ頂点の層番号Ｌから最大距離Ｋを減算することによって得られた値から最小値ｍｉｎ（Ｌ＋Ｋ，Ｌmax）までの閉区間内の層番号、すなわち区間内の層番号［Ｌ−Ｋ，ｍｉｎ（Ｌ＋Ｋ，Ｌmax）］を候補頂点の層番号として決定する。
【０１０３】
ステップｅ．最大距離Ｋがクエリ頂点の層番号Ｌより大きい場合、候補頂点の区画番号が、クエリ頂点の層番号、およびクエリ頂点が置かれている区画の隣接区画の区画番号であることを決定し、その後、ステップｆに進む。
【０１０４】
ステップｆ．クエリ頂点が置かれている区画では、クエリ頂点が置かれている区画内の最大層番号Ｌmaxと、クエリ頂点の層番号Ｌと最大距離Ｋとを加算することによって得られた値との間の最小値、すなわちｍｉｎ（Ｌ＋Ｋ，Ｌmax）を決定し、その後、ステップｇに進む。
【０１０５】
ステップｇ．ゼロから最小値（Ｌ＋Ｋ，Ｌmax）までの閉区間内の層番号、すなわち区間内の層番号［０，ｍｉｎ（Ｌ＋Ｋ，Ｌmax）］を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として決定し、その後、ステップｈに進む。
【０１０６】
ステップｈ．クエリ頂点が置かれている区画の各隣接区画では、隣接区画の最大層番号Ｌmaxと、最大距離Ｋからクエリ頂点の層番号Ｌを減算することによって得られる値との間の最小値、すなわちｍｉｎ（Ｋ−Ｌ，Ｌmax）を決定し、その後、ステップｉに進む。
【０１０７】
ステップｉ．ゼロから最小値ｍｉｎ（Ｋ−Ｌ，Ｌmax）までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号、すなわち区間内の層番号［０，ｍｉｎ（Ｋ−Ｌ，Ｌmax）］として決定する。
【０１０８】
ステップ８０３．その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成する。
【０１０９】
すなわち、前述のステップ８０２で決定された候補区画番号および候補層番号の各グループに含まれる頂点を使用することによって、候補セットが形成される。
【０１１０】
ステップ８０４．クエリ条件に従って候補セットにおいてグラフデータクエリを行う。
【０１１１】
実施形態３
本発明の実施形態３では、グラフデータクエリが行われるクエリ条件は、それぞれ第１のクエリ頂点および第２のクエリ頂点である２つの頂点を示し、クエリ条件は、第１のクエリ頂点と第２のクエリ頂点との間の最短経路をクエリする必要があることを示すことができる。
【０１１２】
例えば、２つのアドレス位置間の最短距離がクエリされる。
【０１１３】
図９は、以下の処理ステップを具体的に含む、本発明の実施形態３によるグラフデータクエリ方法のフローチャートである。
【０１１４】
ステップ９０１．第１のクエリ頂点の区画番号および層番号、ならびに第２のクエリ頂点の区画番号および層番号を取得する。
【０１１５】
第１のクエリ頂点および第２のクエリ頂点のクエリ頂点の区画番号および層番号は、クエリ条件から取得されることが可能である。
【０１１６】
ステップ９０２．第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれているかどうかを決定する。第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、ステップ９０３に進み、そうでなければ、ステップ９０５に進む。
【０１１７】
ステップ９０３．第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、候補頂点の区画番号が、第１のクエリ頂点および第２のクエリ頂点の区画番号であると決定する。
【０１１８】
ステップ９０４．第１のクエリ頂点の層番号Ｌ１から第２のクエリ頂点の層番号Ｌ２までの閉区間内の層番号、すなわち、Ｌ１がＬ２より小さいと想定される場合の区間内の層番号［Ｌ1，Ｌ2］を、候補頂点の層番号として決定する。
【０１１９】
ステップ９０５．第１のクエリ頂点および第２のクエリ頂点が異なる区画に置かれている場合、候補頂点の区画番号が、第１のクエリ頂点および第２のクエリ頂点の区画番号であると決定する。
【０１２０】
ステップ９０６．第１のクエリ頂点が置かれている区画では、ゼロから第１のクエリ頂点の層番号Ｌ１までの閉区間内の層番号、すなわち区間内の層番号［０，Ｌ1］を、候補頂点の層番号であり、第１のクエリ頂点の区画番号と同じグループに属する層番号として決定する。
【０１２１】
ステップ９０７．第２のクエリ頂点が置かれている区画では、ゼロから第２のクエリ頂点の層番号Ｌ２までの閉区間内の層番号、すなわち区間内の層番号［０，Ｌ2］を、候補頂点の層番号であり、第２のクエリ頂点の区画番号と同じグループに属する層番号として決定する。
【０１２２】
ステップ９０８．その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成する。
【０１２３】
すなわち、前述のステップ９０１からステップ９０７ｉで決定された候補区画番号および候補層番号の各グループに対応する頂点を使用することによって、候補セットが形成される。
【０１２４】
ステップ９０９．クエリ条件に従って候補セットにおいてグラフデータクエリを行う。
【０１２５】
このステップでは、クエリ結果が得られると、現在のクエリが終了する。
【０１２６】
しかし、いくつかの実際の応用例シナリオでは、グラフデータクエリが前述の方法で決定された候補セットで行われる場合に、予測グラフデータは見出されることが不可能である。例えば、第１のクエリ頂点と第２のクエリ頂点との間の距離は見出されることが不可能である。この場合、方法はさらに、以下のステップを含む。
【０１２７】
ステップ９１０．必要とされるグラフデータがクエリ条件に従って現在の候補セット内で見出されない場合、拡張された候補セットを得るために候補セット内に含まれる層番号区間を拡張し、拡張された候補セットを新しい候補セットとして使用する。前述のステップ９０９に戻り、すなわち、クエリ条件に従って拡張された候補セットにおいてグラフデータクエリを行う。
【０１２８】
このステップでは、候補セットに含まれる層番号区間を拡張することは、毎回、予め設定された数の層番号を拡張すること、例えば、毎回、１つの層番号を拡張することであってよい。
【０１２９】
確かに、層番号区間の特定の境界値がすでに、特定の境界値が属する区画内の層番号の境界値である場合、この境界値を拡張する必要はない。層番号区間の２つの境界値がさらに拡張されることが不可能である場合、候補セットの範囲は、現在の区画の隣接区画まで拡張されることが可能であり、拡張は、隣接区画の層番号の昇順に従って行われる。
【０１３０】
実施形態４
本発明の実施形態４では、グラフデータクエリがクエリ条件に従って候補セットにおいて行われる前述の方法を、詳細に説明する。図１０に示すように、方法は以下を含む。
【０１３１】
ステップ１００１．候補セットに含まれる頂点のグラフデータをメモリにロードする。
【０１３２】
このステップでは、候補セットに含まれる頂点のグラフデータを、一度にメモリにロードして、グラフデータロード時間を短くし、それによってグラフデータクエリ効率を良くすることができる。
【０１３３】
ステップ１００２．クエリ条件に従って、候補セットに含まれる頂点のグラフデータであり、メモリ内でキャッシュされるグラフデータ上でグラフデータクエリを行う。
【０１３４】
現在、従来技術ではトリニティシステムと呼ばれるメモリベースグラフデータ管理システムがある。トリニティシステムでは、グラフ内の頂点または辺は、セルとして示され、セルは、運用形態（ｒｕｎｔｉｍｅ  ｆｏｒｍ）およびバイナリ形態（ｂｌｏｂ  ｆｏｒｍ）を含む２つの形態を有することができる。ｒｕｎｔｉｍｅ  ｆｏｒｍのセルは、メモリ内のオブジェクト、すなわち、ロードされたグラフデータとして示され、ｒｕｎｔｉｍｅ  ｆｏｒｍのセルは、演算およびクエリのために使用され、比較的大きなメモリ占有率を有する。ｂｌｏｂ  ｆｏｒｍのセルは、バイナリ形態でオブジェクトとして示され、小さなメモリ占有率を有し、ディスクと直接相互作用することができる。（メモリが不十分またはセルが長時間アクセスされない場合、システムはセルをメモリからディスクに転送（スワップ）することができ、シリアル化を行うのと等しい、ｂｌｏｂ  ｆｏｒｍにｒｕｎｔｉｍｅ  ｆｏｒｍから変換された後にのみ、セルがディスクに転送されることが可能である。）
【０１３５】
従来技術では、グラフデータクエリが、トリニティシステムに基づいて行われる場合、現在の頂点では、現在の頂点のグラフデータがメモリにロードされたかどうかを最初に決定する必要がある。現在の頂点のグラフデータがロードされなかった場合、現在の頂点のグラフデータがメモリにロードされ、現在の頂点のグラフデータがロードされた場合、または現在のロードの後に、現在の頂点のグラフデータの形態がｒｕｎｔｉｍｅ  ｆｏｒｍであるかどうかが決定される。現在の頂点のグラフデータの形態がｒｕｎｔｉｍｅ  ｆｏｒｍでない場合、現在の頂点のグラフデータの形態は、ｒｕｎｔｉｍｅ  ｆｏｒｍに変換され、クエリはｒｕｎｔｉｍｅ  ｆｏｒｍのグラフデータに基づいて行われる。
【０１３６】
クエリでは、クエリが複数の頂点のグラフデータ上で行われる必要がある場合、前述の手順は、現在クエリされる必要がある頂点が決定される毎に行われる必要がある。したがって、クエリでは、前述の決定ステップは、複数回実行される必要があり、前述のロードおよび変換ステップも、複数回実行される必要があり、それによって比較的低いクエリ効率が生じる可能性がある。
【０１３７】
しかし、本発明の本実施形態で提供される解決法では、グラフデータクエリがトリニティシステムに基づいて行われる場合、候補セットが予め決定されているので、候補セットに含まれる頂点のグラフデータは、前述のステップ１００１を使用することによって一度にメモリにロードされることが可能であり、候補セットに含まれる頂点のグラフデータの形態は、一度にｒｕｎｔｉｍｅ  ｆｏｒｍに変換される、すなわち、グラフデータがロードされたかどうか、および変換が行われる必要があるかどうかを決定することが避けられ、ロード時間の量が減少し、それによって、グラフデータロード時間が短くなり、さらにグラフデータクエリ効率が良くなる。
【０１３８】
現在、従来技術のＧＢＡＳＥデータベースシステムは、スケーラブル汎用グラフデータ管理システムである。ＧＢＡＳＥデータベースシステムでは、マトリックスは、グラフデータ間の隣接関係を示すために使用され、グラフデータのクエリまたは演算は、ステージ１（Ｉｎｄｅｘ  Ｓｔａｇｅステージ）およびステージ２（Ｑｕｅｒｙ  Ｓｔａｇｅステージ）である２つのステージを含む、マトリックスの演算に変換される。
【０１３９】
ステージ１：最初に、グラフデータは表示のためにマトリックスに変換され、その後、クラスタ化、再順序付けなどがグラフデータ上で行われ、次に、ブロック化および圧縮が行われ、最後に、ブロックがファイルシステムに保存される。
【０１４０】
ステージ２：最初に、クエリ要求がクエリベクトルに変換され、その後、関連するブロックがクエリタイプに従って読み取られ、候補マトリックスが確立され、次に、結果ベクトルが候補マトリックスをベクトルで掛けることによって得られ、最後に、対応する動作が結果ベクトルに従って行われる。
【０１４１】
従来技術におけるＧＢＡＳＥデータベースシステムに基づいてグラフデータクエリを行う解決法では、従来技術を参照することができ、詳細は本明細書では再び説明しない。
【０１４２】
しかし、従来技術では、ＧＢＡＳＥデータベースシステムに基づいてグラフデータクエリを行う場合に、候補マトリックスが確立されていると、クエリ頂点が置かれている行または列の全てのブロックをロードする必要があるが、いくつかのブロックは明らかに、クエリ条件を満たさない。この場合、ロードされたグラフデータのデータ容量が比較的大きいので、効率はその後のクエリで比較的低い。
【０１４３】
しかし、本発明の本実施形態で提供される解決法では、グラフデータクエリがＧＢＡＳＥデータベースシステムに基づいて行われる場合、候補セット内、およびクエリ頂点が置かれている行または列にあるブロックのみがロードされることが可能であり、それによって、ロードされるグラフデータのデータ容量が減少して、データロード処理時間が短くなり、その後のクエリが基づくデータ容量を少なくし、さらに、グラフデータクエリ効率が良くなる。
【０１４４】
実施形態５
同発明の概念に基づいて、および本発明の前述の実施形態で提供されたグラフデータクエリ方法に従って、これに応じて、本発明の実施形態５はさらに、グラフデータ全体セット内のグラフデータのクエリに適用されるグラフデータクエリ装置を提供し、グラフデータ全体セットは複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、区画化および階層化が、グラフデータ全体セットにおける複数の頂点上で予め行われ、頂点が置かれている区画の番号は、頂点の区画番号として使用され、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点の層番号として使用される。クエリ装置の略構造図が、図１１に示され、クエリ装置は具体的に、クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するように構成された取得ユニット１１０１と、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用するように構成された第１の決定ユニット１１０２であって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である、第１の決定ユニット１１０２と、その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するように構成された第２の決定ユニット１１０３と、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたクエリユニット１１０４とを含む。
【０１４５】
さらに、頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、デフォルト層番号は、頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、第１の決定ユニット１１０２は、クエリ条件によって示される候補頂点の区画番号および層番号を決定する前に、クエリ頂点の番号がデフォルト層番号であるかどうかを決定し、決定することの結果が、クエリ頂点の層番号がデフォルト層番号でないことである場合、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップをトリガするようにさらに構成され、第２の決定ユニット１１０３は、クエリ頂点の層番号がデフォルト層番号である場合、その区画番号がクエリ頂点の区画番号であり、その層番号がデフォルト層番号である頂点を使用することによって候補セットを形成するようにさらに構成されている。
【０１４６】
さらに、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有する場合、または辺のどれもが重みを有しない場合、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点と頂点が置かれている区画の区画境界との間の最小ホップカウントであり、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有するのではない場合、頂点と頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、頂点と頂点が置かれている区画の区画境界との間の最短距離として使用され、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、経路に含まれる辺の重みの総和である。
【０１４７】
さらに、第１の決定ユニット１１０２は、クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定するように具体的に構成されている。
【０１４８】
さらに、グラフデータ全体セットにおける複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、第１の決定ユニット１１０２は、クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定するように具体的に構成されている。
【０１４９】
さらに、グラフデータ全体セットにおける複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、区画境界上の頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、第１の決定ユニット１１０２は、クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定するように具体的に構成されている。
【０１５０】
さらに、取得ユニット１１０１は具体的に、クエリ条件を取得し、クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、第１のクエリ頂点の区画番号および層番号、ならびに第２のクエリ頂点の区画番号および層番号を取得するように構成され、第１の決定ユニット１１０２は具体的に、第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点の層番号から第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号として決定する、または、第１のクエリ頂点および第２のクエリ頂点が異なる区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点が置かれている区画について、ゼロから第１のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第１のクエリ頂点の区画番号と同じグループに属する層番号として、決定し、第２のクエリ頂点が置かれている区画について、ゼロから第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第２のクエリ頂点の区画番号と同じグループに属する層番号として、決定するように構成されている。
【０１５１】
さらに、第２の決定ユニット１１０３は、クエリユニットが、クエリ条件に従って、必要とされるグラフデータを候補セットにおいて見出さない場合、拡張された候補セットを得るように候補セットに含まれる層番号区間を拡張するようにさらに構成され、クエリユニット１１０４は、クエリ条件に従って拡張された候補セットにおいてグラフデータクエリを行うようにさらに構成されている。
【０１５２】
さらに、グラフデータ全体セットにおけるグラフデータがファイルシステムに保存されている場合、複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存される。
【０１５３】
さらに、クエリユニット１１０４は、候補セットに含まれる頂点のグラフデータをメモリにロードし、クエリ条件に従って、候補セットに含まれる頂点のグラフデータであり、メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うように具体的に構成されている。
【０１５４】
前述のユニットの機能は、前述の実施形態に示す手順の対応する処理ステップに対応してよく、詳細は本明細書では再び説明しない。
【０１５５】
実施形態６
同発明の概念に基づいて、および本発明の前述の実施形態で提供されるグラフデータクエリ方法に従って、これに応じて、本発明の実施形態６は、グラフデータ全体セットにおけるグラフデータのクエリに適用されるクエリサーバであって、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用される。クエリサーバの略構造図が、図１２に示され、クエリサーバは具体的に、クエリ条件を受信するように構成されたインターフェース１２０１と、クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得し、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用するように構成されたプロセッサ１２０２であって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点であり、その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成し、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたプロセッサ１２０２と、グラフデータ全体セットにおけるグラフデータ、ならびにグラフデータ全体セットにおける複数の頂点の区画番号および層番号を保存するように構成された記憶装置１２０３を含む。
【０１５６】
さらに、頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、デフォルト層番号は、頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、プロセッサ１２０２はさらに、クエリ条件によって示される候補頂点の区画番号および層番号を決定する前に、クエリ頂点の層番号がデフォルト層番号であるかどうかを決定し、決定することの結果が、クエリ頂点の層番号がデフォルト層番号でないことである場合、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップをトリガするように構成されている、またはクエリ頂点の層番号がデフォルト層番号である場合、その区画番号がクエリ頂点の区画番号であり、その層番号がデフォルト層番号である頂点を使用することによって候補セットを形成し、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されている。
【０１５７】
さらに、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有する場合、または辺のどれもが重みを有しない場合、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点と頂点が置かれている区画の区画境界との間の最小ホップカウントであり、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、接続関係を有する各２つの頂点間の辺について、辺の全てが同じ重みを有するのではない場合、頂点と頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、頂点と頂点が置かれている区画の区画境界との間の最短距離として使用され、２つの頂点間の距離は、２つの頂点のうちの一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、経路に含まれる辺の重みの総和である。
【０１５８】
さらに、プロセッサ１２０２は具体的に、クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定するように構成されている。
【０１５９】
さらに、グラフデータ全体セットにおける複数の頂点に対して辺切断区画化が予め行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、プロセッサ１２０２は具体的に、クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として決定するように構成されている。
【０１６０】
さらに、グラフデータ全体セットにおける複数の頂点に対して頂点切断区画化が予め行われ、区画境界が頂点を含み、区画境界上の頂点と、頂点が置かれている区画の区画境界との間の最短距離がゼロであり、プロセッサ１２０２は具体的に、クエリ条件が、候補頂点とクエリ頂点との間の最大距離を示す場合、候補頂点の区画番号および層番号を以下のように決定するように、すなわち、最大距離がクエリ頂点の層番号よりも大きくない場合、候補頂点の区画番号はクエリ頂点の区画番号であることを決定し、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、候補頂点の層番号として、クエリ頂点の層番号から最大距離を減算することによって得られる値から最小値までの閉区間内の層番号を決定する、または、最大距離がクエリ頂点の層番号よりも大きい場合、候補頂点の区画番号はクエリ頂点の区画番号であること、および、クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、クエリ頂点が置かれている区画について、クエリ頂点が置かれている区画における最大層番号と、クエリ頂点の層番号と最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、クエリ頂点の区画番号と同じグループに属する層番号として、決定し、クエリ頂点が置かれている区画の各隣接区画について、隣接区画の最大層番号と、最大距離からクエリ頂点の層番号を減算することによって得られる値との間の最小値を決定し、ゼロから最小値までの閉区間内の層番号を、候補頂点の層番号であり、隣接区画の区画番号と同じグループに属する層番号として、決定するように構成されている。
【０１６１】
さらに、プロセッサ１２０２は具体的に、クエリ条件を取得し、クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、第１のクエリ頂点の区画番号および層番号ならびに第２のクエリ頂点の区画番号および層番号を取得し、第１のクエリ頂点および第２のクエリ頂点が同じ区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点の層番号から第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号として決定する、または、第１のクエリ頂点および第２のクエリ頂点が異なる区画に置かれている場合、候補頂点の区画番号は第１のクエリ頂点および第２のクエリ頂点の区画番号であることを決定し、第１のクエリ頂点が置かれている区画について、ゼロから第１のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第１のクエリ頂点の区画番号と同じグループに属する層番号として、決定し、第２のクエリ頂点が置かれている区画について、ゼロから第２のクエリ頂点の層番号までの閉区間内の層番号を、候補頂点の層番号であり、第２のクエリ頂点の区画番号と同じグループに属する層番号として決定するように構成されている。
【０１６２】
さらに、プロセッサ１２０２は具体的に、クエリ条件に従って、必要とされるグラフデータを候補セットにおいて見出さない場合、拡張された候補セットを得るように候補セットに含まれる層番号区間を拡張し、クエリ条件に従って、拡張された候補セットにおいてグラフデータクエリを行うように構成されている。
【０１６３】
さらに、記憶装置１２０３は具体的に、グラフデータ全体セットにおけるグラフデータをファイルシステムに保存し、複数の頂点の区画番号および層番号を１つのファイルに保存し、同じ区画番号および層番号を有する頂点のグラフデータを１つのファイルに保存し、異なる区画番号および層番号を有する頂点のグラフデータを異なるファイルに保存するように構成されている。
【０１６４】
さらに、プロセッサ１２０２は具体的に、候補セットに含まれる頂点のグラフデータをメモリにロードし、クエリ条件に従って、候補セットに含まれる頂点のグラフデータであり、メモリにキャッシュされているグラフデータに対してグラフデータクエリを行うように構成されている。
【０１６５】
結論として、本発明の実施形態で提供される解決法は、クエリ頂点の区画番号および層番号を取得するステップと、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、それらを候補区画番号および候補層番号として使用するステップと、その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成するステップと、クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップとを含む。本発明の実施形態で提供される解決法を使用することによって、グラフデータクエリ効率が向上される。
【０１６６】
当業者は、本発明の実施形態が、方法、システム、またはコンピュータプログラムとして提供することができることを理解されたい。したがって、本発明は、ハードウェア専用実施形態、ソフトウェア専用実施形態、またはソフトウェアおよびハードウェアの組合せの実施形態のうちの形態を使用することができる。さらに、本発明は、コンピュータ使用可能なプログラムコードを含む、１または複数のコンピュータ使用可能な記憶媒体（これに限らないが、ディスク記憶装置、ＣＤ−ＲＯＭ、光学記憶装置などを含む）上で実施されるコンピュータプログラム製品の形態を使用することができる。
【０１６７】
本発明の実施形態による、方法、デバイス（システム）、およびコンピュータプログラム製品のフローチャートおよび／またはブロック図を参照して本発明を説明する。コンピュータプログラム命令を使用して、フローチャートおよび／またはブロック図における各プロセスおよび／または各ブロック、ならびにフローチャートおよび／またはブロック図におけるプロセスおよび／またはブロックの組合せを実施することができることを理解されたい。これらのコンピュータプログラム命令は、汎用コンピュータ、専用コンピュータ、内蔵プロセッサ、または機械を作り出すためのあらゆる他のプログラム可能データ処理デバイスのプロセッサに提供されることが可能であり、それによって、コンピュータ、またはあらゆる他のプログラム可能データ処理デバイスのプロセッサによって実行される命令が、フローチャートにおける１または複数のプロセス、および／またはブロック図における１または複数のブロックで特定の機能を実施する装置を作り出すようになる。
【０１６８】
これらのコンピュータプログラム命令はまた、特定の方法で機能するようにコンピュータまたはあらゆる他のプログラム可能データ処理デバイスに命令することができるコンピュータ可読記憶装置に保存されることが可能であり、それによって、コンピュータ可読記憶装置に保存された命令は、命令装置を含むアーティファクトを作り出すようになる。命令装置は、フローチャートにおける１または複数のプロセス、および／またはブロック図における１または複数のブロックで特定の機能を実施する。
【０１６９】
これらのコンピュータプログラム命令はまた、コンピュータまたは別のプログラム可能データ処理デバイス上にロードされることが可能であり、それによって、一連の動作およびステップが、コンピュータまたは別のプログラム可能デバイス上で行われ、それによって、コンピュータ実施処理を作り出すようになる。したがって、コンピュータまたは別のプログラム可能デバイス上で実行される命令は、フローチャートにおける１または複数のプロセス、および／またはブロック図における１または複数のブロックで特定の機能を実施するステップを提供する。
【０１７０】
本発明のいくつかの好ましい実施形態が記載されているが、当業者は、基本的な発明概念を習得した場合、これらの実施形態に変化および変更を加えることができる。それによって、以下の特許請求の範囲は、例示的な実施形態、および本発明の範囲内にある全ての変化および変更を含むように解釈されることを意図している。
【０１７１】
明らかに、当業者は、本発明の主旨および範囲から逸脱することなく、本発明に様々な変更および改変を加えることができる。本発明は、以下の特許請求の範囲および同等の技術によって規定された保護範囲内にある限り、これらの変更および改変を含むことを意図している。
【図１】
2017509043.tif 000005
【図２】
2017509043.tif 000006
【図３】
2017509043.tif 000007
【図４】
2017509043.tif 000008
【図５】
2017509043.tif 000009
【図６】
2017509043.tif 000010
【図７】
2017509043.tif 000011
【図８】
2017509043.tif 000012
【図９】
2017509043.tif 000013
【図１０】
2017509043.tif 000014
【図１１】
2017509043.tif 000015
【図１２】
2017509043.tif 000016
【手続補正書】
【提出日】平成28年8月2日(2016.8.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、データ処理技術の分野におけるグラフデータクエリ技術に関し、より詳細には、グラフデータクエリ方法および装置に関する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
第１の態様によると、グラフデータクエリ方法が提供され、これは、グラフデータ全体セットにおけるグラフデータのクエリに適用され、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用され、方法は、
クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するステップと、
クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップ、および候補頂点の区画番号および層番号をそれぞれ候補区画番号および候補層番号として使用するステップであって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である、ステップと、
その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するステップと、
クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップと
を含む。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
第２の態様によると、グラフデータクエリ装置が提供され、これは、グラフデータ全体セットにおけるグラフデータのクエリに適用され、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用され、クエリ装置は、
クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するように構成された取得ユニットと、
クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、候補頂点の区画番号および層番号をそれぞれ候補区画番号および候補層番号として使用するように構成された第１の決定ユニットであって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である、第１の決定ユニットと、
その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するように構成された第２の決定ユニットと、
クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたクエリユニットと
を含む。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
第３の態様によると、クエリサーバが提供され、これは、グラフデータ全体セットにおけるグラフデータのクエリに適用され、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用され、クエリサーバは、
クエリ条件を受信するように構成されたインターフェースと、
クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得し、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、候補頂点の区画番号および層番号をそれぞれ候補区画番号および候補層番号として使用し、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点であり、その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成し、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたプロセッサと、
グラフデータをグラフデータ全体セットに保存し、複数の頂点の区画番号と層番号をグラフデータ全体セットに保存するように構成された記憶装置と
を具体的に含む。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
ステップ１０２．クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップ、および候補頂点の区画番号および層番号をそれぞれ候補区画番号および候補層番号として使用するステップであって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
実際の応用例、いくつかの応用例シナリオでは、２つの頂点間の関係は、２つの頂点が接続関係を有することを示すだけでよく、この場合、重みは２つの頂点間の辺に対して設定されていないことがあり、または同じ重みが各辺に対して設定されていないことがある。例えば、ソーシャルネットワークでは、辺は２つの頂点によって示される２人のユーザが友人関係を有することを示すだけであり、重みは辺に設定されないことがある。しかし、いくつかの応用例シナリオでは、２つの頂点が接続関係を有することを示すことに加えて、２つの頂点間の関係はさらに、接続度を示すことがあり、この場合、重みは２つの頂点間の辺に対して設定されること可能であり、異なる重みは異なる接続度を示す。例えば、マップでは、辺は２つの頂点によって示される地理的位置間の直接経路があることを示し、辺のより大きな重みはより長い経路を示す。例えば、対応する重みが経路長さ範囲に従って決定される場合、同じ範囲内の経路長さは、同じ対応する重みを有する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００８４
【補正方法】変更
【補正の内容】
【００８４】
ステップ８０２．クエリ頂点の区画番号および層番号に基づいて、およびクエリ条件によって示される候補頂点とクエリ頂点との間の距離に従って、候補頂点の区画番号および層番号を決定し、候補頂点の区画番号および層番号をそれぞれ候補区画番号および候補層番号として使用し、候補頂点は、クエリ条件に従ってクエリする必要がある頂点である。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１２８
【補正方法】変更
【補正の内容】
【０１２８】
このステップでは、候補セットに含まれる層番号区間を拡張することは、毎回、予め設定された数の層を拡張すること、例えば、毎回、１つの層を拡張することであってよい。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１４４
【補正方法】変更
【補正の内容】
【０１４４】
実施形態５
同発明の概念に基づいて、および本発明の前述の実施形態で提供されたグラフデータクエリ方法に従って、これに応じて、本発明の実施形態５はさらに、グラフデータ全体セット内のグラフデータのクエリに適用されるグラフデータクエリ装置を提供し、グラフデータ全体セットは複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、区画化および階層化が、グラフデータ全体セットにおける複数の頂点上で予め行われ、頂点が置かれている区画の番号は、頂点の区画番号として使用され、頂点と頂点が置かれている区画の区画境界との間の最短距離は、頂点の層番号として使用される。クエリ装置の略構造図が、図１１に示され、クエリ装置は具体的に、クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するように構成された取得ユニット１１０１と、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、候補頂点の区画番号および層番号をそれぞれ候補区画番号および候補層番号として使用するように構成された第１の決定ユニット１１０２であって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点である、第１の決定ユニット１１０２と、その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成するように構成された第２の決定ユニット１１０３と、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたクエリユニット１１０４とを含む。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１５５
【補正方法】変更
【補正の内容】
【０１５５】
実施形態６
同発明の概念に基づいて、および本発明の前述の実施形態で提供されるグラフデータクエリ方法に従って、これに応じて、本発明の実施形態６は、グラフデータ全体セットにおけるグラフデータのクエリに適用されるクエリサーバであって、グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、グラフデータ全体セットにおける複数の頂点に対して予め区画化および階層化が行われており、頂点が置かれている区画の番号が頂点の区画番号として使用され、頂点と、頂点が置かれている区画の区画境界との間の最短距離が頂点の層番号として使用される。クエリサーバの略構造図が、図１２に示され、クエリサーバは具体的に、クエリ条件を受信するように構成されたインターフェース１２０１と、クエリ条件、ならびにクエリ条件によって示されるクエリ頂点の区画番号および層番号を取得し、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、候補頂点の区画番号および層番号をそれぞれを候補区画番号および候補層番号として使用するように構成されたプロセッサ１２０２であって、候補頂点は、クエリ条件に従ってクエリされる必要がある頂点であり、その区画番号および層番号が候補区画番号および候補層番号をそれぞれ満たす頂点を使用することによって候補セットを形成し、クエリ条件に従って候補セットにおいてグラフデータクエリを行うように構成されたプロセッサ１２０２と、グラフデータ全体セットにおけるグラフデータ、ならびにグラフデータ全体セットにおける複数の頂点の区画番号および層番号を保存するように構成された記憶装置１２０３を含む。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１６５
【補正方法】変更
【補正の内容】
【０１６５】
結論として、本発明の実施形態で提供される解決法は、クエリ頂点の区画番号および層番号を取得するステップと、クエリ頂点の区画番号および層番号に基づいて、クエリ条件によって示される候補頂点の区画番号および層番号を決定し、候補頂点の区画番号および層番号をそれぞれを候補区画番号および候補層番号として使用するステップと、その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成するステップと、クエリ条件に従って候補セットにおいてグラフデータクエリを行うステップとを含む。本発明の実施形態で提供される解決法を使用することによって、グラフデータクエリ効率が向上される。
【手続補正１２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
グラフデータ全体セットにおけるグラフデータのクエリに適用されるグラフデータクエリ方法であって、前記グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、前記グラフデータ全体セットにおける前記複数の頂点に対して区画化および階層化が行われており、頂点が置かれている区画の番号が前記頂点の区画番号として使用され、頂点と、前記頂点が置かれている区画の区画境界との間の最短距離が前記頂点の層番号として使用され、前記方法は、
クエリ条件、および前記クエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するステップと、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定するステップ、および前記候補頂点の前記区画番号および前記層番号をそれぞれ候補区画番号および候補層番号として使用するステップであって、前記候補頂点は、前記クエリ条件に従ってクエリされる必要がある頂点である、ステップと、
その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成するステップと、
前記クエリ条件に従って前記候補セットにおいてグラフデータクエリを行うステップと
を含むことを特徴とする方法。
【請求項２】
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップは、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、および前記クエリ条件によって示される前記候補頂点と前記クエリ頂点との間の距離に従って、前記候補頂点の前記区画番号および前記層番号を決定するステップ
を具体的に含む
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記グラフデータ全体セットにおける前記複数の頂点に対して辺切断区画化が行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、前記頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
前記クエリ条件は、前記候補頂点と前記クエリ頂点との間の最大距離を示し、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の区画番号および層番号を決定する前記ステップは、
前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定するステップ、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定するステップ
を具体的に含み、
前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記候補頂点の区画番号および層番号を決定するステップは、
前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定するステップ、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ、および、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定するステップ、および、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定するステップ
を具体的に含む
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記グラフデータ全体セットにおける前記複数の頂点に対して頂点切断区画化が行われ、区画境界が頂点を含み、前記区画境界上の前記頂点と、前記頂点が置かれている区画の前記区画境界との間の最短距離がゼロであり、
前記クエリ条件は、前記候補頂点と前記クエリ頂点との間の最大距離を示し、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の区画番号および層番号を決定する前記ステップは、
前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定するステップ、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、および、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定するステップ
を具体的に含み、
前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記候補頂点の区画番号および層番号を決定するステップは、
前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定するステップ、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定するステップ、およびゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ、および、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算することによって得られる値との間の最小値を決定するステップ、および、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定するステップ
を具体的に含む
ことを特徴とする請求項２に記載の方法。
【請求項５】
クエリ条件、ならびに前記クエリ条件によって示されるクエリ頂点の区画番号および層番号を取得する前記ステップは、
前記クエリ条件を取得し、前記クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、前記第１のクエリ頂点の区画番号および層番号ならびに前記第２のクエリ頂点の区画番号および層番号を取得するステップ
を具体的に含み、
前記第１のクエリ頂点および前記第２のクエリ頂点が同じ区画に置かれている場合、前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップは、
前記候補頂点の前記区画番号は前記第１のクエリ頂点および前記第２のクエリ頂点の前記区画番号であることを決定するステップ、および、前記第１のクエリ頂点の前記層番号から前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の前記層番号として決定するステップ
を具体的に含み、
前記第１のクエリ頂点および前記第２のクエリ頂点が異なる区画に置かれている場合、前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定する前記ステップは、
前記候補頂点の前記区画番号は前記第１のクエリ頂点の前記区画番号および前記第２のクエリ頂点の前記区画番号であることを決定するステップ、前記第１のクエリ頂点が置かれている区画について、ゼロから前記第１のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第１のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ、および、前記第２のクエリ頂点が置かれている区画について、ゼロから前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第２のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定するステップ
を具体的に含む
ことを特徴とする請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
前記クエリ条件に従って、必要とされるグラフデータが前記候補セットにおいて見出されない場合、拡張された候補セットを得るように前記候補セットに含まれる層番号区間を拡張するステップと、
前記クエリ条件に従って前記拡張された候補セットにおいてグラフデータクエリを実行するステップと
をさらに含む
ことを特徴とする請求項５に記載の方法。
【請求項７】
頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、前記デフォルト層番号は、前記頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
前記クエリ頂点の前記層番号が前記デフォルト層番号である場合、その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成する前記ステップは、
その区画番号が前記クエリ頂点の前記区画番号であり、その層番号が前記デフォルト層番号である頂点を使用することによって候補セットを形成するステップ
を含む
ことを特徴とする請求項１から請求項６のいずれか１項に記載の方法。
【請求項８】
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有する場合、または前記辺のどれもが重みを有しない場合、頂点と前記頂点が置かれている区画の区画境界との間の最短距離は、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最小ホップカウントであり、前記２つの頂点間の距離は、前記２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有するものではない場合、頂点と前記頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最短距離として使用され、２つの頂点間の距離は、前記２つの頂点のうち一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、前記経路に含まれる辺の重みの総和である
ことを特徴とする請求項１から請求項７のいずれか１項に記載の方法。
【請求項９】
前記グラフデータ全体セットにおける前記グラフデータがファイルシステムに保存されている場合、前記複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存されることを特徴とする請求項１から請求項８のいずれか１項に記載の方法。
【請求項１０】
請求項１から請求項９のいずれか１項に記載の方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ可読記憶媒体。
【請求項１１】
グラフデータ全体セットにおけるグラフデータのクエリに適用されるグラフデータクエリ装置であって、前記グラフデータ全体セットは、複数の頂点、および接続関係を有する各２つの頂点間の辺を含み、前記グラフデータ全体セットにおける前記複数の頂点に対して区画化および階層化が行われており、頂点が置かれている区画の番号が前記頂点の区画番号として使用され、頂点と、前記頂点が置かれている区画の区画境界との間の最短距離が前記頂点の層番号として使用され、前記クエリ装置は、
クエリ条件、ならびに前記クエリ条件によって示されるクエリ頂点の区画番号および層番号を取得するように構成された取得ユニットと、
前記クエリ頂点の前記区画番号および前記層番号に基づいて、前記クエリ条件によって示される候補頂点の区画番号および層番号を決定し、前記候補頂点の前記区画番号および前記層番号をそれぞれ候補区画番号および候補層番号として使用するように構成された第１の決定ユニットであって、前記候補頂点は、前記クエリ条件に従ってクエリされる必要がある頂点である、第１の決定ユニットと、
その区画番号および層番号が候補区画番号および候補層番号のあらゆるグループを満たす頂点を使用することによって候補セットを形成するように構成された第２の決定ユニットと、
前記クエリ条件に従って前記候補セットにおいてグラフデータクエリを行うように構成されたクエリユニットと
を含むことを特徴とするグラフデータクエリ装置。
【請求項１２】
前記第１の決定ユニットは、前記クエリ頂点の前記区画番号および前記層番号に基づいて、および前記クエリ条件によって示される前記候補頂点と前記クエリ頂点との間の距離に従って、前記候補頂点の前記区画番号および前記層番号を決定するように具体的に構成された
ことを特徴とする請求項１１に記載の装置。
【請求項１３】
前記グラフデータ全体セットにおける前記複数の頂点に対して辺切断区画化が行われ、区画境界が頂点を含まず、別の区画と交差する辺を有する頂点と、前記頂点が置かれている区画の区画境界との間の最短距離がゼロであり、
前記クエリ条件が、前記候補頂点と前記クエリ頂点との間の最大距離を示す場合、
前記第１の決定ユニットは、
前記候補頂点の前記区画番号および前記層番号を以下のように決定するように、すなわち、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定し、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定する、または、
前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定し、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算し、次いで１を減算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定する
ように具体的に構成された
ことを特徴とする請求項１２に記載の装置。
【請求項１４】
前記グラフデータ全体セットにおける前記複数の頂点に対して頂点切断区画化が行われ、区画境界が頂点を含み、前記区画境界上の前記頂点と、前記頂点が置かれている区画の前記区画境界との間の最短距離がゼロであり、
前記クエリ条件が、前記候補頂点と前記クエリ頂点との間の最大距離を示す場合、
前記第１の決定ユニットは、
前記候補頂点の前記区画番号および前記層番号を以下のように決定するように、すなわち、
前記最大距離が前記クエリ頂点の前記層番号よりも大きくない場合、前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であることを決定し、前記クエリ頂点が置かれている区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、前記候補頂点の前記層番号として、前記クエリ頂点の前記層番号から前記最大距離を減算することによって得られる値から前記最小値までの閉区間内の層番号を決定する、または、
前記候補頂点の前記区画番号は前記クエリ頂点の前記区画番号であること、および、前記最大距離が前記クエリ頂点の前記層番号よりも大きい場合、前記クエリ頂点が置かれている区画の隣接区画の区画番号を決定し、前記クエリ頂点が置かれている前記区画について、前記クエリ頂点が置かれている前記区画における最大層番号と、前記クエリ頂点の前記層番号と前記最大距離とを加算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記クエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定し、前記クエリ頂点が置かれている前記区画の各隣接区画について、前記隣接区画の最大層番号と、前記最大距離から前記クエリ頂点の前記層番号を減算することによって得られる値との間の最小値を決定し、ゼロから前記最小値までの閉区間内の層番号を、前記候補頂点の層番号であり、前記隣接区画の区画番号と同じグループに属する前記層番号として、決定する
ように具体的に構成された
ことを特徴とする請求項１２に記載の装置。
【請求項１５】
前記取得ユニットは、前記クエリ条件を取得し、前記クエリ条件が、第１のクエリ頂点と第２のクエリ頂点との間の最短経路がクエリされる必要があることを示す場合、前記第１のクエリ頂点の区画番号および層番号ならびに前記第２のクエリ頂点の区画番号および層番号を取得するように具体的に構成され、
前記第１のクエリ頂点および前記第２のクエリ頂点が同じ区画に置かれている場合、
前記第１の決定ユニットは、
前記候補頂点の前記区画番号は前記第１のクエリ頂点および前記第２のクエリ頂点の前記区画番号であることを決定し、前記第１のクエリ頂点の前記層番号から前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の前記層番号として決定する、
ように具体的に構成され、
または、
前記第１のクエリ頂点および前記第２のクエリ頂点が異なる区画に置かれている場合、
前記第１の決定ユニットは、
前記候補頂点の前記区画番号は前記第１のクエリ頂点および前記第２のクエリ頂点の前記区画番号であることを決定し、前記第１のクエリ頂点が置かれている区画について、ゼロから前記第１のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第１のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定し、前記第２のクエリ頂点が置かれている区画について、ゼロから前記第２のクエリ頂点の前記層番号までの閉区間内の層番号を、前記候補頂点の層番号であり、前記第２のクエリ頂点の前記区画番号と同じグループに属する前記層番号として、決定する
ように具体的に構成された
ことを特徴とする請求項１１から請求項１４のいずれか１項に記載の装置。
【請求項１６】
前記クエリユニットが、前記クエリ条件に従って、必要とされるグラフデータを前記候補セットにおいて見出さない場合、前記第２の決定ユニットは、拡張された候補セットを得るように前記候補セットに含まれる層番号区間を拡張するようにさらに構成され、
前記クエリユニットは、前記クエリ条件に従って前記拡張された候補セットにおいてグラフデータクエリを行うようにさらに構成された
ことを特徴とする請求項１５に記載の装置。
【請求項１７】
頂点が置かれている区画の区画境界に到達することができない頂点の層番号がデフォルト層番号であり、前記デフォルト層番号は、前記頂点が置かれている区画の区画境界に到達することができる頂点の層番号とは異なり、
前記クエリ頂点の前記層番号が前記デフォルト層番号である場合、前記第２の決定ユニットは、その区画番号が前記クエリ頂点の前記区画番号であり、その層番号が前記デフォルト層番号である頂点を使用することによって候補セットを形成するように具体的に構成された
ことを特徴とする請求項１１から請求項１６のいずれか１項に記載の装置。
【請求項１８】
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有する場合、または前記辺のどれもが重みを有しない場合、頂点と前記頂点が置かれている区画の区画境界との間の最短距離は、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最小ホップカウントであり、前記２つの頂点間の距離は、前記２つの頂点のうちの一方の頂点と他方の頂点との間のホップカウントであり、または、
接続関係を有する各２つの頂点間の前記辺について、前記辺の全てが同じ重みを有するものではない場合、頂点と前記頂点が置かれている区画の区画境界との間の経路の長さにおける最小長さが、前記頂点と前記頂点が置かれている前記区画の前記区画境界との間の最短距離として使用され、２つの頂点間の距離は、前記２つの頂点のうち一方の頂点と他方の頂点との間の経路の長さであり、経路の長さは、前記経路に含まれる辺の重みの総和である
ことを特徴とする請求項１１から請求項１７のいずれか１項に記載の装置。
【請求項１９】
前記グラフデータ全体セットにおける前記グラフデータがファイルシステムに保存されている場合、前記複数の頂点の区画番号および層番号が１つのファイルに保存され、同じ区画番号および層番号を有する頂点のグラフデータが１つのファイルに保存され、異なる区画番号および層番号を有する頂点のグラフデータが異なるファイルに保存されることを特徴とする請求項１１から請求項１８のいずれか１項に記載の装置。
【国際調査報告】
2017509043.tif 000017
2017509043.tif 000018
2017509043.tif 000019
2017509043.tif 000020