(57)【特許請求の範囲】
【請求項１】
連想記憶メモリを有する情報検索装置において、
検索値と情報値から成るエントリーを前記連想記憶メモリに登録する連想記憶メモリ登録手段と、
入力された検索値に基づいて前記連想記憶メモリから出力を得る連想記憶メモリ検索手段と、
入力された検索値に基づいて前記連想記憶メモリから情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリから削除する連想記憶メモリエントリー削除手段と、
を備え、
前記連想記憶メモリ登録手段は、
前回の検索時期が古いエントリーから順番に、前記連想記憶メモリに登録することを特徴とする情報検索装置。
【請求項２】
前記連想記憶メモリを第１優先使用の情報検索方式とし、該連想記憶メモリ以外の第２優先使用の情報検索方式を設け、
前記連想記憶メモリから情報値を得ることができなかった検索値に基づいて、前記第２優先使用の情報検索方式から情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリに登録する順番として、現時点で最後の順番に設定することを特徴とする請求項１に記載の情報検索装置。
【請求項３】
連想記憶メモリのエントリー保持期限を設けたことを特徴とする請求項１に記載の情報検索装置。
【請求項４】
データ単位を入力するデータ入力手段と、
前記データ単位からストリーム識別子を抽出するストリーム識別子取得手段と、
請求項１から請求項３のいずれか１項に記載の情報検索装置と、
データ処理情報を有するデータブロックをストリーム毎に記憶するデータブロック記憶手段と、
前記データブロックのデータ処理情報に基づいて、ストリームに関する処理を行うデータ処理手段と、を備え、
ストリーム識別子を検索値とし、データブロックの記憶領域を示すデータブロックポインタ値を情報値とし、
前記データ単位から抽出したストリーム識別子に基づいて、前記情報検索装置からデータブロックポインタ値を得る、
ことを特徴とするデータ処理装置。
【請求項５】
通信回線を流れる通信データのデータ単位を入力するデータ入力手段と、
前記通信データのデータ単位からストリーム識別子を抽出するストリーム識別子取得手段と、
請求項１から請求項３のいずれか１項に記載の情報検索装置と、
データ処理情報を有するデータブロックをストリーム毎に記憶するデータブロック記憶手段と、
前記データブロックのデータ処理情報に基づいて、ストリームに関するトラヒック測定を行うデータ処理手段と、を備え、
ストリーム識別子を検索値とし、データブロックの記憶領域を示すデータブロックポインタ値を情報値とし、
前記データ単位から抽出したストリーム識別子に基づいて、前記情報検索装置からデータブロックポインタ値を得る、
ことを特徴とする通信トラヒック測定装置。
【請求項６】
通信データのデータ単位は１個の音声パケットであり、ストリームはＩＰ電話の一通話における片方向の音声パケット列であり、ストリーム識別子は音声パケットに含まれる通信識別子であることを特徴とする請求項５に記載の通信トラヒック測定装置。
【請求項７】
データベース装置に格納されている格納データのデータ単位を入力するデータ入力手段と、
前記格納データのデータ単位からストリーム識別子を抽出するストリーム識別子取得手段と、
請求項１から請求項３のいずれか１項に記載の情報検索装置と、
データ処理情報を有するデータブロックをストリーム毎に記憶するデータブロック記憶手段と、
前記データブロックのデータ処理情報に基づいて、ストリームに関する調査を行うデータ処理手段と、を備え、
ストリーム識別子を検索値とし、データブロックの記憶領域を示すデータブロックポインタ値を情報値とし、
前記データ単位から抽出したストリーム識別子に基づいて、前記情報検索装置からデータブロックポインタ値を得る、
ことを特徴とするデータベース調査装置。
【請求項８】
格納データのデータ単位は１個のデータファイルであり、ストリームは一種類の情報に属するデータファイル列であり、ストリーム識別子はデータファイルに含まれる情報種類識別子であることを特徴とする請求項７に記載のデータベース調査装置。
【請求項９】
連想記憶メモリを有する情報検索装置のコンピュータに、
検索値と情報値から成るエントリーを前記連想記憶メモリに登録する連想記憶メモリ登録機能と、
入力された検索値に基づいて前記連想記憶メモリから出力を得る連想記憶メモリ検索機能と、
入力された検索値に基づいて前記連想記憶メモリから情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリから削除する連想記憶メモリエントリー削除機能と、
を実行させるコンピュータプログラムであって、
前記連想記憶メモリ登録機能は、
前回の検索時期が古いエントリーから順番に、前記連想記憶メモリに登録することを特徴とするコンピュータプログラム。
【請求項１０】
前記連想記憶メモリを第１優先使用の情報検索方式とし、該連想記憶メモリ以外の第２優先使用の情報検索方式をさらに用い、
前記連想記憶メモリから情報値を得ることができなかった検索値に基づいて、前記第２優先使用の情報検索方式から情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリに登録する順番として、現時点で最後の順番に設定することを特徴とする請求項９に記載のコンピュータプログラム。
【請求項１１】
連想記憶メモリのエントリー保持期限を設けたことを特徴とする請求項９に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索装置、データ処理装置、通信トラヒック測定装置、データベース調査装置及びコンピュータプログラムに関する。
【背景技術】
【０００２】
従来、通信ネットワークにおいて宛先アドレスから経路情報を検索する経路情報検索方式（例えば、特許文献１参照）や、パケットに含まれるキー毎にパケットの流量を測定する際に、該キーから測定結果格納場所を検索するパケット流量測定方法（例えば、特許文献２参照）が知られている。これら従来の情報検索技術では、連想記憶メモリ（Content Addressable Memory：CAM）を用いた検索方式とツリー検索方式又はハッシュテーブル検索方式とを組合せ、高速検索が可能な連想記憶メモリには参照頻度が高い情報を格納することで、検索時間の短縮を図っている。
【０００３】
特許文献１記載の経路情報検索方式は、連想記憶メモリを用いた検索方式による検索が失敗した場合には、ツリー検索方式を用いた検索を行い、ツリー検索終了時にツリー検索方式で得られたポインタ値と宛先アドレスとを関連付けて連想記憶メモリに登録している。
特許文献２記載のパケット流量測定方法は、連想記憶メモリには受信頻度の高いパケットに対応するエントリーを保持し、ハッシュテーブル用メモリには受信頻度の低いパケットに対応するエントリーを保持する。さらに、連想記憶メモリの最古のエントリーとハッシュテーブル用メモリの最新のエントリーを入れ替え、連想記憶メモリには常に新しい受信パケットに関するエントリーが保持されるようにしている。
【特許文献１】特開平１１−２２０４８３号公報
【特許文献２】特開２００１−５３８０１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、上述した従来の情報検索技術では、参照頻度が高い情報に検索の照準を合わせているために、情報間で参照頻度に差があまりない場合には効果が薄いという問題がある。
【０００５】
具体例として、ＶｏＩＰ（Voice over Internet Protocol）技術を用いたＩＰ（Internet Protocol）電話システムを対象にした音声パケット測定システムを挙げて、従来技術の問題点を説明する。音声パケット測定システムは、通信ネットワーク上のある測定点で、複数の通話について同時に、通話単位で音声パケットの測定を行う。このために、各通話を区別するための通信識別子を音声パケットから抽出し、通信識別子毎に、音声パケットの測定を行って測定結果を記録する。その際、通信識別子から、どの通話に関する測定であるのかの情報（例えば、測定内容、測定結果の格納場所）を検索する。ここで、通常、音声パケットはほぼ一定間隔で発生するので、各通信識別子の出現頻度には差があまりない。従って、従来技術のように連想記憶メモリに参照頻度が高い情報（出現頻度が高い通信識別子に係る情報）を格納して検索時間の短縮を図ろうとしても、どの情報もほぼ同じ参照頻度であるので、連想記憶メモリを十分に活用することができず、思うように効果が上がらないという結果になってしまう。
このように従来技術では、情報間で参照頻度に差があまりない場合には、高速検索が可能な連想記憶メモリを効果的に利用することができない。このため、検索時間の短縮が思うようにいかないという問題が生じる。
【０００６】
本発明は、このような事情を考慮してなされたもので、その目的は、情報間で参照頻度に差があまりない場合に、高速検索が可能な連想記憶メモリを効果的に利用することのできる情報検索装置及びコンピュータプログラムを提供することにある。
【０００７】
また、本発明の他の目的は、本発明の情報検索装置を備えたデータ処理装置、通信トラヒック測定装置及びデータベース調査装置を提供することにある。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、本発明に係る情報検索装置は、連想記憶メモリを有する情報検索装置において、検索値と情報値から成るエントリーを前記連想記憶メモリに登録する連想記憶メモリ登録手段と、入力された検索値に基づいて前記連想記憶メモリから出力を得る連想記憶メモリ検索手段と、入力された検索値に基づいて前記連想記憶メモリから情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリから削除する連想記憶メモリエントリー削除手段と、を備え、前記連想記憶メモリ登録手段は、前回の検索時期が古いエントリーから順番に、前記連想記憶メモリに登録することを特徴とする。
【００１０】
本発明に係る情報検索装置においては、前記連想記憶メモリを第１優先使用の情報検索方式とし、該連想記憶メモリ以外の第２優先使用の情報検索方式を設け、前記連想記憶メモリから情報値を得ることができなかった検索値に基づいて、前記第２優先使用の情報検索方式から情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリに登録する順番として、現時点で最後の順番に設定することを特徴とする。
【００１１】
本発明に係る情報検索装置においては、連想記憶メモリのエントリー保持期限を設けたことを特徴とする。
【００１２】
本発明に係るデータ処理装置は、データ単位を入力するデータ入力手段と、前記データ単位からストリーム識別子を抽出するストリーム識別子取得手段と、前述の情報検索装置と、データ処理情報を有するデータブロックをストリーム毎に記憶するデータブロック記憶手段と、前記データブロックのデータ処理情報に基づいて、ストリームに関する処理を行うデータ処理手段と、を備え、ストリーム識別子を検索値とし、データブロックの記憶領域を示すデータブロックポインタ値を情報値とし、前記データ単位から抽出したストリーム識別子に基づいて、前記情報検索装置からデータブロックポインタ値を得ることを特徴とする。
【００１３】
本発明に係る通信トラヒック測定装置は、通信回線を流れる通信データのデータ単位を入力するデータ入力手段と、前記通信データのデータ単位からストリーム識別子を抽出するストリーム識別子取得手段と、前述の情報検索装置と、データ処理情報を有するデータブロックをストリーム毎に記憶するデータブロック記憶手段と、前記データブロックのデータ処理情報に基づいて、ストリームに関するトラヒック測定を行うデータ処理手段と、を備え、ストリーム識別子を検索値とし、データブロックの記憶領域を示すデータブロックポインタ値を情報値とし、前記データ単位から抽出したストリーム識別子に基づいて、前記情報検索装置からデータブロックポインタ値を得ることを特徴とする。
【００１４】
本発明に係る通信トラヒック測定装置においては、通信データのデータ単位は１個の音声パケットであり、ストリームはＩＰ電話の一通話における片方向の音声パケット列であり、ストリーム識別子は音声パケットに含まれる通信識別子であることを特徴とする。
【００１５】
本発明に係るデータベース調査装置は、データベース装置に格納されている格納データのデータ単位を入力するデータ入力手段と、前記格納データのデータ単位からストリーム識別子を抽出するストリーム識別子取得手段と、前述の情報検索装置と、データ処理情報を有するデータブロックをストリーム毎に記憶するデータブロック記憶手段と、前記データブロックのデータ処理情報に基づいて、ストリームに関する調査を行うデータ処理手段と、を備え、ストリーム識別子を検索値とし、データブロックの記憶領域を示すデータブロックポインタ値を情報値とし、前記データ単位から抽出したストリーム識別子に基づいて、前記情報検索装置からデータブロックポインタ値を得ることを特徴とする。
【００１６】
本発明に係るデータベース調査装置においては、格納データのデータ単位は１個のデータファイルであり、ストリームは一種類の情報に属するデータファイル列であり、ストリーム識別子はデータファイルに含まれる情報種類識別子であることを特徴とする。
【００１７】
本発明に係るコンピュータプログラムは、連想記憶メモリを有する情報検索装置のコンピュータに、検索値と情報値から成るエントリーを前記連想記憶メモリに登録する連想記憶メモリ登録機能と、入力された検索値に基づいて前記連想記憶メモリから出力を得る連想記憶メモリ検索機能と、入力された検索値に基づいて前記連想記憶メモリから情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリから削除する連想記憶メモリエントリー削除機能と、を実行させるコンピュータプログラムであって、前記連想記憶メモリ登録機能は、前回の検索時期が古いエントリーから順番に、前記連想記憶メモリに登録することを特徴とする。
【００１９】
本発明に係るコンピュータプログラムにおいては、前記連想記憶メモリを第１優先使用の情報検索方式とし、該連想記憶メモリ以外の第２優先使用の情報検索方式をさらに用い、前記連想記憶メモリから情報値を得ることができなかった検索値に基づいて、前記第２優先使用の情報検索方式から情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを前記連想記憶メモリに登録する順番として、現時点で最後の順番に設定することを特徴とする。
【００２０】
本発明に係るコンピュータプログラムにおいては、連想記憶メモリのエントリー保持期限を設けたことを特徴とする。
これにより、前述の情報検索装置がコンピュータを利用して実現できるようになる。
【発明の効果】
【００２１】
本発明によれば、情報間で参照頻度に差があまりない場合に、高速検索が可能な連想記憶メモリを効果的に利用することができるという効果が得られる。
【発明を実施するための最良の形態】
【００２２】
以下、図面を参照し、本発明の実施形態について説明する。
【００２３】
本実施形態で扱う用語を説明する。
データ単位：処理対象の単位となるデータ群である。データ単位としては、例えば、ＩＰ電話における１個の音声パケットである。
ストリーム：複数のデータ単位から構成されるデータ系列である。さらに、複数のストリーム間において、各ストリームのデータ単位の出現頻度はほぼ同じであり差があまりない。ストリームとしては、例えば、ＩＰ電話の一通話における片方向の音声パケット列である。一ストリームを構成するデータ単位は、他のストリームと区別可能なストリーム識別子（ストリームＩＤ）を含む。ストリームＩＤとしては、例えば、ＩＰ電話の音声パケットに含まれる通信識別子である。
【００２４】
図１は、本発明の一実施形態に係るデータ処理装置１の構成を示すブロック図である。図１において、データ処理装置１は、データ入力部１１とデータブロック検索部１２とデータ処理部１３と各種記憶部１４，１６，１７，１８，１９，２０と連想記憶メモリ（Content Addressable Memory：ＣＡＭ）１５を有する。
【００２５】
データ入力部１１は、データ単位を入力する。データ入力部１１は、複数のストリームのデータ単位を入力可能である。データブロック検索部１２は、入力されたデータ単位に含まれるストリームＩＤをもとにして、当該ストリームＩＤ用の情報を有するデータブロックを検索する。図２に、該データブロック検索部１２の構成例を示す。図２において、データブロック検索部１２は、データブロック検索に係る各部３１〜４０を有する。データ処理部１３は、データブロック検索部１２による検索結果のデータブロックに含まれる情報に基づいて、ストリームに関する処理を行う。
【００２６】
データブロック記憶部１４は、ストリーム毎に設けられるデータブロックを記憶する。図３は、データブロック記憶部１４の記憶構成を説明するための概念図である。図３において、データブロック記憶部１４は、データブロックポインタで示される記憶領域にデータブロックを記憶する。データブロックポインタの指定は、該データブロックポインタに固有のポインタ値によって行う。データブロックポインタとデータブロックは一対一の関係になっている。
【００２７】
図４は、データブロックが有する情報の構成例である。図４において、データブロックは、ストリームＩＤ、参照順リスト情報、二分探索木情報、最終参照時刻及びデータ処理情報を有する。ストリームＩＤは、当該データブロックが割り当てられたストリームを示す。
【００２８】
参照順リスト情報は、参照順リストを構成する情報である。参照順リストは、データブロックの参照順を示すリストである。参照順リスト情報は、参照順リスト上のリスト順位が当該データブロックよりも、１つ上のデータブロックのデータブロックポインタのポインタ値と１つ下のデータブロックのデータブロックポインタのポインタ値と、を有する。
【００２９】
二分探索木情報は、二分探索（binary search、バイナリ・サーチ）用の探索木を構成する情報である。二分探索木情報は、当該データブロックについて、二分探索木上、１つの親データブロックのデータブロックポインタのポインタ値と２つの子データブロックのデータブロックポインタのポインタ値と、を有する。該二分探索木によって、あるストリームＩＤ用のデータブロックのデータブロックポインタを、二分探索することができる。
【００３０】
最終参照時刻は、当該データブロックが最後に参照された時刻である。
データ処理情報は、当該データブロックが割り当てられたストリームＩＤ用の情報である。データ処理情報としては、例えば、処理内容や処理結果の格納場所などの情報、実際の処理データなどが挙げられる。
【００３１】
ＣＡＭ１５には、検索値と情報値から成るエントリーを複数登録することができる。但し、登録可能なエントリーの個数には制限がある。ＣＡＭ１５は、検索値が入力されると、該検索値を含むエントリーに含まれる情報値を出力する。
【００３２】
図５は、ＣＡＭ１５の記憶構成を説明するための概念図である。図５において、ＣＡＭ１５は、ストリームＩＤ（検索値に対応）とデータブロックポインタのポインタ値（情報値に対応）を対として記憶する。ＣＡＭ１５は、入力されたストリームＩＤと対になっているデータブロックポインタのポインタ値を出力する。このポインタ値によってデータブロックポインタを指定し、データブロック記憶部１４のデータブロックを参照することができる。ＣＡＭ１５に対して、ストリームＩＤとデータブロックポインタの組（エントリー）を制限個数内で任意に登録し、又、登録済みのエントリーを任意に削除することができる。
【００３３】
図６は、ハッシュテーブル記憶部１６の記憶構成を説明するための概念図である。図６において、ハッシュテーブル記憶部１６は、ハッシュ値で示される記憶領域にルートデータブロックポインタのポインタ値を記憶する。ルートデータブロックポインタは、二分探索木の根（root、ルート）であるデータブロックのデータブロックポインタである。ハッシュ値は、ストリームＩＤを所定のハッシュ関数で変換した値である。ストリームＩＤから得られたハッシュ値によってハッシュテーブル記憶部１６からルートデータブロックポインタのポインタ値を取得することで、該ルートデータブロックポインタを根に持つ二分探索木によって当該ストリームＩＤ用のデータブロックポインタを二分探索することができる。
【００３４】
図７は、参照順リストの構成を説明するための概念図である。図７において、リスト順位はデータブロックの参照順を示し、その順番は参照時期の古い順である。従って、参照順リスト中の先頭のデータブロックは、最古の参照対象であり、その最終参照時刻（図４参照）は最も古い。一方、参照順リスト中の最後尾のデータブロックは、最新の参照対象であり、その最終参照時刻は最も新しい。
【００３５】
図１中の参照順リスト先頭ポインタ記憶部１７は、参照順リスト中の先頭のデータブロックのデータブロックポインタのポインタ値を記憶する。参照順リスト最後尾ポインタ記憶部１８は、参照順リスト中の最後尾のデータブロックのデータブロックポインタのポインタ値を記憶する。ＣＡＭ登録ポインタ記憶部１９は、参照順リストにおいて次のＣＡＭ登録対象であるデータブロックポインタのポインタ値を記憶する。従って、次回のＣＡＭ登録時には、ＣＡＭ登録ポインタ記憶部１９のポインタ値で指定されるデータブロックポインタが最初の登録対象となる。
【００３６】
図１中のデータブロック保持タイムアウト値記憶部２０は、所定のデータブロック保持タイムアウト値を記憶する。データブロック保持タイムアウト値は、データブロックの保持期限の時間を示す。従って、最終参照時刻（図４参照）から既にデータブロック保持タイムアウト値を経過しているデータブロックは、削除対象となる。データブロック保持タイムアウト値としては、データ単位が出現する間隔に対してある程度の余裕を持たせた時間（ほぼ確実にデータ単位が出現するはずの時間）に設定する。例えば、ＩＰ電話の音声パケット（データ単位）に対して、音声パケット発生間隔に余裕時間を加算した時間（伝送遅延ゆらぎ等の変動要因を加味したとしても、ほぼ確実に音声パケットが出現するはずの時間）をデータブロック保持タイムアウト値とすることが挙げられる。これにより、あるストリーム（例えばＩＰ電話のある通話）が終了したときに、当該ストリームに係るデータブロックを削除するようにする。なお、データブロック保持タイムアウト値は、ＣＡＭ１５のエントリー保持期限の時間を示すものでもある。従って、保持期限の切れたデータブロックに係るエントリーは、データブロックの削除時に、ＣＡＭ１５から削除される。
【００３７】
次に、図２を参照して、データブロック検索部１２の構成を説明する。
ストリームＩＤ取得部３１は、入力されたデータ単位からストリームＩＤを抽出する。ＣＡＭ検索部３２は、ストリームＩＤをＣＡＭ１５に入力し、その出力を得る。このとき、該ストリームＩＤを含むエントリーがＣＡＭ１５に登録されていれば、該ストリームＩＤと対のデータブロックポインタのポインタ値が出力されるが、該エントリーがＣＡＭ１５に登録されていなければ、“エントリーなし”の信号が出力される。ＣＡＭエントリー削除部３３は、ＣＡＭ１５から登録済みのエントリーを削除する。
【００３８】
二分探索木ルート取得部３４は、ストリームＩＤを所定のハッシュ関数で変換し、該ハッシュ値をもとにしてハッシュテーブル記憶部１６からルートデータブロックポインタのポインタ値を取得する。このとき、該ハッシュ値とルートデータブロックポインタのポインタ値の組がハッシュテーブル記憶部１６に登録されていれば、該ハッシュ値と対のルートデータブロックポインタのポインタ値が出力されるが、該組がハッシュテーブル記憶部１６に登録されていなければ、“データなし”の信号が出力される。
【００３９】
二分探索木探索部３５は、ストリームＩＤとルートデータブロックポインタのポインタ値をもとにして、該ルートデータブロックポインタを根に持つ二分探索木によって当該ストリームＩＤを含むデータブロックのデータブロックポインタを二分探索する。
【００４０】
新規データブロック生成部３６は、新たなストリームＩＤ用のデータブロックをデータブロック記憶部１４の記憶領域に生成する。二分探索木登録部３７は、新規に生成されたデータブロックのデータブロックポインタを二分探索木に登録する。参照順リスト最後尾更新部３８は、参照順リスト中の最後尾のデータブロックを更新すると共に、参照順リスト最後尾ポインタ記憶部１８を更新する。
【００４１】
データブロック削除部３９は、データブロック保持タイムアウト値記憶部２０のデータブロック保持タイムアウト値に基づいて削除対象のデータブロックを削除すると共に、関連する情報の削除を行う。ＣＡＭ登録部４０は、ＣＡＭ１５にエントリーを登録する。
【００４２】
次に、図８を参照して、データブロック検索部１２が行う情報検索処理を説明する。図８は、本実施形態に係る情報検索処理の流れを示すフローチャートである。
データブロック検索部１２は、データ単位が入力されると、図８の処理を開始する。図８において、ステップＳ１では、入力されたデータ単位からストリームＩＤを抽出する。
【００４３】
ステップＳ２では、抽出したストリームＩＤをＣＡＭ１５に入力し、ＣＡＭ１５からの出力を得る。これにより、“今回出現したストリーム”用のデータブロックを参照するためのデータブロックポインタのポインタ値の取得を試みる。この結果、ＣＡＭ１５からデータブロックポインタのポインタ値を取得することができた場合には、取得したデータブロックポインタのポインタ値をデータ処理部１３に出力する。さらに、該データブロックを参照順リストから外し、参照順リスト上の外した箇所のつなぎを行う。この参照順リスト処理としては、参照順リストから外すデータブロックに対してリスト順位で１つ上と１つ下の各データブロックがリスト上の隣接関係になるように、該１つ上と１つ下の各データブロックの参照順リスト情報を書き換える。この後、ステップＳ３に進む。なお、データ処理部１３は、データブロックポインタのポインタ値を受け取ると、該ポインタ値に基づいてデータブロック記憶部１４のデータブロックを参照し、参照したデータブロックのデータ処理情報に基づいてストリームに関する処理を行う。
一方、データブロックポインタのポインタ値を取得することができなかった場合にはステップＳ４に進む。
【００４４】
ステップＳ３では、ステップＳ２で取得したデータブロックポインタのポインタ値と該ストリームＩＤから成るエントリーをＣＡＭ１５から削除する。これにより、検索のあったエントリーは直ぐにＣＡＭ１５から削除する。言い換えると、出現したストリームに係るエントリーは検索後、直ぐにＣＡＭ１５から削除する。これは、複数のストリーム間において各ストリームのデータ単位の出現頻度はほぼ同じであり、今回出現したストリームのデータ単位は、この後、一定期間は出現しない可能性が高いので、他のストリーム（特には、前回の出現時期がより古いストリーム）に係るエントリーをＣＡＭ１５に登録できるように、ＣＡＭ１５のエントリー登録の空きを作るためである。その後、ステップＳ８に進む。
【００４５】
ステップＳ４では、ステップＳ２でＣＡＭ１５からは“今回出現したストリーム”用のデータブロックを参照するためのデータブロックポインタのポインタ値を取得できなかったので、二分探索木探索のためのルートデータブロックポインタ（ルートポインタ）のポインタ値の取得を試みる。具体的には、ステップＳ１で抽出したストリームＩＤのハッシュ値を計算し、該ハッシュ値に基づいてハッシュテーブル記憶部１６からルートポインタのポインタ値を取得することを試みる。この結果、ハッシュテーブル記憶部１６からルートポインタのポインタ値を取得することができた場合には、ステップＳ５に進む。
一方、ハッシュテーブル記憶部１６からルートポインタのポインタ値を取得することができなかった場合には、ステップＳ６に進む。この場合、今回出現したストリームは新規ストリームである。
【００４６】
ステップＳ５では、取得したルートポインタのポインタ値と当該ストリームＩＤに基づいて、該ルートポインタを根に持つ二分探索木によって該ストリームＩＤを含むデータブロックのデータブロックポインタを二分探索する。この結果、データブロックポインタのポインタ値を取得することができた場合には、ステップＳ２と同様に、取得したデータブロックポインタのポインタ値をデータ処理部１３に出力し、さらに、該データブロックを参照順リストから外し、参照順リスト上の外した箇所のつなぎを行う。その後、ステップＳ８に進む。
一方、データブロックポインタのポインタ値を取得することができなかった場合にはステップＳ６に進む。この場合、今回出現したストリームは新規ストリームである。
【００４７】
なお、今回出現したストリームが新規ストリームであるにもかかわらず、ハッシュテーブル記憶部１６からルートポインタのポインタ値を取得できる場合がある。これは、一つのハッシュ値が複数のストリームＩＤから得られるために、新規ストリームであってもハッシュテーブル記憶部１６の登録データにヒットしてしまう場合があるためである。
【００４８】
ステップＳ６では、今回出現したストリームが新規ストリームであるので、該新規ストリームＩＤ用のデータブロックを生成する。具体的には、データブロック記憶部１４の記憶領域に該新規データブロックを生成し、該記憶領域を示すデータブロックポインタを生成し、該データブロックポインタのポインタ値を定める。なお、この時点では、該データブロックには、ストリームＩＤとデータ処理内容を格納する。該ストリームＩＤはステップＳ１で取得したものである。該データ処理内容は当該新規ストリームに関する所定の内容である。
【００４９】
ステップＳ７では、ステップＳ６で生成した新規データブロックのデータブロックポインタのポインタ値と当該ストリームＩＤから得られたハッシュ値に基づいて、該新規データブロックポインタを二分探索木へ登録する処理を行う。具体的には、新規データブロックに二分探索木情報を格納する。さらに、該新規データブロックポインタが二分探索木の根になる場合には、当該ハッシュ値と組にして該新規データブロックポインタのポインタ値をハッシュテーブル記憶部１６に登録する。このとき、既に当該ハッシュ値の組がハッシュテーブル記憶部１６に登録済みである場合には、該組のデータブロックポインタのポインタ値を該新規データブロックポインタのポインタ値に書き換える。
【００５０】
ステップＳ８では、ステップＳ２若しくはＳ５で得られたデータブロックポインタのポインタ値、又はステップＳ６で生成した新規ストリームＩＤ用のデータブロックのデータブロックポインタのポインタ値に基づいて、参照順リストの最後尾を更新するリスト処理を行う。該データブロックポインタのポインタ値で示されるデータブロックは、最新の参照対象のデータブロックである。このため、当該データブロックを参照順リストの最後尾に配置する。具体的には、該データブロックポインタのポインタ値で示されるデータブロックを参照順リストの最後尾に配置するように、該当のデータブロックの参照順リスト情報を変更する。さらに、参照順リスト最後尾に配置したデータブロックの最終参照時刻を現在時刻にする。このとき、ＣＡＭ登録ポインタ記憶部１９が空であり、いずれのデータブロックポインタのポインタ値も格納されていない場合には、参照順リスト最後尾に配置したデータブロックのデータブロックポインタのポインタ値をＣＡＭ登録ポインタ記憶部１９に格納する。
【００５１】
ステップＳ９では、データブロック保持タイムアウト値記憶部２０のデータブロック保持タイムアウト値に基づいて、データブロックを削除する。具体的には、参照順リスト先頭ポインタ記憶部１７のデータブロックのデータブロックポインタのポインタ値で示される“参照順リスト中の先頭のデータブロック”から順番に、データブロックの最終参照時刻から現在までの経過時間がデータブロック保持タイムアウト値を超えているかを判断する。この結果、データブロック保持タイムアウト値を超えている場合には、当該データブロックを削除する。データブロックを削除した場合には、該削除データブロックに関し、ＣＡＭ１５から該当エントリーを削除すると共に、参照順リスト及び二分探索木から該削除データブロックを削除する処理を行う。このとき、削除データブロックが二分探索木の根である場合には、該二分探索木の根を変更する処理を行う。
【００５２】
ステップＳ１０では、ＣＡＭ１５にエントリー登録の空きがあるか判断する。この結果、エントリー登録の空きがある場合にはステップＳ１１に進み、エントリー登録の空きがない場合には図８の処理を終了する。
【００５３】
ステップＳ１１では、ＣＡＭ１５に対してエントリーの登録を行う。具体的には、ＣＡＭ登録ポインタ記憶部１９のデータブロックポインタのポインタ値で示されるデータブロックのストリームＩＤと該データブロックポインタのポインタ値を、ＣＡＭ１５に格納する。このとき、エントリー登録の空きがまだ残っている場合には、参照順リスト上の下位のデータブロックを順次、エントリー登録する。但し、参照順リスト最後尾のデータブロックまで登録した場合には、参照順リスト上の全てのデータブロックがＣＡＭ１５にエントリー登録されているので、ここで、エントリー登録を終了する。ＣＡＭ登録ポインタ記憶部１９には、参照順リスト上、最後にエントリー登録されたデータブロックの次の下位のデータブロックのデータブロックポインタのポインタ値を格納する。但し、参照順リスト最後尾のデータブロックまで登録した場合には、ＣＡＭ登録ポインタ記憶部１９を空にする。この後、図８の処理を終了する。
【００５４】
データ処理部１３は、上述の情報検索処理の結果として出力されたデータブロックポインタのポインタ値に基づいて、データブロック記憶部１４のデータブロックを参照する。データ処理部１３は、該参照したデータブロックのデータ処理情報に基づいて、ストリームに関する処理を行う。
【００５５】
上述した実施形態によれば、連想記憶メモリで検索したエントリーについては、検索後直ぐに連想記憶メモリから削除する。これにより、該検索済みのエントリーに係る情報以外の情報についてのエントリーを連想記憶メモリに登録することができる。この結果、各情報に係るエントリーをほぼ同頻度で連想記憶メモリに登録することができるので、情報間で参照頻度に差があまりない場合には連想記憶メモリにより検索成功する確度が高くなり、高速検索が可能な連想記憶メモリを効果的に利用することができる。
【００５６】
なお、情報検索方式として連想記憶メモリのみを有する場合にも、同様の効果が得られる。この場合の情報検索装置は、検索値と情報値から成るエントリーを連想記憶メモリに登録する連想記憶メモリ登録手段と、入力された検索値に基づいて連想記憶メモリから出力を得る連想記憶メモリ検索手段と、入力された検索値に基づいて連想記憶メモリから情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを連想記憶メモリから削除する連想記憶メモリエントリー削除手段と、を備える。さらには、前回の検索時期が古いエントリーから順番に、連想記憶メモリに登録することが好ましい。
【００５７】
また、上述の実施形態のように、連想記憶メモリを第１優先使用の情報検索方式とし、該連想記憶メモリ以外の第２優先使用の情報検索方式を設ける際には、連想記憶メモリから情報値を得ることができなかった検索値に基づいて、第２優先使用の情報検索方式から情報値を得ることができた場合に、該検索値と該情報値から成るエントリーを連想記憶メモリに登録する順番として、現時点で最後の順番に設定することが好ましい。
【００５８】
なお、上述の第２優先使用の情報検索方式としては、各種の情報検索方式が利用可能である。第２優先使用の情報検索方式としては、例えば、二分探索木等のツリー検索方式、ハッシュテーブル検索方式、検索値と情報値を関連付けて格納した検索テーブル方式などが挙げられる。
【００５９】
次に、本実施形態に係るデータ処理装置１について、いくつかの実施例を挙げて説明する。
【実施例１】
【００６０】
本発明の実施例１を図９に示す。実施例１は、通信回線１００を流れるトラヒックを測定するシステムである。データ処理装置１は、分岐装置１０１を介して、通信回線１００を流れる通信データのデータ単位を受け取る。分岐装置１０１は、通信回線１００を流れる通信データの複製をデータ処理装置１へ出力する。通信回線１００としては、光通信回線であってもよく、或いは電気通信回線であってもよい。
【００６１】
データ処理装置１は、入力された通信データのデータ単位からストリームＩＤを抽出し、該入力された通信データのデータ単位が属するストリームに用いられるデータブロックを検索し、該検索結果のデータブロックのデータ処理情報に基づいて、ストリームに関するトラヒック測定を行う。例えば、ＩＰ電話システムを対象にした音声パケット測定を行う。この音声パケット測定を行う場合には、例えば、通信データのデータ単位は１個の音声パケットとし、ストリームはＩＰ電話の一通話における片方向の音声パケット列とし、ストリームＩＤは音声パケットに含まれる通信識別子とすることが挙げられる。
【００６２】
通常、音声パケットはほぼ一定間隔で発生し各通信識別子の出現頻度には差があまりないので、本実施例１によれば、ＣＡＭを効果的に利用することができる。この結果として、測定時間の短縮ができ、測定能力の向上に寄与することが可能になる。
【実施例２】
【００６３】
本発明の実施例２を図１０に示す。実施例２は、データベース装置２００に格納されているデータを調査するシステムである。データ処理装置１は、データベース装置２００に格納されている格納データのデータ単位を受け取る。
【００６４】
データ処理装置１は、入力された格納データのデータ単位からストリームＩＤを抽出し、該入力された格納データのデータ単位が属するストリームに用いられるデータブロックを検索し、該検索結果のデータブロックのデータ処理情報に基づいて、該ストリームに関する調査を行う。例えば、データベース装置２００に格納されているデータが、どのような種類の情報に属しているかの調査を行う。この情報種類調査を行う場合には、例えば、格納データのデータ単位は１個のデータファイルとし、ストリームは一種類の情報に属するデータファイル列とし、ストリームＩＤはデータファイルに含まれる情報種類識別子とすることが挙げられる。
【００６５】
本実施例２によれば、データベース内に様々な情報種類のデータファイルが格納されている場合において、各情報種類のデータファイルがほぼ一定の順番で出現するように配置格納されているときに、ＣＡＭを効果的に利用することができる。この結果として、調査時間の短縮ができ、調査能力の向上に寄与することが可能になる。
【００６６】
なお、本実施形態に係るデータ処理装置１は、上述の実施例１，２に限定されず、各種の分野のデータ処理装置に適用することができる。
【００６７】
また、本実施形態に係るデータ処理装置１は、専用のハードウェアにより実現されるものであってもよく、あるいはパーソナルコンピュータ等のコンピュータシステムにより構成され、図１に示されるデータ処理装置１の各部の機能を実現するためのプログラムを実行することによりその機能を実現させるものであってもよい。
【００６８】
また、そのデータ処理装置１には、周辺機器として入力装置、表示装置等（いずれも図示せず）が接続されるものとする。ここで、入力装置とはキーボード、マウス等の入力デバイスのことをいう。表示装置とはＣＲＴ（Cathode Ray Tube）や液晶表示装置等のことをいう。
また、上記周辺機器については、データ処理装置１に直接接続するものであってもよく、あるいは通信回線を介して接続するようにしてもよい。
【００６９】
また、図８に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、情報検索処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＤＶＤ（Digital Versatile Disk）等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００７０】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００７１】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【図面の簡単な説明】
【００７２】
【図１】本発明の一実施形態に係るデータ処理装置１の構成を示すブロック図である。
【図２】図１に示すデータブロック検索部１２の構成例である。
【図３】図１に示すデータブロック記憶部１４の記憶構成を説明するための概念図である。
【図４】図３に示すデータブロックが有する情報の構成例である。
【図５】図１に示すＣＡＭ１５の記憶構成を説明するための概念図である。
【図６】図１に示すハッシュテーブル記憶部１６の記憶構成を説明するための概念図である。
【図７】本発明の一実施形態に係る参照順リストの構成を説明するための概念図である。
【図８】本発明の一実施形態に係る情報検索処理の流れを示すフローチャートである。
【図９】本発明に係る実施例１である。
【図１０】本発明に係る実施例２である。
【符号の説明】
【００７３】
１…データ処理装置、１１…データ入力部、１２…データブロック検索部、１３…データ処理部、１４…データブロック記憶部、１５…連想記憶メモリ（ＣＡＭ）、１６…ハッシュテーブル記憶部、１７…参照順リスト先頭ポインタ記憶部、１８…参照順リスト最後尾ポインタ記憶部、１９…ＣＡＭ登録ポインタ記憶部、２０…データブロック保持タイムアウト値記憶部
【図１】
0004994302.tif 000002
【図２】
0004994302.tif 000003
【図３】
0004994302.tif 000004
【図４】
0004994302.tif 000005
【図５】
0004994302.tif 000006
【図６】
0004994302.tif 000007
【図７】
0004994302.tif 000008
【図８】
0004994302.tif 000009
【図９】
0004994302.tif 000010
【図１０】
0004994302.tif 000011