(57)【要約】【課題】CSR（Compressed Sparse Row）フォーマットで表現されたグラフデータにおいて、データ総量の削減を可能とする。【解決手段】グラフの頂点毎に、頂点に接続された辺を表す他の頂点の番号を配列で管理するCSRフォーマットで表現されたグラフデータの並べ替えを行うグラフデータ並べ替え装置において、入力されたグラフデータから、頂点に接続された辺の数のヒストグラムを作成し、作成されたヒストグラムをヒストグラム記憶手段に格納するヒストグラム作成手段と、前記ヒストグラム記憶手段から前記ヒストグラムを読み出し、当該ヒストグラムに示される頂点毎の辺の数に基づいて、接続された辺の数が多い頂点の順に、頂点に接続されている辺を示す他の頂点の番号を順番に新たに割り当て、新たに割り当てられた番号をグラフデータとしてグラフデータ記憶手段に格納するリラベル処理手段とを備える。【選択図】図２
2013228819.tif 000002
【特許請求の範囲】
【請求項１】
グラフの頂点毎に、頂点に接続された辺を表す他の頂点の番号を配列で管理するCSR（Compressed Sparse Row）フォーマットで表現されたグラフデータの並べ替えを行うグラフデータ並べ替え装置であって、
入力されたグラフデータから、頂点に接続された辺の数のヒストグラムを作成し、作成されたヒストグラムをヒストグラム記憶手段に格納するヒストグラム作成手段と、
前記ヒストグラム記憶手段から前記ヒストグラムを読み出し、当該ヒストグラムに示される頂点毎の辺の数に基づいて、接続された辺の数が多い頂点の順に、頂点に接続されている辺を示す他の頂点の番号を順番に新たに割り当て、新たに割り当てられた番号をグラフデータとしてグラフデータ記憶手段に格納するリラベル処理手段と
を備えることを特徴とするグラフデータ並べ替え装置。
【請求項２】
前記リラベル処理手段は、
前記新たな番号の割り当てが行われたときに、当該新たな番号と、当該新たな番号の割り当て前に割り当てられていた番号である旧番号とを対応付けて変換対応関係記憶手段に格納し、
接続された辺の数が多い頂点の順に繰り返し実行されるリラベル処理において、前記変換対応関係記憶手段を参照することにより、既に新たな番号を割り当てられている頂点については当該新たな番号を当該頂点の番号として前記グラフデータ記憶手段に格納する
ことを特徴とする請求項１に記載のグラフデータ並べ替え装置。
【請求項３】
前記グラフデータ並べ替え装置は、前記グラフデータ記憶手段に格納されたグラフデータを圧縮する圧縮処理手段を更に備え、
前記圧縮処理手段は、前記グラフデータ記憶手段に格納されたグラフデータにおける辺の配列内の隣接する頂点の番号間の差分を用いて圧縮を行う
ことを特徴とする請求項１又は２に記載のグラフデータ並べ替え装置。
【請求項４】
グラフの頂点毎に、頂点に接続された辺を表す他の頂点の番号を配列で管理するCSR（Compressed Sparse Row）フォーマットで表現されたグラフデータの並べ替えを行うグラフデータ並べ替え装置が実行するグラフデータ並べ替え方法であって、
入力されたグラフデータから、頂点に接続された辺の数のヒストグラムを作成し、作成されたヒストグラムをヒストグラム記憶手段に格納するヒストグラム作成ステップと、
前記ヒストグラム記憶手段から前記ヒストグラムを読み出し、当該ヒストグラムに示される頂点毎の辺の数に基づいて、接続された辺の数が多い頂点の順に、頂点に接続されている辺を示す他の頂点の番号を順番に新たに割り当て、新たに割り当てられた番号をグラフデータとしてグラフデータ記憶手段に格納するリラベル処理ステップと
を備えることを特徴とするグラフデータ並べ替え方法。
【請求項５】
前記リラベル処理ステップにおいて、前記グラフデータ並べ替え装置は、
前記新たな番号の割り当てが行われたときに、当該新たな番号と、当該新たな番号の割り当て前に割り当てられていた番号である旧番号とを対応付けて変換対応関係記憶手段に格納し、
接続された辺の数が多い頂点の順に繰り返し実行されるリラベル処理において、前記変換対応関係記憶手段を参照することにより、既に新たな番号を割り当てられている頂点については当該新たな番号を当該頂点の番号として前記グラフデータ記憶手段に格納する
ことを特徴とする請求項４に記載のグラフデータ並べ替え方法。
【請求項６】
前記グラフデータ並べ替え方法は、前記グラフデータ記憶手段に格納されたグラフデータを圧縮する圧縮処理ステップを更に備え、
前記圧縮処理ステップにおいて、前記グラフデータ並べ替え装置は、前記グラフデータ記憶手段に格納されたグラフデータにおける辺の配列内の隣接する頂点の番号間の差分を用いて圧縮を行う
ことを特徴とする請求項４又は５に記載のグラフデータ並べ替え方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のグラフデータ並べ替え装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、N個の頂点（Vertex）と、その頂点間を結ぶM個の辺（Edge）から構成されるグラフ構造内部表現のデータ量削減方式に関するものである。
【背景技術】
【０００２】
古くから良く用いられているグラフ表現はEdgeの存在する隣接Vertexを行列で表現する方法とリスト（もしくは配列）で表現する方法の2通りが存在する。本発明は特に後者の表現方法で良く用いられているCompressed Sparse Row(CSR)フォーマットを対象とする。
【０００３】
この表現方法の概要を図1に示す。この表現方法では、Vertexの配列をV[]、Edgeの配列をE[]と表現した場合に、i番目のVertexと結ばれているVertexの配列（ここで、i番目のVertex番号をiと定める）をE[V[i - 1]]からE[V[i]-1]までの配列で管理する。ここでは配列の先頭indexが0、Vertexの先頭番号が1であることを前提としている。例えば、図1の例において、Vertex:1に接続されているVertexは3、2、9、6であるため、V[0]=0、V[1]=4としてE[0]からE[3]までに3、2、9、6を挿入することになる。つまり、番号が１のVertexにはV[0]=0が対応し、E[]の０番目から３番目の位置に、番号が１のVertexに接続されたVertexの番号3、2、9、6が挿入される。番号が２のVertexにはV[1]=4が対応し、E[]の（０番目から数えた）４番目（V[1]番目）から６番目（(V[2]-1)番目）の位置に、番号が２のVertexに接続されたVertexの番号1、7、8が挿入される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】N. Bell et al., "Efficient Sparse Matrix-Vector Multiplication on CUDA", NVIDIA Technical Report, 2008
【発明の概要】
【発明が解決しようとする課題】
【０００５】
グラフを表現したデータにおいては、Vertexのデータ増加量がO(N)に対して、Edgeの増加量はO(N!)である。これはEdgeは2つのVertexの組み合わせ通り数だけ存在するためである。そのため、Vertexデータに対してEdgeデータは非常に規模が大きくなる。
【０００６】
このようにEdge数の増加はVertex数に対して大きく、図１に示した例ではEdge数（Edgeとして挿入されたVertexの数）が16個で各値のサイズを4B整数とした場合に、Edge数の表現に必要なデータ総量は64Bになる。
【０００７】
本発明は上記の点に鑑みてなされたものであり、CSR（Compressed Sparse Row）フォーマットで表現されたグラフデータにおいて、データ総量の削減を可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、本発明は、グラフの頂点毎に、頂点に接続された辺を表す他の頂点の番号を配列で管理するCSR（Compressed Sparse Row）フォーマットで表現されたグラフデータの並べ替えを行うグラフデータ並べ替え装置であって、
入力されたグラフデータから、頂点に接続された辺の数のヒストグラムを作成し、作成されたヒストグラムをヒストグラム記憶手段に格納するヒストグラム作成手段と、
前記ヒストグラム記憶手段から前記ヒストグラムを読み出し、当該ヒストグラムに示される頂点毎の辺の数に基づいて、接続された辺の数が多い頂点の順に、頂点に接続されている辺を示す他の頂点の番号を順番に新たに割り当て、新たに割り当てられた番号をグラフデータとしてグラフデータ記憶手段に格納するリラベル処理手段とを備えることを特徴とするグラフデータ並べ替え装置として構成される。
【０００９】
前記リラベル処理手段は、前記新たな番号の割り当てが行われたときに、当該新たな番号と、当該新たな番号の割り当て前に割り当てられていた番号である旧番号とを対応付けて変換対応関係記憶手段に格納し、
接続された辺の数が多い頂点の順に繰り返し実行されるリラベル処理において、前記変換対応関係記憶手段を参照することにより、既に新たな番号を割り当てられている頂点については当該新たな番号を当該頂点の番号として前記グラフデータ記憶手段に格納するように構成することができる。
【００１０】
前記グラフデータ並べ替え装置は、前記グラフデータ記憶手段に格納されたグラフデータを圧縮する圧縮処理手段を更に備えてもよく、前記圧縮処理手段は、前記グラフデータ記憶手段に格納されたグラフデータにおける辺の配列内の隣接する頂点の番号間の差分を用いて圧縮を行う。
【００１１】
また、本発明は、前記グラフデータ並べ替え装置が実行するグラフデータ並べ替え方法として構成することもできる。更に、本発明は、コンピュータを、前記グラフデータ並べ替え装置における各手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００１２】
本発明によれば、CSR（Compressed Sparse Row）フォーマットで表現されたグラフデータにおいて、データ総量の削減を可能とするグラフデータを取得できる。更に、圧縮処理手段を備えることにより、グラフデータの圧縮を実行することができる。
【図面の簡単な説明】
【００１３】
【図１】Compressed Sparse Row(CSR)フォーマットを説明するための図である。
【図２】本発明の実施の形態に係るグラフデータ圧縮装置の機能構成図である。
【図３】あるVertexと接続されているVertex番号のリラベル処理の例を示す図である。
【図４】昇順にソートしたVertex番号配列（Edge配列）のgap計算と圧縮の例を示す図である。
【図５】ヒストグラム作成部１１が実行するヒストグラム作成処理のフローチャートである。
【図６】リラベル処理部１３が実行するリラベル処理のフローチャートである。
【図７】圧縮処理部１６が実行する圧縮処理のフローチャートである。
【図８】GTGraphの生成データを用いた評価（Vertex総数220）を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１５】
（装置構成）
図２に、本発明の実施の形態に係るグラフデータ圧縮装置１０の機能構成図を示す。グラフデータ圧縮装置１０は、Vertex/Edge入力装置２０から入力されたCSRフォーマットのグラフデータ（例：図1）のEdge配列を圧縮し、圧縮されたグラフデータを結果出力装置３０に出力する装置である。図２に示すように、本実施の形態では、グラフデータ圧縮装置１０の外部にVertex/Edge入力装置２０と結果出力装置３０が接続される構成であるが、グラフデータ圧縮装置１０の内部にVertex/Edge入力装置２０と結果出力装置３０を備える構成であってもよい。
【００１６】
図２に示すように、グラフデータ圧縮装置１０は、ヒストグラム作成部１１、ヒストグラム記憶部１２、リラベル処理部１３、変換対応関係記憶部１４、Vertex/Edge配列記憶部１５、圧縮処理部１６、圧縮配列記憶部１７を有する。
【００１７】
なお、本実施の形態では、グラフデータ圧縮装置１０が、Edge配列の並べ替え（リラベル）を行う機能と、並べ替え後のEdge配列の圧縮を行う機能の両方を含むが、他の形態として、ある装置（この場合の装置を「グラフデータ並べ替え装置」と呼ぶことができる）において、Edge配列の並べ替え（リラベル）を行い、並べ替えられたグラフデータを出力する機能を備え、別の装置に、並べ替え後のEdge配列の圧縮を行う機能を備えることとしてもよい。また、グラフデータ並べ替え装置に更にEdge配列の圧縮を行う機能を加えることにより、グラフデータ圧縮装置１０として機能させることとしてもよい。つまり、グラフデータ圧縮装置１０は、グラフデータ並べ替え装置の一例である。
【００１８】
図２に示すグラフデータ圧縮装置１０の動作概要は以下のとおりである。
【００１９】
まず、ヒストグラム作成部１１が、Vertex/Edge入力装置２０から入力されたVertex/Edgeデータから、Vertexに接続されたEdge数のヒストグラムを作成し、作成されたヒストグラムをヒストグラム記憶部１２に記録する。
【００２０】
次に、リラベル処理部１３が、この作成されたヒストグラムデータをヒストグラム記憶部１２から読み出し、Edge数で降順にソートを行う。その後、接続されたEdge数が多い順に、そのVertexと、そのVertexに接続されているVertexの番号を1から順番に割り当てていく。ここでは、既に番号を割り当てられているVertexは、その番号を使用する。この処理を可能にするために、割り当て済みのVertexは変換対応関係記憶部１４で監視を行う。
【００２１】
Vertex番号の再割り当て（リラベル）が完了したデータはCSRフォーマットでVertex/Edge配列記憶部１５に記録する。そして最後に、圧縮処理部１６が、このリラベル処理を行ったCSRフォーマットのEdgeデータに対して、Vertex毎のgap変換と固定長圧縮処理を行い、これらの処理がされたデータを圧縮配列記憶部１６に記録する。全ての処理が完了後に、この圧縮後のCSRフォーマットを結果出力装置１６に出力する。その後、例えば、結果出力装置１６は、ユーザに対する表示、ネットワークへのデータ出力等を行う。
【００２２】
図３、図４に、本実施の形態における変換、圧縮の概要例を示しているが、これらについては次の処理詳細説明のところで説明する。
【００２３】
本実施の形態に係るグラフデータ圧縮装置１０（圧縮機能を含まないグラフデータ並べ替え装置についても同様）は、CPU及びメモリ等を有するコンピュータに、本実施の形態で説明する処理に対応するプログラムを実行させることにより実現可能である。当該プログラムは、可搬メモリ等の記憶媒体に格納して配布し、上記コンピュータにインストールして用いてもよいし、ネットワーク上のサーバからダウンロードして上記コンピュータにインストールしてもよい。また、本実施の形態で説明する処理をハードウェア回路として実現し、当該ハードウェア回路を備える装置としてグラフデータ圧縮装置１０を実現してもよい。
【００２４】
（処理の詳細）
以下、各機能部による処理の詳細をフローチャートを参照して説明する。
【００２５】
＜ヒストグラム作成処理＞
まず、図５のフローチャートを参照して、ヒストグラム作成部１１によるヒストグラム作成処理を説明する。
【００２６】
ステップS500）Vertex/Edge配列入力装置２０からVertex/Edgeの配列（CSRフォーマットのグラフデータ）を取得する。 
ステップS505）Vertex/EdgeのCSRフォーマットの配列から、Vertexの総数Nを数え上げる。
【００２７】
ステップS510)変数iを値1で初期化する。
【００２８】
ステップS515）Vertex/Edgeの配列から、i番目のVertexのEdge総数(つまり、i番目のVertexに対応してEdge配列に含まれるVertexの総数)を取得して、iとEdge総数をヒストグラム記憶部１２に記録する。
【００２９】
ステップS520）iに1を加算する。
【００３０】
ステップS525）iとNの大きさを比較し、iがNより大きければヒストグラム作成処理を終了し、iがNより大きくなければステップS515からの処理を繰り返す。
【００３１】
ヒストグラム記憶部１２内の1エントリのフォーマットは<Vertex番号，Edge総数>で定められ、最終的にVertex総数に等しいNエントリが記録される。
＜リラベル処理＞
次に、図６のフローチャートを参照して、リラベル処理部１３が実行するリラベル処理を説明する。
【００３２】
ステップS600）ヒストグラム記憶部１２からヒストグラムデータを読み込む。すなわち、リラベル処理部１３は、N個の<Vertex番号，Edge総数>エントリを読み込む。
【００３３】
ステップS605）読み込んだN個の<Vertex番号，Edge総数>エントリに対し、Edge総数で降順にソートを行い、降順ソート済みのN個の<Vertex番号，Edge総数>エントリを得る。
【００３４】
ステップS610）変数numを値1で初期化する。
【００３５】
ステップS615）変数iを値1で初期化する。
【００３６】
ステップS620）降順ソート済みのN個の<Vertex番号，Edge総数>エントリから、i番目に総数の多いVertexを取得し、そのVertexのM個のEdgeを取得する。すなわち、  ステップS620では、i番目にEdge総数が多いVertexのEdge配列（配列サイズをMとする）が取得される。
【００３７】
ステップS625）変数jを値1で初期化する。
【００３８】
ステップS630）i番目にEdge総数が多いVertexのEdge配列から、j番目のEdge番号（つまり、Edgeとして表現されているVertexの番号）を取得する。
【００３９】
ステップS635）変換対応関係記憶部１４を参照し、ステップS630で取得したEdge番号に対し、新規のEdge番号が既に割り当てられているかどうかを判定する。既に割り当てられている場合はステップS640に進み、新規のEdge番号が未だ割り当てられていない場合はステップS645に進む。
【００４０】
ステップS640）新規のEdge番号が既に割り当てられている場合、変換対応関係記憶部１４から、ステップS630で取得したj 番目のEdge番号に対応する新規のEdge番号を取得する。
【００４１】
ステップS645）新規のEdge番号が未だ割り当てられていない場合、ステップS630で取得したj 番目のEdge番号をnumの値に設定し、その変換後の対応関係を変換対応関係記憶部１４に記録する。変換対応関係記憶部１４内は< j 番目の旧Edge番号，j 番目の新Edge番号>を記録し、既に書き換えたEdge番号を管理する。
【００４２】
ステップS650）numに1を加算する。
【００４３】
ステップS655）新規に割り当てられたEdge番号をi番目Vertexのj番目EdgeとしてCSRフォーマットに併せてVertex/Edge配列記憶部１５に記録する。
【００４４】
ステップS660）jに1を加算する。
【００４５】
ステップS665）jとＭの大きさを比較し、jがＭより大きければステップS670に進み、jがＭより大きくなければステップS630からの処理を繰り返す。
【００４６】
ステップS670）iに1を加算する。
【００４７】
ステップS675）iとNの大きさを比較し、iがNより大きければリラベル処理を終了し、iがNより大きくなければステップS620からの処理を繰り返す。
【００４８】
図３は、上記のフローで実行されるリラベル処理の概要例を示している。図３に示すように、リラベル処理では、Edge数の最も多いVertexからEdge番号の振り直しが行われる。図３の例では、Edge数の最も多いVertexについて、変換前の８個のEdge番号（98, 71, 23, 43, 39, 9, 64, 88）が、（2, 3, 4, 5, 6, 7, 8, 9）に変換されたことが示されている。この変換後のVertex/Edge配列がVertex/Edge配列記憶部１５に記憶される。
＜圧縮処理＞
次に、図７のフローチャートを参照して、圧縮処理部１６が実行する圧縮処理を説明する。
【００４９】
ステップS700）Vertex/Edge記憶部１５からEdge番号を振り直したCSRフォーマットのVertex/Edge配列を取得する。
【００５０】
ステップS705）ステップS700で取得したVertex/Edge配列から、Vertexの総数Nを数え上げ、Vertexの総数Nを取得する。
【００５１】
ステップS710）変数iを値1で初期化する。
【００５２】
ステップS715）ステップS700で取得したVertex/Edge配列におけるi番目のVertexのEdge配列を昇順にソートする。
【００５３】
ステップS720）昇順にソートしたi番目のVertexのEdge配列の中から最小値MINを取得する。ここでは、昇順にソートしてあるため先頭の値が最小値MINとなる。
【００５４】
ステップS725）昇順にソートしたi番目のVertexのEdge配列の前後の値のgapを計算しgap配列を生成する。
【００５５】
ステップS730）ステップS725で生成したgap配列中の最大値MAXを取得する。
【００５６】
ステップS735）昇順にソートしたi番目のVertexのEdge配列、Edge配列中の最小値MIN、gap配列中の最大値MAXを用いることにより、先頭に最小値MINを、その後続に(log2(MAX) + 1)bit長とそのbit長で表現したgap配列とを含むEdge配列を圧縮配列記憶部１７に記録する。このとき、Vertex配列を含むCSRフォーマットで記録してもよい。
【００５７】
ステップS740）iに1を加算する。
【００５８】
ステップS745）iとNの大きさを比較し、iがNより大きければステップS750に進み、iがNより大きくなければステップS715からの処理を繰り返す。
【００５９】
ステップS750）圧縮配列記憶部１７に記憶されたデータを用いて、圧縮後のCSRフォーマットのVertex/Edge配列を出力する。
【００６０】
図４は、圧縮処理の概要例を示す図である。ここでは、図３における変換後のVertex１に対するEdge配列（32bit×8のサイズ）を圧縮する例を示している。
【００６１】
本例では、Edge配列の最小値MINは２である。また、Edge配列中の隣り合うVertex番号の差分である各gapは、3-2=1, 4-3=1, 5-4=1, 6-5=1, 7-6=1, 8-7=1, 9-8=1であるから、gapは全て１で、gap配列は(1, 1, 1, 1, 1, 1, 1)になる。gap配列中の最大値MAXは1であるから、(log2(MAX) + 1)は１となる。すなわち、1bitで、どのgap値も表現することができる。仮に、MAXが２だとすれば、(log2(MAX) + 1)は２となり、各gap値は2bitで表現されることになる。
【００６２】
本例では、非圧縮の値が32bitで表現され、gap配列の各値のbit長の値が8bitで表現され、gap配列の各値のbit長が１bitであるから、図４の「圧縮後」に示すように、Vertex１に対するEdge配列は、32+8+1*7の47bitで表現される。この例では、Edge配列の各bitを配列の要素としているので、Vertex:２に対応するVertex配列の値は47となっている。
【００６３】
なお、本実施の形態における圧縮の手法は一例であり、Vertex番号並べ替え後のEdge配列に対して、他の圧縮手法を適用することも可能である。
【００６４】
（実施の形態のまとめ、効果）
上述したように、本実施の形態では、Vertexに接続されているEdge数のヒストグラムを作成し、接続されている接続Edge数が多い順に、その接続されているVertex番号のgapが小さくなるように値を順番に振り直すこととしている。 
この技術により、各Vertexに接続されているVertex番号間のgapが統計的に小さくなる傾向が得られ、結果としてその後に行う圧縮の効率が高まる効果が得られる。具体的には、図３で説明したように、あるVertexに接続されているVertexの番号はランダムに割り当てられているため、ソート後の前後の値（gap）が大きくなりがちになる一方で、本実施の形態に係るリラベル処理を行うことでgapが小さくなる傾向が得られる（図３の例では全てのgapが1になる）。統計的に小さい値の出現確率が高くなるため、このような統計的特徴に最適化された圧縮アルゴリズムを適用することでEdgeのデータ総サイズの削減が可能となる。
【００６５】
グラフジェネレータ「GTGraph」を用いてVertex総数を220に固定してEdge総数を変化させた場合の無圧縮のCSRデータと本発明の技術を使用して圧縮したCSRデータのデータサイズ変化（MBで表記）を図8に示す。図８に示すとおり、Edge総数が多くなるにつれて本発明の効果が高くなる。
【００６６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６７】
１０  グラフデータ圧縮装置
１１  ヒストグラム作成部
１２  ヒストグラム記憶部
１３  リラベル処理部
１４  変換対応関係記憶部
１５  Vertex/Edge配列記憶部
１６  圧縮処理部
１７  圧縮配列記憶部
２０  Vertex/Edge入力装置
３０  結果出力装置
【図１】
2013228819.tif 000003
【図２】
2013228819.tif 000004
【図３】
2013228819.tif 000005
【図４】
2013228819.tif 000006
【図５】
2013228819.tif 000007
【図６】
2013228819.tif 000008
【図７】
2013228819.tif 000009
【図８】
2013228819.tif 000010