(57)【特許請求の範囲】
【請求項１】
データの確率的処理方法において、前記データは、（ｘ１，...，ｘｎ）の形の多次元ｎ−タプルからなるデータ集合Ｓの形式で提供され、
ビット行列を用意し、
前記行列内のビットを指定するために使用されるＫ個の独立なハッシュ関数Ｈｋを用意し、
前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルのすべての値ｘに対するハッシュ値Ｈｋ（ｘ）を計算して結果を前記行列のビット［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］にセットすることにより前記ビット行列に前記ｎ−タプル（ｘ１，...，ｘｎ）を挿入する、
ことによってｎ次元データ構造が生成され、
前記ビット行列がＭ行およびＮ列を有し、
１次元だけで確定した値ｘｉを含むｎ−タプルのワイルドカードクエリ、すなわち単純ワイルドカードクエリが、
前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルの確定値ｘｉに対するハッシュ値Ｈｋ（ｘｉ）を計算し、
Ｋ個のビットマップ［Ｈｋ（ｘ），ｍ］（∀ｋ∈１...Ｋ，ｍ∈１...Ｍ）の論理的ＯＲとしてビットマップＢｘｉを計算する、
ことによって実行され、
複合ワイルドカードクエリが、
前記複合ワイルドカードクエリを構成するすべての単純ワイルドカードクエリの前記ビットマップＢｘｉを計算し、
前記ビットマップＢｘｉの間のビットごとの演算により集約ビットマップを計算する、
ことによって実行される
ことを特徴とする、データの確率的処理方法。
【請求項２】
数ＭおよびＮが、前記データ集合Ｓの前記ｎ−タプルの可能な値ｘの濃度に適応されることを特徴とする請求項１に記載の方法。
【請求項３】
ｎ−タプル（ｘ１，...，ｘｎ）の単純メンバーシップクエリが、
前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルのすべての値ｘに対するハッシュ値Ｈｋ（ｘ）を計算し、
前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて位置［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］における前記行列のすべてのビットがセットされているかどうかを分析する、
ことによって実行されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて位置［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］における前記行列のすべてのビットがセットされている場合、出力「真」が返されることを特徴とする請求項３に記載の方法。
【請求項５】
前記ビットマップＢｘｉにおいて少なくともＫビットがセットされている場合、出力「真」が返されることを特徴とする請求項１に記載の方法。
【請求項６】
積集合演算子が論理的ＡＮＤ演算にマップされることを特徴とする請求項１に記載の方法。
【請求項７】
和集合演算子が論理的ＯＲ演算にマップされることを特徴とする請求項１または６に記載の方法。
【請求項８】
前記集約ビットマップにおいて少なくともＫビットがセットされている場合、出力「真」が返されることを特徴とする請求項１、６および７のいずれか１項に記載の方法。
【請求項９】
前記ビットマップＢｘｉに基づいて、単純および複合両方のワイルドカード条件を満たすｎ−タプルの集合にわたる濃度クエリに対して回答されることを特徴とする請求項１、５ないし８のいずれか１項に記載の方法。
【請求項１０】
しきい値超過イベントが、
しきい値を設定し、
１次元ブルームフィルタによる前記設定しきい値に対応するセットビットの個数Ｎｔｈｒｅｓｈを計算し、
前記ビット行列の各行について、Ｎｔｈｒｅｓｈ／Ｋより多くのビットがセットされているかどうかチェックする、
ことにより検出されることを特徴とする請求項１ないし９のいずれか１項に記載の方法。
【請求項１１】
前記ビット行列の少なくともＫ行がＮｔｈｒｅｓｈ／Ｋより多くのセットビットを含む場合、出力「真」が返されることを特徴とする請求項１０に記載の方法。
【請求項１２】
データの確率的処理システムであって、請求項１ないし１１のいずれか１項に記載の方法を実行するシステムにおいて、前記データは、（ｘ１，...，ｘｎ）の形の多次元ｎ−タプルからなるデータ集合Ｓの形式で提供され、該システムは、
前記ｎ−タプルを受容する入出力要素と、
ビット行列を用意し、前記行列内のビットを指定するために使用されるＫ個の独立なハッシュ関数Ｈｋを用意し、前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルのすべての値ｘに対するハッシュ値Ｈｋ（ｘ）を計算して結果を前記行列のビット［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］にセットすることにより前記ビット行列に前記ｎ−タプル（ｘ１，...，ｘｎ）を挿入する、ことによってｎ次元データ構造を生成する処理要素と、
前記ビット行列を保存する保存要素と
を備えたことを特徴とする、データの確率的処理システム。
【請求項１３】
前記入出力要素が、単純メンバーシップクエリ、単純および／または複合ワイルドカードクエリ、および／またはしきい値超過クエリを受容するように構成されることを特徴とする請求項１２に記載のシステム。
【請求項１４】
ネットワークシステムであって、
ネットワークと、
該ネットワークにわたって配備され、パケットの送信元アドレスおよび宛先アドレスを観測することによりネットワークパケットモニタリングを実行する複数のネットワークプローブと、
前記ネットワークプローブから、それぞれのネットワークプローブによって観測された送信元アドレスおよび宛先アドレスのペアのサマリを含むモニタリングレポートを受容するように構成されたモニタリングアプリケーションと
を備え、
前記ネットワークプローブおよび前記モニタリングアプリケーションが、前記サマリの生成および／またはクエリを実行するために請求項１ないし１１のいずれか１項に記載の方法を使用するように構成される
ことを特徴とするネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの確率的処理方法およびシステムに関する。前記データは、（ｘ１，...，ｘｎ）の形のｎ−タプルからなるデータ集合Ｓの形式で提供される。
【背景技術】
【０００２】
確率的データ構造一般、特にブルームフィルタ（Bloom Filter, ＢＦ）は、現在、広範囲の重要なネットワークアプリケーションで使用されている。これは、高速なクエリおよび更新を依然として可能としながら、大量の情報をコンパクトに要約することができるためである。ＢＦ（非特許文献１参照）は、（例えば、ルーティング、フィルタリング、モニタリング、ディープパケットインスペクション（deep packet inspection, ＤＰＩ）、侵入検知システム（intrusion detection system, ＩＤＳ）等のために）高速ルックアップを必要とするローカル情報を保存すること、およびデータをエクスポートすることの両方に使用される。分散データベースやピアツーピアシステムにおいて、ＢＦは、各ノードで利用可能なリソースのサマリ（要約）を効率的にエクスポートするためにしばしば使用される。
【０００３】
しかし、標準的なＢＦは、メンバーシップクエリしかサポートしていないので、多くのアプリケーションにとって表現力が不十分である。カウンティングブルームフィルタ（Counting Bloom Filter, 以下ＣＢＦ）と呼ばれるＢＦへの拡張（例えば非特許文献２に記載）は、項目削除および近似的カウンティングをサポート可能な、よりフレキシブルなデータ構造を提供する。非特許文献３では、あるしきい値を超えるフローを検出するための類似のデータ構造が使用されている。しかし、複数のソースによって生成されるＢＦサマリはビットごとのＯＲを実行することによって情報損失なしに容易に集約可能であるのに対して、ＣＢＦは、集約に関して線型でないため、多くのネットワークアプリケーションによってはあまり魅力的でない。
【０００４】
ＢＦを本質的にパケットカウンタとして使用するために、ＢＦの表現力を向上させる他の解決法が提案されている（例えば非特許文献４参照）。しかし、これらの解決法は依然として、「フラット」な１次元キー空間に基づいており、例えばタプル間の関係（例えば、相異なるフローではあるが同じアプリケーションに属する関連するパケット）を追跡するためには使用できない。また、それらは、同一パケットが複数回計上されるのを回避できないという点で、個別カウンティングをサポートしてない。同じことは、スケッチ（sketch）のような他のデータ構造にも当てはまる。スケッチはさまざまなネットワークアプリケーションに一般的に使用され、特にカウンティングスケッチは、大きなベクトルデータを要約するために使用される。
【０００５】
最後に、非特許文献５において、著者は、未定義属性を有する近似的タプルクエリをサポートする、ＢＦベースのデータ構造を使用する解決法を提案している。このアプローチは、各行がタプルの属性の１つに対応するビット行列を使用する。それぞれの要素挿入後、相異なるＫ個の独立なハッシュ関数の集合が全体集合Ｈから選出され、それを用いて、標準的ブルームフィルタと同様に、各行へのマップのビットをセットする。メンバーシップクエリに対しては、特定のルックアップ行列が使用され、Ｈ内の各関数によって出力されるハッシュ値が、入力属性値にわたって計算される。各行でセットビットを指定するＫ個のハッシュ関数が存在する場合に、クエリは陽性（positive）の結果を返す。ワイルドカードクエリを実行するためには、未定義属性に対応する行を単にスキップすればよい。しかし、このデータ構造は、濃度推定クエリもしきい値超過（threshold trespassing）クエリもサポートしていない。さらに、このデータ構造は応答としてブール値しか返すことができないので、カウンティングには適していない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Bloom, B. H. "Space/time trade-offs in hash coding with allowable errors", in Communications of the ACM, vol. 13, no. 7, July, 1970, p. 422-426
【非特許文献２】L. Fan, P. Cao, J. Almeida, and A. Z. Broder, "Summary Cache: A Scalable Wide-Area (WEB) Cache Sharing Protocol", in IEEE/ACM Transactions on Networking, 8(3):281-293, 2000
【非特許文献３】C. Estan and G. Varghese, "New Directions in Traffic Measurement and Accounting", in Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement
【非特許文献４】M. Durand and P. Flajolet, "Loglog counting of large cardinalities," in ESA03, volume 2832 of LNCS, 2003, pp. 605-617
【非特許文献５】Muhammad Mukarram Bin Tariq, "Tuple Set Bloom Filter", Georgia Tech., presentation April 26, 2006
【発明の概要】
【発明が解決しようとする課題】
【０００７】
したがって、本発明の目的は、頭書のようなデータの確率的処理方法およびシステムにおいて、データに対して実行可能なクエリの種類に関して高い表現力を提供すると同時に、データの効率的な要約を実現するような改良およびさらなる展開を行うことである。
【課題を解決するための手段】
【０００８】
本発明によれば、上記の目的は、請求項１の構成を備えた方法によって達成される。この請求項に記載の通り、本方法は、ビット行列を用意し、前記行列内のビットを指定するために使用されるＫ個の独立なハッシュ関数Ｈｋを用意し、前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルのすべての値ｘに対するハッシュ値Ｈｋ（ｘ）を計算して結果を前記行列のビット［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］にセットすることにより前記ビット行列に前記ｎ−タプル（ｘ１，...，ｘｎ）を挿入する、ことによってｎ次元データ構造が生成されることを特徴とする。
【０００９】
また、上記の目的は、請求項１４の構成を備えたシステムによって達成される。この請求項に記載の通り、本システムは、以下のことを特徴とする。すなわち、システムは、前記ｎ−タプルを受容する入出力要素と、ビット行列を用意し、前記行列内のビットを指定するために使用されるＫ個の独立なハッシュ関数Ｈｋを用意し、前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルのすべての値ｘに対するハッシュ値Ｈｋ（ｘ）を計算して結果を前記行列のビット［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］にセットすることにより前記ビット行列に前記ｎ−タプル（ｘ１，...，ｘｎ）を挿入する、ことによってｎ次元データ構造を生成する処理要素と、前記ビット行列を保存する保存要素とを有する。
【００１０】
本発明によって認識されたこととして、上記の目的は、多次元ブルームフィルタとみなすことができる新規なデータ構造を導入することによって達成することができる。以下、このデータ構造を、２次元の場合には２ｄＢＦと略記する。２ｄＢＦは、タプル（ｘ１，ｘ２）∈Ｓ（あるいは一般のｎ次元の場合には（ｘ１，...，ｘｎ）∈Ｓ）の集合Ｓの統計的サマリを提供する。ここで、各タプルは１回だけ計上され、ｘ１，ｘ２（あるいはｘ１，...，ｘｎ）は、任意の種類の関連するデータ（あるいは、ピアツーピア関連の用語ではキー）の値を表す。本発明によるシステムは、前記ｎ−タプルを受容する入出力要素と、ｎ次元データ構造を生成する処理要素と、結果として得られるビット行列を保存する保存要素とを有する。
【００１１】
本発明によって使用されるデータ構造は、確率的データ構造である。確率的データ構造は、その設計および構成により、データを効率的に要約し高速ルックアップを実行する能力のような、ブルームフィルタと同様に有利な性質を継承している。しかし、同時に、確率的データ構造は、それに対して実行可能なクエリの種類に関して、はるかに高い表現力を提供する。本発明による方法およびシステムは、ワイルドカードクエリと、項目の多重度の近似的一意カウントをサポートする。さらに、本データ構造は、チェック対象のキーの集合を指定することを必要とせずに、所与の項目に対応する近似的カウントが所与のしきい値を超過したかどうか（「ブラインド」しきい値超過（"blind" threshold trespassing））を検出するためにも使用可能である。また、このデータサマリは、無損失集約をサポートする。すなわち、集合Ｓ１およびＳ２にわたって計算されたデータ構造の集約は、Ｓ１とＳ２の和集合にわたって計算されたデータ構造に等しい。さらに、同一タプルの多重挿入は、推定される濃度に影響を及ぼさない。というのは、それらは同一ビットを再びセットするだけだからである。したがって、個別カウンティングが暗黙的に実現される。
【００１２】
上記のクエリは、従来のブルームフィルタの表現力を拡張し、より広範囲のネットワーキングアプリケーションをサポートすることができる。標準的ブルームフィルタは、特定のタプルに対するメンバーシップクエリに回答し（ワイルドカード不可）、エントリ総数を推定することしかできない。２ｄＢＦを利用することにより、例えば、（相異なるアドレスの広範囲の集合とコンタクトしているホストを探索することによって）スキャナを検出するために、相異なる測定ポイントからデータサマリを収集することが可能である。また、２ｄＢＦは、入口および出口ポイントごとのフロー数を関連づけることによって、ネットワークトラフィック行列を推定する目的のために使用可能である。
【００１３】
要約すれば、本発明は、ワイルドカードクエリ、しきい値検出クエリおよび一意カウントクエリが非常に高速に実行され、元のデータ構造に対するのとほとんど同じ結果を出力するような性質を保ちながら、多次元データ構造を圧縮する方法およびシステムを提供する。本方法は、独立なハッシュ関数の結果を用いた多次元ビットマップを指定することによって動作する。一意カウンティングに対する従来技術の解決法は、単一の集約カウンタの代わりにキーごとにカウンタを取得することや、相異なるワイルドカードクエリを組み合わせることができない点で、本発明のほうが有利である。従来技術のタプルクエリによるブルームフィルタは、濃度を推定することや、しきい値超過を検出することができない点で、本発明のほうが有利である。
【００１４】
好ましい実施形態によれば、ビット行列は、２次元の場合、Ｍ行およびＮ列を有し、数ＭおよびＮは、前記データ集合Ｓのｎ−タプルの可能な値ｘの濃度に適応されるようにしてもよい。すなわち、ＭおよびＮは、２個のキー／エントリｘ１およびｘ２の値の多重度（すなわち、相異なる値の数）に従って選択される。これにより、ブルームフィルタに固有の偽陽性（false positive）確率を有利に調整することができる。
【００１５】
入出力要素を使用することにより、さまざまなクエリをシステムに送ることができる。この目的のため、入出力要素は、それぞれのクエリを受容し、それらを処理要素へ転送するように構成されてもよい。データ集合Ｓの確率的サマリを提供する本発明によるデータ構造の特定の設計により、特に、単純メンバーシップクエリ、単純および／または複合ワイルドカードクエリ、および／またはしきい値超過クエリが、以下で詳細に説明するようにサポートされる。
【００１６】
例えば、ｎ−タプル（ｘ１，...，ｘｎ）の単純メンバーシップクエリは以下のように実行してもよい。
【００１７】
第１に、前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルのすべての値ｘに対するハッシュ値Ｈｋ（ｘ）を計算する。第２に、前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて位置［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］における行列のすべてのビットがセットされているかどうかを分析する。前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて位置［Ｈｋ（ｘ１），...，Ｈｋ（ｘｎ）］におけるすべてのビットがセットされている場合、これは、ｎ−タプルは高い確率でデータ集合に含まれていることを意味し、システムは「真」を返してよい。そうでない場合、ｎ−タプルは決してデータ集合に含まれておらず、システムは「偽」を返してよい。
【００１８】
また、１次元だけで確定した値ｘｉを含むｎ−タプルの単純ワイルドカードクエリは以下のように実行してもよい。
【００１９】
第１に、前記Ｋ個の独立なハッシュ関数Ｈｋのそれぞれについて前記ｎ−タプルの確定値ｘｉに対するハッシュ値Ｈｋ（ｘｉ）を計算する。第２に、Ｋ個のビットマップ［Ｈｋ（ｘ），ｍ］（∀ｋ∈１...Ｋ，ｍ∈１...Ｍ）の論理的ＯＲとしてビットマップＢｘｉを計算する。Ｂｘｉにおいて少なくともＫビットがセットされている場合、これは、値ｘｉを含むｎ−タプルが高い確率でデータ集合に含まれていることを意味し、システムは「真」を返してよい。そうでない場合、値ｘｉを含むｎ−タプルは決してデータ集合に含まれておらず、システムは「偽」を返してよい。
【００２０】
上記ですでに述べたように、本発明が提案するデータ構造は、（＊，ｘ２）∈Ｓ（２ｄの場合）の形の単純ワイルドカードクエリだけでなく、例えば（＊，ｘ２）∩（＊，ｘ１）∩（ｘ３，＊）∈Ｓの形の複合あるいは合成ワイルドカードクエリも可能である。好ましい実施形態によれば、複合ワイルドカードクエリは、まず複合ワイルドカードクエリを構成するすべての単純クエリによって返されるビットマップＢｘｉを（上記のように）計算した後、それらの間のビットごとの演算により集約ビットマップを計算することによって実行される。特に、積集合演算子は論理的ＡＮＤにマップされ、和集合演算子は論理的ＯＲにマップされてよい。結果として得られる包括的ビットマップにおいて少なくともＫビットがセットされている場合、クエリは陽性の結果を返してよい。
【００２１】
残りのクエリをどのようにして実行することができるかを説明するために、ビットマップＢｘｉについていくつかの考慮点を指摘しておかなければならない。容易に認識されることであるが、このようなビットマップは実際には、集合Ｓｘｉ＝｛（ｘ１，ｘｉ）∈Ｓであるようなｘｉ｝を要約する１次元ブルームフィルタである。このようなビットマップは、複合および単純いずれのワイルドカードクエリによって返されることも可能であり、さらなる処理を実行するために使用可能である。
【００２２】
このようなビットマップに基づいて、複合および単純両方のワイルドカード条件を満たすタプルの集合にわたる濃度クエリに回答することができる。関連するデータ構造の確率的性質により、返される結果は濃度の推定値となるため、推定誤差を伴う。周知の理論的分析から、ブルームフィルタによって要約される集合の濃度は、セットされていないビットの総数に基づいて推定可能であることが証明できる。このような性質は、Ｓｘｉの濃度の推定を行うために利用可能である。しかし、他の行および／または列との衝突による追加的なセットビットの存在のため、一般的に、古典的な推定公式は実際の濃度を過大推定する。これにもかかわらず、このような衝突を考慮に入れた新規な推定量を作ることができる。
【００２３】
これらと同じ原理を利用することにより、
【数１】
0005490905.tif 000002
の形のしきい値超過クエリにも回答することができる。認識されるように、構成から、行列の各行が計上するのは、最終ビットマップにおいてセットされているビットの高々１／Ｋである（Ｋは、使用される独立なハッシュ関数の個数）。これはもちろん控えめな推定値である。というのは、相異なる行のセットビットが重複する可能性があるからである。そこで、濃度が所定しきい値を超過する集合Ｓｘｉに対応するビットマップＢｘｉは、少なくともＮｔｈｒｅｓｈビットがセットされているはずであると仮定される。その結果、行
［Ｈｋ（ｘ），ｍ］  ∀ｋ∈１...Ｋ，ｍ∈１...Ｍ
のそれぞれは、少なくともＮｔｈｒｅｓｈ／Ｋビットがセットされているはずであり、しきい値超過イベントは以下のように検出できる。
【００２４】
第１に、標準的（１次元）ブルームフィルタ公式による所定しきい値に対応するセットビットの個数Ｎｔｈｒｅｓｈを計算する。推定量はゼロ平均なので、これはある信頼区間を考慮に入れることになる。次に、結果として得られるビット行列の各行について、Ｎｔｈｒｅｓｈ／Ｋより多くのビットがセットされているかどうかチェックする。少なくともＫ行が上記の条件を満たす場合、陽性の結果が返される。すなわち、所定しきい値を超過している。
【００２５】
上記で説明した本発明による２ｄＢＦデータ構造によってサポートされるクエリの種類は、さまざまなネットワークモニタリングアプリケーションにおいて有用であることがわかる。特に、同一イベントの相異なる観測を捨てることが依然として可能である一方で、相異なるトラフィックソースに関する情報サマリを集約する必要があるネットワークモニタリングアプリケーションにおいて有用である。
【００２６】
この種のアプリケーションの簡単な例として、スキャンを実行している悪意ホストの検出がある。この場合、モニタリングアプリケーションは、多くの相異なる宛先アドレスに対応するソースアドレスを探索しなければならない。モニタリング対象のネットワークにわたってプローブの集合が配備されており、中央モニタリングアプリケーションの目標は、ネットワーク上の多数の相異なるホストと接続を開始しようとしているアドレスを発見することであると仮定される。この場合、複数のパケットが複数のプローブによってモニタリングされる可能性が高いので、アプリケーションは、パケットが複数回捕捉されたアドレスをスキャナと標識することを確認すべきである。すなわち、重複する測定値を捨てることと、各外部ホストによってスキャンされた相異なるアドレスを考慮することとの両方が可能なように、各プローブからのレポートを集約しなければならない。この使用例では、本発明が提案するデータ構造は、観測される送信元−宛先ペアのサマリをエクスポートするために、各モニタリングプローブによって使用されることが可能である。レポートは、情報損失なしに集約可能であり、配備条件に応じて、（濃度クエリを使用することにより）すでに疑わしいホストの集合によってスキャンされているアドレスの個数をチェックすること、あるいは、（しきい値超過チェックを行うことによって）アドレスがスキャンを実行している可能性が高いかどうかのみをチェックすること、の両方が可能である。
【００２７】
２ｄＢＦ構造のもう１つの簡単な使用例として、トラフィック行列モニタリングがある。各入口および出口ポイントを通るフローを追跡する２つの異なる２ｄＢＦデータ構造を使用し、複合ワイルドカードクエリを実行することにより、所与の送信元−宛先ペアに対するフロー数の推定値を返すことができる。
【００２８】
さらにもう１つの例示的アプリケーションとして、ＶｏＩＰ異常検出がある。ユーザを個別に追跡するとともに、各ユーザごとに発呼を追跡するために、２ｄＢＦを使用することができる。そして、ソースを攻撃者や電話勧誘者（すなわち、異常な発呼数）として識別するために、濃度カウントを使用することができる。
【００２９】
本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１および１４に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００３０】
【図１】本発明の一実施形態による２次元ブルームフィルタデータ構造における挿入およびメンバーシップクエリを例示する模式図である。
【図２】本発明の別の実施形態による２次元ブルームフィルタデータ構造におけるワイルドカードクエリを例示する模式図である。
【発明を実施するための形態】
【００３１】
図１は、Ｍ×Ｎビット行列に基づく２次元ブルームフィルタ（以下２ｄＢＦと略記する）データ構造の構成を例示している。ＭおよびＮは、ｘ１およびｘ２の可能な値の濃度（これらはもちろん、それぞれのアプリケーション状況に依存し、通常は既知であるか、または少なくとも事前に推定可能である）に従って選択された整数値である。ビット行列のサイズを、処理対象の可能な値の濃度に適応させることにより、ブルームフィルタに固有の偽陽性確率を調整することができる。
【００３２】
図１に例示した実施形態は、Ｋ＝２の単純化した例である。Ｋは、行列内でビットを指定するために使用される独立なハッシュ関数の個数である。この単純化は、本発明による方法の基本的な作用原理を説明するために行われたものである。しかし、当業者には明らかなように、現実のアプリケーションでは、行列内でビットを指定する独立なハッシュ関数の個数ははるかに大きい。
【００３３】
新規タプル（ｘ１，ｘ２）の挿入後、Ｋ個の独立なハッシュ関数が、ペアの両方のフィールドにわたって計算され、Ｍ×Ｎ行列内のビットの関連する集合がセットされる。タプルルックアップを実行する際に、同じハッシュ値が計算され、同じ位置のビットがチェックされる。それらがすべてセットされている場合、クエリは陽性の値を返す。
【００３４】
詳細には、図１において、新規タプル（ｘ１，ｘ２）の挿入の手続きは次のように動作する。まず、各ハッシュ関数Ｈｋ（ここではＨ１およびＨ２のみ）について、ｘ１およびｘ２の両者に対するハッシュ値Ｈｋ（ｘ）を計算する。その結果に基づいて、位置
［Ｈｋ（ｘ１），Ｈｋ（ｘ２）］  ∀ｋ∈１...Ｋ
のビットがセットされる。
【００３５】
タプル（ｘ１，ｘ２）のメンバーシップルックアップの手続きは次のように動作する。まず、各ハッシュ関数Ｈｋ（ここでは再びＨ１およびＨ２のみ）について、ｘ１およびｘ２の両者に対するハッシュ値Ｈｋ（ｘ）を計算する。位置
［Ｈｋ（ｘ１），Ｈｋ（ｘ２）］  ∀ｋ∈１...Ｋ
のすべてのビットがセットされている場合、「真」を返す。これは、タプル（ｘ１，ｘ２）が、（偽陽性確率を考慮に入れると）少なくとも高い確率でデータ構造に含まれていることを意味する。そうでない場合、すなわち、関連するビットのうちのただ１つでもセットされていない場合、「偽」を返す。これは、タプル（ｘ１，ｘ２）がデータ構造に決して含まれていないことを意味する。
【００３６】
図２に関連して説明するように、２ｄＢＦは、（ｘ１，＊）にマッチするタプルの集合に関する情報を返すワイルドカードクエリもサポートする。その場合、ｘ１にわたって計算されたハッシュ値を用いて、行列のＫ行の集合を選択する。このような行のビットごとのＯＲを実行することにより、ワイルドカードクエリを満たすすべてのタプルの統計的サマリを提供するビットマップが得られる。このようなビットマップに基づいて、このようなタプルの個数を推定することができ、他の部分集合との積集合または和集合をとることができる。推定は、ＢＦにおいてセットされていないビット数と、対応する集合の濃度との間の周知の関係を利用することにより行われる。このメカニズムは、個別カウンティングを暗黙的に実現している。というのは、同一タプルの多重挿入は全体的結果に影響を及ぼさないからである。
【００３７】
さらに、ある行においてセットされているビット数と、最終的な集約ビットマップにおいてセットされているビット数との間の関係を利用することにより、単に行列内の各行を調べることによって、対応するワイルドカード集合の濃度が所与のしきい値を超えるような項目／キーｘ１が存在するかどうかを判定することができる。
【００３８】
詳細には、図２は、図１と同じＭ×Ｎビット行列に関するものであり、再び簡単のため、２つだけの独立なハッシュ関数が使用される実施形態を選んでいる。図２の実施形態は単純ワイルドカードクエリ（ｘ１，＊）を例示しており、これは以下のように実行される。まず、各ハッシュ関数Ｈｋ（ここではＨ１およびＨ２のみ）についてハッシュ値Ｈｋ（ｘ１）を計算する。次のステップで、その結果に基づいて、第１ステップで求められたＫ（ここではＫ＝２）個のビットマップ
［Ｈｋ（ｘ），ｍ］  ∀ｋ∈１...Ｋ，ｍ∈１...Ｍ
の論理的ＯＲとしてビットマップＢｘ１を計算する。こうして計算されたＢｘ１において少なくともＫビット（すなわち、図２の実施形態では２ビット）がセットされている場合、「真」を返す。例示した状況では、全部で７ビットがセットされているので、これは（（ｘ１，＊）の形のタプルの形式で）値ｘ１が、（偽陽性確率を考慮に入れると）少なくとも高い確率でデータ構造に含まれていることを意味する。そうでない場合、「偽」を返すことになる。これは、（ｘ１，＊）の形のタプルがデータ構造には決して含まれていないことを意味する。
【００３９】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
0005490905.tif 000003
【図２】
0005490905.tif 000004