説明

木構造のデータに対する集約計算を行うコンピュータ・システム、並びにその方法及びコンピュータ・プログラム

【課題】ノードを含む木構造のデータに対する集約計算を行うために、インデックスを作成する方法を提供する。
【解決手段】ノードのそれぞれはノードの種類を示す1つのラベル及び0個以上の値を含む。ノードそれぞれに後行順(post-order)でノードidを割り振るノードid割振部と、ノードそれぞれのノードidと、ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成する第1のインデックス作成部と、ノードそれぞれのノードidと、ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成する第2のインデックス作成部と、特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成する第3のインデックス作成部とを含む。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、木構造のデータに対する集約計算を行うために、インデックスを作成するコンピュータ・システム、並びにその方法及びコンピュータ・プログラムに関する。さらに、本発明は、木構造のデータに対する集約計算を行うコンピュータ・システム、並びにその方法及びコンピュータ・プログラムに関する。
【背景技術】
【0002】
リレーショナル・データベース(RDB)における「GROUP BY」及び「HAVING」などとともに、集約関数を使用して値を集計するという操作が、検索及びデータベースの諸分野に見られる。該集計を効率的に行なうために、様々なインデックス及びデータフォーマットが提案されている。
【0003】
従来の手法は、汎用的な検索及び集約に対して成果を挙げている。しかし、該手法は、集約のために冗長なデータを持っている。そのために、該手法は、大規模データに対するパフォーマンスに難がある。
【0004】
また、RDBで一般的なB−tree(B−tree)を用いた集約についても、検索条件が緩いとき、例えばデータ全体の50%が集計対象の場合などにおいて処理が遅いという問題がある。
【0005】
下記特許文献1は、「Layered Index」及び「Patricia Tree」という二種類の既存の木構造インデックスを組み合わせたインデックス構造を記載する。しかし、該インデックス構造は、検索のためにノードの数を絞り込むときには有効であるが、大量のノードを処理する必要がある場合に不向きである。また、下記特許文献2は、データフォーマットについて従来のRDBのものを用いている。
【0006】
【特許文献1】米国特許第7,287,033号明細書
【特許文献2】米国特許第7,330,848号明細書
【発明の開示】
【発明が解決しようとする課題】
【0007】
検索及びデータベースの諸分野において、値を効率的に集計する手法が求められている。
【課題を解決するための手段】
【0008】
本発明は、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うために、インデックスを作成するコンピュータ・システムを提供する。上記ノードのそれぞれは該ノードの種類を示す1つのラベル及び任意の数の値(value)を含む。任意の数は、0個以上である。上記コンピュータ・システムは、
上記ノードそれぞれに後行順(post-order)でノードidを割り振るノードid割振部と、
上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成する第1のインデックス作成部であって、該1以上の組のデータは上記ラベル毎に作成される、上記第1のインデックス作成部と、
上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成する第2のインデックス作成部であって、該1以上の組のデータは上記ラベル毎に作成される、上記第2のインデックス作成部と、
特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成する第3のインデックス作成部であって、該1以上の組のデータは上記ラベル毎の上記特定の値毎に作成される、上記第3のインデックス作成部と
を含む。集約計算を行うための検索式の結果が、上記作成し第1、第2及び第3のインデックスに基づいて、求められる。上記検索式は例えば、値、又は該値及びその頻度を集計する。特に、上記検索式は、所与のラベルを持つノードを集計単位として、該ノードの値、又は該値及びその頻度を集計する。
【0009】
本発明の1つの実施態様では、上記第1のインデックスが、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む組のデータをシーケンシャルに格納したファイルである。
【0010】
本発明の1つの実施態様では、上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む組のデータをシーケンシャルに格納したファイルであるである。
【0011】
本発明の1つの実施態様では、上記第3のインデックスが、上記特定の値を含む1以上のノードのノードidを含む1以上の組のデータをシーケンシャルに格納したファイルである。
【0012】
本発明の1つの実施態様では、上記コンピュータ・システムはさらに、上記ラベルのそれぞれにラベルidを割り振るラベルid割振部をさらに含む。
【0013】
本発明の1つの実施態様では、上記コンピュータ・システムはさらに、上記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されている第4のインデックス作成部を含む。上記ポインタは上記第1のインデックスを成す上記1以上の組のデータにおけるノードidのデータの位置を示す。
【0014】
本発明はまた、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うためのコンピュータ・システムを提供する。上記ノードのそれぞれは該ノードの種類を示す1つのラベル及び任意の数の値を含む。任意の数は、0個以上である。上記ノードのそれぞれは後行順(post-order)でノードidを割り振られている。上記コンピュータ・システムは、
集約計算を行うための検索式を受信する受信部と
上記検索式の検索対象である値を用い及び、特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有するインデックスを用いて、上記検索式の検索対象である上記値を有する1以上のノードのノードidを含む第1のリストを取得する第1のリスト取得部であって、該1以上の組のデータは上記ラベル毎の上記特定の値毎に作成される、上記第1のリスト取得部と、
上記取得した第1のリストを用い及び、上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところのインデックスを用いて、上記検索式の検索対象である上記値を有する1以上のノードを子孫に持つ各木構造のルート・ノードの1以上のルート・ノードidを含む第2のリストを取得する第2のリスト取得部であって、該1以上の組のデータは上記ラベル毎に作成される、上記第2のリスト取得部と、
上記取得した第2のリストに基づいて、上記検索式の検索対象である上記値を検索する検索部であって、上記検索式の検索対象である上記値が少なくとも1つのキーワードに対応する、上記検索部と
を含む。
【0015】
本発明の1つの実施態様では、上記コンピュータ・システムはさらに、
上記取得した第2のリストを用いて及び、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いて、上記検索式の検索条件を満たす、1以上のノードの1以上の値を含む第3のリストを取得する第3のリスト取得部であって、該1以上の組のデータは上記ラベル毎に作成される、上記第3のリスト取得部と、
上記取得した第3のリストに基づいて、上記検索式の結果を求める計算部と
を含む。
【0016】
本発明はまた、中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うために、インデックスを作成する方法を提供する。上記ノードそれぞれは、該ノードの種類を示す1つのラベル及び任意の数の値を含む。任意の数は、0個以上である。上記方法が、上記中央演算処理ユニットに下記ステップを実行させることを含む。該ステップは、
上記ノードの情報を上記メモリー内に読み込み、上記情報を読み込んだノードそれぞれに後行順(post-order)でノードidを割り振るステップと、
上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成し、該作成した第1のインデックスを上記記憶部に格納するステップであって、該1以上の組のデータは上記ラベル毎に作成される、上記第1のインデックスを格納するステップと、
上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成し、該作成した第2のインデックスを上記記憶部に格納するステップであって、該1以上の組のデータは上記ラベル毎に作成される、上記第2のインデックスを格納するステップと、
特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成し、該作成した第3のインデックスを上記記憶部に格納するステップであって、該1以上の組のデータは上記ラベル毎の上記特定の値毎に作成される、上記第3のインデックスを格納するステップと
を含む。集約計算を行うための検索式の結果が、上記作成し第1、第2及び第3のインデックスに基づいて、求められる。
【0017】
本発明の1つの実施態様では、上記第1のインデックスを上記記憶部に格納するステップが、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む組のデータをシーケンシャルに格納するステップをさらに含む。
【0018】
本発明の1つの実施態様では、上記第2のインデックスを上記記憶部に格納するステップが、上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む組のデータをシーケンシャルに格納するステップをさらに含む。
【0019】
本発明の1つの実施態様では、上記第3のインデックスを上記記憶部に格納するステップが、上記特定の値を含む1以上のノードのノードidを含む1以上の組のデータをシーケンシャルに格納するステップをさらに含む。
【0020】
本発明の1つの実施態様では、上記方法が、上記中央演算処理ユニットに下記ステップをさらに実行させることを含む。該ステップは、上記ラベルのそれぞれにラベルidを割り振るステップを含む。
【0021】
本発明の1つの実施態様では、上記方法が、上記中央演算処理ユニットに下記ステップをさらに実行させることを含む。該ステップは、
上記第1のインデックスにおける値又は上記第3のインデックスにおけるノードidを圧縮するステップを含む。
【0022】
本発明の1つの実施態様では、上記方法が、上記中央演算処理ユニットに下記ステップをさらに実行させることを含む。該ステップは、上記第1のインデックスを作成する前に、上記値が文字列である場合、該文字列を数値に置き換えるステップを含む。
【0023】
本発明の1つの実施態様では、上記方法が、上記中央演算処理ユニットに下記ステップをさらに実行させることを含む。該ステップは、上記第3のインデックスを作成した後に、上記置き換えられた数値を、上記文字列にさらに置き換えるステップを含む。
【0024】
本発明の1つの実施態様では、上記方法が、上記中央演算処理ユニットに下記ステップをさらに実行させることを含む。該ステップは、上記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されている第4のインデックスを作成するステップを含む。上記ポインタは上記第1のインデックスを成す上記1以上の組のデータにおけるノードidのデータの位置を示す。
【0025】
本発明はまた、中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うために、インデックスを作成するためのコンピュータ・プログラムを提供する。上記コンピュータ・プログラムは、上記中央演算処理ユニットに上記に記載の各ステップを実行させることを含む。
【0026】
本発明はまた、中央演算処理ユニット、メモリー及び上記木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行う方法を提供する。上記ノードそれぞれは該ノードの種類を示す1つのラベル及び任意の数の値を含む。任意の数は、0個以上である。上記ノードそれぞれは、後行順(post-order)でノードidを割り振られている。上記方法が中央演算処理ユニットに下記ステップを実行させるステップを含む。該ステップが、
集約計算を行うための検索式を受信し、該受信した検索式を上記メモリー内に記憶するステップと、
上記検索式の検索対象である値を用い及び、特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有するインデックスを用いて、上記検索式の検索対象である上記値を有する1以上のノードのノードidを含む第1のリストを取得し、該取得した第1のリストを上記記憶部に記憶するステップであって、該1以上の組のデータは上記ラベル毎の上記特定の値毎に作成される、上記第1のリストを記憶するステップと、
上記取得した第1のリストを用い及び、上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところのインデックスを用いて、上記検索式の検索対象である上記値を有する1以上のノードを子孫に持つ各木構造のルート・ノードの1以上のルート・ノードidを含む第2のリストを取得し、該取得した第2のリストを上記記憶部に記憶するステップであって、該1以上の組のデータは上記ラベル毎に作成される、上記第2のリストを記憶するステップと、
上記取得した第2のリストに基づいて、上記検索式の検索対象である上記値を検索するステップであって、上記検索式の検索対象である上記値が少なくとも1つのキーワードに対応する、上記検索するステップと
を含む。
【0027】
本発明の1つの実施態様では、上記方法が、上記中央演算処理ユニットに下記ステップをさらに実行させることを含む。該ステップは、
上記取得した第2のリストを用い及び、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いて、上記検索式の検索条件を満たす、1以上のノードの1以上の値を含む第3のリストを取得し、該取得した第3のリストを上記記憶部に記憶するステップであって、該1以上の組のデータは上記ラベル毎に作成される、上記第3のリストを記憶するステップと、
上記取得した第3のリストに基づいて、上記検索式の結果を求めるステップと
を含む。
【0028】
本発明の1つの実施態様では、上記第3のリストが、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いてシーケンシャルアクセスにより取得される。
【0029】
本発明の1つの実施態様では、上記第3のリストが、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックス、及び上記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されているインデックスを用いてランダムアクセスにより取得される。
【0030】
本発明の1つの実施態様では、上記第3のリストの一部が、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いてシーケンシャルアクセスにより取得され、及び
上記第3のリストの残りが、上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックス、及び上記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されているインデックスを用いてランダムアクセスにより取得され、
上記第3のリストが、上記シーケンシャルアクセスと上記ランダムアクセスとを切り替えることによって取得される。
【0031】
本発明はまた、中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うためのコンピュータ・プログラムを提供する。上記コンピュータ・プログラムは、中央演算処理ユニットに上記方法に記載の各ステップを実行させることを含む。
【0032】
本発明はまた、中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行う方法を提供する。上記ノードそれぞれは該ノードの種類を示す1つのラベル及び任意の数の値を含む。任意の数は、0個以上である。上記方法が、上記中央演算処理ユニットに下記ステップを実行させることを含む。該ステップが、
上記ノードの情報を上記メモリー内に読み込み、上記情報を読み込んだノードそれぞれに後行順(post-order)でノードidを割り振るステップと、
上記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成し、該作成した第1のインデックスを上記記憶部に格納するステップであって、該1以上の組のデータは上記ラベル毎に作成される、上記第1のインデックスを格納するステップと、
上記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成し、該作成した第2のインデックスを上記記憶部に格納するステップであって、該1以上の組のデータは上記ラベル毎に作成される、上記第2のインデックスを格納するステップと、
特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成し、該作成した第3のインデックスを上記記憶部に格納するステップであって、該1以上の組のデータは上記ラベル毎の上記特定の値毎に作成される、上記第3のインデックスを格納するステップと、
上記メモリー内に記憶した集約計算を行うための検索式の検索対象である値及び上記第3のインデックスを用いて、上記検索式の検索対象である上記値を有する1以上のノードのノードidを含む第1のリストを取得し、該取得した第1のリストを上記記憶部に記憶するステップと、
上記取得した第1のリスト及び上記第2のインデックスを用いて、上記検索式の検索対象である上記値を有する1以上のノードを子孫に持つ各木構造のルート・ノードの1以上のルート・ノードidを含む第2のリストを取得し、該取得した第2のリストを上記記憶部に記憶するステップと、
上記取得した第2のリスト及び上記第1のインデックスを用いて、上記検索式の検索条件を満たす、1以上のノードの1以上の値を含む第3のリストを取得し、該取得した第3のリストを上記記憶部に記憶するステップと、
上記取得した第3のリストに基づいて、上記検索式の結果を求めるステップと
を含む。
【発明の効果】
【0033】
本発明の実施態様によると、木構造のノードに含まれる値及び該値の頻度を高速に集計することが可能になる。該値は、集約計算を行うための検索式におけるキーワードに対応する。また、本発明の実施態様によると、大量のデータを木構造により扱うことが可能になる。
【発明を実施するための最良の形態】
【0034】
以下、図面に従って、本発明の実施態様を説明する。本実施態様は、本発明の好適な態様を説明するためのものであり、本発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断らない限り、同一の符号は、同一の対象を指す。
【0035】
コールセンターでは、オペレータが、顧客からの問い合わせを受けて応答を行う。コールセンターのシステムは、顧客からの問い合わせ及び該問い合わせに対する応答をログ・データとして記録しうる。ログ・データを分析し活用しようという試みは、データマイニングの分野で見られうる。例えば、「顧客からの問い合わせが、「XXXウイルス」という言葉を含む場合に、オペレータによって多く照会された言葉は、「A」及び「B」のどちらなのかを求める」という分析、或いは「問い合わせと応答で使用される動詞の違いを求める」という分析が考えられる。ログ・データに記録された会話文などの文書は、多くの場合、文書に含まれる文及び単語などの任意の部分をノードとする木構造で表すことができる。木構造を集めたものは、ある問題を解決するための情報の一つになりうる。例えば、コールセンターのログ・データを表した木構造を集めたものは、過去に受けた問い合わせ及び応答の集合である。よって、オペレータがこれから発生しうる問い合わせについて応答をする際に、上記木構造を集めたものが情報として利用されうる。ログ・データに記録された会話文などの文書を木構造で表すために、自然言語処理(Natural Language Processing:NLP)と呼ばれる技術が用いられうる。NLPとは、自然言語で記述されたテキストから、単語及び単語間の依存関係などの情報を抽出する技術である。NLP処理によってログ・データから抜き出された単語および単語間の依存関係などの情報は、木構造に任意の方法でマッピングされうる。
【0036】
図1A及び図1Bは、本発明の実施態様である、NLPを用いてログ・データを処理する方法を示す。
図1Aは、コールセンターにおけるログ・データ(100)の例を示す。ログ・データ(100)では、顧客からの問い合わせがQ及びオペレータの応答がAとして示される。
図1Aはまた、上記ログ・データ(100)にマークアップ言語のタグを付加したデータ(101)の例を示す。該タグは、ログ・データ(100)に木構造を与えるために付加される。マークアップ言語として、例えばXML(Extensible Markup Language)が使用されうる。タグは、ユーザーによって任意に設定されうる。タグ<Document>及び</Document>は、該ログ・データ(100)の種類を示す。タグ<Q>及び</Q>は、質問部分であることを示す。タグ<A>及び</A>は、回答部分であることを示す。
図1Bは、NLPを使用して該ログ・データ(100)から文及び/又は単語を抜き出したデータ(102)を示す。NLP処理を実施するためのソフトウェア技術は例えば、UIMA(Unstructured Information Management Architecture)である。データ(102)では、ログ・データ(100)のうち、NLP処理により抜き出された個所の前後にタグが付加されている。タグ<expression_desire>及び</expression_desire>は、願望の表現を含む部分であることを示す。タグ<noun>及び</noun>は、名詞を含む部分であることを示す。タグ<verb>及び</verb>は、動詞を含む部分であることを示す。タグ<proper_noun>及び</proper_noun>は、固有名詞を含む部分であることを示す。
図1Bはまた、データ(102)からNLP処理により抜き出されなかった個所を除いたデータ(103)の例を示す。データ(103)が、下記に述べる木構造のデータを作成するために使用されうる。
なお、データ(102、103)は、NLP処理により抜き出されたデータのフォーマットの一例であり、図示した構造を必ずしもとるものではない。上記NLP処理は、コールセンターのログ・データに限らず、さまざまな文書についても応用することができる。
【0037】
図2は、本発明の実施態様である、2つの木構造(200A及び200B)の例を示す。
木構造は、少なくとも1つのノードを含む。ノードは、ユニットともいう。木構造について、図2の木構造(200A)を用いて説明する。木構造(200A)は、ルート・ノード(216)及び複数のノード(210〜215)を有する。同様に、木構造(200B)は、ルート・ノード(227)及び複数のノード(220〜226)を有する。各ノード(201)は、リンク(206)で結ばれる。リンクで結ばれたノード(201)のうち、上方に存在するノードを親ノードといい、一方下方に存在するノードを子ノードという。例えば、ノード(210)の親ノードは、ノード(214)である。例えば、ノード(216)の子ノードは、ノード(213〜215)である。ある親ノードから見て、子ノード、子ノードの子ノード(孫ノードである)、・・・、及び最下方に存在する子ノードをまとめて子孫ノードという。例えば、ノード(216)の子孫ノードは、ノード(210〜215)である。ノード(201)は、0個以上の子ノードを持ちうる。ノード(201)のうち、最上流のノードをルート・ノード(202)という。
【0038】
ノード(201)は、データとして、セクション(203)及び値(204)を含む。
セクション(203)は、ノード(201)の種類を示すラベルである。ラベルは、ノード(201)毎に1つ割り当てられる。例として、ノード(210、212)のセクションには、ラベル“Noun”が割り当てられている。同様に、ノード(211)のセクションには、ラベル“Verb”が割り当てられている。ルート・ノード(202)に割り当てるセクションがない場合には、仮想のセクション(205)が割り当てられる。
値(204)は、数値、文字列、又はそれらの組み合わせを含む。1つのノード(201)は、0個以上の値(204)を含む。例として、ノード(213)の値は、20071112の1つであり、ノード(212)の値は、“Internet”及び“modem”の2つである。また、ノード(214)は値を有しないので、0個の値を含む。0個の値は、NULL又は空白で表現されうる。
【0039】
図2の木構造のデータは、上記ログ・データを木構造のデータに変換した一例を示す。木構造(200A、200B)のそれぞれが、ログ・データ(100)の文書を表す。
木構造(200A、200B)のルート・ノード(216、227)の仮想セクション(205)は、該木構造が“DOCUMENT”についてのものであることを示す。木構造(200A、200B)のノード(201)それぞれが、木構造(200A、200B)の文書の持つ情報を示す。例えば、セクションが“Date”のノード(213、223)は、文書の作成日の情報を持つことを示す。文書の作成日は、値として示される。また、セクションが“Question”であるノード(214、224及び225)は、顧客からの問い合わせ内容の情報を持つことを示す。ただし、木構造(200A、200B)では、セクションが“Question”であるノード(214、224及び225)それ自体は、顧客からの問い合わせの内容を値として持たない。“Question”のノード(214、224及び225)は、顧客からの問い合わせの内容をさらに種類ごとに細分化した子ノード(それぞれ210〜211、220及び221)を持つからである。例えば、子ノード(210〜211、220及び221)のうち、セクションが“Noun”であるノード(210、220及び221)は、問い合わせに含まれる名詞を値として持つ。セクションが“Verb”であるノード(211及び222)は、問い合わせに含まれる動詞を値として持つ。木構造のデータを作成する際に値に保存する対象はキーワードでありうる。キーワードは、問い合わせの本文中からNLP処理などの技術を用いて抽出される。抽出の方法は、慣用の方法を使用しうる。例えば、単語の出現頻度を解析して抽出する方法、大規模な単語リストを用いて抽出する方法、及び文の構造を解析して抽出する方法が用いられうる。
【0040】
図2の木構造(200A、200B)のデータを用いて、集約計算を説明する。
集約計算とは、与えられた任意のセクションを持つノードを集計単位として、値を集計することを意味する。集計単位とは、木構造においてノードの子孫ノードに同じ値が何回出現しても1回とカウントする基準である。集計とは例えば、値について、値及びその出現回数(頻度ともいう)の組を頻度の降順若しくは昇順に出力する処理、又は任意の集合関数を用いて計算する処理をいう。任意の集合関数は例えば、count(件数)、sum(合計)、min(最小値)、max(最大値)及びavg(平均)であり、ユーザーが独自に定義した関数も含みうる。
【0041】
図3の表(300)は、下記検索条件において、値及び頻度を降順に出力した結果を示す。
検索条件:図2の各木構造(200A、200B)について、セクションが“Document”であるノード(216、227)を集計単位として、セクションが“Noun”であるノード(210、212、220、221)に含まれる値及びその頻度を降順に出力する。
以下に、上記検索条件による結果を導くプロセスを示す。
最初に、ルート・ノード(216)を集計単位のノードとした場合を考える。集計単位であるルート・ノード(216)の子孫ノードであり且つセクションが“Noun”であるノードは、ノード(210、212)の2つである。ノード(210)の値は、“Internet”、“PC”及び“phone”である。ノード(212)の値は、“Internet”及び“modem”である。よって、ルート・ノード(216)を集計単位のノードとした場合、発生した値は、“Internet”、“PC”、“phone”及び“modem”である。ここで、“Internet”は、ノード(210)及びノード(212)の両方に重複して出現する。しかし、いずれのノード(210、212)も集計単位となるルート・ノード(216)の子孫ノードであるので、値“Internet”の出現回数は1回と数えられる。
次に、ルート・ノード(227)を集計単位のノードとした場合を考える。集計単位であるルート・ノード(227)の子孫ノードであり且つセクションが“Noun”であるノードは、ノード(220、221)の2つである。 ノード(220)の値は、“Internet”及び“phone”である。ノード(221)の値は、“Internet”及び“modem”である。よって、ルート・ノード(227)を集計単位のノードとした場合、発生した値は、“Internet”、“phone”及び“modem”である。ここで、“Internet”は、ノード(220)及びノード(221)の両方に重複して出現する。しかし、いずれのノード(220、221)も集計単位となるルート・ノード(227)の子孫ノードであるので、値“Internet”の出現回数は1回と数えられる。
以上より、セクションが“Document”であるルート・ノード(216、227)を集計単位として、セクションが“Noun”であるノード(210、212、220、221)に含まれる値及びその頻度を求めた場合、値“Internet”が2回であり、値“modem”が2回であり、値“phone”が2回であり、及び値“PC”が1回である。
上記例では、ルート・ノードを集計単位のノードとして考えたが、それ以外のノードの場合にも、上記プロセスが適用される。下記にその例を示す。
【0042】
図3の表(301)は、下記検索条件において、値及びその頻度を降順に出力した結果を示す。以下に、該結果を導くプロセスを示す。
検索条件:図2の各木構造(200A、200B)について、セクションが“Question”であるノード(214、224、225)を集計単位として、セクションが“Noun”であるノード(210、212、220、221)に含まれる値及びその頻度を降順に出力する。
最初に、集計単位となるノードの1つであるノード(214)の子孫ノードであり且つセクションが“Noun”であるノードは、ノード(210)である。ノード(210)の値は、“Internet”、“PC”及び“phone”である。
次に、集計単位となるノードの1つであるノード(224)の子孫ノードであり且つセクションが“Noun”であるノードは、ノード(220)である。ノード(220)の値は、“Internet”及び“phone”である。
最後に、集計単位となるノードの1つであるノード(225)の子孫ノードであり且つセクションが“Noun”であるノードは、ノード(221)である。ノード(221)の値は、“Internet”及び“modem”である。
以上より、セクションが“Question”であるノード(214、224、225)を集計単位として、セクションが“Noun”であるノード(210、212、220、221)に含まれる値及びその頻度を求めた場合、値“Internet”が3回であり、値“phone”が2回であり、値“modem”が1回であり、及び値“PC”が1回である。
【0043】
図3の表(302)は、下記検索条件における値の集約の結果を示す。
検索条件:図2の各木構造(200A、200B)について、セクションが“Document”であるノード(216、227)を集計単位として、セクションが“Question”であるノードの子ノードであり、該子ノードのセクションが“Noun”であり、及び該子ノードに含まれる値が“Internet”である場合に、セクションが“Answer”であるノードの子ノードであり、該子ノードのセクションが“Noun”であるノードの値及びその頻度を集計する。
該検索結果の値は、ノード(212)の値である“Internet”及び“modem”である。該検索結果の頻度は、“Internet”が1であり、及び“modem”が1である。
上記検索条件は、複雑な集約の例である。該集約は、セクションが“Answer”であるノードの子ノードにおいてセクションが“Noun”であるノード(312)のみが集計の対象になる。該集約によって、例えば顧客がインターネットについて言及しているときに、オペレータが発している言葉の内訳を知ることができる。
【0044】
図4は、本発明の実施態様である、各ノードに後行順(post-order)でノードidを割り振る例を示す。
ノードidの割り振りには、木構造の走査(traversal)方法の1つである後行順(post-order)を用いる。後行順(post-order)は、後置順とも呼ばれる。木構造に対する後行順(post-order)とは、木のルート・ノードを T、T の子要素を T1、...、Tk としたとき、「T1をルート・ノードとする木を後行順で処理」、「T2をルート・ノードとする木を後行順で処理」・・・「Tkをルート・ノードとする木を後行順で処理」及び「Tを処理」というように再帰的に定義される処理順序のことである。ノードidは例えば、整数値でありうる。
図4の木構造400A及び400Bは、図2の木構造200A及び200Bにそれぞれ対応する。図4のid:1〜15が、各ノードに割り振られたノードidである。
【0045】
以下に、木構造(400A、400B)について、各ノードに後行順(post-order)でノードidを割り振る手順を示す。
最初に、木構造(400A)のルート・ノードであるノード(416)を選択する。次に、ノード(416)の子ノードのうち、左から1番目の子ノードであるノード(413)を選択する。ノード(413)は子ノードを持たないので、ノード(413)にノードid:1を割り振る。次に、ノード(413)の親ノード(416)を選択する。親ノード(416)の子ノードのうち、左から2番目の子ノードであるノード(414)を選択する。ノード(414)はさらに子ノードを(410、411)持つため、左から1番目の子ノードであるノード(410)を選択する。ノード(410)は子ノードを持たないので、ノード(410)にノードid:2を割り振る。次に、ノード(410)の親ノード(414)を選択する。次に、ノード(414)の子ノードのうち、左から2番目の子ノードであるノード(411)を選択する。ノード(411)は子ノードを持たないので、ノード(411)にノードid:3を割り振る。次に、ノード(411)の親ノード(414)を選択する。ノード(414)の全ての子ノード(410、411)にidが割り振られているので、ノード(414)にノードid:4を割り振る。次に、ノード(414)の親ノード(416)を選択する。ノード(416)の子ノードのうち、左から3番目の子ノードであるノード(415)を選択する。ノード(415)は、さらに子ノード(412)を持つため、左から1番目の子ノードであるノード(412)を選択する。ノード(412)は子ノードを持たないので、ノード(412)にノードid:5を割り振る。次に、ノード(412)の親ノード(415)を選択する。ノード(415)の全ての子ノード(412)にidが割り振られているので、ノード(415)にノードid:6を割り振る。次に、ノード(415)の親ノード(416)を選択する。ノード(416)の全ての子ノード(413、414、415)にidが割り振られているので、ノード(416)にノードid:7を割り振る。以上の手順により、木構造(400A)に含まれる全てのノードに、ノードidが割り振られる。
引き続き別の木構造(400B)について、各ノードに後行順(post-order)でノードidを割り振る場合、ノードidの割り振りは続きのid番号(上記例においては8)から始められる。木構造(400B)について、各ノードに後行順(post-order)でノードidを割り振った結果は、図4を参照されたい。
【0046】
以下の実施態様では、図4の木構造に示されるデータを参照する。また、該木構造に示されるデータの定義は、以下の通りである。
木構造を有するデータの集合を、D={T,T,...,T,...,T}(1≦i≦m)で表す。ここで、mは少なくとも1である。各Tは、有限個のノードを含む。以下、記号Tを用いて、Tのルート・ノードも指す。Tに含まれるノードの個数をnとする。
各ノードは、1つのセクション及び0個以上の値を有する。セクションは、ノードの種類を示す1つのラベル(b)を含む。よって、上記ノードの定義において、セクションをラベルと読み替えることができる。以下では、セクションをSで表し、値をVLで表す。1つのノードは、ノードの親子関係の情報のほかに、{b;VL, VL,..., VL,..., VL}(0≦i≦k)という情報を有する。ここで、kは0であってよい。すなわち、ノードがVLを持たなくてもよい。本発明の1つの実施態様では、値、例えば“modem”のような文字列、は、一意な整数値で符号化されうる。
Dに現れるすべてのラベルの集合をL={b,b,...,b,...,b}(1≦b≦p)で表す。各ラベルbは、圧縮に適した整数値で符号化しうる。符号化の例は、Document=1、Date=2、及びQuestion=3である。D内の木構造を順次読んでいき、未知のラベルが出現した場合は、その都度、新しい整数値がそのラベルに割り振られうる。
上記ルート・ノードのセクションは、全て等しいものである必要はない。なぜならば、後述する集約単位のセクションSに対して、その子孫ノードに対するjoin操作をすることにより、上記ルート・ノードのセクションが全て等しい場合と同じ結果を得ることができるからである。
【0047】
本発明の実施態様では、木構造のデータに対する集約計算を行うために、3つのインデックス、すなわち第1のインデックス、第2のインデックス及び第3のインデックスを作成する。
【0048】
第1のインデックス(以下u2vインデックス)とは、ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを保管したものをいう。u2vインデックスにおいて、該組のデータは、セクション毎に作成される。本発明の1つの実施態様では、u2vインデックスは、上記組のデータをシーケンシャルに格納している。
図5Aは、本発明の実施態様である、u2vインデックスの概念スキーマ及び保管の例を示す。u2vインデックスの概念スキーマは、セクション・ポインター・ツリー(500)及び表(501、502)で示される。セクション・ポインター・ツリー(500)は、表(501)の各行へのポインタの集合データを示す。表(501)の各行は、1セクション分のインデックスを示す。1列目は、行のサイズである。2列目は、セクションに対応するノードの数である。3列目以降は、セクションに対応するノードの数分のEntryである。表(502)は、Entryの詳細を示す。1列目は、ノードidを示す。2列目は、ノードidが割り振られたノードに含まれる値の数を示す。3列目以降は、ノードidが割り振られたノードに含まれる値を示す。本発明の1つの実施態様として、3列目以降に設定される値は、差分圧縮されうる。差分圧縮の方法については後述する。
【0049】
1セクション分のu2vインデックスのデータフォーマットは、次の通りである。該データフォーマットは、テーブル(501)の1行目に対応する。
{byte_size_of_array}(N:number_of_nodes)
[id_1][M1:number_of_values_1]
<value_1,1><value_1,2 -value_1,1>...<value_1,M1- value_1,M1-1>
[id_2][M2:number_of_values_2]
<value_2,1><value_2,2 -value_2,1>...<value_2,M2- value_2,M2-1>
......
[id_N][MN:number_of_value_N]
<value_N,1><value_N,2 -value_N,1>...<value_N,MN- value_N,MN-1>
上記データフォーマット内の改行は、見易さのためであり、データに含まれない。また、{}、()、[]及び<>などの区切りは、論理的なデータの区切りを表示するためのものであり、データに含まれない。{}は、非圧縮long(8bytes)を意味する。()は、非圧縮int(4bytes)を意味する。非圧縮とは、2の補数表記による標準的な符号化のことをいう。また、[]は、圧縮intを意味する。<>は、差分圧縮intを意味する。圧縮は、可変長の符号化でありうる。
byte_size_of_arrayは、先頭の[id_1]から最後の<value_N,MN - value_N,MN-1>までのバイト列の長さを示す。Nは、格納されているノードの数を示す。idは、ノードidを示す。アンダーバーの後に続く値は、ノードを識別するために振った表記上の番号である。Mは、値の数を示す。Mの右下付で示された値は、ノードを識別するために振った表記上の番号である。valueは、値である。アンダーバーの後に続く値は、ノードを識別するために振った表記上の番号である。カンマの後に続く値は、値を識別するために振った表記上の番号である。
u2vインデックスとは、全てのセクションに対して上記データフォーマットを作り、連結したものである。本発明の1つの実施態様として、該データフォーマットは、シーケンシャルに連結されている。セクションが例えば2種類しかなければ、該データフォーマットは次の通りである。
{byte_size_of_array}(N1:number_of_nodes)
[id_1][M1:number_of_values_1]
<value_1,1><value_1,2 -value_1,1>...<value_1,M1- value_1,M1-1>
......
[id_N1][MN1:number_of_value_N1]
<value_N1,1><value_N1,2 -value_N1,1>...<value_N1,MN1- value_N1,MN1-1>
{byte_size_of_array}(N2:number_of_nodes)
[id_1][M1:number_of_values_1]
<value_1,1><value_1,2 -value_1,1>...<value_1,M1- value_1,M1-1>
......
[id_N2][MN2:number_of_value_N2]
<value_N2,1><value_N2,2 -value_N2,1>...<value_N2,MN2- value_N2,MN2-1>
【0050】
上記データフォーマットは、インデックス作成効率向上のために、できるだけコンピュータのメモリー上に記憶しておくのが好ましい。しかし、該メモリーの容量にも限界があるため、該コンピュータは、一定量のデータがメモリー内に蓄積されると該データをファイルに書き出す。ファイルに書き出すタイミングは例えば、処理済みのノード数で判断される。例えば、ファイルの書き出しは、100000ノードごとに行われる。データフォーマットからわかるように、複数のファイルに分割された場合でも、該ファイルのマージは容易である。
【0051】
本発明の実施形態では、任意の圧縮方法を使用しうる。例えば、一般にギャップ符号化(Gap coding)という名前で知られている全文検索エンジン ルシーン(Lucene)で用いられる手法と同じものを用いる。ギャップ符号化は、単調に増大する整数列(例:1、4、37、51、80、...)について差分をとる方法である。例えば、あるノードが(1、4、37、51、80)という5個の値を持つとする。最初に、この手法では、値を昇順に並べる。次に、前の値との差分を求める。該差分を(1、3、33、14、29)という数列に変換し、変換後の各値を「小さい数字に対し、より小さなビット数を割り当てるように」符号化する。復号化の際は、直前の値を覚えておき(初期値は0)、各数字を順に復号したあと直前の値に足すことを繰り返せばよい。この方法によって、特に1つのノードに多くの値が含まれるときに高い圧縮率が得られる。
図5Aの表(502)の例では、最小の値であるvalue[1]を3列目に設定する。次に、2番目に小さい値であるvalue[2]と最小の値であるvalue[1]の差分を4列目に設定する。以下、同様の処理を繰り返す。最後に、最大の値であるvalue[M]と2番目に大きい値である[M−1]の差分を最終列に設定する。
【0052】
差分をとったあとの圧縮手法について、例えば下記手法が知られている。
可変長符号化(Variable−length code)法は、ハフマン符号化、ランレングス符号化、算術符号化及び適応ビット割当に分けられる。
ガンマ符号化(Gamma code)法は、整数を2進数で表現し、そのビット数から1を引いた数の「0」と、整数を2進数で表現した値を合わせた値を、出力する手法である。
ゴーロム符号化(Golumb code)法は、次の三つの手順により構成される。
1.はじめに、floor(n/m)を計算し、このunarycodeを出力する。ここで、floor(x)はxを上回らない最大整数、また正数aのunary codeはa個の“0”とそれに続く1個の“1”から構成される符号“00・・・01”、をそれぞれ表す。
2.続いて、n/mの剰余mod(n/m)を計算し、それをfloor(log2(m))桁のバイナリ符号で表したものを出力する。
3.両者をこの順番で結合したものがnのゴーロム符号となる。
【0053】
図5Bの表(503)は、圧縮効果の結果を示す。圧縮の比較に使用したデータは、コールセンターのログ・データ324677件である。比較は、セクションごとに作成したu2vインデックスファイルを用いて行った。表(503)1列目は、任意のセクションを示す。2列目の非圧縮時のインデックスのファイル・サイズ(A)は、圧縮を行わなかった場合のu2vインデックスファイルのファイル・サイズを示す。3列目の圧縮時のインデックスのファイル・サイズ(B)は、可変長符号化(Variable−length code)法で圧縮したu2vインデックスファイルのファイル・サイズを示す。4列目の圧縮率は、圧縮を行った場合と行わなかった場合のファイル・サイズの圧縮率(%)を示す。
表(503)に見られるように、圧縮率はセクションの種類によって異なる。圧縮を行った場合、u2vインデックスファイルのファイル・サイズは、圧縮を行わなかった場合から35%〜52%のサイズを減らしたサイズになる。
【0054】
図5Cの表(504)は、本発明の実施態様である、各木構造(400A、400B)のデータからu2vインデックスを作成した際のEntryの例を示す。但し、1列目、「セクション」の列は、説明のために追加した列である。表(504)の値に示されている値は、キーワードを示している。本発明の1つの実施態様では、該値は数値に変換される。本発明のさらなる実施態様では、該数値は圧縮される。
【0055】
木構造(400A、400B)のデータから、セクションがNounであるノード(410、412、420、421)及びセクションがVerbであるノード(411、422)について、u2vインデックスを作成する例を、以下に示す。
最初に、セクションがNounであるノード(410、412、420及び421)について示す。
ノード(410)のノードidは、2である。従って、表(504)のセクションがNounの行のEntry[1]のノードidの列には、2が設定される。ノード(410)の持つ値は、Internet、PC、phoneの3つである。従って、セクションがNounの行のEntry[1]の値の数の列には、3が設定される。セクションがNounの行のEntry[1]の値の列には、Internet、PC、phoneが設定される。
ノード(412)のノードidは、5である。従って、表(504)のセクションがNounの行のEntry[2]のノードidの列には、5が設定される。ノード(412)の持つ値は、Internet、modemの2つである。従って、セクションがNounの行のEntry[2]の値の数の列には、2が設定される。セクションがNounの行のEntry[2]の値の列には、Internet、modemが設定される。
ノード(420)のノードidは、9である。従って、表(504)のセクションがNounの行のEntry[3]のノードidの列には、9が設定される。ノード(420)の持つ値は、Internet、phoneの2つである。よって、セクションがNounの行のEntry[3]の値の数の列には、2が設定される。セクションがNounの行のEntry[3]の値の列には、Internet、phoneが設定される。
ノード(421)のノードidは、11である。従って、表(504)のセクションがNounの行のEntry[4]のノードidの列には、11が設定される。ノード(421)の持つ値は、Internet、modemの2つである。従って、セクションがNounの行のEntry[4]の値の数の列には、2が設定される。セクションがNounの行のEntry[4]の値の列には、Internet、modemが設定される。
次に、セクションがVerbであるノード(411、422)について示す。
ノード(411)のノードidは、3である。従って、表(504)のセクションがVerbの行のEntry[1]のノードidの列には、3が設定される。ノード(411)の持つ値は、connect、typeの2つである。従って、セクションがVerbの行のEntry[1]の値の数の列には、2が設定される。セクションがVerbの行のEntry[1]の値の列には、connect、typeが設定される。
ノード(422)のノードidは、13である。従って、表(504)のセクションがVerbの行のEntry[2]のノードidの列には、13が設定される。ノード(422)の持つ値は、connect、readの2つである。従って、Verbの行のEntry[2]の値の数の列には、2が設定される。Verbの行のEntry[2]の値の列には、connect、readが設定される。
【0056】
u2vインデックスは、ファイルに保管される。該ファイルは、1つのファイルである必要はなく、複数のファイルでよい。実装では、各セクションに対するu2vインデックスのオフセットを記録したファイル(図示せず)にセクション・ポインター・ツリー(500)も書き出す。該ファイルには、対応する開始位置、すなわち何バイト目から始まるかの位置を保管する。この保管形式は任意でよい。例えば、B−treeが用いられる。
【0057】
第2のインデックス(以下、relationインデックス)とは、ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを保管したものをいう。relationインデックスにおいて、該組のデータは、セクション毎に作成される。本発明の1つの実施態様では、relationインデックスは、上記組のデータをシーケンシャルに格納している。
図6Aは、本発明の実施態様である、relationインデックスの概念スキーマ及び保管の例を示す。relationインデックスの概念スキーマは、セクション・ポインター・ツリー(600)及び表(601、602)で示される。セクション・ポインター・ツリー(600)は、表(601)の各行へのポインタの集合データを示す。表(601)の各行は、1セクション分のインデックスを示す。1列目は、行のサイズである。2列目は、セクションに対応するノードの数である。3列目以降は、セクションに対応するノードの数分のEntryである。表(602)は、Entryの詳細を示す。1列目は、ノードidを示す。2列目は、子孫ノードのノードidのうち、最小のidを示す。
【0058】
1セクション分のrelationインデックスのデータフォーマットは、次の通りである。該データフォーマットは、テーブル(601)の1行目に対応する。
{byte_size_of_array}(N:number_of_nodes)
[id_1][min_id_1][id_2][min_id_2]......[id_N][min_id_N]
上記データフォーマット内の改行は、見易さのためであり、データに含まれない。また、{}、()、[]などの区切りは、論理的なデータの区切りを表示するためのものであり、データに含まれない。{}は非圧縮long(8bytes)を意味する。()は、非圧縮int(4bytes)を意味する。非圧縮とは、2の補数表記による標準的な符号化のことを示す。また、[]は圧縮intを意味する。圧縮は、可変長の符号化でありうる。
byte_size_of_arrayは、先頭の[id_1]から最後の[min_id_N]までのバイト列の長さを示す。Nは、格納されているノードの数を示す。idは、ノードidを示す。アンダーバーの後に続く値は、ノードを識別するために振った表記上の番号である。min_idは、同じ表記上の番号が振られたノードidの子孫ノードのうち、最小のノードidを持つノードのノードidを示す。
【0059】
図6Bの表(603)は、本発明の実施態様である、各木構造(400A、400B)のデータからrelationインデックスを作成した際のEntryの例を示す。但し、1列目、「セクション」の列は、説明のために追加した列である。
【0060】
上記データフォーマットは、インデックス作成効率向上のために、できるだけコンピュータのメモリー上に記憶しておくのが好ましい。しかし、該メモリーの容量にも限界があるため、該コンピュータは、一定量のデータがメモリー内に蓄積されると該データをファイルに書き出す。ファイルに書き出すタイミングは例えば、処理済みのノード数で判断される。例えば、ファイルの書き出しは、100000ノードごとに行われる。データフォーマットからわかるように、複数のファイルに分割された場合でも、該ファイルのマージは容易である。
【0061】
木構造(400A、400B)のデータからrelationインデックスを作成する例を、以下に示す。
セクションがDocumentであるノード(416、427)について考える。対応するインデックスは、表(603)の2行目、セクションが“Document”の行である。ノード(416)のノードidは、7である。従って、表(603)の2列目、「ノードid」に7を設定する。ノード(416)の子孫ノード(410〜415)のうち、最小のノードidを持つノードは、ノード(413)である。ノード(413)のノードidは、1である。従って、表(603)の3列目、「最小のノードid」に1を設定する。ノード(427)のノードidは、15である。従って、表(603)の4列目、「ノードid」に15を設定する。ノード(427)の子孫ノード(420〜426)のうち、最小のノードidを持つノードは、ノード(423)である。ノード(423)のノードidは、1である。従って、表(603)の5列目、「最小のノードid」に8を設定する。
セクションがQuestionであるノード(414、424、425)について考える。対応するインデックスは、表(603)の3行目、セクションが“Question”の行である。ノード(414)のノードidは、4である。従って、表(603)の2列目、「ノードid」に4を設定する。ノード(414)の子孫ノード(410〜411)のうち、最小のノードidを持つノードは、ノード(410)である。ノード(410)のノードidは、2である。従って、表(603)の3列目、「最小のノードid」に2を設定する。ノード(424)のノードidは、10である。従って、表(603)の4列目、「ノードid」に10を設定する。ノード(424)の子孫ノード(420)のうち、最小のノードidを持つノードは、ノード(420)である。ノード(420)のノードidは、9である。従って、表(603)の5列目、「最小のノードid」に9を設定する。ノード(425)のノードidは、12である。従って、表(603)の6列目、「ノードid」に12を設定する。ノード(425)の子孫ノード(421)のうち、最小のノードidを持つノードは、ノード(421)である。ノード(421)のノードidは、11である。従って、表(603)の7列目、「最小のノードid」に11を設定する。
セクションがAnswerであるノード(415、426)について考える。対応するインデックスは、表(603)の4行目、セクションが“Answer”の行である。ノード(415)のノードidは、6である。従って、表(603)の2列目、「ノードid」に6を設定する。ノード(415)の子孫ノード(412)のうち、最小のノードidを持つノードは、ノード(412)である。ノード(412)のノードidは、5である。従って、表(603)の3列目、「最小のノードid」に5を設定する。ノード(426)のノードidは、14である。従って、表(603)の4列目、「ノードid」に14を設定する。ノード(426)の子孫ノード(422)のうち、最小のノードidを持つノードは、ノード(422)である。ノード(422)のノードidは、13である。従って、表(603)の5列目、「最小のノードid」に13を設定する。
セクションがDate、Noun及びVerbであるノード(413、410、411、412、423、420、421及び422)は、子孫ノードを持たない。このような子ノードを持たないノードであるリーフノードに対しては、relationインデックスは作成されない。
【0062】
relationインデックスは、ファイルに保管される。該ファイルは、1つのファイルである必要はなく、複数のファイルでよい。実装では、各セクションに対するrelationインデックスのオフセットを記録したファイル(図示せず)にセクション・ポインター・ツリー(600)も書き出す。該ファイルには、対応する開始位置、すなわち何バイト目から始まるかの位置を保管する。この保管形式は任意でよい。例えば、B−treeが用いられる。
【0063】
第3のインデックス(以下v2uインデックス)とは、特定の値を含む1以上のノードのノードidを含む1以上の組のデータを保管したものをいう。v2uインデックスにおいて、該組のデータは、ラベル毎に且つ特定の値毎に作成される。本発明の1つの実施態様では、v2uインデックスは、上記組のデータをシーケンシャルに格納している。v2uインデックスは、各ノードの値から、該値を含むセクションのノードidの一覧を検索できるデータフォーマットをとる。
図7Aは、本発明の実施態様である、v2uインデックスの概念スキーマ及び保管の例を示す。v2uインデックスの概念スキーマは、セクション・ポインター・ツリー(700)、セクションに対応する数のハッシュ構造(701)及びハッシュ構造に対応する表(702)で示される。セクション・ポインター・ツリー(700)は、セクションごとに用意されたハッシュ構造(701)へのポインタの集合データを示す。ハッシュ構造(701)は、表(702)に示す各行へのポインタの集合データを示す。表(702)の各行は、特定の値毎のインデックスを示す。1列目は、行のサイズである。2列目は、特定の値を有するノードの数である。3列目以降は、特定の値を有するノードのノードidである。本発明の1つの実施態様では、表(702)の3列目以降に含まれるノードidは、u2vインデックスの例と同様に圧縮される。
【0064】
図7Bの表(703)は、本発明の実施態様である、各木構造(400A、400B)のデータからセクションがNounであるノード(410、412、420、421)について、v2uインデックスを作成した際のデータの例を示す。但し、1列目、「値」の列は、説明のために追加した列であり、v2uインデックスに含まれない。また、本発明の1つの実施態様として、ノードidは、圧縮されている。
【0065】
1セクション分の1つの値に対するv2uインデックスのデータフォーマットは、次の通りである。データフォーマットは、表(702)の1行目と対応する。
{byte_size_of_array}(N:number_of_nodes)
<id,1><id,2 - id,1>...<id,N1- id,N1-1>
上記データフォーマット内の改行は、見易さのためであり、データに含まれない。また、{}、()、<>などの区切りは、論理的なデータの区切りを表示するためのものであり、データに含まれない。{}は、非圧縮long(8bytes)を意味する。()は、非圧縮int(4bytes)を意味する。非圧縮とは、2の補数表記による標準的な符号化のことをいう。<>は、差分圧縮intを意味する。圧縮は、可変長の符号化でありうる。
byte_size_of_arrayは、先頭の<id,1>から最後の<id,N1 - id,N1-1>までのバイト列の長さを示す。Nは、格納されているノードの数を示す。idはノードidを示す。カンマの後に続く値は、ノードを識別するために振った表記上の番号である。
【0066】
上記データフォーマットは、インデックス作成効率向上のために、できるだけコンピュータのメモリー上に記憶しておくのが好ましい。しかし、該メモリーの容量にも限界があるため、該コンピュータは、一定量のデータがメモリー内に蓄積されると該データをファイルに書き出す。ファイルに書き出すタイミングは例えば、処理済みのノード数で判断される。例えば、ファイルの書き出しは、100000ノードごとに行われる。データフォーマットからわかるように、複数のファイルに分割された場合でも、該ファイルのマージは容易である。
【0067】
木構造(400A、400B)のデータから、セクションがNounであるノード(410、412、420、421)について、v2uインデックスを作成する例を、以下に示す。
セクションがNounであるノード(410、412、420及び421)のうち、値にinternetを持つノードは、ノード(410、412、420及び421)である。従って、表(702)の1行目には、ノード(410、412、420、421)のノードidである、2、5、9、11が設定される。
セクションがNounであるノード(410、412、420及び421)のうち、値にPCを持つノードは、ノード(410)である。従って、表(702)の2行目には、ノード(410)のノードidである、2が設定される。
セクションがNounであるノード(410、412、420及び421)のうち、値にmodemを持つノードは、ノード(412、421)である。従って、表(702)の3行目には、ノード(412、421)のノードidである、5、11が設定される。
セクションがNounであるノード(410、412、420及び421)のうち、値にphoneを持つノードは、ノード(410、420)である。従って、表(802)の4行目には、ノード(410、420)のノードidである、2、9が設定される。
【0068】
v2uインデックスは、ファイルに保管される。該ファイルは、1つのファイルである必要はなく、複数のファイルでよい。実装では、各セクションに対するv2uインデックスのオフセットを記録したファイル(図示せず)にセクション・ポインター・ツリー(700)も書き出す。該ファイルには、対応する開始位置、すなわち何バイト目から始まるかの位置を保管する。この保管形式は、任意でありうる。例えば、B−treeが用いられる。さらに、value(値)が与えられたとき、表(702)の各行にランダムアクセスするためのポインタをハッシュ(701)で保持する。このハッシュの仕組みは,value(値)に対して定数時間でポインタの値を引くことができれば任意で良い。また、ハッシュもセクションごとに作成するため、セクションからハッシュ構造へのポインタも保持する。
【0069】
図8A〜図8Fは、インデックスの作成のフローチャート及びそれに付随する図を示す。
フローチャートで使用する用語を以下に説明する。木構造をTで表す。また、|T|と記載した場合、|T|は、Tの持つノードの個数を表す。木構造(400A)の例では、|T|=7である。ノードをNで表す。ノードNの持つセクションを、N.sectionで表す。ノードNの持つ値を、N.Valuesで表す。ノードNに割り振られたノードidをN.unitIdで表す。また、セクションは、あらかじめ数値に変換されているものとする。例えば、“Document”=1であり、“Question”=2であり、“Noun”=3などである。
ノード(410)の例では、N.sectionは、“Noun”=3であり、N.valuesは、“Internet”、“PC”及び“phone”であり、N.unitIdは2である。
【0070】
図8Aは、本発明の実施態様である、インデックスを作成または更新する処理の全体のフローチャートを示す。
ステップ800では、コンピュータが、変数currentUnitIdを0で初期化する。currentUnitIdは、コンピュータが処理対象の木構造にノードidを割り振る際の初期値を保管する変数である。0での初期化は、最初に振られるノードidが0であることを示す。本発明の1つの実施態様として、値が文字列である場合、該文字列を数値に置き換えることが可能である。
ステップ801では、コンピュータが、処理対象の木構造がまだ存在するかの判定を行う。処理対象の木構造がある場合、ステップ802に進む。全ての木構造について処理済みであれば、ステップ807に進む。
ステップ802では、コンピュータが、後続のステップ(803〜806)で用いる木構造を選択する処理である。後続のステップ(803〜806)は木構造の単位で処理を行う。
ステップ803では、ステップ802で選択した木構造について、コンピュータが、後行順でノードidを割り振る。ノードidの開始値には、currentUnitIdを用いる。
ステップ804では、コンピュータが、Relationインデックスを作成または更新する。Relationインデックス及び該処理については、後述する。
ステップ805では、コンピュータが、u2vインデックスを作成または更新する。u2vインデックス及び該処理については、後述する。ステップ804とステップ805は、どちらのステップを先に実行してもかまわない。
ステップ806では、コンピュータが、変数currentUnitIdに|T|を加える処理を行う。該処理で求めた値は、次に処理対象とする木にノードidを割り振る際の初期値になる。
ステップ807では、コンピュータが、v2uインデックスを作成または更新する。本発明の1つの実施態様として、v2uインデックスを作成または更新後に、上記文字列が数値に置き換えられた値について、該数値を文字列に再び置き換えることが可能である。
【0071】
図8Bは、本発明の実施態様である、relationインデックスを作成または更新する処理のフローチャートを示す。また、図8Bは、図8Aのステップ(804)の詳細を示す。該フローチャートは、1つの木構造Tについてのものである。
ステップ810では、コンピュータが、木のノードを、unitIdの小さい順に並べる。
ステップ811では、コンピュータが、処理対象のノードがまだ残っているかの判定を行う。処理対象のノードがある場合は、ステップ812に進む。全てのノードについて処理済みであれば、処理を終了し、図8Aのステップ805へ進む。
ステップ812では、コンピュータが、木構造TからノードNを取り出す。
ステップ813では、コンピュータが、ステップ812で取り出したノードNの子孫ノードのうち、ノードidが最少のノードを選択する。ここで、ノードidが最少のノードをN´とする。
ステップ814では、コンピュータが、ステップ812で取り出したノードNが持つノードid、及びステップ813で選択したノードN´が持つノードidをrelationインデックスに追加する。追加先は、ノードNに設定されたセクションに対応する個所である。上記追加先は、セクション・ポインター・ツリーから求めることができる。コンピュータは、セクション・ポインター・ツリーから該セクションを指すポインタを取得し、relationインデックスにおいて、そのポインタの指す先の最後尾にノードNが持つノードid及びノードN´が持つノードidを追加すればよい、新規のセクションの場合は、セクション・ポインター・ツリーに、該セクションを指すポインタを追加する。コンピュータは、relationインデックスの設定項目であるノードの数及び行のサイズを更新する。
【0072】
図8Cは、本発明の実施態様である、u2vインデックスを作成または更新する処理のフローチャートを示す。また、図8Cは、図8Aのステップ805の詳細を示す。該フローチャートは、1つの木構造Tについてのものである。
ステップ820では、コンピュータが、木のノードを、unitIdの小さい順に並べる。
ステップ821では、コンピュータが、処理対象のノードがまだ残っているかの判定を行う。処理対象のノードがある場合は、ステップ822に進む。全てのノードについて処理済みであれば、処理を終了し、図8Aのステップ806へ進む。
ステップ822では、コンピュータが、木構造TからノードNを取り出す。
ステップ823では、コンピュータが、ステップ822で取り出したノードNが持つノードid、値及び値の数をu2vインデックスに追加する。追加先は、ノードNに設定されたセクションに対応する個所である。上記追加先は、セクション・ポインター・ツリーから求めることができる。コンピュータは、セクション・ポインター・ツリーから該セクションを指すポインタを取得し、u2vインデックスにおいて、そのポインタの指す先の最後尾にノードNが持つノードid、値及び値の数を追加すればよい、新規のセクションの場合は、セクション・ポインター・ツリーに、該セクションを指すポインタを追加する。差分圧縮を行う場合は、該ステップで行う。コンピュータは、u2vインデックスの設定項目であるノードの数及び行のサイズを更新する。
【0073】
図8Dは、本発明の実施態様である、v2uインデックスを作成または更新する処理のフローチャートを示す。
ステップ830では、コンピュータが、処理対象のセクションがまだ残っているかの判定を行う。処理対象のセクションがある場合は、ステップ831に進む。全てのセクションについて処理済みであれば、処理を終了する。
ステップ831では、コンピュータが、転置行列Iを作成する。コンピュータは、Section Sを1つ選び、u2vインデックスからセクションSに対応する部分を読み込む。そして、コンピュータは、該読み込んだデータから転置行列Iを作成する。転置行列については後述する。
ステップ832では、コンピュータが、転置行列を書き出す。転置行列とは、u2vインデックス内のデータを、各値に対してその値を含むノードのノードidを保持する形式に変換したものである。転置行列は、検索エンジンのインデックスとして一般的な行列である。上記書き出す処理については後述する。該書き出す処理が終了したら、コンピュータは、再びステップ830に処理を戻す。
コンピュータは、ステップ(830〜832)の処理を、処理するセクションがなくなるまで繰り返す。
【0074】
図8Eは、本発明の実施態様である、転置行列の例を示す。
表(840)は、あるセクションにおけるu2vインデックス内のデータの例を示す。該データの例は、転置行列に変換する前のデータの例に相当する。表(841)は、表(840)のデータを、転置行列に変換した例を示す。本願発明の1つの実施態様では、表に含まれる値は、数字で表現されうる。
表(840)において、値“Internet”は、ノードidが2、5、9、11の行に含まれる。値“PC”は、ノードidが2の行に含まれる。値“phone”は、ノードidが2、9の行に含まれる。値“modem”は、ノードidが5、11の行に含まれる。値“keyboard”は、ノードidが11の行に含まれる。この関係を表したものが、表(841)で示す転置行列になる。
【0075】
図8Fは、本発明の実施態様である、転置行列の書き出しの処理を示すフローチャートである。該フローチャートは、セクションごとに実施される。
ステップ850では、コンピュータが、v2uの値ハッシュの初期化を行う。値ハッシュとは、図7Aのハッシュ構造(701)を示す。コンピュータは、空の値ハッシュを新規作成する。コンピュータは、値ハッシュにポインタを設定するための変数であるpointerに、0をセットする。
ステップ851では、コンピュータが、処理対象の値がまだ残っているかの判定を行う。コンピュータは、処理対象の値がある場合は、ステップ852に進む。コンピュータは、全ての値について処理済みであれば、図8Dのステップ830に進む。
ステップ852では、コンピュータが、圧縮リストCL(v)を作成する。圧縮リストCL(v)は、図7Aの表(702)における各行に対応するデータを指す。コンピュータは、値vを1つ選ぶ。コンピュータは、ステップ(831)で作成した転置行列Iから、該値vに対応するノードidを読み出す。コンピュータは、該読み出したノードid、ノードidの数及び、該ノードidと該ノードidの数のサイズを用いて、圧縮リストCL(v)作成する。本発明の1つの実施態様では、該ノードidは差分圧縮される。
ステップ853では、コンピュータが、値ハッシュ及びv2uインデックスにデータを設定する。コンピュータは、値vとpointerの組を、値ハッシュに追加する。
また、コンピュータは、CL(v)をv2uインデックスに追加する。コンピュータは、v2uインデックスが存在しない場合は、v2uインデックスを作成する。
ステップ854では、コンピュータが、pointerにCL(v)のサイズを加える。該ステップの処理が終了したら、コンピュータは、再びステップ851に処理を戻す。
コンピュータは、ステップ(851〜854)の処理を、処理する値がなくなるまで繰り返す。
【0076】
図9A〜図9Cは、本発明の実施態様である、インデックスを用いた集約処理のフローチャートを示す。
該フローチャートにおける入力パラメータの定義は、以下の通りである。
検索条件値をvとする。vは例えば、検索エンジンを使うときに用いるキーワードに該当する。例えば、値 “phone”(電話)が該当する。また、単一の値の代わりに、値の任意の論理式を用いることもできる。vの例は、「phone and Internet」である。
検索条件セクションをSsとする。Ssは、vを含むセクションの指定であり、vとのペアで意味を持つ。Ssの例は、「Answerセクションの中に値“phone”が存在するような木に関して集約する。」という場合におけるAnswerセクションである。
ルートセクションをSrとする。Srは、集約対象の木構造のルート・ノードのセクションの指定である。Srの例は、Documentである。
集約対象セクションをSaとする。Saは、集約する値を含むセクションの指定である。Saの例は、「Nounセクションの値を集約する。」場合におけるNounセクションである。
集約単位セクションをScとする。Scは、集約関数を適用する単位の指定であり、Saとのペアで意味を持つ。Scの例は、「Questionセクションの単位で、Nounセクションの値を集約する。」場合における、Questionセクションである。
集約処理の出力は、vと、集約関数fのv上での値f(v)との組(v, f(v))のリストで表される。以下、f(v)=(vのSc単位の出現回数)とする。fとして任意の集約関数を用いることもできる。
【0077】
図9Aは、本発明の実施態様である、集約処理の主処理を示すフローチャートである。該主処理には、入力パラメータとして、v、Ss、Sr、Sa、Scが与えられる。該主処理は、検索条件処理(900)及び値集約処理(901)を実行する。
【0078】
図9Bは、本発明の実施態様である、検索条件処理(900)のフローチャートを示す。該検索条件処理(900)では、v2uインデックス及びrelationインデックスを使用して、値、すなわちキーワードが求められうる。
ステップ910では、コンピュータが、セクションSsを用いてv2uインデックスの検索を行い、圧縮リスト(以下CL(v))を取得する。1つの実施態様として、該検索はシーケンシャルに行われる。
ステップ911では、コンピュータが、ステップ910で取得したCL(v)を解凍し、ノードidのリスト(以下L(v))を取得する。該ノードidのリストが、第1のリストに対応する。
ステップ912では、コンピュータが、relationインデックスを検索して、セクションSrの行(以下R(Sr))を取得する。1つの実施態様として、該検索は、シーケンシャルに行われうる。
ステップ913では、コンピュータが、L(v)とR(Sr)のマッチングを行い、R(Sr)の部分集合(以下R’(Sr))を取得する。該R’(Sr)が、第2のリストに対応する。
【0079】
図9Cは、本発明の実施態様である、マッチング処理のフローチャートを示す。
図9Cは、例としてL(v)とR(Sr)とのマッチング処理を示す。L(v)の行に含まれる各数値は、vを持つノードのノードidを示す。例えば、リスト(920)において、ノードidの各数値は、3,7,16,20及び38である。また、R(Sr)の行に含まれる各数値は、セクションSrを持つノードのノードidと、そのノードidを持つノードの子孫ノードのうち最小のノードidを持つノードのノードidの組を示す。例えば、リスト(920)において、(5,1)、(15,10)及び(45,27)の各組が、ノードidの組である。なお、(5,1)という表記は、5がセクションSrのノードidであり、1が、ノードidが5であるノードの子孫ノードの持つノードidのうちの最小のノードidであることを意味する。
他のデータについてのマッチング処理についても上記と同様である。
【0080】
図9Cのマッチング処理の手順は、以下の通りである。
コンピュータは、カーソル(924)を各リスト(L(v)、R(Sr))の先頭にセットする(921)。
コンピュータは、L(v)のカーソルが指すノードidが、R(Sr)の指す値のペアの範囲に入っているかどうかチェックし、入っていたらそのペアを、メモリー上に保管する。マッチング対象のリスト(921)の例では、3は範囲(5,1)に入っているため、コンピュータは、(5,1)をメモリー上に保管する(921)。
次に、コンピュータは、L(v)のカーソルを、ノードidの値が現在のR(Sr)のペアの範囲を越えるまで(すなわち、7)移動する(922)。
次に、コンピュータは、R(Sr)のカーソルを移動する。
上記を繰り返すことによって、条件を満たすペアがすべて求まる。そのペア全体R’(Sr)とする。図9Cの例では、R’(Sr)={(5,1),(45,27)}である。
【0081】
図9Dは、本発明の実施態様である、値の集約処理のフローチャートを示す。
ステップ930では、コンピュータは、relationインデックスを検索し、セクションScの行(以下R(Sc))を取得する。該検索はシーケンシャルに行う。
ステップ931では、コンピュータは、R’(Sr)とR(Sc)をマッチングして、R(Sr)の部分集合(以下R’(Sc))を求める。
ステップ932では、コンピュータは、u2vインデックスを検索し、セクションSaの行(以下R(Sa))を取得する。該検索はシーケンシャルアクセスに限らず、下記のランダムアクセスを使用することもできる。該取得したR(Sa)とR’(Sc)とをマッチングする。該マッチングによって、集約計算を行うための検索式の検索条件を満たすvのリストを取得する。該vのリストが第3のリストに対応する。該vのリストを使用して、値の集計を行う。
ステップ932において、コンピュータが、u2vインデックスを検索する場合、シーケンシャルアクセスの他に、ランダムアクセスを使用しうる。はじめの検索条件値vがきつく(厳しい)且つ集計対象のノード数が少ない場合は、シーケンシャルアクセスよりもランダムアクセスのほうが高速な場合がある。
【0082】
図9Eは、本発明の実施態様である、シーケンシャルアクセスとランダムアクセスにおけるヒット率と実行時間との関係を示す。グラフ(940)の横軸は、ヒット率を示す。SrとSaとの関係がわかっている場合は、検索条件さえ分かれば、シーケンシャルアクセスとランダムアクセスのいずれが有利であるかを、例えば下記の切り替えアルゴリズムを使用して推定することが可能である。
以下に、SrとSaが1:1の場合、記号を以下のように定める
Tk :ランダムアクセスによるu2vインデックスでのシーク時間
Tq :シーケンシャルアクセスによるユニット当たりのリード時間
N :Saのu2vインデックスにおけるユニットの数
Nv : Saのu2vインデックスにおける、検索式を満たすユニットの数
TS及びTRそれぞれをシーケンシャルアクセス及びランダムアクセスの実行時間とすると、以下のように見積もられる。
TS = Tk + N* Tq
TR = Nv * (Tk + Tq)
TS = TR を解くと,切り替えの閾値を与える Nv の値が求まる
Nv 〜 N/ (1 + (Tk/Tq))
【0083】
図9Fは、本発明の実施態様である、ランダムアクセス用インデックスの概念スキーマを示す。
ランダムアクセスを行う場合は、ランダムアクセス用インデックスを使用する。ランダムアクセス用インデックスとは、セクション毎に、各ノードidとu2vインデックス内のアクセスしたいEntryの位置をシーケンシャルに保管したものをいう。
ランダムインデックスの概念スキーマが、表(951)で示される。また、表(950)は、前述したu2vインデックスの概念スキーマの表(501)と同一のものである。
表(951)は、ある1つのセクションについての例である。表(951)の各行は、ある1つのセクションに含まれる1つのノードを示す。1列目は、ユニットid(ノードidと同じ)を示す。2列目は、u2vインデックス(950)内において、該ノードの情報を持つEntryの位置を指すPointerを示す。該Pointerは、該当するセクションの先頭からのバイト数で表わされる。1列目、2列目ともに固定長である。例えば、1列目を4バイト、2列目を8バイトとすることができる。
【0084】
図9Gは、本発明の実施態様である、ランダムアクセスを行う場合の、値の集約処理(901)のフローチャートを示す。
ステップ960は、ステップ930と同じ処理である。ステップ961は、ステップ931と同じ処理である。ステップ962は、ステップ932に対応する。ステップ962とステップ932との違いは、コンピュータが、u2vインデックスを検索する際に、シーケンシャルアクセスではなく、ランダムアクセスインデックスを使用してランダムアクセスをする点のみである。ランダムアクセスインデックスを使用してu2vインデックスを検索する方法は、ランダムアクセスをサポートするインデックスであれば任意のものが使える。例えば、ランダムアクセスインデックス内をノードidに関して二分探索し、Pointerを求める方法、ランダムアクセスインデックス内のノードidをB−treeに当てはめて、Pointerを求める方法がある。コンピュータは、u2vインデックスの各ノードidを読み込む際に、ランダムアクセスを行うことにより、集約の結果に含まれないノードidの読み込みをなくすことができる。
【0085】
テキストマイニングでは、文書データに対して大量の処理結果(名詞及び動詞などの抽出されたキーワード)を伴う。該処理結果をデータベースに格納する場合、レコード数が元文書数に対して大幅に増大することが知られている。
以下では、本発明の実施態様のプロトタイプと、関係データベースとして広く使われているPostgreSQLとの性能を比較した結果を示す。性能比較は、2種類のデータを用いて行った。該データは、PCコールセンターのログ・データ及び、生命科学のデータである。ここで、PCコールセンターのログ・データを用いて行った比較を実験1、生命科学のデータを用いて行った比較を実験2とする。
【実施例1】
【0086】
実験1で用いたデータの件数は、324677件である。図10Aの木構造(1000)は、本実験1で使用したデータの構造を示す。セクション、ノードid及び値の3つ組の異なり数は、25150042である。
PostgreSQLのテーブルスキーマは、現在広く用いられる細分化手法で作成する。また、該テーブルスキーマは、高速化のために必要最小限のデータを扱うのに適した構造にする。具体的には、PostgreSQLのテーブルは、セクションごとに作成した。該テーブルは、2つのINT列を持つ。セクションがDocument、Question及びAnswerのノードに対応するテーブル列には、親ノードのノードidとノードidを設定した。セクションが、Document、Question及びAnswer以外のノードに対応するテーブル列には、親ノードのノードidと値を設定した。値が複数個ある場合は、値分のレコードを用意した。また、全てのテーブルに対して、1列目から2列目、及び2列目から1列目の両方向にB−treeインデックスを張った。
実験1で使用したコンピュータは、Pentium(商標)4 3GHzのCPUを2台、及び3ギガバイトのメモリーを含む。また、該コンピュータのOSは、Linux RHEL3.0である。
図10Bは、実験1で使用した9種類のクエリを示す。表(1001)の「・・・のどこかに・・・」という表現は、「あるセクションを持つノードの子孫ノードのどこかに」という意味である。また、集計対象のスコアは、すべてcountである。なお、表(1001)で、vとして用いた値には、頻度がそれぞれ45437、16293、1340と違うものを使用した。ここで頻度とは、セクションがdocumentのノードを単位とした頻度である。頻度にばらつきを持たせたのは、検索条件を変化させたときにパフォーマンスがどのように変わるかを見るのが目的である。
また、表(1001)の各クエリと対応するSQLを以下に示す。該SQLは、該クエリをPostgreSQL用に変換したものである。

