(57)【特許請求の範囲】
【請求項１】
データ格納部から共通バスを介してデータ集合を読み出して、前記データ集合の多重ソートを行なう多重ソート装置において、
前記共通バスに接続され、前記データ集合を読み出すインターフェース手段と、
作業用メモリと、
前記インターフェース手段によって読み出されたデータ集合の各エントリを前記作業用メモリの所定のアドレスに格納すると共に、前記データ集合の優先キーに基づく優先キー配置マップを前記作業用メモリに作成するマップ作成手段と、
前記作業用メモリの優先キー配置マップに基づいて、前記作業用メモリのデータ集合の各エントリの場所を交換する交換手段と、
この交換手段によって交換されたデータ集合を第２のキーでソートするソート手段と
を有し、
マップ作成手段は、前記優先キーの種類ごとに、優先キー、この優先キーの出現回数、スタートアドレス、交換回数カウンタを組とする優先キー配置マップを作成し、
交換手段は、前記作業用メモリの優先キー配置マップの出現回数からスタートアドレスを求め、この求めたスタートアドレスと交換回数カウンタとに基づいてエントリの交換を行ない、交換後に交換回数カウンタの値をインクリメントすることを特徴とする多重ソート装置。
【請求項２】
データ格納部から共通バスを介してデータ集合を読み出して、前記データ集合の多重ソートを行なう多重ソート装置において、
前記共通バスに接続され、前記データ集合を読み出すインターフェース手段と、
作業用メモリと、
前記インターフェース手段によって読み出されたデータ集合の各エントリを前記作業用メモリの所定のアドレスに格納すると共に、前記データ集合の優先キーに基づく優先キー配置マップを前記作業用メモリに作成するマップ作成手段と、
前記作業用メモリの優先キー配置マップに基づいて、前記作業用メモリのデータ集合の各エントリの場所を交換する交換手段と、
この交換手段によって交換されたデータ集合を第２のキーでソートするソート手段と
を有し、
前記データ集合は、複数のラベルを組にしたエントリで構成され、
マップ作成手段は、前記ラベルの全部又は一部の種類ごとに、ラベル、ラベルに基づく優先キー、前記ラベルの出現回数、スタートアドレス、交換回数カウンタを組とする優先キー配置マップを作成し、
交換手段は、前記作業用メモリの優先キー配置マップの出現回数からスタートアドレスを求め、この求めたスタートアドレスと交換回数カウンタとに基づいてエントリの交換を行ない、交換後に交換回数カウンタの値をインクリメントすることを特徴とする多重ソート装置。
【請求項３】
前記データ集合は、複数のラベルを組にしたエントリで構成され、
前記データ集合のうち全部又は一部の前記ラベルから前記作業用メモリ内における優先キー配置マップの場所を検索する検索手段を設け、
マップ作成手段は、前記検索手段の検索結果を参照して前記作業用メモリ内の優先キー配置マップの場所を特定することを特徴とする請求項１または２記載の多重ソート装置。
【請求項４】
検索手段は、ＣＡＭ（Content Addressable Memory）であることを特徴とする請求項３記載の多重ソート装置。
【請求項５】
優先キーの種類および順序を設定する設定手段を設けたことを特徴とする請求項１〜４のいずれかに記載の多重ソート装置。
【請求項６】
マップ作成手段は、前記データ集合のうち、前記設定手段で設定された優先キーを含むエントリのみを作業用メモリに格納することを特徴とする請求項５記載の多重ソート装置。
【請求項７】
請求項１〜６のいずれかに記載の多重ソート装置と、
インターネット上を流れるデータを集計し、前記多重ソート装置のデータ格納部に格納する集計エンジンと
を設けたことを特徴とするトラフィック統計システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート対象のデータ集合を多重ソートする多重ソート装置およびこの多重ソート装置を用いたトラフィック統計システムに関し、詳しくは、データ集合のエントリ数が多くとも短時間でソートができ、共通バスの使用状況にも影響されずに短時間でソートができる多重ソート装置およびこれを用いたトラフィック統計システムに関するものである。
【背景技術】
【０００２】
インターネット等に代表されるコンピュータネットワーク上では、トラフィックを監視することが重要になっている。そして、トラフィックを監視する装置では、トラフィックの統計値を求め解析等を行なうが、監視対象を選別するためのブロックとしてソートが行なわれる。この際、１個のソートキー（以下、キーと略する）でデータをソートするのでなく複数のキーを用いてソートする、いわゆる、多重ソートが行なわれる（例えば、特許文献１、２、非特許文献１参照）。
【０００３】
また、コンピュータネットワークに限らず、大量のエントリを持つデータベースでは、所望の順位での多重ソートが一般的に行なわれる。
【０００４】
図１５は、従来の多重ソート装置の構成を示した図である。
ＣＰＵ１、作業用メモリ２、データベース格納メモリ３のそれぞれは、共通バス４で相互に接続される。作業用メモリ２は、ＣＰＵ１が高速にアクセス可能であり、例えば、主記憶メモリである。データベース格納メモリ３は、データ格納部であり、作業用メモリ２よりも大容量の、例えばハードディスク等であり、ソート対象のデータ集合を１個または複数種類格納する。ここで、データ集合とは、複数のラベルを組にしたエントリで構成され、所望のラベルがキーとして選択される。従って、全てのラベルをキーとして用いてもよく、１種類のラベルのみをキーとしてもよい。
【０００５】
このような装置の動作を説明する。
まず、１個のキーでソートする動作から説明する。
ＣＰＵ１が、データベース格納メモリ３から、ソートを行なうデータ集合を検索し、データ集合を、共通バス４を使用して、作業用メモリ２に転送する。そして、ＣＰＵ１が、作業用メモリ２内のデータに対し、所望のキーを用いてソート（例えば、クイックソート、マージソート等）を行なう。さらに、ソート終了後にＣＰＵ１が、ソート後のデータ集合を共通バス４を使用して、データベース格納メモリ３に格納する。
【０００６】
次に、多重ソートを説明する。ここで、多重ソートとは、１個目の優先キーにてデータ集合をソートした結果に対し、同値だったデータ集合に対してさらに２個目のキーを使用してソートを行なうこととする。
【０００７】
多重ソートの一例として２個のキーによる多重ソートの動作を説明する。ここで、図１６は、ソート結果の一例を示した図である。図１６（ａ）〜（ｃ）のそれぞれは、ソート前、優先キーによるソート後、２個目のキーによるソート後の結果を示した図である。
【０００８】
ＣＰＵ１が、データベース格納メモリ３から、ソートを行なうデータ集合Ｄ１を検索し、データ集合Ｄ１を、共通バス４を使用して、作業用メモリ２に転送する（図１６（ａ）参照）。
【０００９】
そして、ＣＰＵ１が、作業用メモリ２内のデータに対し、優先キーＫ１を使用してソート（例えば、クイックソート、マージソート等）を行なう。これにより、データ集合Ｄ１は、優先キーＫ１の値が同一となるデータ集合Ｄ２〜Ｄ６に分類される（図１６（ｂ）参照）。
【００１０】
さらに、ＣＰＵ１が、作業用メモリ２からデータ集合Ｄ２のみを検索し、このデータ集合Ｄ２に対して２個目のキーＫ２を使用してソートを行なう。そして、データ集合Ｄ３〜Ｄ６それぞれに対して順番に、２個目のキーＫ２を使用してソートを行なう（図１６（ｃ）参照）。
【００１１】
そして、２個目のキーＫ２でのソート終了後にＣＰＵ１が、ソート後のデータ集合Ｄ１を共通バス４を使用して、データベース格納メモリ３に格納する。
【００１２】
図１７は、従来の多重ソート装置のその他の構成を示した図である。ここで、図１５と同一のものは同一符号を付し説明を省略する。図１７において、作業用メモリ２の代わりに、入出力メモリ５が設けられる。入出力メモリ５は、例えば、主記憶メモリである。また、ソート処理部６が、共通バス６に接続され、ＣＰＵ１，データベース格納メモリ３、入出力メモリ５と相互に接続される。作業用メモリ７は、ソート処理部６の専用メモリとして、ソート処理部６と相互に接続される。
【００１３】
このような装置の多重ソートの動作を説明する。
ＣＰＵ１が、ソート対象のデータ集合Ｄ１をデータベース格納メモリ３から検索し、データ集合Ｄ１を連続的に取り出して、共通バス４を経由して連続的にソート処理部６に出力する。このとき、必要に応じて入出力メモリ５をバッファとして使用し、ソート処理部６に出力する。
【００１４】
そして、ソート処理部６が、ＣＰＵ１からの指示に基づいて、入力されたデータ集合Ｄ１を優先キーＫ１にてソート処理し、優先キーＫ１のソート結果を共通バス４を介してＣＰＵ１に送り返す。さらに、ＣＰＵ１が、送り返されたソート後の結果をデータベース格納メモリ３の所定の領域に格納する。
【００１５】
そして、優先キーＫ１のソート終了およびデータベース格納メモリ３への格納終了後、２個目のキーＫ２によるソートを開始する。ＣＰＵ１が、優先キーＫ１の値（図１６において、”６”）が同一のデータ集合Ｄ２を、データベース格納メモリ３から検索し、共通バス４を経由して、データ集合Ｄ２をソート処理部６に出力する。
【００１６】
そして、ソート処理部６が、ＣＰＵ１からの指示に基づいて、入力されたデータ集合Ｄ２をキーＫ２にてソート処理し、処理結果を共通バス４を介してＣＰＵ１に送り返す。さらに、ＣＰＵ１が、送り返されたソート後の結果をデータベース格納メモリ３の所定の領域に格納する。
【００１７】
そして、次に優先キーＫ１の値（図１６において、”５”）が同一のデータ集合Ｄ３を、データベース格納メモリ３から検索し、共通バス４を経由して、データ集合Ｄ３をソート処理部６に出力する。さらに、ソート処理部６が、データ集合Ｄ３をキーＫ２でソートし、ＣＰＵ１が，共通バス４を経由して結果を受け取り、データベース格納メモリ３に格納する。さらに、データ集合Ｄ４〜Ｄ６それぞれも同様にソートしてデータベース格納メモリ３に格納する。
【００１８】
【特許文献１】特許第３１９６６３７号
【特許文献２】特許第３５１８４２０号
【非特許文献１】伏見信也、他４名、「データベースプロセッサＧＲＥＯ」、情報処理、１９９２年、第３３巻、第１２号、ｐ．１４１６−１４２３
【発明の開示】
【発明が解決しようとする課題】
【００１９】
図１５に示す装置は、ＣＰＵ１がソートを行なうので、特別なハードウェアが不要であり装置全体としてコストを抑えられ、また、比較的複雑なアルゴリズムであっても適用が容易なのでクイックソート等を用いて高速にソートすることができる。
【００２０】
しかしながら、ソート中はＣＰＵ１および共通バス４がソート作業に長時間占有されるため、ソート以外のその他の処理（ソート結果を用いたデータ解析等）が行なえないという問題があった。また、ソートアルゴリズムがソフトウェアのみで動作するため、高速なクイックソート等を用いても、実際のソート作業が低速になるという問題があった。さらに、ソート作業を頻繁に行なうと、ソート作業およびデータ集合Ｄ１〜Ｄ６の検索に共通バスを使用するため、ＣＰＵ１の他の制御と競合すると、ソート作業自体も低速になってしまうという問題があった。
【００２１】
一方、図１７に示す装置は、ＣＰＵ１とは別に設けるハードウェアのソート処理部６にてソートアルゴリズムが動作するので、図１５に示す装置よりも高速にソート作業を行なえる。
【００２２】
しかしながら、多重ソートにおいては、ＣＰＵ１が、優先キーＫ１の値が同一のデータ集合Ｄ２〜Ｄ６それぞれを、データベース格納メモリ３から検索し、共通バス４を経由してソート処理部６に転送し、ソート結果も共通バスを経由してデータベース格納メモリ３に格納する。そのため、ＣＰＵ１、共通バス４を長時間占有する必要があり、その他の処理と競合すると、ソート作業自体が低速になってしまうという問題あった。
【００２３】
また、多重ソートの場合、２回目のソートでは、ソート対象の範囲が狭く問題ないが、1回目のソートでは、ソート対象の範囲（つまり、エントリ数）が非常に多数となる。そして、一般的なソート方法であるクイックソート、マージソート、ヒープソート等は、エントリ数の増加に伴って処理時間も飛躍的に増加するので、ソート作業に時間がかかるという問題があった。
【００２４】
そこで本発明の目的は、データ集合のエントリ数が多くとも短時間でソートができ、共通バスの使用状況にも影響されずに短時間でソートができる多重ソート装置およびこれを用いたトラフィック統計システムを実現することにある。
【課題を解決するための手段】
【００２５】
請求項１記載の発明は、
データ格納部から共通バスを介してデータ集合を読み出して、前記データ集合の多重ソートを行なう多重ソート装置において、
前記共通バスに接続され、前記データ集合を読み出すインターフェース手段と、
作業用メモリと、
前記インターフェース手段によって読み出されたデータ集合の各エントリを前記作業用メモリの所定のアドレスに格納すると共に、前記データ集合の優先キーに基づく優先キー配置マップを前記作業用メモリに作成するマップ作成手段と、
前記作業用メモリの優先キー配置マップに基づいて、前記作業用メモリのデータ集合の各エントリの場所を交換する交換手段と、
この交換手段によって交換されたデータ集合を第２のキーでソートするソート手段と
を有し、
マップ作成手段は、前記優先キーの種類ごとに、優先キー、この優先キーの出現回数、スタートアドレス、交換回数カウンタを組とする優先キー配置マップを作成し、
交換手段は、前記作業用メモリの優先キー配置マップの出現回数からスタートアドレスを求め、この求めたスタートアドレスと交換回数カウンタとに基づいてエントリの交換を行ない、交換後に交換回数カウンタの値をインクリメントすることを特徴とするものである。
請求項２記載の発明は、
データ格納部から共通バスを介してデータ集合を読み出して、前記データ集合の多重ソートを行なう多重ソート装置において、
前記共通バスに接続され、前記データ集合を読み出すインターフェース手段と、
作業用メモリと、
前記インターフェース手段によって読み出されたデータ集合の各エントリを前記作業用メモリの所定のアドレスに格納すると共に、前記データ集合の優先キーに基づく優先キー配置マップを前記作業用メモリに作成するマップ作成手段と、
前記作業用メモリの優先キー配置マップに基づいて、前記作業用メモリのデータ集合の各エントリの場所を交換する交換手段と、
この交換手段によって交換されたデータ集合を第２のキーでソートするソート手段と
を有し、
前記データ集合は、複数のラベルを組にしたエントリで構成され、
マップ作成手段は、前記ラベルの全部又は一部の種類ごとに、ラベル、ラベルに基づく優先キー、前記ラベルの出現回数、スタートアドレス、交換回数カウンタを組とする優先キー配置マップを作成し、
交換手段は、前記作業用メモリの優先キー配置マップの出現回数からスタートアドレスを求め、この求めたスタートアドレスと交換回数カウンタとに基づいてエントリの交換を行ない、交換後に交換回数カウンタの値をインクリメントすることを特徴とするものである。
請求項３記載の発明は、請求項２記載の発明において、
前記データ集合は、複数のラベルを組にしたエントリで構成され、
前記データ集合のうち全部又は一部の前記ラベルから前記作業用メモリ内における優先キー配置マップの場所を検索する検索手段を設け、
マップ作成手段は、前記検索手段の検索結果を参照して前記作業用メモリ内の優先キー配置マップの場所を特定することを特徴とするものである。
請求項４記載の発明は、請求項３記載の発明において、
検索手段は、ＣＡＭ（Content Addressable Memory）であることを特徴とするものである。
請求項５記載の発明は、請求項１〜４のいずれかに記載の発明において、
優先キーの種類および順序を設定する設定手段を設けたことを特徴とするものである。
請求項６記載の発明は、請求項５記載の発明において、
マップ作成手段は、前記データ集合のうち、前記設定手段で設定された優先キーを含むエントリのみを作業用メモリに格納することを特徴とするものである。
請求項７記載の発明は、
請求項１〜６のいずれかに記載の多重ソート装置と、
インターネット上を流れるデータを集計し、前記多重ソート装置のデータ格納部に格納する集計エンジンと
を設けたことを特徴とするものである。
【発明の効果】
【００２６】
本発明によれば、マップ作成手段が、共通バスを介して入力されるデータ集合内の優先キーの出現回数に基づいて優先キー配置マップを作成し、交換手段が、優先キー配置マップを用いてエントリの交換を行なう。そして、ソート手段が、優先キー配置マップを参照してソート対象の範囲を求め２回目のソートを行なう。これにより、ソート前のデータ集合のエントリ数が多くとも、短時間でソートを行なうことができる。また、共通バスの占有率を減少でき、共通バスの動作状況に影響されず、短時間でソートを行なうことができる。
【発明を実施するための最良の形態】
【００２７】
以下図面を用いて本発明の実施の形態を説明する。
［第１の実施例］
図１は、本発明の第１の実施例を示した構成図である。ここで、図１７と同一のものは同一符号を付し、説明を省略する。図１において、ソート処理部１０は、ソート処理部６の代わりに設けられ、データ転送バスの共通バス４を介してＣＰＵ１、データベース格納メモリ３、入出力メモリ５と相互に接続される。
【００２８】
ソート処理部１０は、インターフェース手段１１、制御手段１２、マップ作成手段１３、ＣＡＭ１４、ソート手段１５、作業用メモリ１６、交換手段１７を有し、ＣＰＵ１の指示に基づいて、データベース格納メモリ３の所望のデータ集合に対して多重ソートし、ソート結果をデータベース格納メモリ３に格納する。
【００２９】
インターフェース手段１１は、共通バス４を介してデータの入出力（例えば、メモリ３、５からのデータ転送、格納等）の制御や、共通バスの競合制御を行なう。
【００３０】
制御手段１２は、ＣＰＵ１の指示に基づいて、ソート処理部１０全体のシーケンス制御を行ない、インターフェース手段１１へのデータ転送の指示等を行なう。
【００３１】
マップ作成手段１３は、制御手段１２の指示に基づいて、インターフェース手段１１を介して入力される共通バスからの転送データ（例えば、ソート対象のデータ集合Ｄ１）を作業用メモリ１６に転送したり、データ集合Ｄ１に関する優先キー配置マップを作業用メモリ１６に作成する。ここで、優先キー配置マップとは、データ集合の一種であり、具体的には、データ集合Ｄ１の優先キーＫ１，同一データ（例えば、同一の値）となる優先キーＫ１の出現回数、スタートアドレスの値、交換回数カウンタの値を組とするエントリから構成される。
【００３２】
ＣＡＭ（Content Addressable Memory）１４は、メモリを持つ検索手段であり、マップ作成手段１３に接続され、制御手段１２の指示によって制御され、マップ作成手段１３の転送するデータを入力データとして、検索結果をマップ作成手段１３に出力する。例えば、ＣＡＭ１４内のメモリに同一のデータの登録があれば、データを登録しているアドレスをマップ作成手段１３に出力し、同一のデータが無ければ登録が無い旨の信号（”ＮｏＭａｔｃｈ”信号）をマップ作成手段１３に出力する。なお、マップ作成手段１３は、ＣＡＭの検索結果を利用して作業用メモリ１６の転送位置の検索やマップ作成を行なう。
【００３３】
ソート手段１５は、ハードウェアで構成されたソートブロックであり、制御手段１２の指示に従って、作業用メモリ１６の指定された範囲のデータに対してソート（例えば、クイックソート、マージソート、ヒープソート等）を行なう。
【００３４】
作業用メモリ１６は、優先キー配置マップ領域とデータ領域に分けられ、データ領域にはデータ集合Ｄ１やソート結果が格納される。また、優先キー配置マップ領域のアドレスは、ＣＡＭ１４が出力するアドレスとの対応付けがあらかじめされている。
【００３５】
交換手段１７は、制御手段１２からの指示によって制御され、作業用メモリ１６の優先キー配置マップを読み出して、ＣＡＭ１４の検索結果を用いて、データ領域のデータ集合Ｄ１を構成するエントリの場所の入れ替えをし、データ集合Ｄ１のソートを行なう。
【００３６】
このように、ソート処理部１０にて共通バス４に接続されるのはインターフェース手段１１だけであり、その他の手段１２〜１５、１７、作業用メモリ１６は、共通バス４に直接には接続されず、ソート処理部１０内の内部バスで接続される。
【００３７】
このような装置の動作を説明する。ここで、図１６に示すデータ集合Ｄ１に対して優先キーＫ１とキーＫ２とで多重ソートする場合を一例として説明する。また、図２は、図１に示す装置の動作を説明したフローチャートである。そして、図３は、測定対象のデータ集合と作業用メモリの内容を示した図であり、図４〜図５は、作業用メモリの内容を示した図である。
【００３８】
ＣＰＵ１が、共通バス４、ソート処理部１０のインターフェース１１を介して、ソート処理部１０の制御手段１２に、ソート対象のデータ集合Ｄ１の範囲、優先キーＫ１、キーＫ２を通知する（Ｓ１０）。
【００３９】
そして、制御手段１２が、インターフェース手段１１に、データベース格納メモリ３からデータ集合Ｄ１を取得するように指示をする。これにより、インターフェース手段１１が、共通バス４を介して、データベース格納メモリ３からデータ集合Ｄ１を読み出し、マップ作成手段１３に転送する（Ｓ１１）。
【００４０】
さらに、マップ作成手段１３が、インターフェース手段１１から順次転送されてくるデータ集合Ｄ１を、順番に作業用メモリ１６のデータ領域に転送する。ここで、データ領域の先頭アドレス値を”１”とし、先頭アドレスから各エントリを順番に格納する。また、各エントリそれぞに新たなラベルとして交換フラグを付加して格納する。そして、マップ作成手段１３が、転送と同時に各エントリの優先キーＫ１をＣＡＭ１４に出力し、ＣＡＭ１４に検索を行なわせる（Ｓ１２）。
【００４１】
そして、ＣＡＭ１４が、ＣＡＭ１４内のメモリを検索し、優先キーＫ１に関して”ＮｏＭａｔｃｈ”の場合、ＣＡＭ１４内のメモリに優先キーＫ１を登録すると同時にマップ作成手段１３に”ＮｏＭａｔｃｈ”信号を出力する（Ｓ１３、Ｓ１４）。これにより、マップ作成手段１３が、作業用メモリ１６の優先キー配置マップ領域内に”ＮｏＭａｔｃｈ”となった優先キーＫ１の値、出現回数（初期値は１）、スタートアドレス（初期値は０）、交換カウンタ（初期値は０）を組として登録する。作業用メモリ１６の優先キー配置マップ領域に書き込む場所は、ＣＡＭ１４内のメモリに登録したアドレスに対応させる（Ｓ１６）。
【００４２】
一方、ＣＡＭ１４が、ＣＡＭ１４内のメモリを検索し、優先キーＫ１に関して同一のデータ（つまり、同じ値）が存在した場合、ＣＡＭ１４が、検索した優先キーＫ１に対応するアドレスをマップ作成手段１３に出力する（Ｓ１３、Ｓ１５）。そして、マップ作成手段１３が、ＣＡＭ１４の出力したアドレスに対応する作業用メモリ１３の優先キー配置マップ領域内の場所を検索し、検索した場所に登録されている出現回数の値を”＋１”する（Ｓ１６）。
【００４３】
データ集合Ｄ１のエントリＡ〜Ｊ全ての転送、登録が終了するまで、ステップＳ１３〜Ｓ１６を繰り返し、優先キーＫ１それぞれに対し、出現回数、スタートアドレス、交換回数カウンタからなる優先キー配置マップを作成する（Ｓ１７、Ｓ１２〜Ｓ１６）。
【００４４】
優先キー配置マップの作成が終了すると、制御手段１２からの指示に従って、ソート手段１５が、作業用メモリ１６の優先キー配置マップ領域内のデータを対象として、優先キーＫ１を使って降順ソートを行なう（Ｓ１７、Ｓ１８）。
【００４５】
そして、交換手段１７が、制御手段１２の指示に従って、作業用メモリ１６のソート後の優先キー配置マップのスタートアドレスを、（自身よりも上にあるデータの出現回数の合計値＋１）にする。例えば、優先キーＫ１の値”６”では、自身よりも上にデータが存在しないので（ステップＳ１８で降順ソートしているため）、スタートアドレスを”１”にする。そして、優先キーＫ１の値”５”では、自身よりも上のデータ”６”の出現回数の値が”３”なので、優先キーＫ１の値”５”のスタートアドレスを”４”にする。以下、同様に優先キーＫ１の値”３”〜”１”のスタートアドレスを求める（Ｓ１９）。
【００４６】
さらに、交換手段１７が、作業用メモリ１６のデータ領域の先頭データから交換フラグの値が”０”のエントリを探し、このエントリの優先キーＫ１をＣＡＭ１４で検索させる。そして、ＣＡＭ１４の検索結果（アドレス）から、優先キー配置マップ領域内の該当する優先キーＫ１の「スタートアドレス」＋「交換回数カウンタ」の値を求め、この値に該当するデータ領域内のアドレスのエントリと交換を行なう。そして、交換後に交換先のエントリの「交換フラグ」の値を”１”にする。さらに、優先キー配置マップ領域内の検索された該当アドレスの「交換回数カウンタ」の値を”＋１”する。
【００４７】
例えば、１回目の交換では、エントリＡのデータの優先キーＫ１の値”５”を、ＣＡＭ１４で検索する。この検索により、優先キー配置マップの優先キーＫ１の値”５”と組になっている「スタートアドレス”４”」＋「交換回数カウンタ”０”」の加算値”４”を求める。求めた加算値”４”、すなわちアドレス値”４”に該当するデータ領域内のエントリＤとエントリＡとを交換する。その後、エントリＡの交換フラグを”１”にする。また、優先キー配置マップの優先キーＫ１の値”５”と組にした「交換回数カウンタ」の値を”＋１”する。
【００４８】
そして、２回目の交換では、データ領域の先頭から交換フラグが”０”のエントリＤのデータの優先キーＫ１の値”５”を、ＣＡＭ１４で検索する。この検索により、優先キー配置マップの優先キーＫ１の値”５”と組になっている「スタートアドレス”４”」＋「交換回数カウンタ”１”」の加算値”５”を求める。求めた加算値”５”、すなわちアドレス値”５”に該当するデータ領域内のエントリＥとエントリＤとを交換する。その後、エントリＤの交換フラグを”１”にする。また、優先キー配置マップの優先キーＫ１の値”５”と組にした「交換回数カウンタ」の値を”＋１”する。
【００４９】
以降順番に、エントリＡ〜Ｊの全データの「交換フラグ」の値が”１”になるまで、すなわち、エントリの入れ替えを１０回繰り返す。これにより、優先キーＫ１によるデータ集合Ｄ１の１回目のソートが終了する（Ｓ２０）。
【００５０】
次に、キーＫ２による２回目のソートを行なう。
２回目のソートでは、優先キーＫ１の値が同一のデータ集合Ｄ２〜Ｄ５ごとに、キーＫ２でソートを行なうが、各データ集合Ｄ２〜Ｄ５の範囲は、作業用メモリ５の優先キー配置マップを参照して行なう。具体的には、ソート手段１５が、作業用メモリ５の優先キー配置マップの先頭から順にエントリを読み出し、読み出したエントリの（「スタートアドレス」＋「出現回数」−１）を求め、読み出した「スタートアドレス」の値から求めた値の範囲のデータ集合Ｄ２〜Ｄ５を対象として、キーＫ２でソートを行なう。例えば、優先キーＫ１の値”６”では、データ領域のアドレス”１”〜”３”をソート対象とし、優先キーＫ１の値”５”では、データ領域のアドレス”４”〜”６”をソート対象とし、優先キーＫ１の値”３”では、データ領域のアドレス”７”〜”８”をソート対象とする。以降、同様に優先キー配置マップの全エントリに対してキーＫ２によるソートを行なう（Ｓ２１）。
【００５１】
２回目のソートが終了すると、制御手段１２の指示に従って、インターフェース手段１１が、作業用メモリ１６のデータ領域の多重ソート後のデータ集合を読み出し、共通バス４を介してデータベース格納メモリ３の所定の領域に格納する。なお、ソート結果のデータ集合を参照するためのインデックス等として使用できるように、インターフェース手段１１が、作業用メモリ１６の優先キー配置マップも、検索結果と共にデータベース格納メモリ３に格納してもよい（Ｓ２２）。
【００５２】
このようにマップ作成手段１３が、共通バス４を介して入力されるデータ集合Ｄ１内の優先キーＫ１の出現回数に基づいて優先キー配置マップを作成し、交換手段１７が、優先キー配置マップを用いてエントリの交換を行なう。そして、ソート手段１５が、優先キー配置マップを参照してソート対象の範囲を求め、２回目のソートを行なう。これにより、ソート前のデータ集合Ｄ１のエントリ数が多くとも、短時間でソートを行なうことができる。また、ＣＰＵ１や共通バス４の占有率を減少でき、ＣＰＵ１や共通バス４の動作状況に影響されず、短時間でソートを行なうことができる。
【００５３】
また、ＣＡＭ１４が、入力される優先キーＫ１に対して検索を行なって、マップ作成手段１３に検索結果のアドレスを返すので、マップ作成手段１３が、優先キーＫ１それぞれの出現回数をカウントする必要が無く、優先キー配置マップを高速に作成することができる。また、このマップを用いることにより、簡易なアルゴリズムでの高速な多重ソートを実現できる。
【００５４】
［第２の実施例］
図１に示す装置と構成は同じだが、マップ作成手段１３、交換手段１７の動作が異なる。第１の実施例では、データ集合Ｄ１に交換フラグを付加して多重ソートする一例を示したが、交換フラグを付加せずに多重ソートする一例を説明する。
【００５５】
このような装置の動作を説明する。ここで、第１の実施例と異なる動作を主に説明するう。図２に示すフローチャートのステップＳ１０〜Ｓ１１までは、第１の実施例と同様で、ステップＳ１２において、マップ作成手段１３が、インターフェースからのデータ集合Ｄ１の各エントリに交換フラグを付加することなく、作業用メモリのデータ領域にそのまま格納する。
【００５６】
そして、ステップＳ１３〜Ｓ１９までは、第１の実施例と同様で、ステップＳ１９において、交換手段１７が、作業用メモリ１６のデータ領域の先頭アドレス（アドレス値”１”）を、判断アドレスとし、この判断アドレスに登録されているエントリの優先キーＫ１を取得し、このエントリの優先キーＫ１をＣＡＭ１４で検索させる。そして、ＣＡＭ１４の検索結果（アドレス）から、優先キー配置マップ領域内の該当する優先キーＫ１の「スタートアドレス」＋「交換回数カウンタ」の値を求め、この値に該当するデータ領域内のアドレスのエントリと交換を行なう。そして、検索結果で求めた優先キーＫ１に対応した優先キー配置マップ領域にある「交換回数カウンタ」の値を”＋１”する。
【００５７】
ここで、「スタートアドレス」＋「交換回数カウンタ」によって求めた結果が、交換先と交換元のエントリが同じ場合は、検索結果で求めた優先キーＫ１に対応した優先キー配置マップ領域にある「交換回数カウンタ」の値を”＋１”し、判断アドレスを”＋１”する。
【００５８】
具体的に図６、図７を用いて説明する。１回目の交換では、判断アドレスが”１”なので、アドレス”１”のエントリＡのデータの優先キーＫ１の値”５”を、ＣＡＭ１４で検索する。この検索により、優先キー配置マップの優先キーＫ１の値”５”と組になっている「スタートアドレス”４”」＋「交換回数カウンタ”０”」の加算値”４”を求める。求めた加算値”４”、すなわちアドレス値”４”に該当するデータ領域内のエントリＤとエントリＡとを交換する。その後、優先キー配置マップの優先キーＫ１の値”５”と組にした「交換回数カウンタ」の値を”＋１”する（図６参照）。
【００５９】
そして、２回目の交換では、アドレス”１”（判断アドレスが”１”なため）のエントリＤのデータの優先キーＫ１の値”５”を、ＣＡＭ１４で検索する。この検索により、優先キー配置マップの優先キーＫ１の値”５”と組になっている「スタートアドレス”４”」＋「交換回数カウンタ”１”」の加算値”５”を求める。求めた加算値”５”、すなわちアドレス値”５”に該当するデータ領域内のエントリＥとエントリＤとを交換する。その後、優先キー配置マップの優先キーＫ１の値”５”と組にした「交換回数カウンタ」の値を”＋１”する（図６参照）。
【００６０】
一方、交換元と交換先のアドレスが同一の場合を、図７を用いて説明する。
判断アドレスが”１”なので、アドレス”１”のエントリＦのデータの優先キーＫ１の値”６”を、ＣＡＭ１４で検索する。この検索により、優先キー配置マップの優先キーＫ１の値”６”と組になっている「スタートアドレス”１”」＋「交換回数カウンタ”０”」の加算値”１”を求める。求めた加算値”１”、すなわちアドレス値”１”は、交換元、交換先ともにエントリＦとなっているので、判断アドレスを”１”から”２”にする。その後、優先キー配置マップの優先キーＫ１の値”６”と組にした「交換回数カウンタ」の値を”＋１”する（図７参照）。
【００６１】
そして、次の交換では、アドレス”２”（判断アドレスが”２”に変更されたため）のエントリＢのデータの優先キーＫ１の値”３”を、ＣＡＭ１４で検索する。この検索により、優先キー配置マップの優先キーＫ１の値”３”と組になっている「スタートアドレス”７”」＋「交換回数カウンタ”０”」の加算値”７”を求める。求めた加算値”７”、すなわちアドレス値”７”に該当するデータ領域内のエントリＧとエントリＢとを交換する。その後、優先キー配置マップの優先キーＫ１の値”３”と組にした「交換回数カウンタ」の値を”＋１”する（図７参照）。
【００６２】
以降順番に、エントリＡ〜Ｊの数分（図６、７では１０回）交換を繰り返し、優先キーＫ１によるデータ集合Ｄ１の１回目のソートが終了する（Ｓ２０）。なお、ステップＳ２１、２２の動作は同様なので説明を省略する。
【００６３】
このようにマップ作成手段１３が、共通バス４を介して入力されるデータ集合Ｄ１内の優先キーＫ１の出現回数に基づいて優先キー配置マップを作成し、交換手段１７が、優先キー配置マップを用いてエントリの交換を行なう。そして、ソート手段が、優先キー配置マップを参照してソート対象の範囲を求め、２回目のソートを行なう。これにより、ソート前のデータ集合Ｄ１のエントリ数が多くとも、短時間でソートを行なうことができる。また、ＣＰＵ１や共通バス４の占有率を減少でき、ＣＰＵ１や共通バス４の動作状況に影響されず、短時間でソートを行なうことができる。
【００６４】
また、ＣＡＭ１４が、入力される優先キーＫ１に対して検索を行なって、マップ作成手段１３に検索結果のアドレスを返すので、マップ作成手段１３が、優先キーＫ１それぞれの出現回数をカウントする必要が無く、優先キー配置マップを高速に作成することができる。また、このマップを用いることにより、簡易なアルゴリズムでの高速な多重ソートを実現できる。
【００６５】
［第３の実施例］
多重ソートする場合に、データ集合のなかから、所望のキーを有するエントリだけを抽出してソートを行ないたいという要求が強い。例えば、トラフィックを監視する装置・システムでは、各エントリは、複数種類のラベル（例えば、”宛先アドレス（destination address）”、”送信元アドレス（source address）”、”フレーム数”）を組とし、このうち”宛先アドレス”を優先キーとし、”フレーム数”を第２のキーとして多重ソートする場合が多い。
【００６６】
しかしながら、宛先アドレスの種類は膨大であり、全宛先アドレスに対してソートを行なったとしてもユーザに取って不必要な情報が多く、ソート結果の解析が困難というも問題があった。
【００６７】
図８は、本発明の第３の実施例を示した構成図である。ここで、図１と同一のものには同一符号を付し、説明を省略する。図８において、設定手段８が新たに設けられ、共通バス４に接続される。また、ソート処理部１０のマップ作成手段１３の代わりに、マップ作成手段１８が設けられる。入出力メモリ５の図示は省略する。
【００６８】
設定手段８は、ユーザから優先キーの種類および優先順位が入力され、ＣＰＵ１に設定する。マップ作成手段１８は、制御手段１２の指示に従って動作し、インターフェース１１、ＣＡＭ１４、作業用メモリ１６と接続される。
【００６９】
このような装置の動作を図９に示すフローチャートを用いて説明する。図１に示す装置と異なる部分を主に説明する。また、図１０（ａ）〜（ｃ）のそれぞれは、ソート対象のデータ集合、優先キー配置マップ、データ領域の中身を示した図である。ここで、抽出対象の優先キーＫ１の種類および優先順位は、宛先アドレスの”Ｂｄ”、”Ｃｄ”、”Ａｄ”とする。
【００７０】
ユーザが、設定手段８を介してＣＰＵ１に、ソート対象のデータ集合（図１０（ａ）参照）、１回目のソートで使用する優先キー、２回目のソートで使用するキーが入力され、ソートに用いる優先キーの種類（つまり、抽出対象のキー）および優先順位の設定を行なう（Ｓ３０）。
【００７１】
そして、ＣＰＵ１が、共通バス４、ソート処理部１０のインターフェース１１を介して、ソート処理部１０の制御手段１２に、ソート対象のデータ集合の範囲、優先キーＫ１、キーＫ２、優先キーの種類および優先順位の設定を行なうを通知する（Ｓ３１）。
【００７２】
そして、制御手段１２が、ＣＡＭ１４とマップ作成手段１８に、ソートに使用する優先キーの種類および優先順位を通知し、ＣＡＭ１４が、ＣＡＭ１４内のメモリに、あらかじめ優先キー配置マップの内容を登録し、マップ作成手段１８が、作業用メモリ１６の優先キー配置マップ領域内に、優先キーＫ１の値、出現回数（初期値は０）、スタートアドレス（初期値は０）、交換カウンタ（初期値は０）を組として登録する。作業用メモリ１６の優先キー配置マップ領域に書き込む場所は、ＣＡＭ１４内のメモリに登録したアドレスに対応させる。この際、優先キーは、設定された優先順位に従って先頭から順に優先キー配置マップに登録する（Ｓ３２）。
【００７３】
そして、制御手段１２が、インターフェース手段１１に、データベース格納メモリ３からデータ集合を取得するように指示をする。これにより、インターフェース手段１１が、共通バス４を介して、データベース格納メモリ３からデータ集合を読み出し、マップ作成手段１８に転送する（Ｓ３３）。
【００７４】
さらに、マップ作成手段１８が、インターフェース手段１１から順次転送されてくるデータ集合を、順番にエントリの優先キーをＣＡＭ１４に出力し、ＣＡＭ１４に検索を行なわせる（Ｓ３４）。
【００７５】
そして、ＣＡＭ１４が、ＣＡＭ１４内のメモリを検索し、優先キーＫ１に関して”ＮｏＭａｔｃｈ”の場合、ＣＡＭ１４内のメモリに優先キーＫ１を新たに登録せず、マップ作成手段１８に”ＮｏＭａｔｃｈ”信号を出力する。さらに、マップ作成手段１８も、”ＮｏＭａｔｃｈ”であったエントリは、作業用メモリ１６に転送せず、マップを変更しない（Ｓ３４、Ｓ３５）。
【００７６】
一方、ＣＡＭ１４が、ＣＡＭ１４内のメモリを検索し、優先キーＫ１に関して同一のデータが存在した場合、ＣＡＭ１４が、検索した優先キーＫ１に対応するアドレスをマップ作成手段１８に出力する（Ｓ３４、Ｓ３６）。そして、マップ作成手段１８が、ＣＡＭ１４の出力したアドレスに対応する作業用メモリ１３の優先キー配置マップ領域内の場所を検索し、検索した場所に登録されている出現回数の値を”＋１”すると共に、検索したエントリを、作業用メモリのデータ領域の先頭から順に転送する（Ｓ３７）。
【００７７】
そして、データ集合のエントリ全ての検索が終了するまで、ステップＳ３８、Ｓ３４〜Ｓ３７を繰り返し、設定された優先キーそれぞれに対し、出現回数、スタートアドレス、交換回数カウンタからなる優先キー配置マップを作成する。これにより、作業用メモリ１６のデータ領域に転送されるエントリは、優先キーの宛先アドレスＡｄ、Ｂｄ，Ｃｄを含むもののみとなる（図１０（ｂ）参照）（Ｓ３８、Ｓ３４〜Ｓ３７）。
【００７８】
そして、スタートアドレスを算出し、優先キーＫ１によるエントリの入れ替え，キーＫ２による降順ソート（ソート結果は、図１０（ｃ）参照）、ソート結果の格納は、図１に示す装置と同様なので説明を省略する。なお、予め優先キー配置マップを作成しているので、図２に示すステップＳ１８のマップのソートは、不必要である。
【００７９】
このように、設定手段８で設定された優先キーを含むエントリのみを対象として多重ソートを行なうので、ソート結果に不要なエントリが含まれず、ソート結果の解析等が容易になる。
【００８０】
［第４の実施例］
図１１は、本発明の第４の実施例を示した構成図であり、図８に示す装置を、トラフィックを監視する装置・システムに適用した一例である。ここで、図８と同一のものには同一符号を付し、説明を省略する。図１１において、トラフィック統計システム２０は、インターネット１００に接続され、インターネット１００を流れるトラフィックの統計、解析などを行なう。トラフィック統計システム２０は、ＣＰＵ１、設定手段８、ソート処理部１０、データベース格納メモリ３である集計メモリ３ａ、ソート結果メモリ３ｂを有し、共通バス４にて相互に接続される。また、トラフィック統計システム２０は、集計エンジン９を有する。集計メモリ３ａは、集計エンジン９と接続され、集計エンジン９が集計したデータ集合を保存する。ソート結果メモリ３ｂは、ソート処理部１０がソートした結果を保存する。集計エンジン９は、インターネット１００と接続され、インターネット１００からのフレームを集計し、集計メモリ３ａに格納する。
【００８１】
このような装置の動作を説明する。
トラフィック統計システム２０が、インターネット１００のモニタ回線に接続される。そして、集計エンジン９が、インターネット１００からのデータを、例えば図１０に示したような”あて先アドレス”、”送信元アドレス”、”フレーム数”を組とし、組としたエントリを所定時間または所定量集計し、データ集合として集計メモリ３ａに格納する。
【００８２】
そして、図８に示したように設定手段８からＣＰＵ１に設定が行なわれ、ＣＰＵ１が設定手段８の設定に従って、ソート処理部１０に集計メモリ３ａ内のデータ集合の多重ソートを指示にする。この指示に従って、ソート処理部１０が多重ソートを行ない、ソート結果をソート結果メモリ３ｂに格納する。さらに、ＣＰＵ１が、ソート結果をユーザにレポートする。
【００８３】
［第５の実施例］
ソート対象のデータ集合に含まれるラベルを優先キーとして用いるだけでなく、データ集合に含まれないパラメータにて多重ソートを行なう要求がある。例えば、テストの結果を個人の合計点順（優先キー）で、かつ、個人の中で得点の高い科目順（２回目のソート用のキー）に並べたい場合等である。
【００８４】
図１２は、本発明の第５の実施例を示した構成図である。ここで、図１と同一のものには同一符号を付し、説明を省略する。図１２において、ソート処理部１０に加算手段１９が新たに設けられる。加算手段１９は、マップ作成手段１３からのデータを加算して加算した値をマップ作成手段１３に返す。
【００８５】
このような装置の動作を説明する。ここで、図１３は、ソート対象のデータ集合、および優先キー配置マップを示している。図１３において、ソート対象のデータ集合の各エントリは、”個人名”、”科目”、”点数”を組としている。また、優先キー配置マップのエントリは、”個人名”、”優先キー”、”出現回数”、”スタートアドレス”、”交換回数カウンタ”からなる。”優先キー”は、各個人の”点数”の合計点である。
【００８６】
マップ作成手段１３が、作業用メモリ１６のデータ領域にデータ集合を転送し、”個人名”でＣＡＭ１４に検索させる。そして、ＣＡＭ１４の検索結果に基づいて、優先キー配置マップの作成、書き込みを行なうが、検索させたアドレスに対応する個人の優先キーの値を作業用メモリ１６のマップから読み出して、検索したエントリの点数と読み出した優先キーを加算手段１９に加算させ、加算した合計値、つまり、個人ごとの合計点をマップの各エントリの優先キーに格納する。
【００８７】
そして、合計点の優先キーで、マップを降順ソートし、マップを参照して図１に示す装置と同様に多重ソートを行なう。さらに、図１４に示すようにソート結果を出力する。この際、ＣＰＵ１が、データ格納メモリ３に格納されるマップを参照して、合計点を付加してレポート出力するとよい。
【００８８】
このように、優先キー配置マップ作成時に、優先キーに対して演算／集計をおこなうことにより、初期のデータ集合にないパラメータを優先キーとして使用することができる。
【００８９】
なお、本発明はこれに限定されるものではなく、以下に示すようなものでもよい。
トラフィック統計システムに、図８に示す第３の実施例を適用する構成を示したが、図１に示す第１、第２の実施例、図１２に示す第５の実施例を適用してもよい。
【００９０】
ソート対象のデータ集合のエントリの構成は、どのような種類のラベルを組み合わせてもよい。また、１回目ソート用の優先キー、２回目ソート用のキーは、どのような組み合わせでもよい。そして、設定手段８で設定される優先キー配置マップも、どのような組み合わせでもよい。
【００９１】
また、降順ソートする例を示したが、昇順ソートでもよい。
【００９２】
図１２に示す装置において、加算手段１９が、加算を行なって優先キーを作成する構成を示したが、演算は加算に限らずどのような演算でもよく、要は、優先キーとなるデータ値に、所望のラベルの種類ごとで集計した集計データを用いればよい。
【図面の簡単な説明】
【００９３】
【図１】本発明の第１の実施例を示した構成図である。
【図２】図１に示す装置の動作を説明したフローチャートである。
【図３】測定対象のデータ集合と作業用メモリの内容を示した図である。
【図４】作業用メモリの内容を示した図である。
【図５】作業用メモリの内容を示した図である。
【図６】作業用メモリの内容を示した図である。
【図７】作業用メモリの内容を示した図である。
【図８】本発明の第３の実施例を示した構成図である。
【図９】図８に示す装置の動作を説明したフローチャートである。
【図１０】測定対象のデータ集合と作業用メモリの内容を示した図である。
【図１１】本発明の第４の実施例を示した構成図である。
【図１２】本発明の第５の実施例を示した構成図である。
【図１３】測定対象のデータ集合と作業用メモリの内容を示した図である。
【図１４】測定対象のデータ集合とソート結果の内容を示した図である。
【図１５】従来の多重ソート装置の構成を示した図である。
【図１６】測定対象のデータ集合と作業用メモリの内容を示した図である。
【図１７】従来の多重ソート装置のその他の構成を示した図である。
【符号の説明】
【００９４】
３  データベース格納メモリ
４  共通バス
３ａ  集計メモリ
３ｂ  ソート結果メモリ
８  設定手段
９  集計エンジン
１１インターフェース手段
１３、１８  マップ作成手段
１４  ＣＡＭ
１５  ソート手段
１６  作業用メモリ
１７  交換手段
１９  加算手段
２０  トラフィック統計システム
【図１】
0004766324.tif 000002
【図２】
0004766324.tif 000003
【図３】
0004766324.tif 000004
【図４】
0004766324.tif 000005
【図５】
0004766324.tif 000006
【図６】
0004766324.tif 000007
【図７】
0004766324.tif 000008
【図８】
0004766324.tif 000009
【図９】
0004766324.tif 000010
【図１０】
0004766324.tif 000011
【図１１】
0004766324.tif 000012
【図１２】
0004766324.tif 000013
【図１３】
0004766324.tif 000014
【図１４】
0004766324.tif 000015
【図１５】
0004766324.tif 000016
【図１６】
0004766324.tif 000017
【図１７】
0004766324.tif 000018