(57)【特許請求の範囲】
【請求項１】
複数のノード装置からなる木構造の構造化オーバレイシステムのデータキャッシュ方法であって、
前記ノード装置に入力された、前記構造化オーバレイシステムが蓄積する時系列データを解析する解析手順と前記解析手順で解析された解析結果を記録する全解析記録ステップと、
所定期間毎に、前記全解析記録ステップで記録した複数の前記解析手順から部分的に共通する部分操作列を抽出し、前記部分操作列を記録する部分操作列抽出ステップと、
前記部分操作列抽出ステップで記録した前記部分操作列を含む新たな解析手順が前記ノード装置に入力されたときに前記部分操作列で解析された解析結果を部分解析結果として記録する部分解析結果記録ステップと、
前記部分解析結果記録ステップの後に、前記部分操作列を含む新たな解析手順がさらに前記ノード装置に入力されたときに、前記部分解析結果記録ステップで記録した前記部分解析結果を利用して解析を行う解析結果再利用ステップと、
を行うことを特徴とするデータキャッシュ方法。
【請求項２】
前記部分操作列抽出ステップで抽出した前記部分操作列を前記ノード装置の上位にある上位ノード装置へ転送する上位転送ステップ、
をさらに行うことを特徴とする請求項１に記載のデータキャッシュ方法。
【請求項３】
前記上位ノード装置で、一定期間毎に、複数の前記ノード装置から前記上位転送ステップで転送されてきた複数の前記部分操作列から部分的に共通するノード間共通操作列を抽出するノード間共通操作列抽出ステップと、
前記ノード間共通操作列抽出ステップで抽出した前記ノード間共通操作列を前記部分操作列として前記ノード装置に記録させるため、前記上位ノード装置から前記ノード装置へ前記ノード間共通操作列を転送する下位転送ステップと、
を行うことを特徴とする請求項２に記載のデータキャッシュ方法。
【請求項４】
木構造の構造化オーバレイシステムを構成するノード装置であって、
キャッシュストレージと、
時系列データを保存するデータストレージと、
前記構造化オーバレイシステム上にて木構造を辿ることで特定の時系列データを探索する経路制御モジュールと、
入力された、前記構造化オーバレイシステムが蓄積する時系列データを解析する解析手順と前記解析手順で解析された解析結果を前記キャッシュストレージに記録させること、
所定期間毎に、前記キャッシュストレージが記録した複数の前記解析手順に部分的に共通する部分操作列を抽出し、前記部分操作列を前記キャッシュストレージに記録させること、
前記部分操作列を含む新たな解析手順が入力されたときに前記部分操作列で解析された解析結果を部分解析結果として前記キャッシュストレージに記録させること、及び
前記部分操作列を含む新たな解析手順がさらに入力されたときに、前記キャッシュストレージが記録する前記部分解析結果を利用して解析すること
を行うコントローラと、
を備えることを特徴とするノード装置。
【請求項５】
前記コントローラは、抽出した前記部分操作列を自装置の上位にある上位ノード装置へ転送することを特徴とする請求項４に記載のノード装置。
【請求項６】
前記コントローラは、
前記上位ノード装置が、一定期間毎に抽出した、複数の前記部分操作列に部分的に共通するノード間共通操作列を受け取り、前記ノード間共通操作列を前記部分操作列として前記キャッシュストレージに記憶させること、をさらに行うことを特徴とする請求項５に記載のノード装置。
【請求項７】
請求項１から３のいずれかに記載のデータキャッシュ方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構造化オーバレイシステムにおけるデータ解析を行う際のデータキャッシュ方法、当該データキャッシュ方法を実現するノード装置、及びそのプログラムに関する。
【背景技術】
【０００２】
構造化オーバレイとは、ひとつの論理的なＩＤ空間を複数のノードで分担し管理する技術であり、Ｋｅｙ  Ｖａｌｕｅ  Ｓｔｏｒｅ等の分散データベースにて利用されている。構造化オーバレイにデータを配置する場合、当該データの名前をキーとし、当該キーを担当するノードに対して当該データを配置する。データをオーバレイから取得する場合、取得したいデータの名前をキーとし、オーバレイ上から当該キーを担当するノードを探し、データを取得する。本手法はＨａｄｏｏｐ（非特許文献１）、Ｊｕｂａｔｕｓ（非特許文献３）といった大規模データ解析基盤等で用いられるデータの保存方法である。これらの解析基盤は、保存されているデータに対してＭａｐＲｅｄｕｃｅ処理（非特許文献２）を行うことで高速かつ分散的にデータの解析を行うことができる。既存手法（非特許文献６）では、解析者がＳＱＬライクな言語を用いて記述した解析手順をＭａｐＲｅｄｕｃｅ処理に射影するＰｉｇ（非特許文献７）と呼ばれるシステムにて、全ての解析手順と解析結果の対を保存しておくことで、新たな解析手順に対する解析結果の算出を高速化している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｋ．  Ｓｈｖａｃｈｋｏ，  Ｈ．  Ｋｕａｎｇ，  Ｓ．  Ｒａｄｉａ，  ａｎｄ  Ｒ．  Ｃｈａｎｓｌｅｒ，  “Ｔｈｅ  Ｈａｄｏｏｐ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ”  ｉｎ  Ｐｒｏｃ．  ＩＥＥＥ  ＭＳＳＴ，  ２０１０．
【非特許文献２】Ｊ．  Ｄｅａｎ  ａｎｄ  Ｓ．  Ｇｈｅｍａｗａｔ，  “ＭａｐＲｅｄｕｃｅ：  Ｓｉｍｐｌｉｆｉｅｄ  Ｄａｔａ  Ｐｒｏｃｅｓｓｉｎｇ  ｏｎ  Ｌａｒｇｅ  Ｃｌｕｓｔｅｒｓ”，  ｉｎ  Ｐｒｏｃ．  ＯＳＤＩ  ２００４：  ６ｔｈ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，  ２００４．
【非特許文献３】韓  正圭，牧野  浩之，熊崎  宏樹，「リアルタイム型大規模データ処理基盤Ｊｕｂａｔｕｓとその活用事例について」，  経営の科学  ５７（１２），  ｐｐ．  ６８９−６９４，  ２０１２．
【非特許文献４】Ｌ．  Ａｖｉｎａｓｈ  ａｎｄ  Ｍ．  Ｐｒａｓｈａｎｔ，“Ｃａｓｓａｎｄｒａ：  Ａ  Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ｓｔｒｕｃｔｕｒｅｄ  Ｓｔｏｒａｇｅ  Ｓｙｓｔｅｍ”  ｉｎ  ＡＣＭ  ＳＩＧＯＰＳ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｒｅｖｉｅｗ，  ｖｏｌ．  ４４，  Ｉｓｓｕｅ．  ２，  ｐｐ．  ３５−４０，  ２０１０．
【非特許文献５】Ａ．  Ｔｈｕｓｏｏ，  Ｊ．  Ｓ．  Ｓａｒｍａ，  Ｎ．  Ｊａｉｎ，  Ｚ．  Ｓｈａｏ，  Ｐ．  Ｃｈａｋｋａ，  Ｎ．  Ｚｈａｎｇ，  Ｓ．  Ａｎｔｏｎｙ，  Ｈ．  Ｌｉｕ，  ａｎｄ  Ｒ．  Ｍｕｒｔｈｙ，  “Ｈｉｖｅ−Ａ  Ｐｅｔａｂｙｔｅ  Ｓｃａｌｅ  Ｄａｔａ  Ｗａｒｅｈｏｕｓｅ  Ｕｓｉｎｇ  Ｈａｄｏｏｐ”，  ｉｎ  Ｐｒｏｃ．  ＩＣＤＥ，  ２０１０．
【非特許文献６】Ｉ．  Ｅｌｇｈａｎｄｏｕｒ  ａｎｄ  Ａ．  Ａｂｏｕｌｎａｇａ，“ＲｅＳｔｏｒｅ：  Ｒｅｕｓｉｎｇ  Ｒｅｓｕｌｔｓ  ｏｆ  ＭａｐＲｅｄｕｃｅ  Ｊｏｂｓ”  ｉｎ  Ｐｒｏｃ．  ＶＬＤＢ  Ｅｎｄｏｗｍｅｎｔ，  ｖｏｌ．  ５，  Ｉｓｓｕｅ．  ６，  ｐｐ．  ５８６−５９７，  ２０１２．
【非特許文献７】Ｏ．  Ｃｈｒｉｓｔｏｐｈｅｒ  ｅｔ  ａｌ，“Ｐｉｇ  Ｌａｔｉｎ：  Ａ  Ｎｏｔ−Ｓｏ−Ｆｏｒｅｉｇｎ  Ｌａｎｇｕａｇｅ  ｆｏｒ  Ｄａｔａ  Ｐｒｏｃｅｓｓｉｎｇ”  ｉｎ  Ｐｒｏｃ．  ＳＩＧＭＯＤ  ２００８，  ｐｐ．  １０９９−１１１０，  ２００８．
【非特許文献８】武井  洋介，太田  耕平，加藤  寧，根元  義章，「トラヒックパターンを用いた不正アクセス検出及び追跡方式」，  電子情報通信学会論文誌Ｂ，  ｖｏｌ．  Ｊ８４−Ｂ，  Ｎｏ．  ８，  ｐｐ．  １４６４−１４７３，  ２００１．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献７のような高速化手法では、全ての解析手順と解析結果の対を保存するため、複雑かつ多様な解析の実行により解析結果の保存量（キャッシュ）が大きく増加し、ハードディスク容量が枯渇する可能性があるという課題がある。
【０００５】
そこで、本発明は、上記課題を解決するべく、データ解析を高速化できるとともにハードディスク容量が枯渇する可能性を低減できるデータキャッシュ方法、ノード装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係るデータキャッシュ方法は、入力された解析手順とその解析結果を記録し、所定期間毎に、記録された解析手順から頻繁に利用される部分解析手順を抽出し、その後、抽出された部分解析手順を含む解析手順が入力された時に該部分解析手順の解析結果を保存しておき、新たに該部分解析手順を含む解析手順が入力された際に保存された解析結果を再利用することとした。
【０００７】
具体的には、本発明に係るデータキャッシュ方法は、複数のノード装置からなる木構造の構造化オーバレイシステムのデータキャッシュ方法であって、
前記ノード装置に入力された、前記構造化オーバレイシステムが蓄積する時系列データを解析する解析手順と前記解析手順で解析された解析結果を記録する全解析記録ステップと、
所定期間毎に、前記全解析記録ステップで記録した複数の前記解析手順から部分的に共通する部分操作列を抽出し、前記部分操作列を記録する部分操作列抽出ステップと、
前記部分操作列抽出ステップで記録した前記部分操作列を含む新たな解析手順が前記ノード装置に入力されたときに前記部分操作列で解析された解析結果を部分解析結果として記録する部分解析結果記録ステップと、
前記部分解析結果記録ステップの後に、前記部分操作列を含む新たな解析手順がさらに前記ノード装置に入力されたときに、前記部分解析結果記録ステップで記録した前記部分解析結果を利用して解析を行う解析結果再利用ステップと、
を行うことを特徴とする。
【０００８】
また、本発明に係るノード装置は、木構造の構造化オーバレイシステムを構成するノード装置であって、
キャッシュストレージと、
時系列データを保存するデータストレージと、
前記構造化オーバレイシステム上にて木構造を辿ることで特定の時系列データを探索する経路制御モジュールと、
入力された、前記構造化オーバレイシステムが蓄積する時系列データを解析する解析手順と前記解析手順で解析された解析結果を前記キャッシュストレージに記録させること、
所定期間毎に、前記キャッシュストレージが記録した複数の前記解析手順に部分的に共通する部分操作列を抽出し、前記部分操作列を前記キャッシュストレージに記録させること、
前記部分操作列を含む新たな解析手順が入力されたときに前記部分操作列で解析された解析結果を部分解析結果として前記キャッシュストレージに記録させること、及び
前記部分操作列を含む新たな解析手順がさらに入力されたときに、前記キャッシュストレージが記録する前記部分解析結果を利用して解析すること
を行うコントローラと、
を備えることを特徴とする。
【０００９】
本発明は、多数のサーバにて構築される木構造の構造化オーバレイに蓄積されているトラフィックデータやセンサデータ等の時系列データ解析する際に、過去の解析手順から頻繁に利用される解析手順（部分操作列）とその結果を記録しておき、新たな解析手順が投入された場合、過去の解析手順（部分操作列）の結果を再利用することで、解析時間を短縮する。また、本発明は、頻繁に利用される部分操作列とその結果のみを記録するため、キャッシュ容量を低減できる。
【００１０】
従って、本発明は、データ解析を高速化できるとともにハードディスク容量が枯渇する可能性を低減できるデータキャッシュ方法及びノード装置を提供することができる。
【００１１】
本発明に係るデータキャッシュ方法は、前記部分操作列抽出ステップで抽出した前記部分操作列を前記ノード装置の上位にある上位ノード装置へ転送する上位転送ステップをさらに行うことを特徴とする。
【００１２】
本発明に係るデータキャッシュ方法は、
前記上位ノード装置で、一定期間毎に、複数の前記ノード装置から前記上位転送ステップで転送されてきた複数の前記部分操作列から部分的に共通するノード間共通操作列を抽出するノード間共通操作列抽出ステップと、
前記ノード間共通操作列抽出ステップで抽出した前記ノード間共通操作列を前記部分操作列として前記ノード装置に記録させるため、前記上位ノード装置から前記ノード装置へ前記ノード間共通操作列を転送する下位転送ステップと、
を行うことを特徴とする。
【００１３】
また、本発明に係るノード装置の前記コントローラは、抽出した前記部分操作列を自装置の上位にある上位ノード装置へ転送することを特徴とする。
【００１４】
本発明に係るノード装置の前記コントローラは、
前記上位ノード装置が、一定期間毎に抽出した、複数の前記部分操作列に部分的に共通するノード間共通操作列を受け取り、前記ノード間共通操作列を前記部分操作列として前記キャッシュストレージに記憶させること、をさらに行うことを特徴とする。
【００１５】
本発明は、時系列データの特徴である近接性（近い時間のデータ同士は相関関係が強い）を考慮し、近い時間の時系列データを保存しているサーバ間で頻繁に利用される解析手順（部分操作列）を共有しておくことで、互いの解析手順（部分操作列）の再利用性を向上させる。
【００１６】
本発明に係るプログラムは、データキャッシュ方法をコンピュータに実行させるためのプログラムである。前記ノード装置は、コンピュータと本プログラムによっても実現でき、本プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【発明の効果】
【００１７】
本発明は、データ解析を高速化できるとともにハードディスク容量が枯渇する可能性を低減できるデータキャッシュ方法、ノード装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明に係るノード装置の構成を説明する図である。
【図２】木構造を持つ構造化オーバレイの例を説明する図である。
【図３】本発明に係るデータキャッシュ方法を説明する図である。
【図４】本発明に係るデータキャッシュ方法を説明する図である。
【図５】本発明に係るデータキャッシュ方法を説明する図である。
【図６】本発明に係るデータキャッシュ方法を説明する図である。
【発明を実施するための形態】
【００１９】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２０】
図１は、本実施形態のノード装置の構成を説明する図である。本ノード装置は、木構造の構造化オーバレイシステムを構成するノード装置であって、
キャッシュストレージ３０と、
時系列データを保存するデータストレージ４０と、
前記構造化オーバレイシステム上にて木構造を辿ることで特定の時系列データを探索する経路制御モジュール１０と、
入力された、前記構造化オーバレイシステムが蓄積する時系列データを解析する解析手順と前記解析手順で解析された解析結果をキャッシュストレージ３０に記録させること、
所定期間毎に、キャッシュストレージ３０が記録した複数の前記解析手順に部分的に共通する部分操作列を抽出し、前記部分操作列をキャッシュストレージ３０に記録させること、
前記部分操作列を含む新たな解析手順が入力されたときに前記部分操作列で解析された解析結果を部分解析結果としてキャッシュストレージ３０に記録させること、及び
前記部分操作列を含む新たな解析手順がさらに入力されたときに、キャッシュストレージ３０が記録する前記部分解析結果を利用して解析すること
を行うキャッシュストレージコントローラ２０と、
を備えることを特徴とする。
【００２１】
また、本ノード装置が行うデータキャッシュ方法は、次の通りである。本データキャッシュ方法は、複数のノード装置からなる木構造の構造化オーバレイシステムのデータキャッシュ方法であって、
前記ノード装置に入力された、前記構造化オーバレイシステムが蓄積する時系列データを解析する解析手順と前記解析手順で解析された解析結果を記録する全解析記録ステップと、
所定期間毎に、前記全解析記録ステップで記録した複数の前記解析手順から部分的に共通する部分操作列を抽出し、前記部分操作列を記録する部分操作列抽出ステップと、
前記部分操作列抽出ステップで記録した前記部分操作列を含む新たな解析手順が前記ノード装置に入力されたときに前記部分操作列で解析された解析結果を部分解析結果として記録する部分解析結果記録ステップと、
前記部分解析結果記録ステップの後に、前記部分操作列を含む新たな解析手順がさらに前記ノード装置に入力されたときに、前記部分解析結果記録ステップで記録した前記部分解析結果を利用して解析を行う解析結果再利用ステップと、
を行うことを特徴とする。
【００２２】
経路制御モジュール１０は、木構造を持つ構造化オーバレイにおける経路制御モジュールであり、構造化オーバレイ上にて、特定のＩＤを持つデータ等を、木構造の親子関係を辿ることによって探索する機能を持っている。木の末端のノードはＩＤを持ち、ノードｉ（０≦ｉ＜ＩＤ＿Ｓｐａｃｅ＿Ｓｉｚｅ）のＩＤをＸｉとする。ＩＤ空間は０とＩＤ＿Ｓｐａｃｅ＿Ｓｉｚｅにて連結しており、リング構造をもっているものとする。この時、Ｘｉから右回りにもっとも近いノードをノードｉのＳｕｃｃｅｓｓｏｒ（ＩＤ：  ｓｕｃｉ）と呼び、ノードｉの担当領域は［Ｘｉ，  ｓｕｃｉ）となる。なお、［Ａ，Ｂ）はＡ以上Ｂ未満を意味し、（Ａ，Ｂ］はＡより大きくＢ以下を意味する。
【００２３】
木の節に当たるノードは自身の下に存在するノードの担当領域を記録しておく。これらの木構造のオーバレイの例を図２に示す。図２において、符号Ａ〜Ｇで示した装置がノード装置である。本実施形態では、時系列データを構造化オーバレイにて管理することを想定するため、ＩＤ空間の大きさは［０，  ８６４００）とし、時系列データは時間（秒）をキーとしてデータストレージ４０に保存されているものとする。
【００２４】
キャッシュストレージ３０では、自身の担当領域内のデータに対する解析手順と解析結果を格納するストレージであり、キャッシュストレージコントローラ２０は、解析手順と解析結果をキャッシュストレージ３０に格納するか否かを決定する。提案手法はキャッシュストレージ３０とキャッシュストレージコントローラ２０にて達成されるため、以下ではこれらの詳細について述べる。
【００２５】
キャッシュストレージコントローラ２０は、部分操作列抽出部２１、解析手順実行部２２、及び情報共有部２３から構成される。ここで、（ｐ，  ｑ］  ｐ≠ｑの時間範囲のデータに対して、解析手順｛Ａ−Ｂ−Ｃ−Ｄ｝を実行することを考える。ここでの、ＡやＢは、「ある特徴量を数え上げる」といったデータに対する操作を示しており、｛Ｘ−Ｙ−Ｚ｝はＸ，Ｙ，Ｚの順で操作することを示している。本解析手順は、（ｐ，  ｑ］を包含する担当領域を持つノードのキャッシュストレージコントローラ２０にて実行される。
【００２６】
１．解析手順実行部
図３は、解析手順実行部２２の動作を説明する図である。
まず、解析手順｛Ａ−Ｂ−Ｃ−Ｄ｝が入力された際、解析手順実行部２２にて、過去に同じ解析手順が入力されたかどうかを判断する（Ｓ０１）。もし、入力された解析手順が過去に行われていなければ、データストレージ４０から当該解析手順に該当するデータを読み込み（Ｓ０２）、解析を行った結果を
【数１】
0006319694.tif 000002
といった形（キャッシュ）で、キャッシュストレージ３０に対して解析結果を保存する（Ｓ０３）。ステップＳ０１、Ｓ０２及びＳ０３は前記全解析記録ステップである。
【００２７】
以降、解析手順実行部２２は、ノード装置に入力された解析手順についてキャッシュストレージ３０に確認する（Ｓ０４）。そして、解析手順実行部２２は、当該解析手順がキャッシュストレージ３０に格納されていた場合、当該キャッシュを読み込むこと（Ｓ０５）で、過去と重複する解析手順（データ解析を行い解析結果を取得すること）を省略する。
【００２８】
また、解析手順実行部２２は、後述する部分操作列抽出部２１で頻度が高いと判定された部分操作列を含む解析手順が入力された場合、当該部分操作列で解析した結果（部分解析結果）をキャッシュストレージ３０に書き込む。
【００２９】
２．部分操作列抽出部
図４は、部分操作列抽出部２１の動作を説明する図である。
解析手順と解析結果を記憶し続けると、キャッシュによってハードディスクの容量が枯渇する可能性がある。このため、本実施形態では、部分操作列抽出部２１が所定期間毎に、上記の解析手順と解析結果から頻繁に解析される手順を部分操作列として抽出し（Ｓ０６）、キャッシュストレージ３０に書き込む（Ｓ０７）。ステップＳ０６及びＳ０７は前記部分操作列抽出ステップである。
【００３０】
具体的には、ｋ（＞０）回以上出現する（手順長がｌ以上）部分手順をまとめて抽出することにする。手順長とは解析手順内に存在するデータ操作回数を示し、｛Ａ−Ｂ−Ｃ｝の解析手順の手順長さは３である。図５は、部分操作列抽出部２１が行う部分操作列の抽出方法を説明する図である。
Ｓｔｅｐ  １：
全ての解析手順から、トライ木を作成し、共有操作をまとめる。また、各操作を何回行ったかを保存する。
Ｓｔｅｐ  ２：
作成したトライ木から、ｋ回以上出現し、かつ手順長がｌ以上の部分操作列を取得する。
図５の例では、｛Ａ−Ｂ｝と｛Ｃ−Ａ｝の部分操作列を抽出することができた。
【００３１】
そして、部分操作列抽出部２１は、抽出した部分操作列をキャッシュストレージ３０に記憶させた後、前記所定期間内に解析手順実行部２２がキャッシュストレージ３０に記憶させた解析手順と解析結果を削除する。
【００３２】
解析手順実行部２２は、新たに解析手順が入力されたときに当該解析手順についてキャッシュストレージ３０を確認し（Ｓ０８）、当該解析手順が抽出された実行頻度の高い部分操作列を含む場合（Ｓ０９）、キャッシュストレージ３０に当該部分操作列の部分解析結果を保存しておく（Ｓ１０）。ステップＳ０８〜Ｓ１０は前記部分解析結果記録ステップである。
【００３３】
例えば、ある範囲（ｒ，  ｓ］に対する解析手順が入力された際、解析手順実行部２２は、当該解析手順に先頭から｛Ａ−Ｂ｝と｛Ｃ−Ａ｝を含む場合、キャッシュストレージ３０に当該解析結果（部分解析結果）を保存しておく。例えば、解析手順Ｃ−Ａ−Ｄが入力された場合、解析手順実行部２２は、
【数２】
0006319694.tif 000003
というキャッシュをキャッシュストレージ３０に保存しておく。
【００３４】
本データキャッシュ方法によって、頻繁に利用される解析結果を再利用し、解析結果の高速化を達成することができる（解析結果再利用ステップ）。また、全ての解析手順とその結果を保存するのではなく、頻繁に利用される解析手順の部分列を保存することで、キャッシュの再利用率を向上させることができるとともに、ハードディスク容量が枯渇する可能性を低減することができる。
【００３５】
３．情報共有部
図４及び図６は、情報共有部２３の動作を説明する図である。
キャッシュストレージコントローラ２０は、抽出した前記部分操作列を自装置の上位にある上位ノード装置へ転送し、前記上位ノード装置が、一定期間毎に抽出した、複数の前記部分操作列に部分的に共通するノード間共通操作列を受け取り、前記ノード間共通操作列を前記部分操作列として前記キャッシュストレージに記憶させる。
【００３６】
また、本ノード装置が行うデータキャッシュ方法は、次の通りである。本データキャッシュ方法は、
前記部分操作列抽出ステップで抽出した前記部分操作列を前記ノード装置の上位にある上位ノード装置へ転送する上位転送ステップと、
前記上位ノード装置で、一定期間毎に、複数の前記ノード装置から前記上位転送ステップで転送されてきた複数の前記部分操作列から部分的に共通するノード間共通操作列を抽出するノード間共通操作列抽出ステップと、
前記ノード間共通操作列抽出ステップで抽出した前記ノード間共通操作列を前記部分操作列として前記ノード装置に記録させるため、前記上位ノード装置から前記ノード装置へ前記ノード間共通操作列を転送する下位転送ステップと、
をさらに行う。
【００３７】
時系列データは一般的に、近い時間同士に特定の相関がみられると考えられており（非特許文献８）、似たデータ同士に対しては、類似する解析が行われると考えられる。そのため、情報共有部２３は、各ノード装置が調べた頻度の高い部分操作列を他のノード装置と共有することにする。
【００３８】
図４と図６に共有方法の例を示す。
部分操作列抽出部２１は、抽出した頻度の高い部分操作列を情報共有部２３へ引き渡す（Ｓ１１）。各ノード装置の情報共有部２３は、当該部分操作列を自装置の上位にある上位ノード装置（親ノード）の情報共有部２３に対して送信する（Ｓ１２）。ステップＳ１１及びＳ１２は前記上位転送ステップである。
【００３９】
親ノードは、当該部分操作列を親ノードのキャッシュストレージ３０に記憶する（Ｓ１３）。そして、親ノードの部分操作列抽出部２１は一定期間毎に部分操作列を読み込み、その中でも頻度の高い部分操作列を見出す（Ｓ１４、Ｓ１５）。ステップＳ１４及びＳ１５は前記ノード間共通操作列抽出ステップである。例えば、部分操作列抽出部２１は親ノード自身のｌとｋの条件を満たす部分操作列を探し出す。
【００４０】
そして、親ノードの部分操作列抽出部２１は探し出した部分操作列を親ノードの情報共有部２３へ引き渡し（Ｓ１６）、情報共有部２３は配下の子ノード間で当該部分操作列を共有させる（Ｓ１７）。子ノードの情報共有部２３は親ノードから受信した部分操作列もキャッシュストレージ３０に保持しておく。ステップＳ１６及びＳ１７は前記下位転送ステップである。
【００４１】
子ノードは、自身で抽出した部分操作列と親ノードから転送された部分操作列とを保持しており、自身のある範囲（ｖ，  ｗ］に対する解析手順が入力され際に、先頭から｛Ａ−Ｂ｝と｛Ｃ−Ａ｝と｛Ｋ−Ａ｝を含む場合、キャッシュストレージ３０に当該部分解析結果を保存しておく。例えば、解析手順｛Ｃ−Ａ−Ｂ｝が入力された場合、
【数３】
0006319694.tif 000004
をキャッシュストレージ３０に保存しておき、当該部分操作列を含む解析手順が投入された場合は、当該解析結果を利用する。
【００４２】
この時、例えば、解析手順｛Ｃ−Ｋ−Ａ｝のように、｛Ｋ−Ａ｝が含まれているものの先頭から一致しない解析手順が入力された場合、解析手順実行部２２は当該部分操作列｛Ｋ−Ａ｝の部分解析結果を保存しない。
【００４３】
なお、各親ノードが抽出した部分操作列を、さらに上位の親ノードに共有させてもよい。
【００４４】
なお、本データキャッシュ方法の全解析記録ステップは、図３のＳ０１〜Ｓ０３に相当し、部分操作列抽出ステップは図４のＳ０６〜Ｓ０７に相当し、部分解析結果記録ステップは図４のＳ０８〜Ｓ１０に相当する。
また、上位転送ステップは図４のＳ１１〜Ｓ１２に相当し、ノード間共通操作列抽出ステップは図４のＳ１４〜Ｓ１５に相当し、下位転送ステップは図４のＳ１６〜Ｓ１７に相当する。
【００４５】
４．プログラム
本プログラムは、上記データキャッシュ方法をコンピュータに実行させるためのプログラムである。ネットワーク等で接続された複数のコンピュータに本プログラムを実行させることで上記データキャッシュ方法を実現できる。
【００４６】
（効果）
本発明は、多数のサーバにて構築される木構造の構造化オーバレイに蓄積されているトラフィックデータやセンサデータ等の時系列データ解析する際に、過去の解析手順から頻繁に利用される解析手順とその結果を記録しておき、新たな解析手順が投入された場合、過去の似た解析手順の結果を再利用することで、解析時間を短縮する技術に関する。また、時系列データの特徴である近接性（近い時間のデータ同士は相関関係が強い）を考慮し、近い時間の時系列データを保存しているサーバ間で頻繁に利用される解析手順を共有しておくことで、互いの解析手順の再利用性を向上させる。
【符号の説明】
【００４７】
１０：経路制御モジュール
２０：キャッシュストレージコントローラ
２１：部分操作列抽出部
２２：解析手順実行部
２３：情報共有部
３０：キャッシュストレージ
４０：データストレージ
【図１】
0006319694.tif 000005
【図２】
0006319694.tif 000006
【図３】
0006319694.tif 000007
【図４】
0006319694.tif 000008
【図５】
0006319694.tif 000009
【図６】
0006319694.tif 000010