Q1:
select x.value, count(distinct z.value) as freq from L12 as x, B8 as z where x.pid = z.value group by x.value order by freq desc
Q2-1、Q2-2、Q2-3、Q2-4:
select x.value, count(distinct z.value) as freq from L12 as x, L12 as y, B8 as z where x.pid=z.value and y.pid=z.value and y.value=V group by x.value order by freq desc
ここで、y.value=VのVには、検索キーワードに対応するキーワードIDが入る。
Q3-1、Q3-2、Q3-3、Q3-4:
select x.value, count(distinct w.value) as freq from L12 as x, L12 as y, M9 as v, M19 as w, B8 as z where x.pid=w.value and w.pid=z.value and z.value=v.pid and v.value=y.pid and y.value=V group by x.value order by freq desc

ここで、y.value=VのVには、検索キーワードに対応するキーワードIDが入る。
また、B8、M9、M19及びL12は、それぞれ“Document”、“Question”、“Answer”及び“Noun”のセクションに対応するテーブルを表す。
【0087】
図10Cは、実験1の結果を示す。グラフ(1002)の横軸は、テストケースを示す。該テストケースは、表(1001)のクエリと対応する。グラフ(1002)の縦軸は、クエリの実行時間(秒、対数目盛)を示す。また、グラフ(1002)の“PostgreSQL”は、PostgreSQLを用いた場合の集約の処理時間を示す。“SAWAN-R”は、本発明の実施形態の一つであるランダムアクセスを用いた場合の集約の処理時間を示す。“SAWAN-S”は、本発明の実施形態の一つであるシーケンシャルアクセスを用いた場合の集約の処理時間を示す。本発明の実施形態の1つであるシーケンシャルアクセスを用いた集約では、全てのテストケースにおいて、1秒前後(0.4秒〜1.1秒)の処理時間である。また、本発明の実施形態の1つであるランダムアクセスを用いた集約では、処理にかかる時間は、0.4秒〜30.1秒である。一方、PostgreSQLを用いた集約では、一番処理時間が少ないテストケースである、クエリQ3−3の例でも約3.2秒である。また、一番処理時間が多いテストケースであるクエリQ1の例では、約38.4秒である。
実験1の結果より、シーケンシャルアクセスを用いた集約の性能は、検索の種類に依存しないことが分かる。また、PostgreSQLを用いた集約は、特定の検索を行う場合にのみ優れていることがわかる。これは、B+−Treeを実装するランダムアクセスによるものである。
【実施例2】
【0088】
実験2で使用したデータの件数は、生命科学のデータ700071件である。これは、実験1で使用したデータの約2倍の数のデータである。図10Dの木構造(1003)は、該データの構造を示す。セクション、ノードid及び、値の3つ組の異なり数は、163994676である。これは、実験1で使用したデータの異なり数の約6.5倍以上の数である。データ件数の比約2.2(=700071÷324677)に比べて大きいのは、生命科学のデータの方が1文書中あたりのテキスト量が多く、従って1文書あたりキーワードの個数も多いためである。
実験2で使用した、PostgreSQLのテーブルスキーマ、クエリ及び該クエリに対応するSQLは、実験1の“Question”が“Title”に及び実験1の“Answer”が“AbstractText”に変わる以外は、実験1で使用したそれらと同じである。ただし、キーワードの値は、生命科学のデータから実験に適した任意のものを使用した。実験2で使用したコンピュータの構成は、実験1で使用したものと同じである。
【0089】
図10Eは、実験2で使用した9種類のクエリを示す。図10Fは、実験2の結果を示す。グラフ(1005)の横軸は、テストケースを示す。該テストケースは、表(1004)のクエリ番号と対応する。グラフ(1005)の縦軸は、クエリの実行時間(秒、対数目盛)を示す。グラフ(1005)の“PostgreSQL”は、PostgreSQLを用いた場合の集約の処理時間を示す。“SAWAN-R”は、本発明の実施形態の一つであるランダムアクセスを用いた場合の集約の処理時間を示す。“SAWAN-S”は、本発明の実施形態の一つであるシーケンシャルアクセスを用いた場合の集約の処理時間を示す。本発明の実施形態の1つであるシーケンシャルアクセスを用いた集約では、処理にかかる時間は、1.7秒〜13.2秒である。また、本発明の実施形態の1つであるランダムアクセスを用いた集約では、処理にかかる時間は、0.6秒〜79.9秒である。一方、PostgreSQLを用いた集約では、処理にかかる時間は、22.3秒〜1141.1秒である。Q1のクエリのように、検索にキーワードを使用しなかった場合、PostgreSQLを用いて集約を求める処理は、千秒以上かかる。
【0090】
以下に、実験1、2より得られた、本発明の実施形態による集約処理の2つの特徴を示す。本発明の実施形態による集約処理は、検索条件を指定しないときでも数秒で処理を終えることができる。また、ランダムアクセスは、検索条件が選択的である時、優れたパフォーマンスを示す可能性がある。
以上の実験結果より、本発明の実施形態の有効性がわかる。本発明の実施形態の1つであるシーケンシャルアクセスを用いた場合に、集約にかかる時間がほぼ一定である理由は、ほとんどの時間がインデックスのシーケンシャルリードに費やされているからである。シーケンシャルリードは、検索条件に依存しない。PostgreSQLでは、検索条件が強いほどselectivityが効いて高速になっているが、もっとも良く効いている場合でも本発明の実施形態の1つであるシーケンシャルアクセスに比べて2倍以上遅い。
【0091】
図10Gは、インデックスの構築にかかる時間を示す。表(1006)は、実験1及び2で使用したデータについて、PostgreSQL上でのインデックス作成処理にかかった時間と、本発明の実施形態であるインデックス作成処理にかかった時間を示す。PostgreSQL上でのインデックス作成処理にかかった時間には、XMLファイルの構文解析をする時間、及びキーワードにidを割り振る時間を含まない。また、入力データは、CSV形式のデータを使用した。CSV形式のデータは、Javaとデータベースの接続のためのAPIであるJDBCを使用してデータベースにデータを取り込む際に優れたデータである。一方、本発明の実施形態であるインデックス作成処理にかかった時間には、XMLファイルの構文解析をする時間及びキーワードにidを割り振る時間を含む。
本発明の実施形態は、インデックス構築にかかる時間についても、RDBにおけるインデックス構築処理よりも速い。
【0092】
本発明の実施態様では、インクリメンタルにインデックスを作成することができるため、複数台のコンピュータを用意し、各コンピュータ上に独立してインデックスを作成することが可能である。すなわち,システム及び処理の並列化が可能である。利用者は、並列プログラミングの規格であるMPIなど既存の並列化フレームワークも利用することができる。
【0093】
また、本発明の実施態様では、集約計算の実行時に、各コンピュータがそれぞれ独立して集約計算を実行する。最後に、集約サーバが、結果をマージしうる。集約サーバを別途独立に用意してもよいし、上記コンピュータのうちから1台を集約サーバとして選択してもよい。
【0094】
図11は、本発明の実施態様で使用されうるコンピュータの例を示す。該コンピュータは、CPUとメイン・メモリと含み、これらはバスに接続されている。CPUは好ましくは、32ビットまたは64ビットのアーキテクチャに基づくものであり、例えば、インテル社のXeon(商標)シリーズ、Core(商標)シリーズ、Pentium(商標)シリーズ、Celeron(商標)シリーズ、AMD社のPhenom(商標)シリーズ、Athlon(商標)シリーズなどを使用することができる。CPUはさらに、その内部にキャッシュ・メモリーを含みうる。バスには、ディスプレイ・コントローラを介して、LCDモニタなどのディスプレイが接続される。ディスプレイは、コンピュータの管理のために、通信回線を介してネットワークに接続されたコンピュータについての情報と、そのコンピュータ上で動作中のソフトウェアについての情報を、適当なグラフィック・インターフェースで表示するために使用される。バスにはまた、IDE又はSATAコントローラを介して、ハードディスク又はシリコン・ディスクと、CD−ROM又はDVDドライブが接続される。
【0095】
ハードディスクには、オペレーティング・システム、J2EEなどのJava(商標)処理環境を提供するプログラム、その他のプログラム及びデータが、メイン・メモリにロード可能に記憶されている。本発明の1つの実施態様として、ハードディスクは、u2vインデックス、relationインデックス、v2uインデックス、及び集約計算に使用するために上記インデックスから作成されたデータ、例えば第1のリスト、第2のリスト及び第3のリスト、並びに木構造を格納している。
【0096】
CD−ROM、DVD又はBDドライブは、必要に応じて、CD−ROM、DVD−ROM又はBDからプログラムをハードディスクに追加導入するために使用される。バスには更に、キーボード・マウス・コントローラを介して、キーボード及びマウスが接続されている。
【0097】
通信インタフェースは、例えばイーサネット(商標)・プロトコルに従うものであり、通信コントローラを介してバスに接続され、コンピュータ及び通信回線を物理的に接続する役割を担い、コンピュータのオペレーティング・システムの通信機能のTCP/IP通信プロトコルに対して、ネットワーク・インターフェース層を提供する。尚、通信回線は、有線LAN環境、或いは例えばIEEE802.11a/b/g/nなどの無線LAN接続規格に基づく無線LAN環境であってもよい。
【図面の簡単な説明】
【0098】
【図1A】本発明の実施態様である、NLPを用いてログ・データを処理する方法を示す。
【図1B】本発明の実施態様である、NLPを用いてログ・データを処理する方法を示す。
【図2】本発明の実施態様である、2つの木構造の例を示す。
【図3】本発明の実施態様である、集約計算の結果の例を示す。
【図4】本発明の実施態様である、ノードそれぞれに後行順(post-order)でノードidを割り振る例を示す。
【図5A】本発明の実施態様である、u2vインデックスの概念スキーマ及び保管の例を示す。
【図5B】本発明の実施態様である、圧縮効果の結果を示す。
【図5C】本発明の実施態様である、u2vインデックスを作成した際のEntryの例を示す。
【図6A】本発明の実施態様である、relationインデックスの概念スキーマ及び保管の例を示す。
【図6B】本発明の実施態様である、relationインデックスを作成した際のEntryの例を示す。
【図7A】本発明の実施態様である、v2uインデックスの概念スキーマ及び保管の例を示す。
【図7B】本発明の実施態様である、v2uインデックスを作成した際のデータの例を示す。
【図8A】本発明の実施態様である、インデックスを作成または更新する処理の全体のフローチャートを示す。
【図8B】本発明の実施態様である、relationインデックスを作成または更新する処理のフローチャートを示す。
【図8C】本発明の実施態様である、u2vインデックスを作成または更新する処理のフローチャートを示す。
【図8D】本発明の実施態様である、v2uインデックスを作成または更新する処理のフローチャートを示す。
【図8E】本発明の実施態様である、転置行列の例を示す。
【図8F】本発明の実施態様である、転置行列の書き出しの処理を示すフローチャートである。
【図9A】本発明の実施態様である、集約処理の主処理を示すフローチャートである。
【図9B】本発明の実施態様である、検索条件処理のフローチャートを示す。
【図9C】本発明の実施態様である、マッチング処理のフローチャートを示す。
【図9D】本発明の実施態様である、値の集約処理のフローチャートを示す。
【図9E】本発明の実施態様である、シーケンシャルアクセスとランダムアクセスにおけるヒット率と実行時間との関係を示す。
【図9F】本発明の実施態様である、ランダムアクセス用インデックスの概念スキーマを示す。
【図9G】本発明の実施態様である、ランダムアクセスを行う場合の、値の集約処理のフローチャートを示す。
【図10A】実験1で使用した木構造を示す。
【図10B】実験1で使用した9種類のクエリを示す。
【図10C】実験1の結果を示すグラフである。
【図10D】実験2で使用した木構造を示す。
【図10E】実験2で使用した9種類のクエリを示す。
【図10F】実験2の結果を示すグラフである。
【図10G】インデックスの構築にかかる時間を示す。
【図11】本発明の実施態様である、コンピュータの構成図を示す。

