"段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能なコンピュータに、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換し、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定し、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得し、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断し、同一であると判断された場合、第p段が第1段であるか否かを判断し、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する、処理を実行させることを特徴とする検索プログラム。前記ビット幅sのうち前記所定ビット幅に応じた前記分割データ構造のビット範囲と前記ノード群の各ノードとを対応付けた対応テーブルを参照することで、特定された前記第p段の転置ブルームフィルタを保持するノードを特定する処理を前記コンピュータに実行させ、前記第p段の転置ブルームフィルタを取得する処理では、特定先ノードから、特定された前記第p段の転置ブルームフィルタを取得することを特徴とする請求項1に記載の検索プログラム。前記第p段の転置ブルームフィルタを取得する処理では、特定された前記第p段の転置ブルームフィルタが複数存在する特定先ノードから前記第p段の転置ブルームフィルタの論理積を取得し、擬陽性を示すビットのビット位置が同一であるか否かを判断する処理では、取得された論理積に基づいて、前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断することを特徴とする請求項2に記載の検索プログラム。第p段が第1段であると判断された場合、前記対応テーブルを参照することで、前記特定のデータブロックを有するノードを特定する処理を前記コンピュータに実行させることを特徴とする請求項1~3のいずれか一つに記載の検索プログラム。段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群のいずれかのノードに、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信し、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信し、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信し、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索し、検索結果を前記コンピュータに送信する、処理を実行させることを特徴とする検索プログラム。段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能なコンピュータが、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換し、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定し、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得し、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断し、同一であると判断された場合、第p段が第1段であるか否かを判断し、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する、処理を実行することを特徴とする検索方法。段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群のいずれかのノードが、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信し、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信し、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信し、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索し、検索結果を前記コンピュータに送信する、処理を実行することを特徴とする検索方法。段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能な検索装置であって、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換する処理部と、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定する処理部と、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得する処理部と、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断する処理部と、同一であると判断された場合、第p段が第1段であるか否かを判断する処理部と、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する処理部と、を備えることを特徴とする検索装置。段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群のいずれかのノードであって、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信する処理部と、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信する処理部と、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信する処理部と、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索する処理部と、検索結果を前記コンピュータに送信する処理部と、を備えることを特徴とするノード。上述したように、B木は多量のデータを扱うことができるため、キャッシュを適切に実装すれば、ディスクI/Oを減らすことは可能である。しかしながら、その回数をある一定以上減らすことはできない。また、データエントリの追加により木構造が変化すると、木構造管理のためのI/Oが必要になることもある。また、ブルームフィルタは、データエントリの存在だけがわかるものであるため、そのままではデータ管理に使うことはできない。また、ブルームフィルタは、管理可能なデータ量に比例したサイズのメモリを占有する。したがって、重複除去ストレージシステムに適用した場合、当該システム全体の容量がノードに搭載できるメモリ量によって決まってしまうという問題があった。したがって、重複データを広い範囲で検索できないという問題があった。1つの側面では、本発明は、データ検索の高速化又は管理可能なデータ量の拡大化を図ることができる検索プログラム、検索方法、検索装置、ノードおよび検索システムを提供することを目的とする。本発明の一側面では、段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能なコンピュータが、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換し、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定し、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得し、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断し、同一であると判断された場合、第p段が第1段であるか否かを判断し、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する、検索プログラム、検索方法、および検索装置を用いる。本発明の他の側面では、段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群で検索システムが構成される場合、前記ノード群内の各ノードが、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信し、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信し、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信し、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索し、検索結果を前記コンピュータに送信する、検索プログラム、検索方法、検索装置、ノードおよび検索システムを用いる。一態様によれば、データ検索の高速化を図ることができる。また、一態様によれば、管理可能なデータ量の拡大化を図ることができる。以下に添付図面を参照して、本発明にかかる検索プログラム、検索方法、検索装置、ノードおよび検索システムの実施の形態を詳細に説明する。<検索システムのシステム構成例>図1は、実施の形態にかかる検索システムのシステム構成例を示す説明図である。図1において、検索システム100は、複数図1では例として4台のノードN1~N4と、管理サーバMと、一または複数図1では例として3台のクライアントC1~C3と、がネットワークNWを介して通信可能に接続されて構成されている。ネットワークNWとしては、たとえば、LANLocalAreaNetwork、WANWideAreaNetwork、インターネットが挙げられる。本実施の形態では、階層型転置ブルームフィルタtBFをノード数で分割して、階層型分割転置ブルームフィルタを各ノードに持たせておく。階層型転置ブルームフィルタtBFとは、階層型ブルームフィルタを転置したインデックス情報である。階層型ブルームフィルタとは、ブルームフィルタを階層構造にしたインデックス情報である。ブルームフィルタとは、所定数のデータブロック内での擬陽性疑陽性、偽陽性ともいうまたは陰性を示すビットが複数配列されたインデックス情報である。ブルームフィルタのビットがONのときは擬陽性を示し、OFFのときは陰性を示す。なお、ビットの値が1をONとし、0をOFFとしてもよく、逆に、ビットの値が0をONとし、1をOFFとしてもよい。本実施の形態では、ビットの値が1をON擬陽性とし、0をOFF陰性とする。なお、階層型ブルームフィルタについては、図2を用いて後述する。また、階層型ブルームフィルタと階層型転置ブルームフィルタtBFとの対応関係については、図3を用いて後述する。また、図1では、例として階層型転置ブルームフィルタtBFの階層数を3とする。したがって、階層型転置ブルームフィルタtBFは、1段目最下段の転置ブルームフィルタ列tBF1、2段目の転置ブルームフィルタ列tBF2、3段目最上段の転置ブルームフィルタ列tBF3を階層化したブルームフィルタである。また、図1では、例として階層型転置ブルームフィルタtBFのビット幅sを64ビットとする。また、図1では、例として4台のノードで階層型転置ブルームフィルタtBFを16ビットのビット幅で分割するものとする。たとえば、ノードN1に割り当てられる階層型分割転置ブルームフィルタtBF1は、階層型転置ブルームフィルタtBFの1ビット目から16ビット目までのインデックス範囲となる。ノードN2~N4についても同様に、図1に示したようにインデックス範囲が決まる。また、階層型転置ブルームフィルタtBFにはデータブロック集合dbが対応付けられている。データブロック集合dbは、階層型転置ブルームフィルタtBFのビット幅sと同一ビット幅とする。したがって、データブロック集合dbは、階層型転置ブルームフィルタtBFと同じインデックス範囲で分割される。たとえば、分割データブロック集合ddb1は、階層型分割転置ブルームフィルタtBF1とともにノードN1に割り当てられることとなる。分割データブロック集合ddb2~dbb4についても同様に、図1に示したように割り当てられる。また、各ノードN1~N4は、ハッシュテーブルHT1~HT8を有している。ハッシュテーブルHT1~HT8とは、データと、当該データを各ノードに共通のハッシュ関数たとえば、SHA-1に与えたときのハッシュ値と、を関連付けたテーブルである。ハッシュテーブルHT1~HT8は、データブロックごとに用意されている。たとえば、ハッシュテーブルHT1はデータブロックdb1に対応する。また、ハッシュテーブルHT1~HT8のポインタで指定されるデータは、そのハッシュテーブルHT1~HT8に対応するデータブロックdb1~db8に格納されている。たとえば、ハッシュテーブルHT1のポインタで指定されるデータD11,D12は、データブロックdb1に格納されている。なお、図1の例では、分割データブロック集合ddb1~ddb4内の数字はデータブロックの番号を示しており、たとえば、分割データブロック集合ddb1内の1はデータブロックdb1、分割データブロック集合ddb1内の2はデータブロックdb2となる。このように、階層型転置ブルームフィルタtBFおよびデータブロック集合dbを複数のノードに分散させることにより、重複除去ストレージのスケーラビリティの向上を図ることができる。また、階層型転置ブルームフィルタtBFを分散させておくことで、検索速度の高速化も図ることができる。管理サーバMは、複数のノードN1~N4を管理するコンピュータである。管理サーバMは、対応テーブルTを有している。対応テーブルTとは、階層型分割転置ブルームフィルタのインデックス範囲と当該インデックス範囲を担当するノードとを関連付けたテーブルである。管理サーバMは、対応テーブルTを参照することで、複数のノードN1~N4のいずれかのノードにデータエントリ処理やフィルタエントリ処理を実行したり、複数のノードN1~N4からデータの検索処理を実行したりする。なお、管理サーバMは、物理マシンでもよいが、いずれかのノードにおいて仮想マシンとして機能させてもよい。クライアントC1~C3は、複数のノードN1~N4を利用するコンピュータである。クライアントC1~C3は、対応テーブルTを有していない場合は、管理サーバMを介してデータエントリ処理やフィルタエントリ処理、データの検索処理を実行する。クライアントC1~C3は、対応テーブルTを有している場合は、管理サーバMを介さずにデータエントリ処理やフィルタエントリ処理、データの検索処理を実行する。クライアントC1~C3に対応テーブルTを持たせた場合は、必ずしも管理サーバMは必要ではない。また、クライアントC1~C3が対応テーブルTを有している場合でも、たとえば、管理サーバMはデータエントリ処理やフィルタエントリ処理をおこない、クライアントC1~C3はデータの検索処理をおこなうなど、担当する処理を分けて実行することとしてもよい。なお、データエントリ処理やフィルタエントリ処理を実行するコンピュータは、フィルタエントリ処理に必要な各段の転置ブルームフィルタ列tBFpの配列数やビット幅sを記憶しているものとする。このような検索システム100では、検索対象データが与えられると、階層型分割転置ブルームフィルタtBF1~tBF4を参照して、検索対象データが存在するであろうデータブロックdbを特定することになる。検索対象データが存在するであろうデータブロックdbが特定されなかった場合は、いずれのデータブロックdbにも検索対象データは存在しない陰性。逆に、検索対象データが存在するであろうデータブロックdbが特定された場合でも、特定されたデータブロックdbには、必ずしも検索対象データが存在するとは限らない擬陽性。なお、擬陽性が陽性になるか陰性になるかは、最終的に特定されたデータブロックdbに対応するハッシュテーブルHTでの検索結果に依存する。たとえば、最終的に特定されたデータブロックdbに対応するハッシュテーブルHTにおいて、検索対象データのハッシュ値がヒットすれば陽性、ヒットしなければ陰性となる。<階層型ブルームフィルタ>つぎに、図1に示した階層型転置ブルームフィルタtBFの転置元となる階層型ブルームフィルタについて説明する。図2は、階層型ブルームフィルタの一例を示す説明図である。階層型ブルームフィルタBFは、h段×sビット幅のメモリ領域で構成されている。sビット幅は、データブロック集合dbのビット幅に対応する。また、各段のビット長sは最上段である第h段の分割数dに基づいて分割される。分割された各々はブルームフィルタであり、各段においてブルームフィルタ列を構成する。分割数dは基本的には2以上の整数であるが、最上段である第h段を単一のブルームフィルタとする場合は、d=1としてもよい。任意の段をpとすると、第p段のブルームフィルタ列BFpを構成するブルームフィルタbfpのビット幅mは、m=s/dhとなる。図2では、d=2としている。また、第p段のブルームフィルタ列BFpのブルームフィルタbfpの配列数nは、n=dhとなる。したがって、階層型ブルームフィルタBFでは、段が下がるhが小さくなるにつれ、第p段のブルームフィルタ列BFpのブルームフィルタbfpの配列数が増加する。なお、最下段第1段のブルームフィルタ列BF1のブルームフィルタbf1の配列数は、データブロックdbの個数と同一とする。これにより、第1段までたどり着いたときにヒットしたブルームフィルタbf1とデータブロックdbとが一対一対応することになる。また、階層型ブルームフィルタBFの段数hは基本的には複数段であるが、1段h=1としてもよい。ただし、この場合は、d≠1とする。ここで、ブルームフィルタの擬陽性による影響について説明する。ブルームフィルタの擬陽性の発生確率FPRは、ビット長がmのブルームフィルタがh段ある場合、データ登録数NN<m、ハッシュ関数の個数をk個とすると、ブルームフィルタの性質より、次式1のように表すことができる。FPR={1-1-1/mkN}k≒{1-e}k1この場合、k,m,Nを変更することにより、擬陽性の発生確率FPRを非常に小さくすることができる。すなわち、k,m,Nの設定次第で、擬陽性の発生確率FPRを1よりも非常に小さい値ほぼ0に設定することができるようになる。また、データブロック数Ndbをdhとすると、高さ段数hは、次式2にて表すことができる。h=logNdb/logd12上記式2は、logNdb/logdが割り切れる場合を前提にしたが、そうでない場合、段によりdの値を他の段とは変えることで、hを決定することができる。また、検索処理ではハッシュ値の数k回定数だけ照合を行う必要があり、検索における1段あたりのフィルタリング対象の数は多くてもd個である。したがって、検索によるメモリアクセス回数MAは、最大でも次式3で表される程度である。MA=k×d×logNdb/logd3すなわち、段数h=メモリ量は、分割数dを増やすことにより小さくすることができ、その一方で、検索回数は分割数dの増加とともに大きくなるというトレードオフの関係にある。したがって、この関係を考慮することで、適切なメモリの運用が可能となる。<階層型転置ブルームフィルタtBF>つぎに、階層型転置ブルームフィルタtBFについて説明する。図2に示した階層型ブルームフィルタBFを転置させることで、階層型ブルームフィルタBFよりも検索速度をさらに高速化させることができる。図3は、階層型ブルームフィルタBF内の第p段のブルームフィルタ列BFpの転置例を示す説明図である。Aは、ブルームフィルタ列BFpを示している。ここでは、ブルームフィルタ列BFpは、例として、4分割されたブルームフィルタbfp-1~bfp-4を示している。すなわち、ブルームフィルタ列BFpは、8ビット×4フィルタ数のビット列である。転置する場合は、4ビット×8フィルタ数のビット列となる。すなわち、転置により、配列数とビット幅が入れ替わる。Bは、ブルームフィルタ列BFpの転置を示している。転置する場合、各ブルームフィルタbfp-1~bfp-4の同一位置のビットを集めて、同一位置ごとに集められたビット列を、ビット位置順に配列させる。具体的には、各ブルームフィルタbfp-1~bfp-4の各先頭ビットを配列番号順にまとめてビット列{0110}とする。左から先頭ビット0がブルームフィルタbfp-1の先頭ビット、2番目のビット1がブルームフィルタbfp-2の先頭ビット、3番目のビット1がブルームフィルタbfp-3の先頭ビット、末尾ビット0がブルームフィルタbfp-4の先頭ビットである。このビット列{0110}を、転置ブルームフィルタtbfp-1と称す。2番目~末尾のビット位置についても同様にまとめることで、転置ブルームフィルタtbfp-1~tbfp-8を得る。転置ブルームフィルタtbfp-1~tbfp-8がビット位置順に配列されたインデックス情報が、転置ブルームフィルタ列tBFpである。転置ブルームフィルタ列tBFpをすべての段で生成することで、階層型転置ブルームフィルタtBFとなる。Cは、ブルームフィルタ列BFpと転置ブルームフィルタ列tBFpとの検索比較例を示している。ここでは、2種類のハッシュ関数により対象データDのハッシュ値を2つ求め、ブルームフィルタ列BFpを構成するブルームフィルタbfpのビット幅10で割り算した余り値を、4および8とする。ブルームフィルタ列BFpで検索する場合、余り値4および8となるビット位置4および8がすべてONになっているブルームフィルタbfpをブルームフィルタ列BFpから探す。この場合、ブルームフィルタbfp-2が該当する。一方、転置ブルームフィルタ列tBFpを用いる場合、ブルームフィルタ列BFpのように、ビット位置4および8がすべてONになっているブルームフィルタbfpを検索せず、余り値4および8と同一配列番号の転置ブルームフィルタtbfp-4,tbfp-8を抽出する。そして、抽出された転置ブルームフィルタtbfp-4,tbfp-8をAND演算することで、ともにONになっているビット位置2を特定する。ブルームフィルタ列BFpの場合は、4個のブルームフィルタbfp-1~bfp-4内の4ビット目と8ビット目を参照するため、8=4×2のメモリアクセスが必要となる。一方、転置ブルームフィルタ列tBFpは、転置前のブルームフィルタbfp-1~bfp-4のビット位置ごとに折りたたまれたインデックス情報である。したがって、転置ブルームフィルタtbfp-4,tbfp-8を抽出するという2回のメモリアクセスとそのAND演算により判定することが可能となる。したがって、階層型ブルームフィルタBFよりもメモリアクセス頻度が低減され、検索速度が高速化することとなる。このようにして得られた階層型転置ブルームフィルタtBFをインデックス範囲で分割してノードに割り当てることで、各ノードでの検索処理において、メモリアクセス頻度が低減され、検索速度が高速化することとなる。また、複数のノードに分散されているため、単ノードに比べて、複数のノード全体でのインデックス範囲を広くとることができる。このように、管理可能なデータ量の拡大を図ることで、重複データを広い範囲で検索をおこなうことができ、検索対象データを見つけやすくすることができる。<コンピュータのハードウェア構成例>図4は、実施の形態にかかるコンピュータノードN1~N4、管理サーバM、クライアントC1~C3のハードウェア構成例を示すブロック図である。図4において、検索装置は、CPUCentralProcessingUnit401と、ROMReadOnlyMemory402と、RAMRandomAccessMemory403と、磁気ディスクドライブ404と、磁気ディスク405と、光ディスクドライブ406と、光ディスク407と、ディスプレイ408と、I/FInterface409と、キーボード140と、マウス411と、スキャナ412と、プリンタ413と、を備えている。また、各構成部はバス400によってそれぞれ接続されている。ここで、CPU401は、コンピュータの全体の制御を司る。ROM402は、ブートプログラムなどのプログラムを記憶している。RAM403は、CPU401のワークエリアとして使用される。磁気ディスクドライブ404は、CPU401の制御にしたがって磁気ディスク405に対するデータのリード/ライトを制御する。磁気ディスク405は、磁気ディスクドライブ404の制御で書き込まれたデータを記憶する。光ディスクドライブ406は、CPU401の制御にしたがって光ディスク407に対するデータのリード/ライトを制御する。光ディスク407は、光ディスクドライブ406の制御で書き込まれたデータを記憶したり、光ディスク407に記憶されたデータをコンピュータに読み取らせたりする。ディスプレイ408は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ408は、たとえば、CRT、TFT液晶ディスプレイ、プラズマディスプレイなどを採用することができる。インターフェース以下、I/Fと略する。409は、通信回線を通じてネットワークNWに接続され、このネットワークNWを介して他の装置に接続される。そして、I/F409は、ネットワークNWと内部のインターフェースを司り、外部装置からのデータの入出力を制御する。I/F409には、たとえばモデムやLANアダプタなどを採用することができる。キーボード410は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス411は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。スキャナ412は、画像を光学的に読み取り、コンピュータ内に画像データを取り込む。なお、スキャナ412は、OCROpticalCharacterReader機能を持たせてもよい。また、プリンタ413は、画像データや文書データを印刷する。プリンタ413には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。<エントリ処理例>つぎに、エントリ処理について説明する。エントリ処理では、エントリの対象となるデータ以下、対象データを登録するデータエントリ処理と、階層型分割転置ブルームフィルタ群へのフィルタエントリ処理とが実行される。以下、図5を用いて説明する。図5は、エントリ処理の一例を示す説明図である。ここでは、図1に示した階層型分割転置ブルームフィルタ群tBF1~tBF4を例にあげて説明する。図5では、対象データDxがデータブロック集合dbにまだエントリされていないものとする。また、エントリ処理を実行するコンピュータは、管理サーバMまたはクライアントC1~C3となるが、ここでは一例として管理サーバMとする。データエントリ処理例まず、データエントリ処理例について説明する。登録される対象データDxが与えられるハッシュ関数の種類数kをk=3とする。ここでは、ハッシュ関数H1,H2,H3を用いることとする。また、ハッシュテーブルHT1~HT8の登録対象となるハッシュ関数をH1とする。まず、管理サーバMでは、対象データをエントリさせるノード登録先ノードを指定する。どのノードにエントリするかは、管理サーバMの利用者が任意に指定することができる。また、あらかじめ各ノードの空き容量に応じて、エントリさせるノードを指定することとしてもよい。各ノードの空き容量は、各ノードが管理サーバMに対して定期的にまたは管理サーバMからの要求に応じて通知されるものとする。図5では、ノードN2が指定されたものとする。また、対象データDxを各ハッシュ関数H1,H2,H3に与えたときのハッシュ値は、例として以下の値とする。H1Dx=x1H2Dx=x2H3Dx=x3また、エントリ処理では、更新対象となる転置ブルームフィルタtbfp内の特定のビットをONにするが、その特定のビットがすでにONになっている場合はそのままとする。ここで、管理サーバMは、対象データDxについてのハッシュテーブルエントリExを作成する。そして、管理サーバMは、作成されたハッシュテーブルエントリExを、登録先ノードとなるノードN2に送信する。なお、図5の例では、ノードN2は、分割データブロック集合ddb2内のデータブロックdb4に、対象データDxを登録したものとする。この場合、ハッシュテーブルエントリExは、ノードN2のハッシュテーブルHT4に追加される。なお、実際には、対象データDxは、データブロックdb4に格納されており、ハッシュテーブルHT4では、ハッシュ値x1とデータブロックdb4に格納された対象データDxへのポインタとが関連付けられることになる。ノードN2は、ハッシュテーブルHT4へのエントリが完了すると、管理サーバMにリプライを返す。リプライには、登録先のデータブロックのブロック番号が含まれている。この場合は、登録先のデータブロックdb4のブロック番号4が含まれている。フィルタエントリ処理例つぎに、フィルタエントリ処理例について説明する。まずは、第1段のフィルタエントリ処理が実行される。管理サーバMは、更新対象となる転置ブルームフィルタtbf1を、第1段の転置ブルームフィルタ列tBF1の中から特定する。具体的には、管理サーバMは、各ハッシュ値x1~x3を、第1段の転置ブルームフィルタ列tBF1の配列数である8で割り算し、余り値を算出する。余り値は、転置ブルームフィルタの配列位置をあらわす位置情報となる。ここでは、ハッシュ値x1の余り値は2、ハッシュ値x2の余り値は5、ハッシュ値x3の余り値は7になったものとする。したがって、第1段での更新対象となる転置ブルームフィルタtbf1は、転置ブルームフィルタtbf1-2,tbf1-5,tbf1-7となる。また、第1段最下段では、リプライで特定される登録先のデータブロックdb4のブロック番号4に対応するビット位置を更新対象ビットとする。そして、管理サーバMは、第1段での更新対象となる転置ブルームフィルタtbf1-2,tbf1-5,tbf1-7のインデックス範囲を特定する。たとえば、第1段の転置ブルームフィルタtbf1のビット幅は8ビットであるため、先頭から2番目の転置ブルームフィルタtbf1-2のインデックス範囲は、9ビット目から16ビット目となる。このインデックス範囲は、対応テーブルTを参照することで、ノードN1のインデックス範囲であると特定される。したがって、転置ブルームフィルタtbf1-2はノードN1に属していることが判明する。転置ブルームフィルタtbf1-5,tbf1-7についても同様に、それぞれノードN3,N4に属していることが判明する。そして、管理サーバMは、ノードN1,N3,N4に更新対象ビット位置を通知する。通知を受けたノードN1,N3,N4は、更新対象となる転置ブルームフィルタtbf1の先頭から4ビット目のビットをONにする。これにより、第1段の転置ブルームフィルタ列tBF1のフィルタエントリ処理を終了する。つぎに、第2段のフィルタエントリ処理が実行される。管理サーバMは、更新対象となる転置ブルームフィルタtbf2を、第2段の転置ブルームフィルタ列tBF2の中から特定する。具体的には、管理サーバMは、各ハッシュ値x1~x3を、第2段の転置ブルームフィルタ列tBF2の配列数である16で割り算し、余り値を算出する。ここでは、ハッシュ値x1の余り値は8、ハッシュ値x2の余り値は11、ハッシュ値x3の余り値は13になったものとする。したがって、第2段での更新対象となる転置ブルームフィルタtbf2は、転置ブルームフィルタtbf2-8,tbf2-11,tbf2-13となる。つぎに、転置ブルームフィルタtbf2-8,tbf2-11,tbf2-13内のどのビット位置のビットをONにするかについて説明する。転置前の階層型ブルームフィルタBFでは、分割数をdとして、各ブルームフィルタ列BFpをn=dh個に分割した。そして、これにより、各ブルームフィルタ列BFpのビット幅は、m=s/nビットになった。このため、階層型ブルームフィルタBFでは、第p-1段での更新対象のブルームフィルタbfp-1-のビット位置を包含するブルームフィルタbfpを、第p段のブルームフィルタ列BFpの中から特定していた。これに対し、階層型転置ブルームフィルタtBFでは、配列数nとビット幅mが入れ替わっているため、第p-1段の更新対象のブルームフィルタbfp-1-の配列番号ではなく、第p-1段での更新対象ビット位置を分割数dで割り算し、端数を切り上げる。分割数dは転置後では最上段hの転置ブルームフィルタtbfhのビット幅となる。第2段の場合、前段である第1段での更新対象ビットは、先頭から4ビット目のビットであり、転置ブルームフィルタtbf1-2,tbf1-5,tbf1-7の4ビット目がONにされた。したがって、第2段の更新対象ビットは、d=2であるため、先頭から4/d=2ビット目のビットを更新対象ビットとする。本例では、転置ブルームフィルタtbf2-8,tbf2-11,tbf2-13の先頭から2ビット目が更新対象ビット位置となる。そして、管理サーバMは、第1段と同様、転置ブルームフィルタtbfのビット幅第2段は4ビットと対応テーブルTを用いることで、第2段での更新対象となる転置ブルームフィルタtbf2-8,tbf2-11,tbf2-13を有するノードN2~N4を特定する。そして、管理サーバMは、ノードN2~N4に更新対象ビット位置を通知する。通知を受けたノードN2~N4は、更新対象となる転置ブルームフィルタtbf2の先頭から2ビット目のビットをONにする。これにより、第2段の転置ブルームフィルタ列tBF2のフィルタエントリ処理を終了する。つぎに、第3段最上段のフィルタエントリ処理が実行される。管理サーバMは、更新対象となる転置ブルームフィルタtbf3を、第3段の転置ブルームフィルタ列tBF3の中から特定する。具体的には、管理サーバMは、各ハッシュ値x1~x3を、第3段の転置ブルームフィルタ列tBF3の配列数である32で割り算し、余り値を算出する。ハッシュ値x1の余り値は2、ハッシュ値x2の余り値は19、ハッシュ値x3の余り値は27になったものとする。したがって、第3段での更新対象となる転置ブルームフィルタtbf3は、転置ブルームフィルタtbf3-2,tbf3-19,tbf3-27となる。つぎに、転置ブルームフィルタtbf3-2,tbf3-19,tbf3-27内の更新対象ビット位置を決める。第2段と同様、第p-1段の更新対象のブルームフィルタbfp-1-の配列番号ではなく、第p-1段での更新対象ビット位置を分割数dで割り算し、端数を切り上げる。第3段の場合、前段である第2段での更新対象ビットは、先頭から2ビット目のビットであり、転置ブルームフィルタtbf2-8,tbf2-11,tbf2-13の2ビット目がONにされた。したがって、第3段の更新対象ビットは、d=2であるため、先頭から2/d=1ビット目を更新対象ビット位置とする。本例では、転置ブルームフィルタtbf3-2,tbf3-19,tbf3-27の先頭から1ビット目が更新対象ビット位置となる。そして、管理サーバMは、第1段、第2段と同様、転置ブルームフィルタtbfのビット幅第3段は2ビットと対応テーブルTを用いることで、第3段での更新対象となる転置ブルームフィルタtbf3-2,tbf3-19,tbf3-27を有するノードN1,N3,N4を特定する。そして、管理サーバMは、ノードN1,N3,N4に更新対象ビット位置を通知する。通知を受けたノードN1,N3,N4は、更新対象となる転置ブルームフィルタtbf3の先頭から1ビット目のビットをONにする。これにより、第3段の転置ブルームフィルタ列tBF3のフィルタエントリ処理を終了する。登録元コンピュータによるエントリ処理手順図6は、実施の形態にかかる登録元コンピュータによるエントリ処理手順例を示すフローチャートである。エントリ処理を実行するコンピュータたとえば、管理サーバMまたはクライアント。以下、単に登録元コンピュータ。は、登録したい対象データたとえば、図5に示した対象データDxがあるか否かを判断するステップS601。対象データDxがある場合ステップS601:Yes、登録元コンピュータは、k種類のハッシュ関数H1を含むのそれぞれに対象データを与えてk個のハッシュ値を算出するステップS602。そして、登録元コンピュータは、段数pをp=1に設定しステップS603、データエントリ処理ステップS604およびフィルタエントリ処理ステップS605を実行する。その後、ステップS601に戻る。そして、コンピュータは、登録したい対象データがない場合ステップS601:No、エントリ処理を終了する。これにより、図5に示したように、対象データDxについてデータエントリ処理とフィルタエントリ処理が実行され、対象データDxについて検索可能状態となる。データエントリ処理手順図7は、図6に示したデータエントリ処理の詳細な処理手順例を示すフローチャートである。図7において、まず、登録元コンピュータは、対象データDxのハッシュテーブルエントリを生成するステップS701。たとえば、登録元コンピュータは、図5に示したように、ハッシュテーブルエントリExを生成する。つぎに、登録元コンピュータは、登録先ノードを指定するステップS702。具体的には、たとえば、管理サーバMの利用者が入力装置を操作することで任意に指定することができる。また、あらかじめ各ノードの空き容量に応じて、エントリさせるノードを指定することとしてもよい。図5に示した例では、ノードN2が指定されている。そして、登録元コンピュータは、登録先ノードにデータエントリリクエスト801を送信しステップS703、データエントリリクエスト801に対する登録先ノードからのリプライを待ち受けるステップS704。図8は、データエントリリクエスト801およびリプライのデータ構造例を示す説明図である。図8において、Aはデータエントリリクエスト801、Bはリプライ802を示す。図8のデータ構造例は、図5のデータエントリ処理例に対応している。Aのデータエントリリクエスト801のヘッダは、データエントリリクエスト801の送信元アドレスと宛先アドレスとを保持する。図8では、コンピュータに割り当てた符号M,N2をアドレスの代わりに表記している。また、Aのデータエントリリクエスト801のペイロードは、種類項目、属性項目、ハッシュ値項目、登録データ項目に対しそれぞれの情報が保持されている。たとえば、種類項目には、登録、属性項目にはデータエントリ、ハッシュ値項目にはx1、登録データ項目には、Dxが保持されている。また、Bのリプライ802のヘッダは、データエントリリクエスト801の送信元アドレスと宛先アドレスとが入れ替わった送信元アドレスと宛先アドレスとを保持する。Bのリプライ802のペイロードは、登録データである対象データDxが登録されたデータブロックdb4のブロック番号4が保持されている。図7に戻り、リプライ802が受信されていない場合ステップS704:No、登録元コンピュータは、データエントリリクエスト801の送信から所定時間経過したか否かを判断するステップS705。所定時間経過していない場合ステップS705:No、ステップS704に戻る。一方、所定時間経過した場合ステップS705:Yes、登録元コンピュータは、エラー出力をおこなうステップS706。たとえば、ディスプレイ408に、データエントリできなかった旨の表示をおこなう。一方、リプライ802が受信された場合ステップS704:Yes、フィルタエントリ処理ステップS605を実行することとなる。このデータエントリ処理ステップS604により、対象データDxが、指定された登録先ノードに、対象データDxのハッシュ値と関連付けられて登録されることとなる。フィルタエントリ処理図9は、図6に示したフィルタエントリ処理の詳細な処理手順例を示すフローチャートである。図9において、まず、登録元コンピュータは、図7のステップS704で受信したリプライ802から登録先データブロックのブロック番号を抽出するステップS901。図8のBに示した例では、4が抽出される。つぎに、登録元コンピュータは、p>hhは階層型分割転置ブルームフィルタ群の最上段であるか否かを判断するステップS902。p>hでない場合ステップS902:No、登録元コンピュータは、k個のハッシュ値を第p段の転置ブルームフィルタtbfpの配列数で除算して、k個の余り値を算出するステップS903。なお、階層型転置ブルームフィルタtBFのビット幅sと段ごとの転置ブルームフィルタの配列数については登録元コンピュータに保持されているものとする。そして、登録元コンピュータは、k個の余り値と同一配列番号のk個の転置ブルームフィルタtbfpを特定するステップS904。このあと、p=1であるか否かを判断しステップS905、p=1である場合ステップS905:Yes、登録元コンピュータは、ステップS901で抽出された登録先データブロックのブロック番号を、エントリすべきブロック番号として特定するステップS906。図5の例では、ブロック番号は4であるため、エントリすべきブロック番号は4である。一方、p≠1である場合ステップS905:No、登録元コンピュータは、特定されたk個の転置ブルームフィルタtbfpに、対象データDxの第p-1段での更新対象ビット位置エントリ番号ep-1を分割数dで除算した商端数切り上げを、エントリすべきブロック番号として特定するステップS907。図5の例において、第2段の場合、第1段での更新対象ビット位置である4を、転置前の最上段の分割数=2で除算した商2がエントリすべきブロック番号となる。ステップS906またはS907のあと、登録元コンピュータは、転置ブルームフィルタtbfpを有するノードを特定するステップS908。第1段を例に挙げると、第1段の転置ブルームフィルタtbfのビット幅は8ビットであるため、先頭から2番目の転置ブルームフィルタtbf1-2のインデックス範囲は、9ビット目から16ビット目となる。このインデックス範囲は、対応テーブルTを参照することで、ノードN1のインデックス範囲であると特定される。そして、登録元コンピュータは、ステップS908での特定先ノードに対し、フィルタエントリリクエストを配信しステップS909、リプライ802ACKを待ち受けるステップS910。図10は、フィルタエントリリクエストのデータ構造例を示す説明図である。図10のデータ構造例は、図5の第1段でのデータエントリ処理例に対応している。フィルタエントリリクエスト1000のヘッダは、フィルタエントリリクエスト1000の送信元アドレスと宛先アドレスとを保持する。図10では、コンピュータに割り当てた符号M,N1をアドレスの代わりに表記している。また、フィルタエントリリクエスト1000のペイロードは、種類項目、属性項目、特定先転置ブルームフィルタ項目、特定先ブロック番号項目に対しそれぞれの情報が保持されている。たとえば、種類項目には、登録、属性項目にはフィルタエントリ、転置ブルームフィルタ項目には特定された転置ブルームフィルタの識別子tbf1-2特定先ノード宛先がN1のため、特定先ブロック番号項目には、4が保持されている。転置ブルームフィルタ項目において、特定された転置ブルームフィルタの識別子としては、特定された転置ブルームフィルタのビット位置を示すインデックス範囲が挙げられる。たとえば、tbf1-2の場合は、9ビット目~16ビット目となる。図9に戻り、リプライが受信されていない場合ステップS910:No、登録元コンピュータは、フィルタエントリリクエスト1000の送信から所定時間経過したか否かを判断するステップS911。所定時間経過していない場合ステップS911:No、ステップS910に戻る。一方、所定時間経過した場合ステップS911:Yes、登録元コンピュータは、エラー出力をおこなうステップS912。たとえば、ディスプレイに、フィルタエントリできなかった旨の表示をおこなう。一方、リプライが受信された場合ステップS910:Yes、登録元コンピュータは、段数pを1つインクリメントしステップS913、ステップS902に戻る。そして、登録元コンピュータは、p>hと判断した場合ステップS902:Yes、ステップS601に戻ることで、フィルタエントリ処理ステップS605を終了する。このフィルタエントリ処理ステップS605により、対象データを検索するためのフィルタが設定されることとなる。ノードによるエントリ処理図11は、実施の形態にかかるノードによるエントリ処理の詳細な処理手順例を示すフローチャートである。図11の処理手順は、複数のノードノードN1~N4のいずれのノードでも実行される処理手順である。まず、ノードは、リクエストの受信を待ち受けるステップS1101:No。リクエストが受信された場合ステップS1101:Yes、ノードは、リクエストの種類を特定するステップS1102。具体的には、リクエスト内の種類項目が登録または検索であるかを特定する。登録である場合ステップS1102:登録、ノードは、属性を特定するステップS1103。具体的には、リクエスト内の属性項目がデータエントリまたはフィルタエントリであるかを特定する。データエントリの場合ステップS1103:データエントリ、受信したリクエストがデータエントリリクエスト801であると判明する。この場合、ノードは、データエントリリクエスト801の登録データ項目内のデータを、保持しているいずれかのデータブロックに登録するステップS1104。また、ノードは、データエントリリクエスト801のハッシュ値項目内のハッシュ値をハッシュテーブルに登録し、ステップS1104で登録されたデータおよびハッシュ値を関連付けるステップS1105。このあと、ノードは、登録先データブロックのブロック番号を含むリプライ802を、データエントリリクエスト801の送信元に返すステップS1106。これにより、ノードによるデータエントリ処理が終了する。一方、ステップS1103において、属性がフィルタエントリである場合ステップS1103:フィルタエントリ、受信したリクエストがフィルタエントリリクエスト1000であると判明する。この場合、ノードは、転置ブルームフィルタtbfpの特定先ブロック番号をエントリするステップS1107。具体的には、ノードは、フィルタエントリリクエスト1000の転置ブルームフィルタ項目で特定される転置ブルームフィルタtbfpにおいて、特定先ブロック番号が更新対象ビット位置であるとして、更新対象ビット位置のビットをONにする。このあと、ノードは、エントリした旨のリプライを、フィルタエントリリクエスト1000の送信元に返すステップS1108。これにより、ノードによるフィルタエントリ処理が終了する。なお、検索の場合ステップS1102:検索以降の処理手順S1109~S1115については後述する。<検索処理例>つぎに、検索処理について説明する。検索処理では、検索対象データが与えられると、階層型分割転置ブルームフィルタ群で絞り込むことで、検索対象データがノード群に存在するか否かを特定する処理である。以下、図12~図14を用いて説明する。図12~図14では、図1に示した階層型転置ブルームフィルタ群tBF1~tBF4を例にあげて説明する。また、検索処理を実行する検索元コンピュータは、管理サーバMまたはいずれかのクライアントC1~C3となるが、ここでは一例としてクライアントC1とする。図12~図14は、検索処理例を示す説明図である。図12~図14では、説明上、図1に示したように、全ビット幅s=64ビット、段数h=3段、転置前の第h段での分割数d=2とする。図12において、最上段である第3段のブルームフィルタ列BF3を構成するブルームフィルタのビット幅は、32=s/dh=64/21ビットである。このため、最上段である第3段の転置ブルームフィルタ列tBF3は、32=s/dh=64/21個の転置ブルームフィルタtbf3-1~tbf3-32により構成される。図13において、第2段の転置ブルームフィルタ列tBF2を構成するブルームフィルタのビット幅は、16=s/dh=64/22ビットである。このため、第2段の転置ブルームフィルタ列tBF2は、16=s/dh=64/22個の転置ブルームフィルタtbf2-1~tbf2-16により構成される。図14において、最下段である第1段のブルームフィルタ列BF1を構成するブルームフィルタのビット幅は、8=s/dh=64/23ビットである。このため、最下段である第1段の転置ブルームフィルタ列tBF1は、8=s/dh=64/23個の転置ブルームフィルタtbf1-1~tbf1-8により構成される。なお、図12~図14では、説明上、比較のため、転置ブルームフィルタ列tBF1~tBF3とともに、転置前のブルームフィルタ列BF1~BF3を併記しておく。まず、図12において、クライアントC1は、検索対象データDxについてのハッシュ関数H1~H3での3個のハッシュ値を、第3段の転置ブルームフィルタ数32で割り算したときの余り値2、5、22を求める。つぎに、クライアントC1は、フィルタリング対象となる転置ブルームフィルタを第3段の転置ブルームフィルタ列tBF3から特定する。具体的には、余り値と同一ビット位置余り値が0の場合は末尾位置となる転置ブルームフィルタtbf3-2,tbf3-5,tbf3-22を特定する。第3段の転置ブルームフィルタtbf3-1~tbf3-32は、32個であるため、全ビット幅s=64ビットを32個で割ることで、第3段の転置ブルームフィルタ1個あたりのビット幅は2ビットである。このことから、クライアントC1は、先頭から2番目の転置ブルームフィルタtbf3-2のインデックス範囲を、3ビット目~4ビット目であることを割り出す。これにより、クライアントC1は、対応テーブルTを参照することで、転置ブルームフィルタtbf3-2がノードN1に所属することが判明する。転置ブルームフィルタtbf3-5,tbf3-22についても同様に処理することで、転置ブルームフィルタtbf3-5はノードN1に所属することが判明し、転置ブルームフィルタtbf3-22は、ノードN3に所属することが判明する。そして、クライアントC1は、特定された転置ブルームフィルタtbf3-2,tbf3-5,tbf3-22が所属するノードN1,N3に対し、AND演算要求のリクエストを配信する。当該リクエストを受けたノードN1,N3は、特定された転置ブルームフィルタtbf3-2,tbf3-5,tbf3-22のAND演算を実行する。具体的には、たとえば、ノードN1は、所属する転置ブルームフィルタtbf3-2,tbf3-5のAND演算を実行する。図12の場合、AND結果r3-1は、r3-1={10}となる。ノードN1は、AND結果r3-1をクライアントC1に返す。同様に、ノードN3の特定された所属転置ブルームフィルタはtbf3-22だけなので、AND結果r3-3は、r3-3=tbf3-22={10}となる。ノードN3は、AND結果r3-3をクライアントC1に返す。このように、必要なノードのみAND演算が実行されるため、検索処理の効率化を図ることができる。また、クライアントC1では、ノードN1,N3から返ってきたAND結果r3-1,r3-3のAND演算を実行し、AND結果R3={10}を得る。クライアントC1は、AND結果R3に1が含まれていない場合は、いずれのデータブロックdb1~db8にも検索対象データDxが存在しないと判定する。一方、AND結果R3に1が含まれている場合、検索対象データDxを登録したかもしれないため、1つ下の段に移る。図12の場合、AND結果R3にはビット位置が1ビット目において1が存在するため、1つ下の第2段図13を参照に移行する。つぎに、図13において、第2段においても、まず、クライアントC1は、検索対象データDxについての3個のハッシュ値を、第2段の転置ブルームフィルタ数16で割り算したときの余り値6、8、13を求める。つぎに、クライアントC1は、フィルタリング対象となる転置ブルームフィルタを第2段の転置ブルームフィルタ列tBF2から特定する。具体的には、余り値と同一ビット位置余り値が0の場合は末尾位置となる転置ブルームフィルタtbf2-6,tbf2-8,tbf2-13を特定する。第2段の転置ブルームフィルタtbf2-1~tbf2-16は、16個であるため、全ビット幅s=64ビットを16個で割ることで、第2段の転置ブルームフィルタ1個あたりのビット幅は4ビットである。このことから、クライアントC1は、先頭から6番目の転置ブルームフィルタtbf2-6のインデックス範囲を、21ビット目~24ビット目であることを割り出す。これにより、クライアントC1は、対応テーブルTを参照することで、転置ブルームフィルタtbf2-6がノードN2に所属することが判明する。転置ブルームフィルタtbf2-8,tbf2-13についても同様に処理することで、転置ブルームフィルタtbf2-8はノードN2に所属することが判明し、転置ブルームフィルタtbf2-13は、ノードN4に所属することが判明する。そして、クライアントC1は、特定された転置ブルームフィルタtbf2-6,tbf2-8,tbf2-13が所属するノードN2,N4に対し、AND演算要求のリクエストを配信する。当該リクエストを受けたノードN2,N4は、特定された転置ブルームフィルタtbf2-6,tbf2-8,tbf2-13のAND演算を実行する。具体的には、たとえば、ノードN2は、所属する転置ブルームフィルタtbf2-6,tbf2-8のAND演算を実行する。図13の場合、AND結果r2-2は、r2-2={0100}となる。ノードN2は、AND結果r2-2をクライアントC1に返す。同様に、ノードN4の特定された所属転置ブルームフィルタはtbf2-13だけなので、AND結果r2-4は、r2-4=tbf2-13={0100}となる。ノードN4は、AND結果r2-4をクライアントC1に返す。このように、必要なノードのみAND演算が実行されるため、検索処理の効率化を図ることができる。また、クライアントC1では、ノードN2,N4から返ってきたAND結果r2-2,r2-4のAND演算を実行し、AND結果R2={0100}を得る。クライアントC1は、AND結果R2に1が含まれていない場合は、いずれのデータブロックdb1~db8にも検索対象データDxが存在しないと判定する。一方、AND結果R2に1が含まれている場合、検索対象データDxを登録したかもしれないため、1つ下の段に移る。図13の場合、AND結果R2にはビット位置が2ビット目において1が存在するため、1つ下の第1段図14を参照に移行する。つぎに、図14において、第1段においても、まず、クライアントC1は、検索対象データDxについての3個のハッシュ値を、第1段の転置ブルームフィルタ数8で割り算したときの余り値1、2、7を求める。つぎに、クライアントC1は、フィルタリング対象となる転置ブルームフィルタを第1段の転置ブルームフィルタ列tBF1から特定する。具体的には、余り値と同一ビット位置余り値が0の場合は末尾位置となる転置ブルームフィルタtbf1-1,tbf1-2,tbf1-7を特定する。第1段の転置ブルームフィルタtbf1-1~tbf1-8は、8個であるため、全ビット幅s=64ビットを8個で割ることで、第1段の転置ブルームフィルタ1個あたりのビット幅は8ビットである。このことから、クライアントC1は、先頭から1番目の転置ブルームフィルタtbf1-1のインデックス範囲を、1ビット目~8ビット目であることを割り出す。これにより、クライアントC1は、対応テーブルTを参照することで、転置ブルームフィルタtbf1-1がノードN1に所属することが判明する。転置ブルームフィルタtbf1-2,tbf1-7についても同様に処理することで、転置ブルームフィルタtbf1-2はノードN1に所属することが判明し、転置ブルームフィルタtbf1-7は、ノードN4に所属することが判明する。そして、クライアントC1は、特定された転置ブルームフィルタtbf1-1,tbf1-2,tbf1-7が所属するノードN1,N4に対し、AND演算要求のリクエストを配信する。当該リクエストを受けたノードN1,N4は、特定された転置ブルームフィルタtbf1-1,tbf1-2,tbf1-7のAND演算を実行する。具体的には、たとえば、ノードN1は、所属する転置ブルームフィルタtbf1-1,tbf1-2のAND演算を実行する。図14の場合、AND結果r1-1は、r1-1={00110010}となる。ノードN1は、AND結果r1-1をクライアントC1に返す。同様に、ノードN4の特定された所属転置ブルームフィルタはtbf1-7だけなので、AND結果r1-4は、r1-4=tbf1-7={00010010}となる。ノードN4は、AND結果r1-4をクライアントC1に返す。このように、必要なノードのみAND演算が実行されるため、検索処理の効率化を図ることができる。また、クライアントC1では、ノードN1,N4から返ってきたAND結果r1-1,r1-4のAND演算を実行し、AND結果R1={00010010}を得る。クライアントC1は、AND結果R1に1が含まれていない場合は、いずれのデータブロックdb1~db8にも検索対象データDxが存在しないと判定する。一方、AND結果R1に1が含まれている場合、検索対象データDxを登録したかもしれないため、1つ下の段に移る。図14の場合、AND結果R1にはビット位置が4ビット目および7ビット目において1が存在する。この場合、これ以上下の段は存在しないため、擬陽性により、AND結果R1={00010010}が1のビット位置4,7に対応するデータブロックdb4,db7に検索対象データDxが存在する可能性がある。データブロックdb4,db7のインデックス範囲は、第1段の転置ブルームフィルタtbf1-4,tbf1-7と同一である。したがって、クライアントC1は、先頭から4番目の転置ブルームフィルタtbf1-4のインデックス範囲を、25ビット目~32ビット目であることを割り出す。同様に、クライアントC1は、転置ブルームフィルタtbf1-7のインデックス範囲を、49ビット目~56ビット目であることを割り出す。これにより、データブロックdb4がノードN2に所属し、データブロックdb7がノードN4に所属することが判明する。したがって、クライアントC1は、ノードN2,N4に対しハッシュテーブル検索のリクエストを配信する。当該リクエストを受けたノードN2,N4は、それぞれ該当するハッシュテーブルHT4,HT7を検索して、リクエストに含まれているH1のハッシュ値に対応するデータを検索する。図14の例では、ノードN2のデータブロックdb4に検索対象データDxが記憶されているため、ノードN2は、検索対象データDxが存在する旨をクライアントC1に返す。たとえば、検索対象データDxが辞書の見出し語である場合は、検索対象データDxに関連付けて記憶されている解説文データも読み出して検索結果としてクライアントC1に返してもよい。一方、ノードN4のデータブロックdb7に検索対象データDxが記憶されていないため、ノードN4は、検索対象データDxが存在しない旨をクライアントC1に返す。なお、クライアントC1がデータブロックdb4について先にリクエストを送った場合、検索対象データDxが存在する旨の検索結果が得られるため、ノードN4に対してリクエストを送信しなくてもよい。これにより、検索処理の高速化を実現することができる。このような手順により、クライアントC1は、階層型分割転置ブルームフィルタ群を利用することで、より高速かつ広範囲で対象データを検索することができる。検索元コンピュータによるエントリ処理手順図15は、実施の形態にかかる検索元コンピュータによる検索処理手順例を示すフローチャート前半である。検索処理を実行するコンピュータたとえば、管理サーバMまたはクライアント。以下、単に検索元コンピュータ。は、検索対象データDxを待ち受けステップS1501:No、検索対象データDxが受け付けられた場合ステップS1501:Yes、検索元コンピュータは、検索対象データDxをk種類のハッシュ関数に与えてk個のハッシュ値を算出するステップS1502。そして、検索元コンピュータは、p=h、すなわち、段数pを最大段数hに設定しステップS1503、検索元コンピュータは、k個のハッシュ値をp段目の転置ブルームフィルタtbfpの配列数で除算して、k個の余り値を算出するステップS1504。そして、検索元コンピュータは、p段目の転置ブルームフィルタ列tBFpから、k個の余り値に対応するk個の転置ブルームフィルタtbfpを特定するステップS1505。そして、検索元コンピュータは、k個の転置ブルームフィルタtbfpが所属するノードを、対応テーブルTを参照することで特定するステップS1506。このあと、検索元コンピュータは、ステップS1506での特定先ノードに対し、AND演算要求のリクエストを配信しステップS1507、特定先ノードからのリプライを待ち受けるステップS1508。図16は、AND演算要求のリクエストおよびリプライのデータ構造例を示す説明図である。図16において、AはAND演算要求のリクエスト1601、Bはリプライ1602を示す。図16のデータ構造例は、図12~図14の検索処理例に対応している。AのAND演算要求のリクエスト1601のヘッダは、AND演算要求のリクエスト1601の送信元アドレスと宛先アドレスとを保持する。図16では、コンピュータに割り当てた符号C1,N1をアドレスの代わりに表記している。また、AのAND演算要求のリクエスト1601のペイロードは、種類項目、属性項目、特定先転置ブルームフィルタ項目に対しそれぞれの情報が保持されている。たとえば、種類項目には、検索、属性項目にはAND演算要求、特定先転置ブルームフィルタ項目には、特定された転置ブルームフィルタの識別子tbf3-2,tbf3-5が保持されている。特定された転置ブルームフィルタの識別子としては、特定された転置ブルームフィルタのビット位置を示すインデックス範囲が挙げられる。たとえば、tbf3-2の場合は、3ビット目~4ビット目となる。また、Bのリプライ1602のヘッダは、AND演算要求のリクエスト1601の送信元アドレスと宛先アドレスとが入れ替わった送信元アドレスと宛先アドレスとを保持する。Bのリプライ1602のペイロードには、特定先ノードN1でのAND結果r3-1={10}が保持されている。図15に戻り、リプライ1602が受信されていない場合ステップS1508:No、検索元コンピュータは、AND演算要求のリクエスト1601の送信から所定時間経過したか否かを判断するステップS1509。所定時間経過していない場合ステップS1509:No、ステップS1508に戻る。一方、所定時間経過した場合ステップS1509:Yes、検索元コンピュータは、エラー出力をおこなうステップS1510。たとえば、ディスプレイ408に、AND演算要求できなかった旨の表示をおこなう。一方、リプライ1602が受信された場合ステップS1508:Yes、検索元コンピュータは、各リプライ1602に含まれているAND結果についてAND演算を実行するステップS1511。たとえば、図16に示したように、ノードN1からのリプライ1602に含まれているAND結果r3-1とノードN3からのリプライ不図示に含まれているAND結果r3-3のAND演算を実行してAND結果R3を得る。このあと、図17のステップS1701に移行する。図17は、実施の形態にかかる検索元コンピュータによる検索処理手順例を示すフローチャート後半である。検索元コンピュータは、ステップS1511のAND演算のあと、当該AND結果の先頭ビットを対象ビットに設定するステップS1701。たとえば、上述のAND結果R3={10}の場合、先頭ビット1を対象ビットに設定する。つぎに、検索元コンピュータは、対象ビットがON=1であるか否かを判断するステップS1702。ONでない対象ビット=0場合ステップS1702:No、検索元コンピュータは、後続ビットへシフト可能か否かを判断するステップS1703。具体的には、対象ビットが末尾ビットであるか否かを判断する。上述のAND結果R3={10}の場合、対象ビットが先頭ビット1である場合、シフト可能となり、対象ビットが末尾ビット0である場合、シフト不可能と判断する。シフト可能である場合ステップS1703:Yes、検索元コンピュータは、対象ビットを1ビット末尾方向へシフトしステップS1704、ステップS1702に戻る。一方、ステップS1703においてシフト可能でない場合ステップS1703:No、検索元コンピュータは、検索結果陰性と判定し、その旨を出力するステップS1705。検索結果陰性である場合、検索対象データDxは、ノード群には存在しないデータであることがわかる。これにより、検索結果が陰性である場合の処理手順を終了する。一方、ステップS1702において、対象ビットがONであった場合ステップS1702:Yes、検索元コンピュータは、現在の段数pがp=1であるか否かを判断するステップS1706。p=1でない場合ステップS1706:No、pを1つデクリメントしてステップS1707、図15のステップS1504に戻る。これにより、第1段になるまで、ステップS1504~S1511、S1701~S1705が繰り返し実行ただし、図15および図17でENDになればその時点で終了されることになる。一方、p=1である場合ステップS1706:Yes、検索元コンピュータは、登録先ノード候補を特定するステップS1708。具体的には、たとえば、図14に示したように、クライアントC1が第1段でのAND結果R1においてステップS1702でONになったビット位置4で指定されるデータブロックdb4の所属ノードN2を、登録先ノード候補として特定する。より具体的には、データブロックdb4に対応する転置ブルームフィルタtbf1-4のインデックス範囲25ビット目~32ビット目から、対応テーブルTを参照することで、登録先ノード候補であるノードN2を割り出すことになる。そして、検索元コンピュータは、登録先ノード候補に、ハッシュテーブル検索のリクエストを送信しステップS1709、リプライを待ち受けるステップS1710。図18および図19は、ハッシュテーブル検索のリクエストおよびリプライのデータ構造例を示す説明図である。図18および図19において、Aはハッシュテーブル検索のリクエスト1801,1901、Bはリプライ1802,1902を示す。図18および図19のデータ構造例は、図12~図14の検索処理例に対応している。なお、図18は登録先ノード候補がノードN2の場合であり、図19は登録先ノード候補がノードN4の場合である。図18および図19において、Aのハッシュテーブル検索のリクエスト1801,1901のヘッダは、ハッシュテーブル検索のリクエスト1801,1901の送信元アドレスと宛先アドレスとを保持する。図18および図19では、コンピュータに割り当てた符号C1,N2,N4をアドレスの代わりに表記している。また、Aのハッシュテーブル検索のリクエスト1801,1901のペイロードは、種類項目、属性項目、特定先転置ブルームフィルタ項目に対しそれぞれの情報が保持されている。たとえば、種類項目には、検索、属性項目にはハッシュテーブル検索、ハッシュ値項目には、検索対象データDxのハッシュ関数H1でのハッシュ値x1が保持されている。また、Bのリプライ1802,1902のヘッダは、ハッシュテーブル検索のリクエスト1801,1901の送信元アドレスと宛先アドレスとが入れ替わった送信元アドレスと宛先アドレスとを保持する。Bのリプライ1802,1902のペイロードには、図18の場合は、登録先ノード候補であるノードN2での検索結果Dxあり、すなわち、陰性である旨が保持されており、図19の場合は、登録先ノード候補であるノードN4での検索結果Dxなしが保持されている。図17に戻り、リプライたとえば1802が受信されていない場合ステップS1710:No、検索元コンピュータは、ハッシュテーブル検索のリクエストたとえば1801の送信から所定時間経過したか否かを判断するステップS1711。所定時間経過していない場合ステップS1711:No、ステップS1710に戻る。一方、所定時間経過した場合ステップS1711:Yes、検索元コンピュータは、エラー出力をおこなうステップS1712。たとえば、ディスプレイ408に、ハッシュテーブル検索できなかった旨の表示をおこなう。一方、リプライが受信された場合ステップS1710:Yes、検索元コンピュータは、リプライに検索対象データDxが存在するか否かを判断するステップS1713。検索対象データDxが存在しない場合ステップS1713:No、ステップS1703に戻り、対象ビットがシフト可能か否かを判断することとなる。一方、検索対象データDxが存在する場合ステップS1713:Yes、検索元コンピュータは、検索結果陽性を出力するステップS1714。なお、検索元コンピュータは、必要に応じてより関連するデータを抽出して検索結果として出力する。これにより、検索結果が陰性である場合の処理手順を終了する。ノードによる検索処理手順つぎに、ノードによる検索処理手順について図11を用いて説明する。図11において、ノードは、リクエストの受信を待ち受けるステップS1101:No。リクエストが受信された場合ステップS1101:Yes、ノードは、リクエストの種類を特定するステップS1102。具体的には、リクエスト内の種類項目が登録または検索であるかを特定する。検索である場合ステップS1102:検索、ノードは、属性を特定するステップS1109。具体的には、リクエスト内の属性項目がAND演算要求またはハッシュテーブル検索であるかを特定する。AND演算要求の場合ステップS1109:AND演算要求、受信したリクエストがAND演算要求のリクエスト1601であると判明する。この場合、ノードは、AND演算要求のリクエスト1601の転置ブルームフィルタ項目内の転置ブルームフィルタの識別子を抽出するステップS1110。たとえば、図16のAの場合、転置ブルームフィルタtbf3-2,tbf3-5のインデックス範囲をAND演算要求のリクエスト1601から抽出する。そして、ノードは、抽出されたインデックス範囲から所属する転置ブルームフィルタを特定し、AND演算を実行するステップS1111。上記の例では、転置ブルームフィルタtbf3-2,tbf3-5が特定されるため、ノードN1では、tbf3-2={10}と,tbf3-5={11}のAND演算を実行し、AND結果r3-1={10}を得る。このあと、ノードは、ステップS1111でのAND演算によるAND結果を含むリプライを、検索元コンピュータに送信してステップS1112、ノードによる検索処理を終了する。上記の例では、図16のBに示したように、ノードN1は、AND結果r3-1={10}を含むリプライ1602を返すことになる。また、ステップS1109において、属性がハッシュテーブル検索である場合ステップS1109:ハッシュテーブル検索、受信したリクエストがハッシュテーブル検索のリクエスト1801,1901であると判明する。この場合、ノードは、ハッシュテーブル検索のリクエスト1801,1901に含まれているハッシュ関数による検索対象データのハッシュ値を、ハッシュテーブル検索のリクエスト1801,1901から抽出するステップS1113。たとえば、図18のAの場合、ハッシュテーブル検索のリクエスト1801,1901に含まれているハッシュ関数H1による検索対象データDxのハッシュ値x1を、ハッシュテーブル検索のリクエスト1801,1901から抽出する。そして、ノードは、保持しているハッシュテーブルを参照して、抽出されたハッシュ値に関連付けられているデータを検索しステップS1114、検索結果をリプライ1802,1902として、検索元コンピュータに送信するステップS1115。たとえば、上記の例では、図18のBに示したように、ノードN1は、検索結果陰性、すなわち、検索対象データDxを含むリプライ1802を返すことになる。これにより、ノードによる検索処理を終了する。なお、図11において、リクエストの属性がAND演算要求の場合、ステップS1111において、転置ブルームフィルタtbfpが複数あると、ノードがAND演算を実行する内容としたが、各転置ブルームフィルタtbfpのビット列をそのままリプライとして検索元コンピュータに返してもよい。これにより、ノードでAND演算を実行する必要がなくなり、ノードの負荷低減を図ることができる。このように、上述した検索処理では、階層型分割転置ブルームフィルタ群を利用することで、より高速かつ広範囲で対象データを検索することができる。以上説明したように、本実施の形態によれば、ブルームフィルタ列BFpを転置して転置ブルームフィルタ列tBFpとすることで、メモリアクセスが低減され、検索速度が高速化するという効果を奏する。特に、階層型転置ブルームフィルタtBFとすることで、段ごとのメモリアクセスが低減されるため、より高速に検索をおこなうことができる。また、階層型転置ブルームフィルタtBFをビット幅方向に分割して、複数のノードに割り当てているため、管理可能なデータ量の増大化を図ることができる。また、階層型分割転置ブルームフィルタ群を利用することで、より高速かつ広範囲で対象データを検索することができる。また、対応テーブルTを参照することで、検索元コンピュータでは、第p段の転置ブルームフィルタを保持するノードやデータブロックを有するノードを特定することができる。したがって、ノード群以外のコンピュータからでもノード群に対し検索をおこなうことができる。また、特定先ノードにおいて、第p段の転置ブルームフィルタが複数存在する場合、AND演算をおこなってAND結果を検索元コンピュータにリプライとして返している。このように、ノードにおいて複数の転置ブルームフィルタをAND演算することで、AND結果という1個のビット列に圧縮できるため、検索元コンピュータでの演算負荷の低減化を図ることができる。これに対し、特定先ノードにおいて、第p段の転置ブルームフィルタが複数存在する場合、AND演算をおこなわずに、複数の転置ブルームフィルタのビット列の各々をリプライとして検索元コンピュータに返してもよい。この場合は、ノードの計算負荷の低減化を図ることができる。また、上述した各フローチャートで示したステップは、具体的には、たとえば、図4に示したROM402、RAM403、磁気ディスク405、光ディスク407などの記憶装置に記憶された検索プログラムをCPU401に実行させた処理である。また、実行させた実行結果は、その都度、記憶装置に書き込まれ、他の処理で必要に応じて読み出される。これにより、本実施の形態で説明した検索方法は、検索プログラムをパーソナルコンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本検索プログラムは、ハードディスク、フレキシブルディスク、CD-ROM、MO、DVD等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行されることになる。上述した実施の形態に関し、さらに以下の付記を開示する。付記1段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能なコンピュータに、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換し、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定し、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得し、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断し、同一であると判断された場合、第p段が第1段であるか否かを判断し、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する、処理を実行させることを特徴とする検索プログラム。付記2前記ビット幅sのうち前記所定ビット幅に応じた前記分割データ構造のビット範囲と前記ノード群の各ノードとを対応付けた対応テーブルを参照することで、特定された前記第p段の転置ブルームフィルタを保持するノードを特定する処理を前記コンピュータに実行させ、前記第p段の転置ブルームフィルタを取得する処理では、特定先ノードから、特定された前記第p段の転置ブルームフィルタを取得することを特徴とする付記1に記載の検索プログラム。付記3前記第p段の転置ブルームフィルタを取得する処理では、特定された前記第p段の転置ブルームフィルタが複数存在する特定先ノードから前記第p段の転置ブルームフィルタの論理積を取得し、擬陽性を示すビットのビット位置が同一であるか否かを判断する処理では、取得された論理積に基づいて、前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断することを特徴とする付記2に記載の検索プログラム。付記4第p段が第1段であると判断された場合、前記対応テーブルを参照することで、前記特定のデータブロックを有するノードを特定する処理を、前記コンピュータに実行させることを特徴とする付記1~3のいずれか一つに記載の検索プログラム。付記5第p段が第1段ではないと判断された場合、第p段の1つ下の段をあらたに第p段として前記コンピュータに実行させることを特徴とする付記1~4のいずれか一つに記載の検索プログラム。付記6段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群のいずれかのノードに、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信し、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信し、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信し、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索し、検索結果を前記コンピュータに送信する、処理を実行させることを特徴とする検索プログラム。付記7段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能なコンピュータが、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換し、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定し、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得し、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断し、同一であると判断された場合、第p段が第1段であるか否かを判断し、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する、処理を実行することを特徴とする検索方法。付記8段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群のいずれかのノードが、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信し、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信し、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信し、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索し、検索結果を前記コンピュータに送信する、処理を実行することを特徴とする検索方法。付記9段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群にアクセス可能な検索装置であって、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データを、前記転置ブルームフィルタの配列位置をあらわす位置情報に変換する処理部と、前記第p段の転置ブルームフィルタ列の中から、前記位置情報に対応する前記第p段の転置ブルームフィルタを位置情報ごとに特定する処理部と、特定された前記第p段の転置ブルームフィルタを保持するノードから、特定された前記第p段の転置ブルームフィルタを取得する処理部と、取得された前記第p段の転置ブルームフィルタで擬陽性を示すビットのビット位置が同一であるか否かを判断する処理部と、同一であると判断された場合、第p段が第1段であるか否かを判断する処理部と、第1段であると判断された場合、擬陽性を示すビットのビット位置に応じた特定のデータブロックを有するノードから、前記特定のデータブロック内での前記検索対象データの存否を示す検索結果を取得する処理部と、を備えることを特徴とする検索装置。付記10段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群のいずれかのノードであって、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信する処理部と、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信する処理部と、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信する処理部と、前記いずれかのノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索する処理部と、検索結果を前記コンピュータに送信する処理部と、を備えることを特徴とするノード。付記11段数h、ビット幅s、擬陽性または陰性を示すビットが配列された第h段の分割数d、第p1≦p≦h段のブルームフィルタのビット幅m=s/dh、第p段のブルームフィルタの配列数n=dhである階層型ブルームフィルタを、段ごとにブルームフィルタ列を構成する各ブルームフィルタ内の同一位置のビットどうしでまとめることで転置した階層型転置ブルームフィルタと、前記階層型ブルームフィルタの第1段のブルームフィルタ列に対応するデータブロック集合と、からなるデータ構造が、所定ビット幅で分割されており、前記所定ビット幅で分割された各分割データ構造を保持するノード群で構成される検索システムであって、前記ノード群内の各ノードが、前記ノード群にアクセス可能なコンピュータから、複数種類のハッシュ関数に基づいて、ハッシュ関数ごとに、検索対象データから変換された前記転置ブルームフィルタの配列位置をあらわす位置情報を受信する処理部と、前記位置情報が受信された場合、前記第p段の転置ブルームフィルタ列の中から位置情報ごとに特定された、前記位置情報に対応する前記第p段の転置ブルームフィルタを前記コンピュータに送信する処理部と、前記コンピュータから前記複数種類のハッシュ関数の中の特定のハッシュ関数に前記検索対象データを与えたときのハッシュ値を受信する処理部と、自ノードに対応するデータブロックに記憶されているデータと当該データを前記特定のハッシュ関数に与えたときのハッシュ値とを関連付けたハッシュテーブルを参照することにより、受信されたハッシュ値に関連付けられているデータを、前記いずれかのノードに対応するデータブロックの中から検索する処理部と、検索結果を前記コンピュータに送信する処理部と、を備えることを特徴とする検索システム。"