(57)【要約】  本発明は、2次元フィルタの生成方法、クエリ方法、及び装置を開示する。上記の解決方法においては、2次元フィルタは2次元マトリクスを含み、2次元マトリクスを複数の鍵値エレメント・グループにリンクさせてもよく、したがって、フィルタの柔軟性を改善する。さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、上記の2次元フィルタに基づいてクエリを実行することが必要であるにすぎず、各々の鍵値エレメント・グループに対応するブルーム・フィルタを生成する必要はない。さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、複数のブルーム・フィルタの各々に基づいて1つずつクエリを実行する必要はない。したがって、現状では低いクエリ効率の問題をさらに解決することができる。
2017526081.tif 000002
【特許請求の範囲】
【請求項１】
鍵値エレメントのクエリを実行する方法であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを含む、
方法。
【請求項２】
いずれかの2の異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列法が異なっている、請求項１に記載の方法。
【請求項３】
前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップは、特に、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得するステップと、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するステップとを含む、請求項１又は２に記載の方法。
【請求項４】
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップは、特に、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するステップを含む、請求項３に記載の方法。
【請求項５】
2次元フィルタを生成する方法であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している、ステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、ステップと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するステップとを含む、
方法。
【請求項６】
前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外７）
2017526081.tif 000009
よりも大きいか又は等しく、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である、請求項５に記載の方法。
【請求項７】
前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である、請求項５又は６に記載の方法。
【請求項８】
前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するステップをさらに含む、請求項５乃至７のいずれか１項に記載の方法。
【請求項９】
鍵値エレメントのクエリを実行する装置であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するように構成される決定ユニットと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するように構成される設定ユニットと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するように構成される計算ユニットと、
前記クエリを実行されるべき鍵値エレメント・グループの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するように構成される取得ユニットと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するように構成されるクエリ・ユニットとを含む、
装置。
【請求項１０】
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記決定ユニットによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記決定ユニットによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列方法が異なっている、請求項９に記載の装置。
【請求項１１】
前記計算ユニットは、特に、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するように構成される、請求項９又は１０に記載の装置。
【請求項１２】
前記取得ユニットは、特に、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するように構成される、請求項１１に記載の装置。
【請求項１３】
2次元フィルタを生成する装置であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するように構成される確立ユニットと、
ハッシュ関数セットを決定し、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応し、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するように構成される決定ユニットであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、決定ユニットと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するように構成される生成ユニットとを含む、
装置。
【請求項１４】
前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外８）
2017526081.tif 000010
よりも大きいか又は等しく、前記行ベクトル及び前記列ベクトルは、前記確立ユニットによって生成される前記2次元マトリクスに含まれ、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である、請求項１３に記載の装置。
【請求項１５】
前記決定ユニットによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記決定ユニットによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記決定ユニットによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記決定ユニットによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である、請求項１３又は１４に記載の装置。
【請求項１６】
前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するように構成される初期化ユニットをさらに含む、請求項１３乃至１５のいずれか１項に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エレメント・クエリ技術及びマッチング技術、特に、2次元フィルタの生成方法、クエリ方法、及び装置に関する。
【背景技術】
【０００２】
コンピュータ・ソフトウェアを設計する場合には、通常、あるエレメントがあるセットの中に存在するか否かを判定する必要がある。例えば、文書処理ソフトウェアにおいては、ある英単語が正しく綴られているか否かを検査する必要があり(すなわち、その英単語が既知の辞書の中に存在するか否かを検査する必要があり)、他の例では、URL(Universal  Resource  Locator、統一資源位置指定子)フィルタリング・ソフトウェアにおいては、あるURLがフィルタリング・リストの中に存在するか否かが判定される。最も直接的な方法は、あるセットの中のすべてのエレメントをコンピュータに格納し、新たなエレメントが出現した際に、その新たなエレメントをそのセットの中のエレメントと直接的に比較することである。検索速度を改善するため、通常、ハッシュ・テーブル(Hash  Table)がセットを格納するのに使用される。ハッシュ・テーブルは、あるエレメントのキー・コード値にしたがってそのエレメントの記憶位置を迅速にマッピングするデータ構造であり、マッピング関数は、いわゆるハッシュ関数である。ハッシュ・テーブルの構造が図1Aに示されている。最初に、ハッシュ関数を使用することにより、あるセットの中のあるエレメントのハッシュ位置を取得し、その後、その位置におけるハッシュ・リンク・リストの中にそのエレメントを記録する。図1Aにおいて、ハッシュ関数がHASHであり、A1,A2,…,A8が、セットの中のエレメントであると仮定すると、図から、HASH(A1)=HASH(A2)=H1、HASH(A3)=HASH(A4)=H2、HASH(A5)=HASH(A6)=H3、及びHASH(A7)=HASH(A8)=H4であるということを理解できる。
【０００３】
ハッシュ・テーブルの利点は、あるエレメントがあるセットの中にあるか否かを迅速かつ正確に判定することができるという点であり、欠点は、比較的大きな記憶スペースが必要であるという点である。記憶スペースを低減するために、1次元のブルーム・フィルタが、1970年にBurton  Bloomによって提案され、ブルーム・フィルタの原理は、以下のようになる、すなわち、1次元のブルーム・フィルタは、相互に独立であるK個のハッシュ関数h1,h2,…,hk及び長さがmであるビット・ベクトルによって形成される。各々のハッシュ関数の値の範囲は、{0,1,…,m-1}であり、1バイトは、8ビットからなる。したがって、ビット・ベクトルによって実際に占有されるメモリ・スペースは、m/8バイトであり、ビット・ベクトルのすべてのビットは、0に初期化される。セットS={s1,s2,…,sn}であり、ハッシュ・シーケンス(h1(s),h2(s),…,hk(s))は、k個のハッシュ関数を使用することにより、セットSの中の各エレメントについて計算され、その後、ビット・ベクトルの中の対応するハッシュ・シーケンス・ビットが1に設定され、その結果、データ・エレメントのセットSがブルーム・フィルタにロードされる、又は、そのブルーム・フィルタが、データ・エレメントのセットSを表すとされる。例えば、h1(s1)=5である場合に、ビット・ベクトルの6番目のビットは、1に設定され、h2(s1)=10である場合に、ビット・ベクトルの11番目のビットは、1に設定され、hk(s1)=n-1となるまで、ビット・ベクトルのn番目のビットは、1に設定され、その結果、データ・エレメントs1がそのブルーム・フィルタにロードされるといわれる。セットSの中のすべてのデータ・エレメントがそのブルーム・フィルタにロードされると、そのブルーム・フィルタがデータ・エレメントのセットSを表すとされる。あるデータ・エレメントがセットSの中に存在するか否かについてクエリが行われると、同じk個のハッシュ関数を使用することにより、そのデータ・エレメントについてハッシュ・シーケンスの計算が行われる。そのハッシュ・シーケンスに対応するビット・ベクトルの各々のビットが1である場合には、そのデータ・エレメントは、Sに属していると考えられ、そうでない場合には、そのデータ・エレメントは、Sに属していないと考えられる。データが完全に格納される場合と比較して、記憶スペースを低減するのにブルーム・フィルタを使用してもよく、ブルーム・フィルタを使用すれば、あるセットに属するいずれのエレメントも、見逃されることはない。
【０００４】
以下の記載では、ジャンクEmailのアドレスの例を参照してブルーム・フィルタを簡単に説明する。
【０００５】
ジャンクEmailアドレスの数が1億であると仮定すると、最初に、その長さが16億ビットのビット・ベクトル、すなわち、2億バイトのベクトルが確立され、その後、16億のバイナリ・ビットのすべてが、0に初期化される。既知のジャンクEmailアドレスの各々について、8個の異なるハッシュ関数(F1,F2,…,F8)が8個のハッシュ値(f1,f2,…,f8)を生成するのに使用され、そのビット・ベクトルの位置であって8個のハッシュ値に対応する位置が、すべて1に設定される。上記の1億のジャンクEmailアドレスのすべてがそのような方法で処理された後に、ブルーム・フィルタが、これらのジャンクEmailアドレスについて生成される。図1Bに示されているように、図1Bは、ブルーム・フィルタを使用することによりあらわされるジャンクEmailアドレスの例示的な略図である。あるジャンクEmailアドレスXXX@163.comについて、8個の異なるハッシュ関数(F1,F2,…,F8)が8個のハッシュ値(f1,f2,…,f8)を生成するのに使用され、そのビット・ベクトルの位置であって8個のハッシュ値に対応する位置が、すべて1に設定され、この場合には、そのジャンクEmailアドレスがそのブルーム・フィルタにロードされるといわれる。
【０００６】
上記の生成されたブルーム・フィルタは、1つの鍵値エレメント・グループについてのものであり、すなわち、1つのブルーム・フィルタは1つの鍵値エレメント・グループのみにリンクさせることが可能であり、生成される必要があるブルーム・フィルタの数は、鍵値エレメント・グループの数によって決まる。したがって、ブルーム・フィルタの柔軟性は相対的に乏しいという欠点が存在する。
【発明の概要】
【０００７】
本発明の複数の実施形態は、2次元フィルタの生成方法、クエリ方法、及び装置を提供し、ブルーム・フィルタの柔軟性を改善する。
【０００８】
本発明の複数の実施形態において提示される特定の技術的解決方法は、以下のようになる。
【０００９】
第1の態様によれば、鍵値エレメントのクエリを実行する方法であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを含む、
鍵値エレメントのクエリを実行する方法が提供される。
【００１０】
第1の態様に関して、第1の態様の第1の可能な実装方法において、いずれかの2の異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列法が異なっている。
【００１１】
第1の態様又は第1の態様の第1の可能な実装方法に関して、第1の態様の第2の可能な実装方法において、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップは、特に、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得するステップと、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するステップとを含む。
【００１２】
第1の態様の第2の可能な実装方法に関して、第1の態様の第3の可能な実装方法において、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップは、特に、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するステップを含む。
【００１３】
第2の態様によれば、2次元フィルタを生成する方法であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している、ステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、ステップと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するステップとを含む、
2次元フィルタを生成する方法が提供される。
【００１４】
第2の態様に関して、第2の態様の第1の可能な実装方法において、前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外１）
2017526081.tif 000003
よりも大きいか又は等しく、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００１５】
第2の態様又は第2の態様の第1の可能な実装方法に関して、第2の態様の第2の可能な実装方法において、前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００１６】
第2の態様又は第2の態様の第1及び第2の可能な実装方法に関して、第2の態様の第3の可能な実装方法において、当該方法は、
前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するステップをさらに含む。
【００１７】
第3の態様によれば、鍵値エレメントのクエリを実行する装置であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するように構成される決定ユニットと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するように構成される設定ユニットと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するように構成される計算ユニットと、
前記クエリを実行されるべき鍵値エレメント・グループの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するように構成される取得ユニットと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するように構成されるクエリ・ユニットとを含む、
鍵値エレメントのクエリを実行する装置が提供される。
【００１８】
第3の態様に関して、第3の態様の第1の可能な実装方法において、いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記決定ユニットによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記決定ユニットによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列方法が異なっている。
【００１９】
第3の態様又は第3の態様の第1の可能な実装方法に関して、第3の態様の第2の可能な実装方法において、前記計算ユニットは、特に、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するように構成される。
【００２０】
第3の態様の第2の可能な実装方法に関して、第3の態様の第3の可能な実装方法において、前記取得ユニットは、特に、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するように構成される。
【００２１】
第4の態様によれば、2次元フィルタを生成する装置であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するように構成される確立ユニットと、
ハッシュ関数セットを決定し、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応し、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するように構成される決定ユニットであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、決定ユニットと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するように構成される生成ユニットとを含む、
2次元フィルタを生成する装置が提供される。
【００２２】
第4の態様に関して、第4の態様の第1の可能な実装方法において、前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外２）
2017526081.tif 000004
よりも大きいか又は等しく、前記行ベクトル及び前記列ベクトルは、前記確立ユニットによって生成される前記2次元マトリクスに含まれ、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００２３】
第4の態様又は第4の態様の第1の可能な実装方法に関して、第4の態様の第2の可能な実装方法において、前記決定ユニットによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記決定ユニットによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記決定ユニットによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記決定ユニットによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００２４】
第4の態様又は第4の態様の第1及び第2の可能な実装方法に関して、第4の態様の第3の可能な実装方法において、当該装置は、前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するように構成される初期化ユニットをさらに含む。
【００２５】
本発明の複数の実施形態において、2次元フィルタは、2次元マトリクスを含み、2次元マトリクスを複数の鍵値エレメント・グループにリンクさせてもよく、したがって、フィルタの柔軟性を改善する。
【図面の簡単な説明】
【００２６】
【図１Ａ】従来技術のハッシュ・テーブルの概略的な構成図である。
【図１Ｂ】従来技術のフィルタを使用してあらわされたジャンクEmailアドレスの例示的な図である。
【図２Ａ】本発明の実施形態にしたがって2次元フィルタを生成するフローチャートである。
【図２Ｂ】本発明の実施形態にしたがった2次元マトリクスの概略図である。
【図３】本発明の実施形態にしたがって鍵値エレメントのクエリを実行するフローチャートである。
【図４】本発明の実施形態にしたがって、2次元フィルタを生成して、鍵値エレメントのクエリを実行する実施形態である。
【図５】本発明の実施形態にしたがって2次元フィルタを生成する装置の機能的な構成の概略図である。
【図６】本発明の実施形態にしたがって2次元フィルタを生成する装置の実態構造の概略図である。
【図７】本発明の実施形態にしたがって鍵値エレメントのクエリを実行する装置の機能的な構成の概略図である。
【図８】本発明の実施形態にしたがって鍵値エレメントのクエリを実行する装置の実態構造の概略図である。
【発明を実施するための形態】
【００２７】
本発明の複数の実施形態の目的、技術的解決方法、及び利点をより明確にするために、以下の記載は、本発明の複数の実施形態に関する複数の添付図面を参照して、本発明のそれらの複数の実施形態に関する技術的解決方法を明確かつ完全に説明する。明らかなことだが、説明される複数の実施形態は、本発明の複数の実施形態のすべてではなく一部にすぎない。創造的な努力なくして本発明の複数の実施形態に基づいて当業者が得ることができる他のすべての実施形態は、本発明の保護範囲に入るものとする。
【００２８】
さらに、本明細書においては、"システム"及び"ネットワーク"の語を交換可能に使用してもよい。本明細書中の"及び/又は"の語は、関連する目的を説明するための関連する関係を説明するにすぎず、3つの関係が存在してもよいということを表している。例えば、A及び/又はBは、以下の3つの場合、すなわち、Aのみが存在する、A及びBの双方が存在する、Bのみが存在するということを表してもよい。さらに、本明細書中の記号"/"は、一般的に、複数関連する対象の間の"又は"の関係を示している。
【００２９】
以下の記載では、複数の添付の図面を参照して、本発明の複数の例示的な実装方法を詳細に説明する。本明細書で説明される例示的な実施形態は、本発明を限定することを意図したものではなく、本発明を解説し、そして、説明するのに使用されるにすぎないということを理解すべきである。本願の複数の実施形態及びそれらの複数の実施形態の特徴は、それらが互いに矛盾しない場合には、相互に組み合わせられてもよい。
【００３０】
以下の記載では、複数の添付の図面を参照して、本発明の複数の例示的な実装方法を詳細に説明する。
【００３１】
実施形態1
図2Aを参照して、本発明の本実施形態において、2次元フィルタを生成する詳細なプロセスは、以下のようになる。
【００３２】
ステップ200:少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立する。
【００３３】
ステップ210: ハッシュ関数セットを決定し、ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応し、ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得し、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか列ベクトルの長さと等しい正の整数である。
【００３４】
ステップ220:2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成する。
【００３５】
本発明の本実施形態において、図2Bに2次元フィルタが示されている。
【００３６】
本発明の本実施形態において、2次元マトリクスのストレージ・データ・ユニットの数は、行ベクトルの数と列ベクトルの数の積になる。図2Bに示されているように、2次元マトリクスにおいては、行ベクトルの数が9であり、そして、列ベクトルの数が9であり、その結果、2次元マトリクスのストレージ・データ・ユニットの数は81となる。
【００３７】
本発明の本実施形態において、確立された2次元マトリクスの行ベクトルの長さ及び確立された2次元マトリクスの列ベクトルの長さの双方は、
（外３）
2017526081.tif 000005
よりも小さく、鍵値エレメント・グループの中の複数の鍵値エレメントがフィルタにロードされると、高い確率で、複数の異なる鍵値エレメントが同じ位置にロードされ、それによってクエリの精度に影響を与えるという可能性がある。したがって、クエリの精度を改善するために、本発明の本実施形態においては、確立された2次元マトリクスの行ベクトルの長さ及び確立された2次元マトリクスの列ベクトルの長さの双方が、
（外４）
2017526081.tif 000006
よりも大きく、Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００３８】
しかしながら、行ベクトルの長さ及び列ベクトルの長さがより大きい場合には、より大きな記憶スペースが必要とされる。したがって、本発明の本実施形態においては、記憶スペースの利用率を改善するために、確立された2次元マトリクスの行ベクトルの長さ及び確立された2次元マトリクスの列ベクトルの長さの双方が、
（外５）
2017526081.tif 000007
に等しくなっている。
【００３９】
本発明の本実施形態においては、第1の鍵値エレメント及び第2の鍵値エレメントは、さまざまな形態であってもよい。選択的に、以下のいくつかの形態が使用されてもよい。
【００４０】
第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含む。
【００４１】
奇数ビットのすべてによって形成された鍵値エレメントは、10進数であってもよく、偶数ビットのすべてによって形成された鍵値エレメントは、10進数であってもよい。もちろん、奇数ビットのすべてによって形成された鍵値エレメント及び偶数ビットのすべてによって形成された鍵値エレメントは、他の記数法で表されてもよく、それらの詳細は、本明細書では再度説明されない。
【００４２】
例えば、鍵値エレメントが37348であり、2進法で表されると、37348は、1001000111100100であり、すべての奇数ビットは、01011010であり、すべての偶数ビットは、10001100であり、奇数ビットのすべてによってあらわされた10進数は、90(第1のサブ鍵値エレメント)であり、偶数ビットのすべてによってあらわされた10進数は、140(第2のサブ鍵値エレメント)である。
【００４３】
代替的に、第1のサブ鍵値エレメント及び第2のサブ鍵値エレメントは、以下の形態であってもよい。
【００４４】
第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００４５】
奇数ビットのすべてによって形成された鍵値エレメントは、10進数であってもよく、偶数ビットのすべてによって形成された鍵値エレメントは、10進数であってもよい。もちろん、奇数ビットのすべてによって形成された鍵値エレメント及び偶数ビットのすべてによって形成された鍵値エレメントは、他の記数法で表されてもよく、それらの詳細は、本明細書では再度説明されない。
【００４６】
例えば、鍵値エレメントが37348であり、2進法で表されると、37348は、1001000111100100であり、0番目のビットから7番目のビットは、10010001であり、8番目のビットから15番目のビットは、11100100であり、0番目のビットから7番目のビットによってあらわされた10進数は、90(第1のサブ鍵値エレメント)であり、8番目のビットから15番目のビットによってあらわされた10進数は、140(第2のサブ鍵値エレメント)である。
【００４７】
本発明の本実施形態において、行ベクトル及び列ベクトルを含む2次元マトリクスを確立した後に、プロセスは、2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するステップをさらに含む。
【００４８】
実施形態2
図3を参照すると、本発明の本実施形態において、図2にしたがって生成された2次元フィルタを使用することにより鍵値エレメントのクエリを実行する詳細なプロセスは、以下のようになる。
【００４９】
ステップ300:ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定する。
【００５０】
ステップ310:各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、その鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがって、ハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定する。
【００５１】
ステップ320:クエリを実行されるべき鍵値エレメントについて、そのクエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算する。
【００５２】
ステップ330:クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得する。
【００５３】
ステップ340:取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定する。
【００５４】
2つの異なるタイプの鍵値エレメントに対応するハッシュ関数サブセットが同じである場合には、それらの鍵値エレメントが2次元フィルタにロードされる位置は、同じであり、その結果、複数の異なる鍵値エレメントが、2次元フィルタの同じ位置に対応している。この場合には、クエリの精度は比較的低い。クエリの精度の改善するため、本発明の本実施形態においては、いずれかの2の異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数は、異なっており、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数は、同じであるが、それらのハッシュ関数は、配列方法が異なっている。
【００５５】
例えば、第1の鍵値エレメント・グループが、複数の地域に関連付けられた売上表であり、第2の鍵値エレメント・グループが、複数の月に関連付けられた売上表である場合に、その第1の鍵値エレメント・グループに対応するハッシュ関数サブセットは、第2の鍵値エレメント・グループに対応するハッシュ関数サブセットとは異なる。
【００５６】
本発明の本実施形態において、クエリを実行されるべき鍵値エレメントのハッシュ値を計算するための複数の手法が存在する。選択的に、上記の手法は、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するのに使用されてもよい。
【００５７】
もちろん、本実施形態の第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含んでもよく、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含み、又は、
第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００５８】
本実施形態における第1のサブ鍵値エレメントの特定の表現形式は、実施形態1における第1のサブ鍵値エレメントの表現形式と同じである。
【００５９】
本発明の本実施形態においては、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得するための複数の手法が存在する。選択的に、以下の手法は、
第1のハッシュ値を行として使用するとともに第2のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するか、或いは、第2のハッシュ値を行として使用するとともに第1のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するのに使用されてもよい。
【００６０】
例えば、いずれかの鍵値エレメントの第1のサブ鍵値エレメントが90であり、そのいずれかの鍵値エレメントの第2のサブ鍵値エレメントが140であり、そのいずれかの鍵値エレメントに対応するハッシュ関数サブセットが(h1,h2,h3)であり、そして、(h1,h2,h3)を使用して90に計算を実行することにより得られた第1のハッシュ値が、それぞれ、6、128、55であり、(h1,h2,h3)を使用して140に計算を実行することにより得られた第2のハッシュ値が、それぞれ、0、101、46である。そうすると、2次元マトリクスの中のいずれかの鍵値エレメントの位置は、(6,0)、(6,101)、(6,46)、(128,0)、(128,101)、(128,46)、(55,0)、(55,101)、及び(55,46)となり、これらの位置に対応するエレメントは、第2のあらかじめ設定された識別子に対するすべての組であり、或いは、2次元マトリクスの中の上記のいずれかの鍵値エレメントの位置は、(0,6)、(101,6)、(46,4)、(0,128)、(101,128)、(46,128)、(0,55)、(101,55)、及び(46,55)となり、これらの位置に対応するエレメントは、第2のあらかじめ設定された識別子に対するすべての組である。
【００６１】
実施形態2においては、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、上記の2次元フィルタに基づいてクエリを実行することが必要であるにすぎず、各々の鍵値エレメント・グループに対応するブルーム・フィルタを生成する必要はない。さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、複数のブルーム・フィルタの各々に基づいて1つずつクエリを実行する必要はない。したがって、現状では低いクエリ効率の問題をさらに解決することができる。
【００６２】
実施形態1及び実施形態2において、2次元マトリクスは説明のための1つの例として使用される。もちろん、3次元マトリクスや4次元マトリクス等の多次元マトリクスを使用してもよい。多次元マトリクスを生成するプロセスは、2次元マトリクスを生成するプロセスと同様であり、多次元マトリクスに基づくクエリプロセスは、2次元マトリクスに基づくクエリプロセスと同様であり、本明細書においては、これらの詳細は再度説明されない。
【００６３】
本発明の本実施形態をよりよく理解するために、以下の記載は、特定の適用のシナリオを提示し、図4に示されているように鍵値エレメントのクエリを実行するプロセスをさらに詳細に説明する。
【００６４】
実施形態3
ステップ400:3つの行ベクトル及び3つの列ベクトルを含む2次元マトリクスを確立する。
【００６５】
ステップ410:ハッシュ関数セットを決定し、2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成する。
【００６６】
ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している。ハッシュ関数セットの中のいずれかのハッシュ関数を使用して少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得し、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか又は行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか又は列ベクトルの長さに等しい正の整数である。
【００６７】
さらに、このステップで決定されるハッシュ関数セットは、10個のハッシュ関数h1、h2、h3、h4、h5、h6、h7、h8、h9、及びh10を含む。
【００６８】
ステップ420:2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化する。
【００６９】
ステップ430:決定されたハッシュ関数セットから2つの鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットを決定する。
【００７０】
ステップ440:2つの鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、その鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子にあらかじめ設定する。
【００７１】
ステップ450:クエリを実行されるべき鍵値エレメントについて、そのクエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算する。
【００７２】
ステップ460:クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得する。
【００７３】
ステップ470:取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子であるか否かを判定し、そうである場合に、そのクエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定し、そうではない場合に、そのクエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属していないということを決定する。
【００７４】
上記の技術的解決方法に基づき、図5を参照すると、本発明の本実施形態は、2次元フィルタを生成するための装置を提示し、その生成装置は、確立ユニット50、決定ユニット51、及び生成ユニット52を含む。
【００７５】
確立ユニット50は、少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するように構成される。
【００７６】
決定ユニット51は、ハッシュ関数セットを決定し、そのハッシュ関数セットの中の各々のハッシュ関数が、少なくとも1つの鍵値エレメント・グループに対応し、ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するように構成され、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか列ベクトルの長さと等しい正の整数である。
【００７７】
生成ユニット52は、2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成するように構成される。
【００７８】
本発明に本実施形態においては、選択的に、行ベクトルの長さ及び列ベクトルの長さの双方が、
（外６）
2017526081.tif 000008
よりも大きいか又は等しく、行ベクトル及び列ベクトルは、確立ユニット50によって生成される2次元マトリクスに含まれる。
【００７９】
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００８０】
本発明の本実施形態においては、選択的に、決定ユニット51によって取得される第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、決定ユニット51によって取得される第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含み、又は、
決定ユニット51によって取得される第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、決定ユニット51によって取得される第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００８１】
本発明の本実施形態においては、当該装置は、2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するように構成される初期化ユニット53をさらに含む。
【００８２】
図6に示されているように、図6は、本発明にしたがって2次元フィルタを生成する装置の実体装置図であり、2次元フィルタを生成する装置は、少なくとも1つのプロセッサ601、通信バス603、メモリ603、及び少なくとも1つの通信インターフェイス604を含む。
【００８３】
通信バス602は、上記の複数の構成要素の間の接続及び通信を実装するように構成され、通信インターフェイス604は、外部装置に接続し、外部装置と通信するように構成される。
【００８４】
メモリ603は、実行される必要があるプログラム・コードを格納するように構成され、メモリ603の中のプログラム・コードを実行すると、プロセッサは、以下の機能、すなわち、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、そのハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応しているステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか列ベクトルの長さと等しい正の整数である、ステップと、
2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成するステップとを実行する。
【００８５】
上記の技術的解決方法に基づき、図７を参照すると、本発明の本実施形態は、鍵値エレメントのクエリを実行する装置を提示し、鍵値エレメントのクエリを実行する装置は、決定ユニット70、設定ユニット71、計算ユニット72、及びクエリ・ユニット74を含む。
【００８６】
決定ユニット70は、ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するように構成される。
【００８７】
設定ユニット71は、各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するように構成される。
【００８８】
計算ユニット72は、クエリを実行されるべき鍵値エレメントについて、クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算するように構成される。
【００８９】
取得ユニット73は、2次元マトリクスの中のクエリを実行されるべき鍵値エレメント・グループのハッシュ値の位置に対応するエレメントを取得するように構成される。
【００９０】
クエリ・ユニット74は、取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するように構成される。
【００９１】
本発明の本実施形態においては、選択的に、いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに決定ユニット70によって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数は、異なっており、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに決定ユニット70によって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数は、同じであるが、ハッシュ関数は、配列方法が異なっている。
【００９２】
本発明の本実施形態においては、選択的に、計算ユニット72は、特に、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するように構成される。
【００９３】
本発明の本実施形態においては、選択的に、取得ユニット73は、特に、
第1のハッシュ値を行として使用するとともに第2のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するか、或いは、第2のハッシュ値を行として使用するとともに第1のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するように構成される。
【００９４】
図8に示されているように、図8は、本発明にしたがって2次元フィルタを生成する装置の実体装置図であり、2次元フィルタを生成する装置は、少なくとも1つのプロセッサ801、通信バス802、メモリ803、及び少なくとも1つの通信インターフェイス804を含む。
【００９５】
通信バス802は、上記の複数の構成要素の間の接続及び通信を実装するように構成され、通信インターフェイス804は、外部装置に接続し、外部装置と通信するように構成される。
【００９６】
メモリ803は、実行される必要があるプログラム・コードを格納するように構成され、メモリ803の中のプログラム・コードを実行すると、プロセッサ801は、以下の機能、すなわち、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、そのクエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを実行する。
【００９７】
結論として、本発明の本実施形態においては、2次元フィルタは2次元マトリクスを含み、2次元マトリクスを複数の鍵値エレメント・グループにリンクさせることが可能であり、したがって、フィルタの柔軟性を改善することが可能である。
【００９８】
さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、上記の2次元フィルタに基づいてクエリを実行することが必要であるにすぎず、各々の鍵値エレメント・グループに対応するブルーム・フィルタを生成する必要はない。さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、複数のブルーム・フィルタの各々に基づいて1つずつクエリを実行する必要はない。したがって、現状では低いクエリ効率の問題をさらに解決することができる。
【００９９】
本発明は、本発明の複数の実施形態にしたがった方法のフローチャート及び/又はブロック図、デバイス(システム)、及びコンピュータ・プログラム製品との関連で説明される。複数のコンピュータ・プログラム命令は、フローチャート及び/又はブロック図の中の各々のプロセス及び/又は各々のブロック並びにフローチャート及び/又はブロック図の中のプロセス及び/又はブロックの組み合わせを実装するのに使用されてもよいということを理解すべきである。汎用コンピュータ、専用コンピュータ、組み込みプロセッサ、又はいずれかの他のプログラム可能なデータ処理デバイスのプロセッサにこれらのコンピュータ・プログラム命令を提供することにより、機械を生成してもよく、その結果、コンピュータ又はいずれかの他のプログラム可能なデータ処理デバイスのプロセッサによって実行されるこれらの命令が、フローチャートの中の1つ又は複数のプロセス及び/又はブロック図の中の1つ又は複数のブロックのある特定の機能を実装する装置を生成する。
【０１００】
これらのコンピュータ・プログラム命令は、コンピュータ読み取り可能なメモリに格納されてもよく、ある特定の方法で動作するように、コンピュータ又はいずれかの他のプログラム可能なデータ処理デバイスに指示してもよく、それによってコンピュータ読み取り可能なメモリに格納されているこれらの命令は、命令装置を含むアーティファクトを生成する。上記の命令装置は、フローチャートの中の1つ又は複数のプロセス及び/又はブロック図の中の1つ又は複数のブロックのある特定の機能を実装する。
【０１０１】
これらのコンピュータ・プログラム命令は、コンピュータ又は他のプログラム可能なデータ処理デバイスにロードされてもよく、それによって、一連の動作及びステップがコンピュータ又は他のプログラム可能なデバイスで実行され、その結果、コンピュータによって実装される処理を生成する。したがって、コンピュータ又は他のプログラム可能なデバイスで実行される命令は、フローチャートの中の1つ又は複数のプロセス及び/又はブロック図の中の1つ又は複数のブロックのある特定の機能を実装する複数のステップを提供する。
【０１０２】
本発明のいくつかの例示的な実施形態が説明されてきたが、基本的な発明概念を知れば、当業者は、これらの実施形態に変更及び修正を加えることができる。したがって、以下の特許請求の範囲は、これらの例示的な実施形態のみならず本発明の範囲に入る変更及び修正のすべてにも及ぶものと解釈されることを意図している。
【０１０３】
明らかなことだが、当業者であれば、本発明の上記の複数の実施形態の趣旨及び範囲から逸脱することなく、本発明のそれらの複数の実施形態に修正及び変形を加えることができる。これらの修正及び変形が、以下の特許請求の範囲及びその等価な技術によって定義される保護の範囲に入る場合には、本発明は、それらの修正及び変形を対象とすることを意図されている。
【図１Ａ】
2017526081.tif 000011
【図１Ｂ】
2017526081.tif 000012
【図２Ａ】
2017526081.tif 000013
【図２Ｂ】
2017526081.tif 000014
【図３】
2017526081.tif 000015
【図４】
2017526081.tif 000016
【図５】
2017526081.tif 000017
【図６】
2017526081.tif 000018
【図７】
2017526081.tif 000019
【図８】
2017526081.tif 000020
【手続補正書】
【提出日】平成29年5月2日(2017.5.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
鍵値エレメントのクエリを実行する方法であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを含む、
方法。
【請求項２】
いずれかの2の異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列法が異なっている、請求項１に記載の方法。
【請求項３】
前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップは、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得するステップと、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するステップとを含む、請求項１又は２に記載の方法。
【請求項４】
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップは、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するステップを含む、請求項３に記載の方法。
【請求項５】
2次元フィルタを生成する方法であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している、ステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、ステップと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するステップとを含む、
方法。
【請求項６】
前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外７）
2017526081.tif 000021
よりも大きいか又は等しく、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である、請求項５に記載の方法。
【請求項７】
前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である、請求項５又は６に記載の方法。
【請求項８】
前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するステップをさらに含む、請求項５乃至７のいずれか１項に記載の方法。
【請求項９】
鍵値エレメントのクエリを実行する装置であって、
少なくとも1つのプロセッサと、
前記プロセッサと電子的に通信するメモリと、
前記メモリに格納されるプログラム・コードとを含み、前記プログラム・コードは、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定し、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算し、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得し、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定する、前記プロセッサによって実行可能である、
装置。
【請求項１０】
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記プロセッサによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記プロセッサによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列法が異なっている、請求項９に記載の装置。
【請求項１１】
前記プロセッサは、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するように構成される、請求項９又は１０に記載の装置。
【請求項１２】
前記プロセッサは、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するように構成される、請求項１１に記載の装置。
【請求項１３】
2次元フィルタを生成する装置であって、
少なくとも1つのプロセッサと、
前記プロセッサと電子的に通信するメモリと、
前記メモリに格納されるプログラム・コードとを含み、前記プログラム・コードは、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立し、
ハッシュ関数セットを決定し、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応し、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得し、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数であり、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するプロセッサにより実行可能である、
装置。
【請求項１４】
前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外８）
2017526081.tif 000022
よりも大きいか又は等しく、前記行ベクトル及び前記列ベクトルは、前記プロセッサによって生成される前記2次元マトリクスに含まれ、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である、請求項１３に記載の装置。
【請求項１５】
前記プロセッサによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記プロセッサによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記プロセッサによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記プロセッサによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である、請求項１３又は１４に記載の装置。
【請求項１６】
前記プロセッサは、前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するように構成される、請求項１３乃至１５のいずれか１項に記載の装置。
【請求項１７】
プログラム・コードが記録されているコンピュータ読み取り可能な記憶媒体であって、前記プログラム・コードは、請求項１乃至４のいずれかに記載の方法をコンピュータに実行させる、コンピュータ読み取り可能な記憶媒体。
【請求項１８】
プログラム・コードが記録されているコンピュータ読み取り可能な記録媒体であって、前記プログラム・コードは、請求項５乃至８のいずれかに記載の方法をコンピュータに実行させる、コンピュータ読み取り可能な記憶媒体。
【請求項１９】
1つ又は複数のコンピュータ実行可能な命令を含むコンピュータ・プログラムであって、前記1つ又は複数のコンピュータ実行可能な命令は、鍵値エレメントのクエリを実行する装置のプロセッサで実行されると、前記装置に、鍵値エレメントのクエリを実行する方法を実行させ、前記方法は、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを含む、
コンピュータ・プログラム。
【請求項２０】
1つ又は複数のコンピュータ実行可能な命令を含むコンピュータ・プログラムであって、前記1つ又は複数のコンピュータ実行可能な命令は、2次元フィルタを生成する装置のプロセッサで実行されると、前記装置に、2次元フィルタを生成する方法を実行させ、前記方法は、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している、ステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、ステップと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するステップとを含む、
コンピュータ・プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エレメント・クエリ技術及びマッチング技術、特に、2次元フィルタを生成する方法及び装置、及び鍵値エレメントのクエリを実行する方法及び装置に関する。
【背景技術】
【０００２】
コンピュータ・ソフトウェアを設計する場合には、通常、あるエレメントがあるセットの中に存在するか否かを判定する必要がある。例えば、文書処理ソフトウェアにおいては、ある英単語が正しく綴られているか否かを検査する必要があり(すなわち、その英単語が既知の辞書の中に存在するか否かを検査する必要があり)、他の例では、URL(Uniform  Resource  Locator、統一資源位置指定子)フィルタリング・ソフトウェアにおいては、あるURLがフィルタリング・リストの中に存在するか否かが判定される。最も直接的な方法は、あるセットの中のすべてのエレメントをコンピュータに格納し、新たなエレメントが出現した際に、その新たなエレメントをそのセットの中のエレメントと直接的に比較することである。検索速度を改善するため、通常、ハッシュ・テーブル(Hash  Table)がセットを格納するのに使用される。ハッシュ・テーブルは、あるエレメントのキー・コード値にしたがってそのエレメントの記憶位置を迅速にマッピングするデータ構造であり、マッピング関数は、いわゆるハッシュ関数である。ハッシュ・テーブルの構造が図1Aに示されている。最初に、ハッシュ関数を使用することにより、あるセットの中のあるエレメントのハッシュ位置を取得し、その後、その位置におけるハッシュ・リンク・リストの中にそのエレメントを記録する。図1Aにおいて、ハッシュ関数がHASHであり、A1,A2,…,A8が、セットの中のエレメントであると仮定すると、図から、HASH(A1)=HASH(A2)=H1、HASH(A3)=HASH(A4)=H2、HASH(A5)=HASH(A6)=H3、及びHASH(A7)=HASH(A8)=H4であるということを理解できる。
【０００３】
ハッシュ・テーブルの利点は、あるエレメントがあるセットの中にあるか否かを迅速かつ正確に判定することができるという点であり、欠点は、比較的大きな記憶スペースが必要であるという点である。記憶スペースを低減するために、1次元のブルーム・フィルタが、1970年にBurton  Bloomによって提案され、ブルーム・フィルタの原理は、以下のようになる、すなわち、1次元のブルーム・フィルタは、相互に独立であるK個のハッシュ関数h1,h2,…,hk及び長さがmであるビット・ベクトルによって形成される。各々のハッシュ関数の値の範囲は、{0,1,…,m-1}であり、1バイトは、8ビットからなる。したがって、ビット・ベクトルによって実際に占有されるメモリ・スペースは、m/8バイトであり、ビット・ベクトルのすべてのビットは、0に初期化される。セットS={s1,s2,…,sn}であり、ハッシュ・シーケンス(h1(s),h2(s),…,hk(s))は、k個のハッシュ関数を使用することにより、セットSの中の各エレメントについて計算され、その後、ビット・ベクトルの中の対応するハッシュ・シーケンス・ビットが1に設定され、その結果、データ・エレメントのセットSがブルーム・フィルタにロードされる、又は、そのブルーム・フィルタが、データ・エレメントのセットSを表すとされる。例えば、h1(s1)=5である場合に、ビット・ベクトルの6番目のビットは、1に設定され、h2(s1)=10である場合に、ビット・ベクトルの11番目のビットは、1に設定され、hk(s1)=n-1となるまで、ビット・ベクトルのn番目のビットは、1に設定され、その結果、データ・エレメントs1がそのブルーム・フィルタにロードされるといわれる。セットSの中のすべてのデータ・エレメントがそのブルーム・フィルタにロードされると、そのブルーム・フィルタがデータ・エレメントのセットSを表すとされる。あるデータ・エレメントがセットSの中に存在するか否かについてクエリが行われると、同じk個のハッシュ関数を使用することにより、そのデータ・エレメントについてハッシュ・シーケンスの計算が行われる。そのハッシュ・シーケンスに対応するビット・ベクトルの各々のビットが1である場合には、そのデータ・エレメントは、Sに属していると考えられ、そうでない場合には、そのデータ・エレメントは、Sに属していないと考えられる。データが完全に格納される場合と比較して、記憶スペースを低減するのにブルーム・フィルタを使用してもよく、ブルーム・フィルタを使用すれば、あるセットに属するいずれのエレメントも、見逃されることはない。
【０００４】
以下の記載では、ジャンクEmailのアドレスの例を参照してブルーム・フィルタを簡単に説明する。
【０００５】
ジャンクEmailアドレスの数が1億であると仮定すると、最初に、その長さが16億ビットのビット・ベクトル、すなわち、2億バイトのベクトルが確立され、その後、16億のバイナリ・ビットのすべてが、0に初期化される。既知のジャンクEmailアドレスの各々について、8個の異なるハッシュ関数(F1,F2,…,F8)が8個のハッシュ値(f1,f2,…,f8)を生成するのに使用され、そのビット・ベクトルの位置であって8個のハッシュ値に対応する位置が、すべて1に設定される。上記の1億のジャンクEmailアドレスのすべてがそのような方法で処理された後に、ブルーム・フィルタが、これらのジャンクEmailアドレスについて生成される。図1Bに示されているように、図1Bは、ブルーム・フィルタを使用することによりあらわされるジャンクEmailアドレスの例示的な略図である。あるジャンクEmailアドレスXXX@163.comについて、8個の異なるハッシュ関数(F1,F2,…,F8)が8個のハッシュ値(f1,f2,…,f8)を生成するのに使用され、そのビット・ベクトルの位置であって8個のハッシュ値に対応する位置が、すべて1に設定され、この場合には、そのジャンクEmailアドレスがそのブルーム・フィルタにロードされるといわれる。
【０００６】
上記の生成されたブルーム・フィルタは、1つの鍵値エレメント・グループについてのものであり、すなわち、1つのブルーム・フィルタは1つの鍵値エレメント・グループのみにリンクさせることが可能であり、生成される必要があるブルーム・フィルタの数は、鍵値エレメント・グループの数によって決まる。したがって、ブルーム・フィルタの柔軟性は相対的に乏しいという欠点が存在する。
【発明の概要】
【０００７】
本発明の複数の実施形態は、2次元フィルタを生成する方法及び装置、及び鍵値エレメントのクエリを実行する方法及び装置を提供し、ブルーム・フィルタの柔軟性を改善する。
【０００８】
本発明の複数の実施形態において提示される特定の技術的解決方法は、以下のようになる。
【０００９】
第1の態様によれば、鍵値エレメントのクエリを実行する方法であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを含む、
鍵値エレメントのクエリを実行する方法が提供される。
【００１０】
第1の態様に関して、第1の態様の第1の可能な実装方法において、いずれかの2の異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列法が異なっている。
【００１１】
第1の態様又は第1の態様の第1の可能な実装方法に関して、第1の態様の第2の可能な実装方法において、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップは、特に、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得するステップと、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するステップとを含む。
【００１２】
第1の態様の第2の可能な実装方法に関して、第1の態様の第3の可能な実装方法において、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するステップは、特に、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するステップを含む。
【００１３】
第2の態様によれば、2次元フィルタを生成する方法であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している、ステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、ステップと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するステップとを含む、
2次元フィルタを生成する方法が提供される。
【００１４】
第2の態様に関して、第2の態様の第1の可能な実装方法において、前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外１）
2017526081.tif 000023
よりも大きいか又は等しく、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００１５】
第2の態様又は第2の態様の第1の可能な実装方法に関して、第2の態様の第2の可能な実装方法において、前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００１６】
第2の態様又は第2の態様の第1及び第2の可能な実装方法に関して、第2の態様の第3の可能な実装方法において、当該方法は、
前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するステップをさらに含む。
【００１７】
第3の態様によれば、鍵値エレメントのクエリを実行する装置であって、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するように構成される決定ユニットと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、前記鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、前記計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するように構成される設定ユニットと、
クエリを実行されるべき鍵値エレメントについて、前記クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、前記対応するハッシュ関数サブセットにしたがって、前記クエリを実行されるべき鍵値エレメントのハッシュ値を計算するように構成される計算ユニットと、
前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の位置に対応するエレメントを取得するように構成される取得ユニットと、
前記取得されたエレメントが、前記クエリを実行されるべき鍵値エレメントの前記ハッシュ値の前記2次元マトリクスの中の前記位置に対応する第2のあらかじめ設定された識別子である場合に、前記クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するように構成されるクエリ・ユニットとを含む、
鍵値エレメントのクエリを実行する装置が提供される。
【００１８】
第3の態様に関して、第3の態様の第1の可能な実装方法において、いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記決定ユニットによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、異なっているか、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに前記決定ユニットによって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数が、同じであるが、前記ハッシュ関数は、配列方法が異なっている。
【００１９】
第3の態様又は第3の態様の第1の可能な実装方法に関して、第3の態様の第2の可能な実装方法において、前記計算ユニットは、特に、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
前記クエリを実行されるべき鍵値エレメントが属する前記鍵値エレメント・グループに対応する前記ハッシュ関数サブセットに基づいて、前記クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するように構成される。
【００２０】
第3の態様の第2の可能な実装方法に関して、第3の態様の第3の可能な実装方法において、前記取得ユニットは、特に、
前記第1のハッシュ値を行として使用するとともに前記第2のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するか、或いは、前記第2のハッシュ値を行として使用するとともに前記第1のハッシュ値を列として使用するエレメントを前記2次元マトリクスから取得するように構成される。
【００２１】
第4の態様によれば、2次元フィルタを生成する装置であって、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するように構成される確立ユニットと、
ハッシュ関数セットを決定し、前記ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応し、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、前記いずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するように構成される決定ユニットであって、前記第1のハッシュ値は、前記行ベクトルの長さよりも小さいか前記行ベクトルの前記長さと等しい正の整数であり、前記第2のハッシュ値は、前記列ベクトルの長さよりも小さいか前記列ベクトルの前記長さと等しい正の整数である、決定ユニットと、
前記2次元マトリクス及び前記ハッシュ関数セットを含む2次元フィルタを生成するように構成される生成ユニットとを含む、
2次元フィルタを生成する装置が提供される。
【００２２】
第4の態様に関して、第4の態様の第1の可能な実装方法において、前記行ベクトルの前記長さ及び前記列ベクトルの前記長さの双方は、
（外２）
2017526081.tif 000024
よりも大きいか又は等しく、前記行ベクトル及び前記列ベクトルは、前記確立ユニットによって生成される前記2次元マトリクスに含まれ、
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００２３】
第4の態様又は第4の態様の第1の可能な実装方法に関して、第4の態様の第2の可能な実装方法において、前記決定ユニットによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、前記決定ユニットによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含むか、或いは、
前記決定ユニットによって取得される前記第1のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、前記決定ユニットによって取得される前記第2のサブ鍵値エレメントは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、前記いずれかの鍵値エレメントが2進法で表された場合に、前記いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００２４】
第4の態様又は第4の態様の第1及び第2の可能な実装方法に関して、第4の態様の第3の可能な実装方法において、当該装置は、前記2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するように構成される初期化ユニットをさらに含む。
【００２５】
本発明の複数の実施形態において、2次元フィルタは、2次元マトリクスを含み、2次元マトリクスを複数の鍵値エレメント・グループにリンクさせてもよく、したがって、フィルタの柔軟性を改善する。
【図面の簡単な説明】
【００２６】
【図１Ａ】従来技術のハッシュ・テーブルの概略的な構成図である。
【図１Ｂ】従来技術のフィルタを使用してあらわされたジャンクEmailアドレスの例示的な図である。
【図２Ａ】本発明の実施形態にしたがって2次元フィルタを生成するフローチャートである。
【図２Ｂ】本発明の実施形態にしたがった2次元マトリクスの概略図である。
【図３】本発明の実施形態にしたがって鍵値エレメントのクエリを実行するフローチャートである。
【図４】本発明の実施形態にしたがって、2次元フィルタを生成して、鍵値エレメントのクエリを実行するフローチャートである。
【図５】本発明の実施形態にしたがって2次元フィルタを生成する装置の機能的な構成の概略図である。
【図６】本発明の実施形態にしたがって2次元フィルタを生成する装置の実態構造の概略図である。
【図７】本発明の実施形態にしたがって鍵値エレメントのクエリを実行する装置の機能的な構成の概略図である。
【図８】本発明の実施形態にしたがって鍵値エレメントのクエリを実行する装置の実態構造の概略図である。
【発明を実施するための形態】
【００２７】
本発明の複数の実施形態の目的、技術的解決方法、及び利点をより明確にするために、以下の記載は、本発明の複数の実施形態に関する複数の添付図面を参照して、本発明のそれらの複数の実施形態に関する技術的解決方法を明確に説明する。明らかなことだが、説明される複数の実施形態は、本発明の複数の実施形態のすべてではなく一部にすぎない。創造的な努力なくして本発明の複数の実施形態に基づいて当業者が得ることができる他のすべての実施形態は、本発明の保護範囲に入るものとする。
【００２８】
さらに、本明細書においては、"システム"及び"ネットワーク"の語を交換可能に使用してもよい。本明細書中の"及び/又は"の語は、関連する目的を説明するための関連する関係を説明するにすぎず、3つの関係が存在してもよいということを表している。例えば、A及び/又はBは、以下の3つの場合、すなわち、Aのみが存在する、A及びBの双方が存在する、Bのみが存在するということを表してもよい。さらに、本明細書中の記号"/"は、一般的に、複数関連する対象の間の"又は"の関係を示している。
【００２９】
以下の記載では、複数の添付の図面を参照して、本発明の複数の例示的な実装方法を詳細に説明する。本明細書で説明される例示的な実施形態は、本発明を限定することを意図したものではなく、本発明を解説し、そして、説明するのに使用されるにすぎないということを理解すべきである。本願の複数の実施形態及びそれらの複数の実施形態の特徴は、それらが互いに矛盾しない場合には、相互に組み合わせられてもよい。
【００３０】
以下の記載では、複数の添付の図面を参照して、本発明の複数の例示的な実装方法を詳細に説明する。
【００３１】
実施形態1
図2Aを参照して、本発明の本実施形態において、2次元フィルタを生成する詳細なプロセスは、以下のようになる。
【００３２】
ステップ200:少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立する。
【００３３】
ステップ210: ハッシュ関数セットを決定し、ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応し、ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得し、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか列ベクトルの長さと等しい正の整数である。
【００３４】
ステップ220:2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成する。
【００３５】
本発明の本実施形態において、図2Bに2次元フィルタが示されている。
【００３６】
本発明の本実施形態において、2次元マトリクスのストレージ・データ・ユニットの数は、行ベクトルの数と列ベクトルの数の積になる。図2Bに示されているように、2次元マトリクスにおいては、行ベクトルの数が9であり、そして、列ベクトルの数が9であり、その結果、2次元マトリクスのストレージ・データ・ユニットの数は81となる。
【００３７】
本発明の本実施形態において、確立された2次元マトリクスの行ベクトルの長さ及び確立された2次元マトリクスの列ベクトルの長さの双方は、
（外３）
2017526081.tif 000025
よりも小さく、鍵値エレメント・グループの中の複数の鍵値エレメントがフィルタにロードされると、高い確率で、複数の異なる鍵値エレメントが同じ位置にロードされ、それによってクエリの精度に影響を与えるという可能性がある。したがって、クエリの精度を改善するために、本発明の本実施形態においては、確立された2次元マトリクスの行ベクトルの長さ及び確立された2次元マトリクスの列ベクトルの長さの双方が、
（外４）
2017526081.tif 000026
よりも大きく、Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００３８】
しかしながら、行ベクトルの長さ及び列ベクトルの長さがより大きい場合には、より大きな記憶スペースが必要とされる。したがって、本発明の本実施形態においては、記憶スペースの利用率を改善するために、確立された2次元マトリクスの行ベクトルの長さ及び確立された2次元マトリクスの列ベクトルの長さの双方が、
（外５）
2017526081.tif 000027
に等しくなっている。
【００３９】
本発明の本実施形態においては、第1のサブ鍵値エレメント及び第2のサブ鍵値エレメントは、さまざまな形態であってもよい。選択的に、以下のいくつかの形態が使用されてもよい。
【００４０】
第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含む。
【００４１】
奇数ビットのすべてによって形成された鍵値エレメントは、10進数であってもよく、偶数ビットのすべてによって形成された鍵値エレメントは、10進数であってもよい。もちろん、奇数ビットのすべてによって形成された鍵値エレメント及び偶数ビットのすべてによって形成された鍵値エレメントは、他の記数法で表されてもよく、それらの詳細は、本明細書では再度説明されない。
【００４２】
例えば、鍵値エレメントが37348であり、2進法で表されると、37348は、1001000111100100であり、すべての奇数ビットは、01011010であり、すべての偶数ビットは、10001100であり、奇数ビットのすべてによってあらわされた10進数は、90(第1のサブ鍵値エレメント)であり、偶数ビットのすべてによってあらわされた10進数は、140(第2のサブ鍵値エレメント)である。
【００４３】
代替的に、第1のサブ鍵値エレメント及び第2のサブ鍵値エレメントは、以下の形態であってもよい。
【００４４】
第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００４５】
1番目のビットからK番目のビットによって形成された鍵値エレメントは、10進数であってもよく、(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントは、10進数であってもよい。もちろん、1番目のビットからK番目のビットによって形成された鍵値エレメント及び(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントは、他の記数法で表されてもよく、それらの詳細は、本明細書では再度説明されない。
【００４６】
例えば、鍵値エレメントが37348であり、2進法で表されると、37348は、1001000111100100であり、0番目のビットから7番目のビットは、10010001であり、8番目のビットから15番目のビットは、11100100であり、0番目のビットから7番目のビットによってあらわされた10進数は、90(第1のサブ鍵値エレメント)であり、8番目のビットから15番目のビットによってあらわされた10進数は、140(第2のサブ鍵値エレメント)である。
【００４７】
本発明の本実施形態において、行ベクトル及び列ベクトルを含む2次元マトリクスを確立した後に、プロセスは、2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するステップをさらに含む。
【００４８】
実施形態2
図3を参照すると、本発明の本実施形態において、図2にしたがって生成された2次元フィルタを使用することにより鍵値エレメントのクエリを実行する詳細なプロセスは、以下のようになる。
【００４９】
ステップ300:ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定する。
【００５０】
ステップ310:各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、その鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがって、ハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定する。
【００５１】
ステップ320:クエリを実行されるべき鍵値エレメントについて、そのクエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算する。
【００５２】
ステップ330:クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得する。
【００５３】
ステップ340:取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定する。
【００５４】
2つの異なるタイプの鍵値エレメントに対応するハッシュ関数サブセットが同じである場合には、それらの鍵値エレメントが2次元フィルタにロードされる位置は、同じであり、その結果、複数の異なる鍵値エレメントが、2次元フィルタの同じ位置に対応している。この場合には、クエリの精度は比較的低い。クエリの精度の改善するため、本発明の本実施形態においては、いずれかの2の異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数は、異なっており、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットの中に含まれるハッシュ関数は、同じであるが、それらのハッシュ関数は、配列方法が異なっている。
【００５５】
例えば、第1の鍵値エレメント・グループが、複数の地域に関連付けられた売上表であり、第2の鍵値エレメント・グループが、複数の月に関連付けられた売上表である場合に、その第1の鍵値エレメント・グループに対応するハッシュ関数サブセットは、第2の鍵値エレメント・グループに対応するハッシュ関数サブセットとは異なる。
【００５６】
本発明の本実施形態において、クエリを実行されるべき鍵値エレメントのハッシュ値を計算するための複数の手法が存在する。選択的に、上記の手法は、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するのに使用されてもよい。
【００５７】
もちろん、本実施形態の第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含んでもよく、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含み、又は、
第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、いずれかの鍵値エレメントが2進法で表された場合に、いずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００５８】
本実施形態における第1のサブ鍵値エレメントの特定の表現形式は、実施形態1における第1のサブ鍵値エレメントの表現形式と同じである。
【００５９】
本発明の本実施形態においては、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得するための複数の手法が存在する。選択的に、以下の手法は、
第1のハッシュ値を行として使用するとともに第2のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するか、或いは、第2のハッシュ値を行として使用するとともに第1のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するのに使用されてもよい。
【００６０】
例えば、いずれかの鍵値エレメントの第1のサブ鍵値エレメントが90であり、そのいずれかの鍵値エレメントの第2のサブ鍵値エレメントが140であり、そのいずれかの鍵値エレメントに対応するハッシュ関数サブセットが(h1,h2,h3)であり、そして、(h1,h2,h3)を使用して90に計算を実行することにより得られた第1のハッシュ値が、それぞれ、6、128、55であり、(h1,h2,h3)を使用して140に計算を実行することにより得られた第2のハッシュ値が、それぞれ、0、101、46である。そうすると、2次元マトリクスの中のいずれかの鍵値エレメントの位置は、(6,0)、(6,101)、(6,46)、(128,0)、(128,101)、(128,46)、(55,0)、(55,101)、及び(55,46)となり、これらの位置に対応するエレメントは、第2のあらかじめ設定された識別子に対するすべての組であり、或いは、2次元マトリクスの中の上記のいずれかの鍵値エレメントの位置は、(0,6)、(101,6)、(46,6)、(0,128)、(101,128)、(46,128)、(0,55)、(101,55)、及び(46,55)となり、これらの位置に対応するエレメントは、第2のあらかじめ設定された識別子に対するすべての組である。
【００６１】
実施形態2においては、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、上記の2次元フィルタに基づいてクエリを実行することが必要であるにすぎず、各々の鍵値エレメント・グループに対応するブルーム・フィルタを生成する必要はない。さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、複数のブルーム・フィルタの各々に基づいて1つずつクエリを実行する必要はない。したがって、現状では低いクエリ効率の問題をさらに解決することができる。
【００６２】
実施形態1及び実施形態2において、2次元マトリクスは説明のための1つの例として使用される。もちろん、3次元マトリクスや4次元マトリクス等の多次元マトリクスを使用してもよい。多次元マトリクスを生成するプロセスは、2次元マトリクスを生成するプロセスと同様であり、多次元マトリクスに基づくクエリプロセスは、2次元マトリクスに基づくクエリプロセスと同様であり、本明細書においては、これらの詳細は再度説明されない。
【００６３】
本発明の本実施形態をよりよく理解するために、以下の記載は、特定の適用のシナリオを提示し、図4に示されているように鍵値エレメントのクエリを実行するプロセスをさらに詳細に説明する。
【００６４】
実施形態3
ステップ400:3つの行ベクトル及び3つの列ベクトルを含む2次元マトリクスを確立する。
【００６５】
ステップ410:ハッシュ関数セットを決定し、2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成する。
【００６６】
ハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応している。ハッシュ関数セットの中のいずれかのハッシュ関数を使用して少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得し、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか又は行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか又は列ベクトルの長さに等しい正の整数である。
【００６７】
さらに、このステップで決定されるハッシュ関数セットは、10個のハッシュ関数h1、h2、h3、h4、h5、h6、h7、h8、h9、及びh10を含む。
【００６８】
ステップ420:2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化する。
【００６９】
ステップ430:決定されたハッシュ関数セットから2つの鍵値エレメント・グループにそれぞれ対応するハッシュ関数サブセットを決定する。
【００７０】
ステップ440:2つの鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、その鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子にあらかじめ設定する。
【００７１】
ステップ450:クエリを実行されるべき鍵値エレメントについて、そのクエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算する。
【００７２】
ステップ460:クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得する。
【００７３】
ステップ470:取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子であるか否かを判定し、取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、そのクエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定し、そうではない場合に、そのクエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属していないということを決定する。
【００７４】
上記の技術的解決方法に基づき、図5を参照すると、本発明の本実施形態は、2次元フィルタを生成するための装置を提示し、その生成装置は、確立ユニット50、決定ユニット51、及び生成ユニット52を含む。
【００７５】
確立ユニット50は、少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するように構成される。
【００７６】
決定ユニット51は、ハッシュ関数セットを決定し、そのハッシュ関数セットの中の各々のハッシュ関数が、少なくとも1つの鍵値エレメント・グループに対応し、ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するように構成され、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか列ベクトルの長さと等しい正の整数である。
【００７７】
生成ユニット52は、2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成するように構成される。
【００７８】
本発明に本実施形態においては、選択的に、行ベクトルの長さ及び列ベクトルの長さの双方が、
（外６）
2017526081.tif 000028
よりも大きいか又は等しく、行ベクトル及び列ベクトルは、確立ユニット50によって生成される2次元マトリクスに含まれる。
【００７９】
Srは、すべての鍵値エレメント・グループに含まれるすべての鍵値エレメントの数であるか、又はSrは、すべての鍵値エレメント・グループの中に含まれるすべての鍵値エレメントがクエリ条件を使用することによりフィルタリングされた後に得られる鍵値エレメントの数である。
【００８０】
本発明の本実施形態においては、選択的に、決定ユニット51によって取得される第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントのすべての奇数ビットによって形成された鍵値エレメントを含み、決定ユニット51によって取得される第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントのすべての偶数ビットによって形成された鍵値エレメントを含み、又は、
決定ユニット51によって取得される第1のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントの1番目のビットからK番目のビットによって形成された鍵値エレメントを含み、決定ユニット51によって取得される第2のサブ鍵値エレメントは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントの(K+1)番目のビットからN番目のビットによって形成された鍵値エレメントを含み、Nは、いずれかの鍵値エレメントが2進法で表された場合に、そのいずれかの鍵値エレメントのビット数であり、1≦K≦Nであり、Kは、正の整数である。
【００８１】
本発明の本実施形態においては、当該装置は、2次元マトリクスの中のいずれかの行ベクトル及びいずれかの列ベクトルによって決定されたエレメントを、第1のあらかじめ設定された識別子に初期化するように構成される初期化ユニット53をさらに含む。
【００８２】
図6に示されているように、図6は、本発明にしたがって2次元フィルタを生成する装置の実体装置図であり、2次元フィルタを生成する装置は、少なくとも1つのプロセッサ601、通信バス603、メモリ603、及び少なくとも1つの通信インターフェイス604を含む。
【００８３】
通信バス602は、上記の複数の構成要素の間の接続及び通信を実装するように構成され、通信インターフェイス604は、外部装置に接続し、外部装置と通信するように構成される。
【００８４】
メモリ603は、実行される必要があるプログラム・コードを格納するように構成され、メモリ603の中のプログラム・コードを実行すると、プロセッサは、以下の機能、すなわち、
少なくとも2つの行ベクトル及び少なくとも2つの列ベクトルを含む2次元マトリクスを確立するステップと、
ハッシュ関数セットを決定するステップであって、そのハッシュ関数セットの中の各々のハッシュ関数は、少なくとも1つの鍵値エレメント・グループに対応しているステップと、前記ハッシュ関数セットの中のいずれかのハッシュ関数を使用して、少なくとも1つの対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第1のサブ鍵値エレメントにハッシュ計算を実行することにより、第1のハッシュ値を取得し、そして、対応する鍵値エレメント・グループの中のいずれかの鍵値エレメントの第2のサブ鍵値エレメントにハッシュ計算を実行することにより、第2のハッシュ値を取得するステップであって、各々の第1のハッシュ値は、行ベクトルの長さよりも小さいか行ベクトルの長さと等しい正の整数であり、各々の第2のハッシュ値は、列ベクトルの長さよりも小さいか列ベクトルの長さと等しい正の整数である、ステップと、
2次元マトリクス及びハッシュ関数セットを含む2次元フィルタを生成するステップとを実行する。
【００８５】
上記の技術的解決方法に基づき、図７を参照すると、本発明の本実施形態は、鍵値エレメントのクエリを実行する装置を提示し、鍵値エレメントのクエリを実行する装置は、決定ユニット70、設定ユニット71、計算ユニット72、及びクエリ・ユニット74を含む。
【００８６】
決定ユニット70は、ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するように構成される。
【００８７】
設定ユニット71は、各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するように構成される。
【００８８】
計算ユニット72は、クエリを実行されるべき鍵値エレメントについて、クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算するように構成される。
【００８９】
取得ユニット73は、2次元マトリクスの中のクエリを実行されるべき鍵値エレメントのハッシュ値の位置に対応するエレメントを取得するように構成される。
【００９０】
クエリ・ユニット74は、取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するように構成される。
【００９１】
本発明の本実施形態においては、選択的に、いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに決定ユニット70によって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数は、異なっており、或いは、
いずれかの2つの異なる鍵値エレメント・グループにそれぞれ対応しているとともに決定ユニット70によって決定されるハッシュ関数サブセットの中に含まれるハッシュ関数は、同じであるが、ハッシュ関数は、配列方法が異なっている。
【００９２】
本発明の本実施形態においては、選択的に、計算ユニット72は、特に、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第1のサブ鍵値エレメントに計算を実行することにより、第1のハッシュ値を取得し、
クエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットに基づいて、クエリを実行されるべき鍵値エレメントの第2のサブ鍵値エレメントに計算を実行することにより、第2のハッシュ値を取得するように構成される。
【００９３】
本発明の本実施形態においては、選択的に、取得ユニット73は、特に、
第1のハッシュ値を行として使用するとともに第2のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するか、或いは、第2のハッシュ値を行として使用するとともに第1のハッシュ値を列として使用するエレメントを2次元マトリクスから取得するように構成される。
【００９４】
図8に示されているように、図8は、本発明にしたがって2次元フィルタを生成する装置の実体装置図であり、2次元フィルタを生成する装置は、少なくとも1つのプロセッサ801、通信バス802、メモリ803、及び少なくとも1つの通信インターフェイス804を含む。
【００９５】
通信バス802は、上記の複数の構成要素の間の接続及び通信を実装するように構成され、通信インターフェイス804は、外部装置に接続し、外部装置と通信するように構成される。
【００９６】
メモリ803は、実行される必要があるプログラム・コードを格納するように構成され、メモリ803の中のプログラム・コードを実行すると、プロセッサ801は、以下の機能、すなわち、
ハッシュ関数セットから各々の鍵値エレメント・グループに対応するハッシュ関数サブセットを決定するステップと、
各々の鍵値エレメント・グループの中のいずれかの鍵値エレメントについて、鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットにしたがってハッシュ値を計算し、そして、計算されたハッシュ値の2次元マトリクスの中の位置に対応するエレメントを、第2のあらかじめ設定された識別子に設定するステップと、
クエリを実行されるべき鍵値エレメントについて、そのクエリを実行されるべき鍵値エレメントが属する鍵値エレメント・グループに対応するハッシュ関数サブセットを決定し、そして、対応するハッシュ関数サブセットにしたがって、クエリを実行されるべき鍵値エレメントのハッシュ値を計算するステップと、
クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応するエレメントを取得するステップと、
取得されたエレメントが、クエリを実行されるべき鍵値エレメントのハッシュ値の2次元マトリクスの中の位置に対応する第2のあらかじめ設定された識別子である場合に、クエリを実行されるべき鍵値エレメントが、2次元フィルタによってあらわされる鍵値エレメント・セットに属しているということを決定するステップとを実行する。
【００９７】
結論として、本発明の本実施形態においては、2次元フィルタは2次元マトリクスを含み、2次元マトリクスを複数の鍵値エレメント・グループにリンクさせることが可能であり、したがって、フィルタの柔軟性を改善することが可能である。
【００９８】
さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、上記の2次元フィルタに基づいてクエリを実行することが必要であるにすぎず、各々の鍵値エレメント・グループに対応するブルーム・フィルタを生成する必要はない。さらに、ある鍵値エレメントが、複数の鍵値エレメント・グループに含まれる鍵値エレメントであるか否かについてクエリが実行される場合に、複数のブルーム・フィルタの各々に基づいて1つずつクエリを実行する必要はない。したがって、現状では低いクエリ効率の問題をさらに解決することができる。
【００９９】
本発明は、本発明の複数の実施形態にしたがった方法のフローチャート及び/又はブロック図、デバイス(システム)、及びコンピュータ・プログラム製品との関連で説明される。複数のコンピュータ・プログラム命令は、フローチャート及び/又はブロック図の中の各々のプロセス及び/又は各々のブロック並びにフローチャート及び/又はブロック図の中のプロセス及び/又はブロックの組み合わせを実装するのに使用されてもよいということを理解すべきである。汎用コンピュータ、専用コンピュータ、組み込みプロセッサ、又はいずれかの他のプログラム可能なデータ処理デバイスのプロセッサにこれらのコンピュータ・プログラム命令を提供することにより、機械を生成してもよく、その結果、コンピュータ又はいずれかの他のプログラム可能なデータ処理デバイスのプロセッサによって実行されるこれらの命令が、フローチャートの中の1つ又は複数のプロセス及び/又はブロック図の中の1つ又は複数のブロックのある特定の機能を実装する装置を生成する。
【０１００】
これらのコンピュータ・プログラム命令は、コンピュータ読み取り可能なメモリに格納されてもよく、ある特定の方法で動作するように、コンピュータ又はいずれかの他のプログラム可能なデータ処理デバイスに指示してもよく、それによってコンピュータ読み取り可能なメモリに格納されているこれらの命令は、命令装置を含むアーティファクトを生成する。上記の命令装置は、フローチャートの中の1つ又は複数のプロセス及び/又はブロック図の中の1つ又は複数のブロックのある特定の機能を実装する。
【０１０１】
これらのコンピュータ・プログラム命令は、コンピュータ又は他のプログラム可能なデータ処理デバイスにロードされてもよく、それによって、一連の動作及びステップがコンピュータ又は他のプログラム可能なデバイスで実行され、その結果、コンピュータによって実装される処理を生成する。したがって、コンピュータ又は他のプログラム可能なデバイスで実行される命令は、フローチャートの中の1つ又は複数のプロセス及び/又はブロック図の中の1つ又は複数のブロックのある特定の機能を実装する複数のステップを提供する。
【０１０２】
本発明のいくつかの例示的な実施形態が説明されてきたが、基本的な発明概念を知れば、当業者は、これらの実施形態に変更及び修正を加えることができる。したがって、以下の特許請求の範囲は、これらの例示的な実施形態のみならず本発明の範囲に入る変更及び修正のすべてにも及ぶものと解釈されることを意図している。
【０１０３】
明らかなことだが、当業者であれば、本発明の上記の複数の実施形態の趣旨及び範囲から逸脱することなく、本発明のそれらの複数の実施形態に修正及び変形を加えることができる。これらの修正及び変形が、以下の特許請求の範囲及びその等価な技術によって定義される保護の範囲に入る場合には、本発明は、それらの修正及び変形を対象とすることを意図されている。
【国際調査報告】
2017526081.tif 000029
2017526081.tif 000030
2017526081.tif 000031
2017526081.tif 000032