【特許請求の範囲】
【請求項1】
少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うために、インデックスを作成するコンピュータ・システムであって、前記ノードのそれぞれは該ノードの種類を示す1つのラベル及び0個以上の値を含み、
前記コンピュータ・システムが、
前記ノードそれぞれに後行順(post-order)でノードidを割り振るノードid割振部と、
前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成する第1のインデックス作成部であって、該1以上の組のデータは前記ラベル毎に作成される、前記第1のインデックス作成部と、
前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成する第2のインデックス作成部であって、該1以上の組のデータは前記ラベル毎に作成される、前記第2のインデックス作成部と、
特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成する第3のインデックス作成部であって、該1以上の組のデータは前記ラベル毎の前記特定の値毎に作成される、前記第3のインデックス作成部と
を含む、前記コンピュータ・システム。
【請求項2】
前記第1のインデックスが、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む組のデータをシーケンシャルに格納したファイルである、請求項1に記載のコンピュータ・システム。
【請求項3】
前記第2のインデックスが、前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む組のデータをシーケンシャルに格納したファイルである、請求項1に記載のコンピュータ・システム。
【請求項4】
前記第3のインデックスが、前記特定の値を含む1以上のノードのノードidを含む1以上の組のデータをシーケンシャルに格納したファイルである、請求項1に記載のコンピュータ・システム。
【請求項5】
前記ラベルのそれぞれにラベルidを割り振るラベルid割振部をさらに含む、請求項1に記載のコンピュータ・システム。
【請求項6】
前記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されている第4のインデックス作成部をさらに含み、前記ポインタは前記第1のインデックスを成す前記1以上の組のデータにおけるノードidのデータの位置を示す、請求項1に記載のコンピュータ・システム。
【請求項7】
少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うコンピュータ・システムであって、前記ノードのそれぞれは該ノードの種類を示す1つのラベル及び0個以上の値を含み、前記ノードのそれぞれは後行順(post-order)でノードidを割り振られており、
前記コンピュータ・システムが、
集約計算を行うための検索式を受信する受信部と
前記検索式の検索対象である値を用い及び、特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有するインデックスを用いて、前記検索式の検索対象である前記値を有する1以上のノードのノードidを含む第1のリストを取得する第1のリスト取得部であって、該1以上の組のデータは前記ラベル毎の前記特定の値毎に作成される、前記第1のリスト取得部と、
前記取得した第1のリストを用い及び、前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところのインデックスを用いて、前記検索式の検索対象である前記値を有する1以上のノードを子孫に持つ各木構造のルート・ノードの1以上のルート・ノードidを含む第2のリストを取得する第2のリスト取得部であって、該1以上の組のデータは前記ラベル毎に作成される、前記第2のリスト取得部と、
前記取得した第2のリストに基づいて、前記検索式の検索対象である前記値を検索する検索部であって、前記検索式の検索対象である前記値が少なくとも1つのキーワードに対応する、前記検索部と
を含む、前記コンピュータ・システム。
【請求項8】
前記取得した第2のリストを用いて及び、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いて、前記検索式の検索条件を満たす、1以上のノードの1以上の値を含む第3のリストを取得する第3のリスト取得部であって、該1以上の組のデータは前記ラベル毎に作成される、前記第3のリスト取得部と、
前記取得した第3のリストに基づいて、前記検索式の結果を求める計算部と
をさらに含む、請求項7に記載のコンピュータ・システム。
【請求項9】
中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行うために、インデックスを作成する方法であって、前記ノードそれぞれは該ノードの種類を示す1つのラベル及び0個以上の値を含み、
前記方法が、前記中央演算処理ユニットに下記ステップを実行させることを含み、該方法が、
前記ノードの情報を前記メモリー内に読み込み、前記情報を読み込んだノードそれぞれに後行順(post-order)でノードidを割り振るステップと、
前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成し、該作成した第1のインデックスを前記記憶部に格納するステップであって、該1以上の組のデータは前記ラベル毎に作成される、前記第1のインデックスを格納するステップと、
前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成し、該作成した第2のインデックスを前記記憶部に格納するステップであって、該1以上の組のデータは前記ラベル毎に作成される、前記第2のインデックスを格納するステップと、
特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成し、該作成した第3のインデックスを前記記憶部に格納するステップであって、該1以上の組のデータは前記ラベル毎の前記特定の値毎に作成される、前記第3のインデックスを格納するステップと
を含む、前記方法。
【請求項10】
前記第1のインデックスを前記記憶部に格納するステップが、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む組のデータをシーケンシャルに格納するステップをさらに含む、請求項9に記載の方法。
【請求項11】
前記第2のインデックスを前記記憶部に格納するステップが、前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む組のデータをシーケンシャルに格納するステップをさらに含む、請求項9に記載の方法。
【請求項12】
前記第3のインデックスを前記記憶部に格納するステップが、前記特定の値を含む1以上のノードのノードidを含む1以上の組のデータをシーケンシャルに格納するステップをさらに含む、請求項9に記載の方法。
【請求項13】
前記方法が、前記中央演算処理ユニットに下記ステップをさらに実行させることを含み、該方法が、
前記ラベルのそれぞれにラベルidを割り振るステップを含む、請求項9に記載の方法。
【請求項14】
前記方法が、前記中央演算処理ユニットに下記ステップをさらに実行させることを含み、該方法が、
前記第1のインデックスにおける値又は前記第3のインデックスにおけるノードidを圧縮するステップを含む、請求項9に記載の方法。
【請求項15】
前記方法が、前記中央演算処理ユニットに下記ステップをさらに実行させることを含み、該方法が、
前記第1のインデックスを作成する前に、前記値が文字列である場合、該文字列を数値に置き換えるステップを含む、請求項9に記載の方法。
【請求項16】
前記方法が、前記中央演算処理ユニットに下記ステップをさらに実行させることを含み、該方法が、
前記第3のインデックスを作成した後に、前記置き換えられた数値を、前記文字列にさらに置き換えるステップを含む、請求項15に記載の方法。
【請求項17】
前記方法が、前記中央演算処理ユニットに下記ステップをさらに実行させることを含み、該方法が、
前記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されている第4のインデックスを作成するステップを含み、前記ポインタは前記第1のインデックスを成す前記1以上の組のデータにおけるノードidのデータの位置を示す、請求項9に記載の方法。
【請求項18】
中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行う方法であって、前記ノードそれぞれは該ノードの種類を示す1つのラベル及び0個以上の値を含み、前記ノードそれぞれは後行順(post-order)でノードidを割り振られており、
前記方法が中央演算処理ユニットに下記ステップを実行させるステップを含み、
該方法が、
集約計算を行うための検索式を受信し、該受信した検索式を前記メモリー内に記憶するステップと、
前記検索式の検索対象である値を用い及び、特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有するインデックスを用いて、前記検索式の検索対象である前記値を有する1以上のノードのノードidを含む第1のリストを取得し、該取得した第1のリストを前記記憶部に記憶するステップであって、該1以上の組のデータは前記ラベル毎の前記特定の値毎に作成される、前記第1のリストを記憶するステップと、
前記取得した第1のリストを用い及び、前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところのインデックスを用いて、前記検索式の検索対象である前記値を有する1以上のノードを子孫に持つ各木構造のルート・ノードの1以上のルート・ノードidを含む第2のリストを取得し、該取得した第2のリストを前記記憶部に記憶するステップであって、該1以上の組のデータは前記ラベル毎に作成される、前記第2のリストを記憶するステップと、
前記取得した第2のリストに基づいて、前記検索式の検索対象である前記値を検索するステップであって、前記検索式の検索対象である前記値が少なくとも1つのキーワードに対応する、前記検索するステップと
を含む、前記方法。
【請求項19】
前記方法が、前記中央演算処理ユニットに下記ステップをさらに実行させることを含み、該方法が、
前記取得した第2のリストを用い及び、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いて、前記検索式の検索条件を満たす、1以上のノードの1以上の値を含む第3のリストを取得し、該取得した第3のリストを前記記憶部に記憶するステップであって、該1以上の組のデータは前記ラベル毎に作成される、前記第3のリストを記憶するステップと、
前記取得した第3のリストに基づいて、前記検索式の結果を求めるステップと
をさらに含む、請求項18に記載の方法。
【請求項20】
前記第3のリストが、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いてシーケンシャルアクセスにより取得される、請求項19に記載の方法。
【請求項21】
前記第3のリストが、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックス、及び前記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されているインデックスを用いてランダムアクセスにより取得される、請求項19に記載の方法。
【請求項22】
前記第3のリストの一部が、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックスを用いてシーケンシャルアクセスにより取得され、及び
前記第3のリストの残りが、前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところのインデックス、及び前記ノードそれぞれのノードidと、該ノードidそれぞれに関連付けられたポインタとを含む組のデータが格納されているインデックスを用いてランダムアクセスにより取得され、
前記第3のリストが、前記シーケンシャルアクセスと前記ランダムアクセスとを切り替えることによって取得される、請求項19に記載の方法。
【請求項23】
中央演算処理ユニット、メモリー及び木構造のデータを記憶する記憶部を有するコンピュータ・システムにおいて、少なくとも1つのノードを含む少なくとも1つの木構造のデータに対する集約計算を行う方法であって、前記ノードそれぞれは該ノードの種類を示す1つのラベル及び0個以上の値を含み、
前記方法が、前記中央演算処理ユニットに下記ステップを実行させることを含み、該方法が、
前記ノードの情報を前記メモリー内に読み込み、前記情報を読み込んだノードそれぞれに後行順(post-order)でノードidを割り振るステップと、
前記ノードそれぞれのノードidと、該ノードに含まれる値とを含む1以上の組のデータを有するところの第1のインデックスを作成し、該作成した第1のインデックスを前記記憶部に格納するステップであって、該1以上の組のデータは前記ラベル毎に作成される、前記第1のインデックスを格納するステップと、
前記ノードそれぞれのノードidと、該ノードの少なくとも1つの子孫ノードの間で最小のノードidを有する子孫ノードのノードidとを含む1以上の組のデータを有するところの第2のインデックスを作成し、該作成した第2のインデックスを前記記憶部に格納するステップであって、該1以上の組のデータは前記ラベル毎に作成される、前記第2のインデックスを格納するステップと、
特定の値を含む1以上のノードのノードidを含む1以上の組のデータを有する第3のインデックスを作成し、該作成した第3のインデックスを前記記憶部に格納するステップであって、該1以上の組のデータは前記ラベル毎の前記特定の値毎に作成される、前記第3のインデックスを格納するステップと、
前記メモリー内に記憶した集約計算を行うための検索式の検索対象である値及び前記第3のインデックスを用いて、前記検索式の検索対象である前記値を有する1以上のノードのノードidを含む第1のリストを取得し、該取得した第1のリストを前記記憶部に記憶するステップと、
前記取得した第1のリスト及び前記第2のインデックスを用いて、前記検索式の検索対象である前記値を有する1以上のノードを子孫に持つ各木構造のルート・ノードの1以上のルート・ノードidを含む第2のリストを取得し、該取得した第2のリストを前記記憶部に記憶するステップと、
前記取得した第2のリスト及び前記第1のインデックスを用いて、前記検索式の検索条件を満たす、1以上のノードの1以上の値を含む第3のリストを取得し、該取得した第3のリストを前記記憶部に記憶するステップと、
前記取得した第3のリストに基づいて、前記検索式の結果を求めるステップと
を含む、前記方法。

【図1A】
image rotate

【図1B】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5A】
image rotate

【図5B】
image rotate

【図5C】
image rotate

【図6A】
image rotate

【図6B】
image rotate

【図7A】
image rotate

【図7B】
image rotate

【図8A】
image rotate

【図8B】
image rotate

【図8C】
image rotate

【図8D】
image rotate

【図8E】
image rotate

【図8F】
image rotate

【図9A】
image rotate

【図9B】
image rotate

【図9C】
image rotate

【図9D】
image rotate

【図9E】
image rotate

【図9F】
image rotate

【図9G】
image rotate

【図10A】
image rotate

【図10B】
image rotate

【図10C】
image rotate

【図10D】
image rotate

【図10E】
image rotate

【図10F】
image rotate

【図10G】
image rotate

【図11】
image rotate


【公開番号】特開2009−294967(P2009−294967A)
【公開日】平成21年12月17日(2009.12.17)
【国際特許分類】
【出願番号】特願2008−148798(P2008−148798)
【出願日】平成20年6月6日(2008.6.6)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【復代理人】
【識別番号】100085545
【弁理士】
【氏名又は名称】松井 光夫
【復代理人】
【識別番号】100118599
【弁理士】
【氏名又は名称】村上 博司
【Fターム(参考)】