(57)【要約】  情報処理装置（１０）は、本体データと順序データとを含む格納データを書き込まれた順序で保持する複数の記憶領域（１０６、１０７、１０８）を有する記憶部（１０５）と、本体データと順序データとを含む複数個の受信データを個別に受信する受信部（１０１）と、記憶領域（１０６、（又は１０７、１０８））の末尾より一つまたは複数の格納データに含まれる順序データと、受信データに含まれる順序データとを比較した結果に基づいて、当該受信データを記憶領域（１０６、（又は１０７、１０８））に書き込むか否かを判定する比較部（１０２）と、比較部（１０２）の判定に応じて当該受信データを格納データとして記憶領域（１０６、（又は１０７、１０８））に書き込む書込部（１０３）と、を備える。
2011070725.tif 000002
【特許請求の範囲】
【請求項１】
本体データと、前記本体データが処理される順序を示す順序データと、を含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域を有する記憶手段と、
前記本体データと、前記順序データとを含む複数個の受信データを個別に受信する受信手段と、
前記複数の記憶領域に含まれる一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、前記受信手段によって受信された前記受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記一の記憶領域に書き込むか否かを判定する比較手段と、
前記比較手段によって、当該受信データを前記一の記憶領域に書き込むと判定されたとき、当該受信データを前記格納データとして前記一の記憶領域に書き込む書込手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
請求項１に記載の情報処理装置であって、
前記比較手段は、前記一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データが示す順序のうち最も早い順序を基準として、前記受信手段によって受信された前記受信データに含まれる前記順序データの示す順序が前記最も早い順序と等しい、またはより遅いとき、当該受信データを前記一の記憶領域に書き込むと判定することを特徴とする情報処理装置。
【請求項３】
請求項１または２に記載の情報処理装置であって、
前記比較手段によって、当該受信データを前記一の記憶領域に書き込まないと判定されたとき、
前記比較手段は、他の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、当該受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記他の記憶領域に書き込むか否かを判定することを特徴とする情報処理装置。
【請求項４】
請求項１乃至３いずれか１項に記載の情報処理装置であって、
前記比較手段によって、前記複数の記憶領域のいずれに対しても、当該受信データを書き込まないと判定されたとき、前記記憶手段に新規の記憶領域を追加する記憶領域追加手段を備え、
前記書込手段は、前記記憶領域追加手段によって追加された前記新規の記憶領域に、当該受信データを書き込むことを特徴とする情報処理装置。
【請求項５】
請求項１乃至４いずれか１項に記載の情報処理装置であって、
前記記憶領域の各々から逐次アクセスで前記格納データを読み出し、読み出された前記格納データの夫々に含まれる前記順序データに基づいて、各々の前記格納データをマージするマージ手段を備えることを特徴とする情報処理装置。
【請求項６】
請求項５に記載の情報処理装置であって、
前記マージ手段は、複数の前記記憶領域の夫々から、各々の前記記憶領域に対する比較判定に用いられた前記格納データの数以上の前記格納データを読み出し保持する第１保持処理を実行した後、保持された複数の前記格納データのうち最も早い順序を示す前記順序データを有する前記格納データを出力する出力処理と、出力された前記格納データが保持されていた前記記憶領域の先頭から前記格納データを読み出し保持する第２保持処理と、を交互に繰り返すことによって、前記格納データをマージすることを特徴とする情報処理装置。
【請求項７】
請求項５または６に記載の情報処理装置であって、
前記マージ手段によってマージされる前記格納データに含まれる前記順序データのうち最も早い値である開始値、または最も遅い値である終了値の少なくとも一方を設定するマージ範囲設定手段を備え、
前記マージ手段は、前記マージ範囲設定手段によって設定された前記終了値または前記開始値に基づいて、前記記憶領域から前記格納データを読み出す開始位置または終了位置を決定し、決定された前記開始位置から前記終了位置までの前記格納データを読み出すことを特徴とする情報処理装置。
【請求項８】
請求項７に記載の情報処理装置であって、
前記マージ手段は、探索範囲の中央の前記格納データに含まれる前記順序データと前記終了値とを比較する二分探索法を用いて前記終了位置を決定し、探索範囲の中央の前記格納データに含まれる前記順序データと前記開始値とを比較する二分探索法を用いて前記開始位置を決定することを特徴とする情報処理装置。
【請求項９】
請求項８に記載の情報処理装置であって、
前記比較手段によって比較判定された各々の前記記憶領域について、比較判定に用いられた前記格納データの数がｎ（１以上の整数）であるとき、
前記マージ手段は、二分探索法の探索範囲に含まれる前記格納データの個数が２ｎ−１以下となったとき、前記探索範囲の中で最も先頭の前記格納データを前記開始位置とし、または前記探索範囲の中で最も後方の前記格納データを前記終了位置として決定することを特徴とする情報処理装置。
【請求項１０】
請求項５乃至９いずれか１項に記載の情報処理装置であって、
前記書込手段は、前記本体データと前記順序データとを複数の前記記憶領域に分割して書き込み、
前記マージ手段は、前記順序データをマージした後に、前記本体データを前記順序データと同じ順番に並び替えることによって前記格納データをマージすることを特徴とする情報処理装置。
【請求項１１】
請求項５乃至１０いずれか１項に記載の情報処理装置であって、
前記格納データまたは前記受信データは複数種の前記順序データを含み、
前記マージ手段は、複数種の前記順序データの夫々に基づいて前記格納データをマージすることを特徴とする情報処理装置。
【請求項１２】
請求項１乃至１１いずれか１項に記載の情報処理装置であって、
前記受信手段によって受信された前記受信データを保持し、保持された前記受信データに含まれる前記順序データに基づいて当該受信データを間欠的にソートするソート手段を備え、
前記比較手段は、前記ソート手段によってソートされた前記受信データを用いることを特徴とする情報処理装置。
【請求項１３】
請求項１２に記載の情報処理装置であって、
前記ソート手段は、所定時間ごとに前記受信データをソートすることを特徴とする情報処理装置。
【請求項１４】
請求項１２に記載の情報処理装置であって、
前記ソート手段は、保持された前記受信データが所定量に達した時、当該受信データをソートすることを特徴とする情報処理装置。
【請求項１５】
請求項１乃至１４いずれか１項に記載の情報処理装置であって、
前記受信手段によって受信された前記受信データが、予め定めた例外基準に適合するか否かを判定する例外判定手段を備え、
前記比較手段は、前記例外判定手段によって適合しないと判定された前記受信データを用いて比較判定することを特徴とする情報処理装置。
【請求項１６】
請求項１乃至１５いずれか１項に記載の情報処理装置であって、
前記複数の記憶領域のうち、所定数以下の前記格納データを保持している過少記憶領域が複数存在しているとき、複数の前記過少記憶領域に保持された前記格納データを読み出し、読み出した前記格納データを当該格納データに含まれる前記順序データに従って並べ替え、他の記憶領域に書き込む統合手段を備えることを特徴とする情報処理装置。
【請求項１７】
本体データと、前記本体データが処理される順序を示す順序データと、を含む複数個の受信データを個別に受信する受信ステップと、
前記本体データと前記順序データとを含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域に含まれる一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、前記受信ステップで受信された前記受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記一の記憶領域に書き込むか否かを判定する比較ステップと、
前記比較ステップで、当該受信データを前記一の記憶領域に書き込むと判定されたとき、当該受信データを前記格納データとして前記一の記憶領域に書き込む書込ステップと、
を備えることを特徴とする情報処理方法。
【請求項１８】
請求項１７に記載の情報処理方法であって、
前記比較ステップでは、前記一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データが示す順序のうち最も早い順序を基準として、前記受信手段によって受信された前記受信データに含まれる前記順序データの示す順序が前記最も早い順序と等しい、またはより遅いとき、当該受信データを前記一の記憶領域に書き込むと判定することを特徴とする情報処理方法。
【請求項１９】
請求項１７または１８に記載の情報処理方法であって、
前記比較ステップでは、当該受信データを前記一の記憶領域に書き込まないと判定されたとき、他の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、当該受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記他の記憶領域に書き込むか否かを判定することを特徴とする情報処理方法。
【請求項２０】
請求項１７乃至１９いずれか１項に記載の情報処理方法であって、
前記比較ステップで、前記複数の記憶領域の全部に対して、当該受信データを書き込まないと判定されたとき、新規の記憶領域を追加する記憶領域追加ステップを備え、
前記書込ステップでは、前記記憶領域追加ステップで追加された前記新規の記憶領域に、当該受信データを書き込むことを特徴とする情報処理方法。
【請求項２１】
請求項１７乃至２０いずれか１項に記載の情報処理方法であって、
前記記憶領域の各々から逐次アクセスで前記格納データを読み出し、読み出された前記格納データの夫々に含まれる前記順序データに基づいて、各々の前記格納データをマージするマージステップを備えることを特徴とする情報処理方法。
【請求項２２】
請求項２１に記載の情報処理方法であって、
前記マージステップでは、複数の前記記憶領域の夫々から、各々の前記記憶領域に対する比較判定に用いられた前記格納データの数以上の前記格納データを読み出し保持する第１保持ステップを実行した後、保持された複数の前記格納データのうち最も早い順序を示す前記順序データを有する前記格納データを出力する出力ステップと、出力された前記格納データが保持されていた前記記憶領域の先頭から前記格納データを読み出し保持する第２保持ステップと、を交互に繰り返すことによって、前記格納データをマージすることを特徴とする情報処理方法。
【請求項２３】
請求項２１または２２に記載の情報処理方法であって、
前記マージステップでマージされる前記格納データに含まれる前記順序データのうち最も早い値である開始値、または最も遅い値である終了値の少なくとも一方を設定するマージ範囲設定ステップを備え、
前記マージステップでは、前記マージ範囲設定ステップで設定された前記終了値または前記開始値に基づいて、前記記憶領域から前記格納データを読み出す開始位置または終了位置を決定し、決定された前記開始位置から前記終了位置までの前記格納データを読み出すことを特徴とする情報処理方法。
【請求項２４】
請求項２３に記載の情報処理方法であって、
前記マージステップは、探索範囲の中央の前記格納データに含まれる前記順序データと前記終了値とを比較する二分探索法を用いて前記終了位置を決定し、探索範囲の中央の前記格納データに含まれる前記順序データと前記開始値とを比較する二分探索法を用いて前記開始位置を決定することを特徴とする情報処理方法。
【請求項２５】
請求項２４に記載の情報処理方法であって、
前記比較ステップによって比較判定された各々の前記記憶領域について、比較判定に用いられた前記格納データの数がｎ（１以上の整数）であるとき、
前記マージステップは、二分探索法の探索範囲に含まれる前記格納データの個数が２ｎ−１以下となったとき、前記探索範囲の中で最も先頭の前記格納データを前記開始位置とし、または前記探索範囲の中で最も後方の前記格納データを前記終了位置として決定することを特徴とする情報処理方法。
【請求項２６】
請求項２１乃至２５いずれか１項に記載の情報処理方法であって、
前記書込ステップでは、前記本体データと前記順序データとを分割して前記一の記憶領域に書き込み、
前記マージステップでは、前記順序データをマージした後に、前記本体データを前記順序データと同じ順番に並び替えることによって前記格納データをマージすることを特徴とする情報処理方法。
【請求項２７】
請求項２１乃至２６いずれか１項に記載の情報処理方法であって、
前記格納データまたは前記受信データは複数種の前記順序データを含み、
前記マージステップでは、複数種の前記順序データの夫々に基づいて前記格納データをマージすることを特徴とする情報処理方法。
【請求項２８】
請求項１７乃至２７いずれか１項に記載の情報処理方法であって、
前記受信ステップで受信された前記受信データを保持し、保持された前記受信データに含まれる前記順序データに基づいて当該受信データを間欠的にソートするソートステップを備え、
前記比較ステップでは、前記ソートステップでソートされた前記受信データを用いることを特徴とする情報処理方法。
【請求項２９】
請求項２８に記載の情報処理方法であって、
前記ソートステップでは、所定時間ごとに前記受信データをソートすることを特徴とする情報処理方法。
【請求項３０】
請求項２８に記載の情報処理方法であって、
前記ソートステップでは、保持された前記受信データが所定量に達した時、当該受信データをソートすることを特徴とする情報処理方法。
【請求項３１】
請求項１７乃至３０いずれか１項に記載の情報処理方法であって、
前記受信ステップで受信された前記受信データが、予め定めた例外基準に適合するか否かを判定する例外判定ステップを備え、
前記比較ステップでは、前記例外判定ステップで適合しないと判定された前記受信データを用いて比較判定することを特徴とする情報処理方法。
【請求項３２】
請求項１７乃至３１いずれか１項に記載の情報処理方法であって、
前記複数の記憶領域のうち、所定数以下の前記格納データを保持している過少記憶領域が複数存在しているとき、複数の前記過少記憶領域に保持された前記格納データを読み出し、読み出した前記格納データを当該格納データに含まれる前記順序データに従って並べ替え、他の記憶領域に書き込む統合ステップを備えることを特徴とする情報処理方法。
【請求項３３】
コンピュータが読み出し可能な記憶媒体に格納されるプログラムであって、
本体データと、前記本体データが処理される順序を示す順序データと、を含む複数個の受信データを個別に受信する受信処理と、
前記本体データと前記順序データとを含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域に含まれる一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、前記受信処理で受信された前記受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記一の記憶領域に書き込むか否かを判定する比較処理と、
前記比較処理で、当該受信データを前記一の記憶領域に書き込むと判定されたとき、当該受信データを前記格納データとして前記一の記憶領域に書き込む書込処理と、
を前記コンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
計算機で扱われる代表的なデータに時系列データがある。時系列データはそれぞれが時刻情報を含む複数個のレコードであり、当該時刻情報はタイムスタンプと呼ばれる。例えば、温度センサから送信される時系列データは各レコードがタイムスタンプと温度情報から構成されることがある。例えば、前記レコードの一例は「２００９年７月１４日１０時１分２７秒」の温度は「２７．４℃」であったことを表す。ここで、「２００９年７月１４日１０時１分２７秒」はタイムスタンプ、「２７．４℃」は本体データである。ＰＯＳ端末の販売データ、ＧＰＳを搭載した移動体からの位置データ、計算機の負荷データ、プログラムのログ、入退場ゲートからのデータ、株価データなど、時系列データは多く存在する。時系列データには、誤った情報を修正する場合を除いて、基本的に更新されない性質がある。【０００３】
時系列データは、多くの場合にタイムスタンプ順の処理を必要とする。しかし、ネットワークから時系列データのレコードを次々に受信するとき、受信順がタイムスタンプ順とは限らない。なぜなら、送信元の時計のずれやネットワーク遅延が原因で順序が入れ替わるためである。障害が原因で送信されず、復旧後に再送されたレコードのタイムスタンプは数日前の場合もある。【０００４】
受信したレコードを一時的にメモリに記憶し、メモリ内でソートしてからハードディスク等にタイムスタンプ順に書き込む方法には限界がある。例えば特許文献１（特開平９−２４４９８４号公報）に記された方法では、求めたネットワークの最大遅延時間の範囲内で、イベントをメモリ内でソートして順序を補正する。【０００５】
このため、時系列データは、ＲＤＢＭＳ（Ｒｅｌａｔｉｏｎａｌ  ＤａｔａＢａｓｅ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ）などを使用し、インデックスをつけて記憶することが一般的である。インデックスは、レコードとは別にハードディスク等に記憶されるメタ情報で、どのレコードがハードディスク等のどこに書き込まれたかを表す。タイムスタンプのインデックスをＢ＋木で作成すると、タイムスタンプ順にレコードを書き込まなくとも、タイムスタンプ順にレコードを読み出せる。例えば、非特許文献１はＲＤＢＭＳで通信システムから発生する大量の時系列データを分析するシステムについて記している。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平９−２４４９８４号公報
【非特許文献】
【０００７】
【非特許文献１】Ｌｕｋａｓｚ  Ｇｏｌａｂ，  ｅｔ  ａｌ，  "Ｓｔｒｅａｍ  Ｗａｒｅｈｏｕｓｉｎｇ  ｗｉｔｈ  ＤａｔａＤｅｐｏｔ"，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３５ｔｈ  ＳＩＧＭＯＤ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｄａｔａ，  ２００９
【発明の概要】
【０００８】
しかし、特許文献１の技術を用いた場合、時計のずれや障害による再送などが原因で、通常のネットワーク遅延を超えるタイムスタンプのずれが発生した場合には対応できない。また、停電などが原因で、メモリ内のデータが失われる危険性がある。
【０００９】
また、非特許文献１のようにインデックスをつけてハードディスク等にデータを書き込むときには、レコードを書き込み、インデックスを更新する２段階のハードディスク等へのアクセスが発生する。データを読み出すときにも、インデックスを読み出して、その情報に基づいてレコードを読み出す２段階のハードディスク等へのアクセスが発生する。シークを伴う２段階のアクセスはランダムアクセスとなる。ハードディスクは、回転する磁気ディスクから磁気ヘッドでデータを読み出す構造上、シーケンシャル（逐次）アクセスは高速であるが、磁気ヘッドを動かすシークを伴うランダムアクセスは低速である。ＮＡＮＤフラッシュメモリ等を用いた半導体ディスクにおいても、ブロック単位の書き換えとキャッシュのために、ランダムアクセスよりシーケンシャルアクセスのほうが高速であることが知られている。時系列データがタイムスタンプ順に書き込まれていれば、タイムスタンプ順に処理するとき、シーケンシャルアクセスで高速に読み出せる。すなわち、非特許文献１を用いた場合、受信順序の問題が解決される反面、性能の低下が懸念される場合がある。
【００１０】
本発明の目的は、処理順序が定められた複数個のデータを個別に受信し、当該複数個のデータを受信した順序で保持するとき、より迅速かつ正確に当該複数個のデータを並び替える情報処理装置、情報処理方法またはプログラムを提供することにある。
【００１１】
本発明によれば、本体データと、前記本体データが処理される順序を示す順序データと、を含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域を有する記憶手段と、前記本体データと、前記順序データとを含む複数個の受信データを個別に受信する受信手段と、前記複数の記憶領域に含まれる一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、前記受信手段によって受信された前記受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記一の記憶領域に書き込むか否かを判定する比較手段と、前記比較手段によって、当該受信データを前記一の記憶領域に書き込むと判定されたとき、当該受信データを前記格納データとして前記一の記憶領域に書き込む書込手段と、を備えることを特徴とする情報処理装置が提供される。
【００１２】
また、本発明によれば、本体データと、前記本体データが処理される順序を示す順序データと、を含む複数個の受信データを個別に受信する受信ステップと、前記本体データと前記順序データとを含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域に含まれる一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、前記受信ステップで受信された前記受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記一の記憶領域に書き込むか否かを判定する比較ステップと、前記比較ステップで、当該受信データを前記一の記憶領域に書き込むと判定されたとき、当該受信データを前記格納データとして前記一の記憶領域に書き込む書込ステップと、を備えることを特徴とする情報処理方法が提供される。
【００１３】
さらに、本発明によれば、コンピュータが読み出し可能な記憶媒体に格納されるプログラムであって、本体データと、前記本体データが処理される順序を示す順序データと、を含む複数個の受信データを個別に受信する受信処理と、前記本体データと前記順序データとを含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域に含まれる一の記憶領域に保持された前記格納データのうち、末尾より一つまたは複数の前記格納データに含まれる前記順序データと、前記受信処理で受信された前記受信データに含まれる前記順序データとを比較した結果に基づいて、当該受信データを前記一の記憶領域に書き込むか否かを判定する比較処理と、前記比較処理で、当該受信データを前記一の記憶領域に書き込むと判定されたとき、当該受信データを前記格納データとして前記一の記憶領域に書き込む書込処理と、を前記コンピュータに実行させることを特徴とするプログラムが提供される。
【００１４】
上記発明によれば、より迅速かつ正確に複数個のデータを並び替える情報処理装置、情報処理方法またはプログラムが提供される。
【図面の簡単な説明】
【００１５】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００１６】
【図１】第１の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図２】第１の実施の形態に係る記憶部に記憶されている格納データの一例を示す図である。
【図３】第１の実施の形態に係る記憶部に記憶されている格納データの一例を示す図である。
【図４】第１の実施の形態に係る記憶部に記憶されている格納データの一例を示す図である。
【図５】第１の実施の形態に係る受信データを書き込む動作を示すフローチャートである。
【図６】第１の実施の形態に係る格納データをマージする動作を示すフローチャートである。
【図７】第２の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図８】第３の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図９】第３の実施の形態に係る読み出し開始位置を決定する動作のフローチャートである。
【図１０】第３の実施の形態に係る読み出し終了位置を決定する動作のフローチャートである。
【図１１】第４の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図１２】第４の実施の形態に係る統合部の動作の一例を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００１８】
〔第１の実施の形態〕
第１の実施の形態を説明する。第１の実施の形態のブロック図を図１に示す。図１に示す情報処理装置１０は、受信部１０１と、比較部１０２と、書込部１０３と、マージ部１０４と、記憶部１０５と、を備える。
【００１９】
記憶部１０５は、格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域１０６、１０７、１０８を有する。記憶領域１０６、１０７、１０８で保持される格納データは、本体データと、本体データが処理される順序を示す順序データと、から構成される。ここで、順序データは、上述したような時系列データのタイムスタンプであってもよい。また、例えば、ネットワークを流れるシーケンス番号のついたパケットの記憶に適用できる。また、例えば、シリアル番号のついた製品出荷データの記憶に適用できる。また、例えば、これらの一部または全部を組み合わせた形態であってもよい。
【００２０】
記憶部１０５は、ハードディスク、ＮＡＮＤフラッシュメモリやＤＲＡＭを用いた半導体メモリ、光磁気ディスクなど、データの書き込みと読み出しができる媒体である。本発明は、特に、逐次アクセス性能が、ランダムアクセス性能を大きく上回る媒体において効果が高い。記憶部１０５は１つのみを図示しているが、記憶媒体は１つでも、複数でもよい。例えば、ハードディスク等をＲＡＩＤで構成してもよい。
【００２１】
記憶領域１０６、１０７、１０８は、記憶部１０５に物理的または論理的に確保される連続した領域である。記憶領域１０６、１０７、１０８は、記憶部１０５に物理的に確保されてもよいし、論理的に確保されてもよい。論理的に確保された記憶領域１０６、１０７、１０８とは、例えば、複数のハードディスクをＲＡＩＤ機能でまとめた仮想的なハードディスク、オペレーティングシステム（ＯＳ）が提供する抽象化されたブロックデバイス、ファイルシステムが提供するファイル、などである。論理的に確保された記憶領域１０６、１０７、１０８は、完全に物理的に連続しているとは限らないが、ＯＳや断片化解消（デフラグ）プログラムによってなるべく連続した領域を使用するように割り当てられる。
【００２２】
記憶領域１０６、１０７、１０８を物理的に確保した場合、逐次アクセスによる処理速度を向上させるメリットがある。また、記憶領域１０６、１０７、１０８を論理的に確保した場合、比較的平易なプログラミングで本発明の処理を実現することができるメリットがある。
【００２３】
受信部１０１は、本体データと、順序データとを含む複数個の受信データを個別に受信する。受信データは、図示されない計算機、センサ、通信機器、携帯電話、ＰＯＳ端末等から送信され、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＬＡＮ）やＷｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＷＡＮ）等のネットワークを介して伝送されてもよい。また、受信部１０１は、ネットワークを介することなく、情報処理装置１０内を伝送した受信データを受信してもよい。なお、受信データは固定長でも可変長でもよく、バイナリ形式でもテキスト形式でもよい。
【００２４】
比較部１０２は、受信部１０１によって受信された受信データを複数の記憶領域１０６、１０７、１０８のいずれに書き込むかを比較判定により判定する。より詳細には、まず比較部１０２は、記憶領域１０６に保持された格納データのうち、末尾より一つまたは複数の格納データに含まれる順序データと、受信部１０１によって受信された受信データに含まれる順序データとを比較した結果に基づいて、当該受信データを記憶領域１０６に書き込むか否かを判定する。その判定基準は、記憶領域１０６に保持された格納データのうち、末尾より一つまたは複数の前記格納データに含まれる順序データが示す順序のうち最も早い順序を基準として、受信部１０１によって受信された受信データに含まれる順序データの示す順序が上記最も早い順序と等しい、またはより遅いとき、当該受信データを記憶領域１０６に書き込むと判定する。
【００２５】
仮に、当該受信データを記憶領域１０６に書き込まないと判定されたとき、比較部１０２は、記憶領域１０７に保持された格納データのうち、末尾より一つまたは複数の格納データに含まれる順序データと、当該受信データに含まれる順序データとを比較した結果に基づいて、当該受信データを記憶領域１０７に書き込むか否かを判定する。さらに、当該受信データを記憶領域１０７に書き込まないと判定されたとき、比較部１０２は、記憶領域１０８に保持された格納データのうち、末尾より一つまたは複数の格納データに含まれる順序データと、当該受信データに含まれる順序データとを比較した結果に基づいて、当該受信データを記憶領域１０８に書き込むか否かを判定する。
【００２６】
なお、上述した比較部１０２による比較判定は本発明の一例であって、この方法に限定されない。例えば、図１では、記憶部１０５は３つの記憶領域１０６、１０７、１０８を有するように図示しているが、さらに多くの記憶領域が存在するのであれば、比較部１０２は、その記憶領域に対しても上述の比較判定を行ってもよい。また、比較部１０２が比較判定とする対象は、一つずつであるように説明したが、複数の記憶領域に対して同時に比較判定を行ってもよい。
【００２７】
さらに、比較部１０２が比較判定を行う記憶領域の順序は、上述の順序に限らない。本実施形態のように、複数の記憶領域１０６、１０７、１０８を同一の記憶部１０５に確保する場合、最初に比較判定の対象となる記憶領域を特定しておくと、当該記憶領域に格納データが偏るので、逐次アクセスが増えて性能が高まる。それぞれの記憶領域が別の記憶媒体に確保されている場合は、最初に比較判定の対象となる記憶領域を均等に振り分ける等によってレコード数が偏らないように追記することで、複数の記憶媒体へのアクセスの並列性が高まり性能が高まる。すなわち、制約条件を満たす複数の記憶領域から最適な追記先を選択する方法は、記憶媒体の物理的な構成によって異なる。
【００２８】
書込部１０３は、比較部１０２によって、書き込み先として判定された記憶領域１０６（または１０７、１０８）に、当該受信データを格納データとして書き込む。
【００２９】
マージ部１０４は、記憶領域１０６、１０７、１０８の各々から逐次アクセスで格納データを読み出し、読み出された格納データの夫々に含まれる順序データに基づいて、各々の格納データをマージする。このとき、読み出す対象の記憶領域の数が少なければ逐次アクセスの読み出し（シーケンシャルリード）が多くなる。
【００３０】
なお、マージ部１０４は、マージした格納データを、ネットワークを介して図示されない他の計算機、記憶装置、表示装置、印刷装置などに送信してもよいし、情報処理装置１０内で他の処理に使用してもよい。マージ部１０４が、各々の記憶領域１０６、１０７、１０８内に保持された格納データをマージする処理は、自律的に行われてもよいし、他の装置からの要求に応じて他律的に行われてもよい。
【００３１】
情報処理装置１０に内包される構成の全部または一部は、ハードウェアで実現されてもよいし、あるいは、プロセッサに処理を実行させるプログラム（またはプログラムコード）で実現されてもよい。プロセッサは、不揮発性メモリなどの記録媒体からそのプログラムを読み出し実行する。
【００３２】
情報処理装置１０に内包される構成がプログラムによって実施される場合、当該プログラムはプロセッサ（コンピュータ）が読み出し可能な記憶媒体に格納される。そして、当該プログラムは、本体データと、本体データが処理される順序を示す順序データと、を含む複数個の受信データを個別に受信する受信処理を、プロセッサに実行させる。また、当該プログラムは、本体データと順序データとを含む格納データを書き込まれた順序でそれぞれ保持する複数の記憶領域に含まれる一の記憶領域に保持された格納データのうち、末尾より一つまたは複数の格納データに含まれる順序データと、受信処理で受信された受信データに含まれる順序データとを比較した結果に基づいて、当該受信データを一の記憶領域に書き込むか否かを判定する比較処理を、プロセッサに実行させる。また、当該プログラムは、比較処理で当該受信データを一の記憶領域に書き込むと判定されたとき、当該受信データを格納データとして一の記憶領域に書き込む書込処理を、プロセッサに実行させる。
【００３３】
記憶部１０５に記憶される格納データの一例を図２に示す。図２に示す記憶領域１０６、１０７、１０８夫々に含まれる各長方形は、各々の記憶領域１０６、１０７、１０８に保持される格納データで、斜線の左側の数値が受信順序、右側の数値が当該格納データに含まれる順序データが示す処理順序を表している。なお、受信順序、処理順序ともに昇順であり、小さい値ほど早い順序、大きい値ほど遅い順序とする。また、これより以降の説明に用いられる順序データも同様に、小さい値ほど早い順序、大きい値ほど遅い順序を示すものとする。
【００３４】
ある時点において、記憶部１０５が図２に示す状態であったと仮定して、本実施形態の情報処理装置１０の動作をより具体的に説明する。例えば、この状態で、受信部１０１が「受信順序／処理順序＝９／９」の受信データを受信したとする。
【００３５】
このとき、比較部１０２は、記憶領域１０６の末尾より一つの格納データを参照すると、当該格納データの処理順序は「１０」であり、当該受信データの処理順序はこれより早い。従って、比較部１０２は、当該受信データを記憶領域１０６に書き込まないと判定する。続いて、比較部１０２は、記憶領域１０７の末尾より一つの格納データを参照すると、当該格納データの処理順序は「４」であり、当該受信データの処理順序はこれより遅い。従って、比較部１０２は、当該受信データを記憶領域１０７に書き込むと判定し、書込部１０３は、当該受信データを記憶領域１０７に書き込む。
【００３６】
比較部１０２が各記憶領域１０６、１０７、１０８の末尾より一つの格納データを参照し、上記の条件で格納データを記憶領域に追記した場合、例えば図３に示すように、それぞれの記憶領域において格納データが処理順序通りに記憶される。それぞれの記憶領域において格納データが処理順序通りであるため、マージ部１０４はこれら格納データをマージして処理順序通りに格納データを出力できる。
【００３７】
上記において比較部１０２は、各々の記憶領域１０６、１０７の末尾より一つの格納データを参照するように説明したが、末尾より複数の格納データを参照してもよい。すなわち、比較部１０２が、記憶領域１０６の末尾より二つの格納データを参照すると、当該格納データの処理順序は「８」と「１０」である。これらの処理順序のうち最も早い順序は「８」であり、これを基準とすると当該受信データの処理順序はこれより遅い。従って、比較部１０２は、当該受信データを記憶領域１０６に書き込むと判定し、書込部１０３は、当該受信データを記憶領域１０６に書き込む。
【００３８】
比較部１０２が各記憶領域１０６、１０７、１０８の末尾より二つの格納データを参照し、上記の条件で格納データを記憶領域に追記した場合、例えば図４に示すように、各記憶領域１０６、１０７、１０８に書き込まれた受信データはほぼ処理順序通りであるが、一部処理順序と異なる順序で書き込まれる可能性がある。
【００３９】
なお、ここでは、全て異なる処理順序を示す格納データと受信データとを比較判定する事例を説明したが、等しい順序を示す格納データと受信データとを比較判定する場合があってもよい。この場合、比較部１０２は、当該記憶領域に当該受信データを書き込むと判定する。
【００４０】
このように、比較部１０２が一つの記憶領域に対する比較判定に用た格納データの個数によって、受信データの書き込み先が変化する。比較部１０２によって比較判定された各々の記憶領域１０６、１０７、１０８について、比較判定に用いられた格納データの数がｎ（１以上の整数）である場合、情報処理装置１０が受信データを記憶部１０５に書き込むまでの動作は、図５のフローチャートのように表すことができる。
【００４１】
まず、受信部１０１は複数個の受信データを個別に受信する（ステップＳ１１）。次に、比較部１０２は変数Ｔｒに受信データに含まれる順序データを代入する（ステップＳ１２）。そして、比較部１０２はループ変数ｉに１を代入し（ステップＳ１３）、ｉ番目の記憶領域（記憶領域１０６、１０７、１０８のいずれか）に記憶されている格納データの数をｍに代入し（ステップＳ１４）、ｎ≦ｍであるとき（ステップＳ１５のＹＥＳ）、変数Ｔｐに、ｉ番目の記憶領域のｍ−ｎ＋１番目からｍ番目（末尾の格納データよりｎ個）の格納データに含まれる順序データのうち最も早い順序を示す値を代入する（ステップＳ１６）。Ｔｒ＜Ｔｐであるとき（ステップＳ１７のＮＯ）、次の記憶領域を検索するためにループ変数ｉに１を加え（ステップＳ１８）、再びステップＳ１４に移行する。ｎ＞ｍであるとき（ステップＳ１５のＮＯ）、またはＴｒ≧Ｔｐであるとき（ステップＳ１７のＹＥＳ）、比較部１０２はｉ番目の記憶領域を受信データの書き込み先として判定し、書込部１０３はｉ番目の記憶領域に受信データを格納データとして書き込む（ステップＳ１９）。
【００４２】
上述のような処理によって各々の記憶領域１０６、１０７、１０８に書き込まれた格納データは、図６のフローチャートに示す手順で、マージ部１０４によってマージされる。まず、マージ部１０４は、記憶領域１０６、１０７、１０８の夫々からｎ個以上の格納データを読み出して保持する（ステップＴ１１）。ただし、ステップＴ１１において、格納データが１つも書き込まれていない記憶領域からは、格納データを読み出さなくてもよい。そして、マージ部１０４は、ステップＴ１１で保持された複数の格納データのうち最も早い順序を示す順序データを有する格納データを出力する（ステップＴ１２）。マージ部１０４は各々の記憶領域１０６、１０７、１０８に保持された全ての格納データが出力済みか否かを判断し、出力済みであれば（ステップＴ１３のＹＥＳ）、処理を終了する。出力済みでなければ（ステップＴ１３のＮＯ）、ステップＴ１２で出力した格納データが記憶されていた記憶領域の先頭から次の格納データを読み出して保持する（ステップＴ１４）、ステップＴ１２に移行する。ただし、ステップＴ１４において、当該記憶領域に格納データが残っていなければ読み出さずにステップＴ１２に移行してもよい。
【００４３】
上述のようなマージ部１０４の処理は、長さがｎ以上の優先度付きキュー（英名：Ｐｒｉｏｒｉｔｙ  Ｑｕｅｕｅ）が使える。優先度付きキューに入れたデータはソートされた状態で取り出せる。つまり、順不同で入れた格納データを、順序データ順に取り出せる。優先度付きキューは当業者に広く使われており多くの実装が公開されているため、実現方法の説明は省略する。比較部１０２による比較判定の際に記憶領域１０６（または１０７、１０８）から参照する格納データの数ｎを大きくし、さらに優先度付きキューの長さもそれに合わせて大きくすると、使用する記憶領域の数が減る反面、優先度付きキューが使用するメモリ量は増える。
【００４４】
以上、説明したように動作することで、本実施形態の情報処理装置１０は、受信順序と処理順序とが異なる受信データをマージして出力することができるが、これは予め用意された記憶領域１０６、１０７、１０８で十分に一連の処理が可能であることを前提にしている。ただし、比較部１０２によって、予め用意された記憶領域１０６、１０７、１０８のいずれに対しても、受信データを書き込まないと判定されたとき、記憶部１０５に新規の記憶領域を追加する機能があれば、書込部１０３は、この機能によって追加された新規の記憶領域に、当該受信データを書き込むことができる。
【００４５】
また、本実施形態では説明の簡単化のために順序データが１つの場合を説明したが、本発明は順序データが２種類以上あっても適用できる。例えば、本体データに、ある事象の開始時刻と終了時刻の２種類のタイムスタンプがつけられることがある。マージ部１０４は、複数種類の順序データがあるとき、それぞれの記憶領域においてすべての種類の順序データについて順序通りになるようにマージすることが望ましい。それぞれの記憶領域において本実施形態のように格納データを書き込めば、マージ部１０４は、複数種の順序データの夫々に基づいて、格納データをマージすることができる。
【００４６】
ここで、第１の実施形態の効果について説明する。本実施形態は、各々の記憶領域１０６、１０７、１０８には、比較判定の制約条件に適合する順序でデータが書き込まれるので、それぞれの記憶領域内において記憶された順序と、処理順序とがある程度一致する。従って、マージ部１０４は、逐次アクセスでマージ可能となり、迅速にマージすることができる。
【００４７】
また、本実施形態は、各々の記憶領域１０６、１０７、１０８における比較判定に用いられた格納データの数：ｎの値を調整することによって、比較判定の制約条件を変えることができる。使用される記憶領域の数を減らす場合はｎの値を大きくすればよく、各々の記憶領域内の先頭からの順序と、格納データの処理順序との一致度を高くしたければ、ｎの値を大きくすればよい。
【００４８】
〔第２の実施の形態〕
第２の実施の形態について説明する。第２の実施の形態のブロック図を図７に示す。図７に示すように、第２の実施の形態における情報処理装置２０は、受信部１０１によって受信された受信データが、予め定めた例外基準に適合するか否かを判定する例外判定部２０１を備えることが第１の実施の形態と異なる。なお、第１の実施の形態と同様の要素については第１の実施の形態と同一の符号を付して詳細な説明を省略する。
【００４９】
本実施形態において、比較部１０２は、例外判定部２０１によって適合しないと判定された受信データを用いて比較判定し、書込部１０３は、比較部１０２の比較判定の結果に応じて記憶領域１０６、１０７、１０８のいずれかに受信データを書き込む。
【００５０】
ここで、例外基準は、システムの特性によって異なる。例えば、通常は順序データ（タイムスタンプ）が現在時刻から１０分以内におさまるシステムでは、現在時刻より１０分以上差のある順序データを持った受信データを例外とすることができる。あるいは、記憶部１０５に書き込まれた格納データに含まれる順序データと比較してもよい。さらに、順序データに含まれる順序データや本体データが、不正な値になっている場合も、例外してもよい。
【００５１】
例外判定部２０１によって例外であると判定された受信データは、破棄してもよいし、記憶部１０５に例外とされた受信データを書き込む専用の記憶領域を用意し、当該記憶領域に書き込んでもよい。例えば、ＲＤＢＭＳを使用すれば、順序データの順序に関係なく格納データを書き込め、かつ、順序データ順に格納データを読み出せる。順序データ順に格納データを読み出せれば、格納データをマージ部１０４でマージすることができる。
【００５２】
また、例外判定部２０１は、書込部１０３が受信データの書き込みに失敗した場合、当該受信データも例外として判定してもよい。例えば、制約条件を満たす記憶領域がないために書込部１０３が例外判定部２０１に受信データの書き込み失敗を通知した場合、例外判定部２０１は当該受信データを例外と判定してもよい。
【００５３】
第２の実施の形態は、例外的なデータが記憶領域１０６、１０７、１０８に記憶されることを防ぐことができる。また、比較部１０２によって、予め用意されている記憶領域１０６、１０７、１０８の全部に書き込めないと判定されたとき、新規の記憶領域を追加する方式を採った場合、例外なデータを書き込むために不要に記憶領域が追加されることを防ぎ、書込部１０３またはマージ部１０４における処理速度の低下を防ぐことができる。
【００５４】
〔第３の実施の形態〕
第３の実施の形態について説明する。第３の実施の形態のブロック図を図８に示す。図８に示すように、情報処理装置３０は、マージ部１０４によってマージされる格納データに含まれる順序データのうち最も早い値である開始値、または最も遅い値である終了値の少なくとも一方を設定するマージ範囲設定部３０１を備えることが第１の実施の形態と異なる。なお、第１の実施の形態と同様の要素については第１の実施の形態と同一の符号を付して詳細な説明を省略する。
【００５５】
本実施形態において、マージ部１０４は、マージ範囲設定部３０１によって設定された終了値または開始値に基づいて、記憶領域１０６（または１０７、１０８）から格納データを読み出す開始位置または終了位置を決定し、決定された開始位置から終了位置までの格納データを読み出す。
【００５６】
順序データがタイムスタンプであって、２００８年のタイムスタンプを含む格納データを読み出すとき、マージ範囲設定部３０１は、開始値を「２００８年１月１日  ０時０分０秒」と設定し、終了値は「２００８年１２月３１日  ２３時５９分５９秒」と設定する。また、例えば、２００９年以降のレコードを読み出すとき、マージ範囲設定部３０１は、開始値を「２００９年１月１日  ０時０分０秒」と設定し、終了値は設定しない。読み出すレコードの範囲を効率よく決定するためには二分探索を応用できるが、比較判定に用いられた格納データの数ｎが２以上の整数である場合、記憶領域１０６、１０７、１０８に書き込まれた格納データの一部が処理順序と異なる順序で書き込まれている可能性があり、それを考慮する必要がある。以下に、本実施形態に適用可能な二分探索の事例を説明する。
【００５７】
図９は、読み出し開始位置を決定する動作のフローチャートである。下記説明において、変数Ｌはそれより前の格納データを読み出す必要がないことを表し、変数Ｒはそれより後の格納データは読み出す必要があることを表している。すなわち、変数Ｌから変数Ｒまでの格納データは読み出す必要があるか未知であって、探索範囲に含まれることを示している。まず、変数Ｌに１を、変数Ｒに記憶領域に記憶されている格納データの件数を、それぞれ代入して初期化し（ステップＳ３１）、不等号Ｒ−Ｌ＞２ｎ−１を評価して成立するとき（ステップＳ３２のＹＥＳ）、変数ｐに（Ｌ＋Ｒ）÷２を代入し、探索位置を決める（ステップＳ３３）。変数Ａにｐ件目（探索範囲の中央）の格納データに含まれる順序データを代入する（ステップＳ３４）。
【００５８】
マージ範囲設定部３０１によって設定された開始値と、ステップＳ３４で代入されたＡとを比較し、開始値がＡ以下であるとき（ステップＳ３５のＹＥＳ）、ｐ件目以降の格納データは読み出す必要があるため、変数Ｒにｐ−１を代入してステップＳ３２に戻る（ステップＳ３６）。開始値がＡを超えるとき（ステップＳ３５のＮＯ）、ｐ−ｎ＋１件目より前の格納データは読み出す必要がないため、変数Ｌにｐ−ｎ＋１を代入してステップＳ３２に戻る（ステップＳ３７）。
【００５９】
不等号Ｒ−Ｌ＞２ｎ−１を評価して成立しないとき、すなわち探索範囲に含まれる格納データの個数が２ｎ−１以下まで狭められたとき（ステップＳ３２のＮＯ）、Ｌ件目の格納データを読み出し開始位置とする（ステップＳ３８）。
【００６０】
図１０は、読み出し終了位置を決定する動作のフローチャートである。下記説明において、変数Ｌはそれより前の格納データを読み出す必要があることを表し、変数Ｒはそれより後の格納データは読み出す必要がないことを表し、変数Ｌから変数Ｒまでの格納データは読み出す必要があるか未知であって、探索範囲に含まれることを示している。まず、変数Ｌに１を、変数Ｒに記憶領域に記憶されている格納データの件数を、それぞれ代入して初期化し（ステップＴ３１）、不等号Ｒ−Ｌ＞２ｎ−１を評価して成立するとき（ステップＴ３２のＹＥＳ）、変数ｐに（Ｌ＋Ｒ）÷２を代入し、探索位置を決める（ステップＴ３３）。変数Ａにｐ件目（探索範囲の中央）の格納データに含まれる順序データを代入する（ステップＴ３４）。
【００６１】
マージ範囲設定部３０１によって設定された終了値と、ステップＴ３４で代入されたＡとを比較し、終了値がＡ未満であれば（ステップＴ３５のＹＥＳ）、ｐ＋ｎ−１件目より後の格納データは読み出す必要がないため、変数Ｒにｐ＋ｎ−１を代入してステップＴ３２に戻る（ステップＴ３６）。終了値がＡ以上であれば（ステップＴ３５のＮＯ）、ｐ件目以前の格納データは読み出す必要があるため、変数Ｌにｐ＋１を代入してステップＴ３２に戻る（ステップＴ３７）。
【００６２】
不等号Ｒ−Ｌ＞２ｎ−１を評価して成立しないとき、すなわち探索範囲に含まれる格納データの個数が２ｎ−１以下まで狭められたとき（ステップＴ３２のＮＯ）、Ｒ件目の格納データを読み出し終了位置とする（ステップＴ３８）。
【００６３】
図９と図１０に示した例で決定した範囲の格納データには、指定された範囲外の順序データをもつ格納データも含まれる場合がある。このため、順序データを調査し範囲外の格納データは無視して送信しなくてもよい。
【００６４】
第３の実施の形態では、記憶領域１０６、１０７、１０８に書き込まれた格納データのうち一部を指定して、マージすることができる。
【００６５】
〔第４の実施の形態〕
第４の実施の形態について説明する。第４の実施の形態のブロック図を図１１に示す。図１１に示すように、第４の実施の形態における情報処理装置４０は、所定数以下の格納データを保持している過少記憶領域が複数存在しているとき、複数の過少記憶領域に保持された格納データを読み出し、読み出した格納データを当該格納データに含まれる順序データに従って並べ替え、他の記憶領域に書き込む統合部４０１、を備えることが第１の実施の形態と異なる。第１の実施の形態と同様の要素については第１の実施の形態と同一の符号を付して詳細な説明を省略する。
【００６６】
第４の実施の形態では、定期的に、または、継続的に、過少記憶領域の数を減らす。格納データ数の少ない過少記憶領域が増えると、ランダムアクセスの割合が増加して書き込みまたは読み出しの処理速度が低下する。過少記憶領域の増加は、例外的な順序データをもつ格納データが多く到着したときに発生する。
【００６７】
統合部４０１は、２つ以上の過少記憶領域に記憶されている格納データを統合してより少ない数の記憶領域に移動する。例えば、２つの過少記憶領域に記憶されている格納データを、それぞれ全て読み出して順序データ順に並び替え、並び替えた格納データを１つの記憶領域に書き込み、元の過少記憶領域に記憶されている格納データを全て消去する。この例では、使用される記憶領域の数が１つ減る。
【００６８】
図１２は、上述の統合部４０１の動作の一例を示すフローチャートである。まず、統合部４０１は、現在統合が可能な状態かを判断する（ステップＳ４１）。具体的には、格納データ数の少ない過少記憶領域が２つ以上存在するか、空の記憶領域が１つ以上存在するか、書き込みと読み出しを禁止しても問題が発生しないか、を判断する。統合が可能でなければ、動作を終了する。統合が可能であれば、不整合の発生を防止するために、書込部１０３による書き込みと、マージ部１０４による読み出しを、一時的に禁止する。（ステップＳ４２）。次に、格納データ数の少ない複数の過少記憶領域を統合元として選択する（ステップＳ４３）。加えて、１つの空の記憶領域を統合先として選択する（ステップＳ４４）。そして、統合部４０１は、統合元から格納データを読み出して、読み出した格納データを当該格納データに含まれる順序データに従って並べ替え、統合先に書き込む（ステップＳ４５）。全ての格納データを書き込んだ後、統合部４０１は統合元の格納データを全て消去し、空にする（ステップＳ４６）。最後に、書込部１０３による書き込みと、マージ部１０４による読み出しの禁止を解除する（ステップＳ４７）。以上の動作により、空の記憶領域が１つ増える。上記動作は、定期的、または、継続的に実行する。
【００６９】
図１２では空の記憶領域を統合先とする例を示したが、統合する全ての格納データがメモリに収まる場合は、統合先と統合元は同じ記憶領域でもよい。統合先と統合元が同じ記憶領域の場合は、併合した格納データは一時的にメモリに保存して統合先に書き込む。しかし、この場合、統合先に書き込んでいる途中で停電などの障害が発生すると、格納データが破壊される可能性がある。
【００７０】
第４の実施の形態は、過少記憶領域の数を定期的に、また継続的に減らし、書き込みまたは読み出しの処理速度の低下を防ぐことができる。
【００７１】
以上、各実施の形態を説明した。これらの実施の形態によれば、順序データ順での受信が保証されない格納データを高速に書き込め、また、順序データ順に高速に読み出せる。より一般的には、処理順を表す情報を含み処理順での受信が保証されないデータ列を高速に書き込め、また、処理順に高速に読み出せる。
【００７２】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【００７３】
例えば、上述の実施形態では、受信部１０１によって受信された受信データは、即座に比較部１０２によって処理されるように説明した。しかし、受信部１０１によって受信された受信データを、比較部１０２に伝送する前に一時的に保持し、保持された受信データに含まれる順序データに基づいて当該受信データを間欠的にソートする機能があってもよい。そして、比較部１０２は、この機能によってソートされた受信データを用いてもよい。なお、この機能は、所定時間ごとに受信データをソートしてもよいし、保持された受信データが所定量に達した時、当該受信データをソートしてもよい。このようにすれば、書き込む順序がより順序データ順に近くなるため、必要な記憶領域の数が減る。なお、ここで間欠的とは、受信部１０１が受信データを受信する間隔と比べて十分に長い間隔を空けることである。
【００７４】
また、上述の実施形態では、書込部１０３が、本体データと順序データとを合わせて同じ記憶領域に書き込む例を説明したが、本体データと順序データとは別の記憶領域に分けて書き込んでもよい。このとき、マージ部１０４は、順序データをマージした後に、本体データを順序データと同じ順番に並び替えることによって格納データをマージすることができる。順序データを単独で記憶領域に記憶することで、第３の実施形態で説明した二分探索による範囲指定の効率が高まる。また、本体データを項目ごとに分けて別の記憶領域に書き込んでもよく、このようにすれば１項目だけを読み出すときの効率が高まる。また、用途に応じて、本体データの同一の項目や順序データを複数の記憶領域に書き込んでもよい。
【００７５】
なお、上述の実施形態では、いずれもマージ部１０４を備えることを前提に説明をしたが、マージ部１０４は必ずしも同一の装置内に備えられなくてもよい。すなわち、上述の実施形態で説明したように書き込まれた格納データを、他の装置に伝送してからマージしても構わない。
【００７６】
なお、上記実施形態の説明には、複数のフローチャートを用いており、それぞれに複数のステップを順番に記載してあるが、その記載の順番は、本発明の情報処理方法のステップを実行する順番を限定するものではない。このため、本発明の情報処理方法を実行するときには、その複数のステップの順番は内容的に支障しない範囲で変更することができる。
【００７７】
なお、当然ながら、上述した実施の形態および複数の変形例は、その内容が相反しない範囲で組み合わせることができる。また、上述した実施の形態および変形例では、各構成要素の機能などを具体的に説明したが、その機能などは本願発明を満足する範囲で各種に変更することができる。
【００７８】
この出願は、２００９年１２月１１日に出願された日本出願特願２００９−２８１９３１号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2011070725.tif 000003
【図２】
2011070725.tif 000004
【図３】
2011070725.tif 000005
【図４】
2011070725.tif 000006
【図５】
2011070725.tif 000007
【図６】
2011070725.tif 000008
【図７】
2011070725.tif 000009
【図８】
2011070725.tif 000010
【図９】
2011070725.tif 000011
【図１０】
2011070725.tif 000012
【図１１】
2011070725.tif 000013
【図１２】
2011070725.tif 000014
【国際調査報告】
2011070725.tif 000015
2011070725.tif 000016