(57)【特許請求の範囲】
【請求項１】
テキスト文書の集合Ｄを検索するための二次元線形スケーラブル・パラレル・アーキテクチャを有する検索エンジンであって、文書を複数のパーティションｄ１、ｄ２、．．．ｄｎに分割することが可能であり、文書集合Ｄをテキストフィルタシステムで前処理して前処理文書集合Ｄｐに前処理パーティションｄｐ１、ｄｐ２．．．ｄｐｎを対応させ、文書集合ＤからインデックスＩを生成して以前に前処理されたパーティションｄｐ１、ｄｐ２、．．．ｄｐｎのそれぞれに対応するインデックスｉ１、ｉ２、．．．ｉｎを得ることが可能であり、前処理パーティションｄｐｋとその対応インデックスｉｋの両方を含むパーティション依存データセットｄｐ、ｋを用いて文書集合Ｄのパーティションｄの検索が実行され（ｌ≦ｋ≦ｎ）、ネットワークで接続された複数群のノード（Ｎ）を形成するデータ処理ユニットを含む検索エンジンにおいて、
第１ノード群がａ個のディスパッチノード
0003586429.tif 000068
を含み、第２ノード群がｂ個の検索ノード
0003586429.tif 000069
を含み、第３ノード群がｇ個のインデックスノード
0003586429.tif 000070
を含み、任意の第４ノード群がｅ個のアクイジションノード
0003586429.tif 000071
を含み、
ネットワーク内においてディスパッチノード
0003586429.tif 000072
がマルチレベル構成で接続され、
ネットワーク内において検索ノード
0003586429.tif 000073
がディスパッチノード
0003586429.tif 000074
とインデックスノード
0003586429.tif 000075
の間に並列接続されるν個の列（Ｓ）にグループ分けされ、
検索クエリーおよび検索応答を処理するようにディスパッチノード
0003586429.tif 000076
が構成され、すべての検索ノード
0003586429.tif 000077
に更に検索クエリーが送られ、アクイジションノード
0003586429.tif 000078
が存在しない場合にはディスパッチノード
0003586429.tif 000079
に検索応答が返され、検索応答がそこで最終検索結果にまとめられ、
各検索ノード
0003586429.tif 000080
が検索ソフトウェアを保持するように構成され、
検索ソフトウェアにインデックスｉを定常的に供給すると共に、各々が検索プロセッサモジュールを含むノード
0003586429.tif 000081
にパーティション依存データセットｄｐ，ｋを随意に供給するようにインデックスノード
0003586429.tif 000082
が構成され、
アクイジションノード
0003586429.tif 000083
が存在する場合、それらはディスパッチノード
0003586429.tif 000084
と同様にネットワーク内においてマルチレベル構成で接続され、検索クエリーに対する応答を収集してその最終結果を出力することによりディスパッチノードのタスクを軽減するように構成され、
データ量のスケーリングを行うために検索ノード列（Ｓ）の数νがパーティションｄの数ｎに応じてスケーリングされ、
性能スケーリングを行うために各検索ノード列
0003586429.tif 000085
における検索ノード
0003586429.tif 000086
の数ｂ／νが推定トラフィック負荷または予測トラフィック負荷に応じてスケーリングされ、
0003586429.tif 000087
それにより、パーティション依存データセットｄｐ，ｋの１つと、各々が同等のパーティション依存データセットｄｐ，ｋを保持する検索ノード列
0003586429.tif 000088
における全検索ノード
0003586429.tif 000089
とを保持する各検索ノード列（Ｓ）によって、あらゆる場合に文書集合Ｄの検索が行われることを特徴とする前記検索エンジン。
【請求項２】
ネットワークにおけるディスパッチノード
0003586429.tif 000090
および随意アクイジションノード
0003586429.tif 000091
のマルチレベル構成が階層状木構造で構成されることを特徴とする請求項１記載の検索エンジン。
【請求項３】
随意アクイジションノード
0003586429.tif 000092
のマルチレベル構成がディスパッチノード
0003586429.tif 000093
のマルチレベル構成の鏡像であることを特徴とする請求項２記載の検索エンジン。
【請求項４】
階層状木構造が２進木構造であることを特徴とする請求項２記載の検索エンジン。
【請求項５】
各検索ノード
0003586429.tif 000094
に検索ソフトウェアモジュール（ＳＷ）が含まれることを特徴とする請求項１記載の検索エンジン。
【請求項６】
少なくともいくつかの検索ノード
0003586429.tif 000095
に少なくとも１つの専用検索プロセッサモジュール（Ｍ）が含まれ、それぞれｑ個の検索クエリーを並列処理するための１つ以上の専用検索プロセッサチップ（ＰＭＣ）を用いて専用検索プロセッサモジュール（Ｍ）が実現されることを特徴とする請求項５記載の検索エンジン。
【請求項７】
検索プロセッサモジュール（Ｍ）内で専用検索プロセッサチップ（ＰＭＣ）がｙ個のプロセッサグループ（Ｇ）に分けて設けられ、各プロセッサグループ（Ｇ）にはｚ個の検索プロセッサチップ（ＰＭＣ）が含まれ、各プロセッサグループ（Ｇ）がそれぞれに割当てられたメモリ（ＲＡＭ）からデータを受け取るように接続されることを特徴とする請求項６記載の検索エンジン。
【請求項８】
データ量スケーリング時におけるパーティションｄの増設には、それに対応するディスパッチノード
0003586429.tif 000096
の増設と、場合によってはアクイジションノード数
0003586429.tif 000097
や随意のインデックスノード
0003586429.tif 000098
の増設が伴うことを特徴とする請求項１記載の検索エンジン。
【請求項９】
各検索ノード
0003586429.tif 000099
には検索ソフトウェアモジュール（ＳＷ）のみが含まれ、パーティション依存データセットにはインデックスｉｋのみが含まれることを特徴とする請求項１記載の検索エンジン。
【請求項１０】
少なくとも１つの検索ノードには、検索ソフトウェアモジュール（ＳＷ）と少なくとも１つの専用検索プロセッサモジュール（Ｍ）が含まれ、パーティション依存データセットｄｐ、ｋは前処理されたパーティションｄｐと対応するインデックスｉｋを含むことを特徴とする請求項１記載の検索エンジン。
【請求項１１】
データ通信網で接続された１つ以上のワークステーションに個別のノードセット
0003586429.tif 000100
がそれぞれ設けられることを特徴とする請求項１記載の検索エンジン。
【発明の詳細な説明】
【０００１】
本発明は一群のテキスト文書Ｄを検索するための二次元線形スケーラブル・パラレル・アーキテクチャを有する検索エンジンに関するものである。文書は複数のパーティションｄ１、ｄ２．．．ｄｎに分割することができる。一群の文書Ｄはテキストフィルタシステムにおいて前処理され、前処理された文書群Ｄｐはパーティションｄｐ１、ｄｐ２．．．ｄｐｎに対応する。文書群ＤからインデックスＩを生成することが可能であり、あらかじめ前処理されたパーティションｄｐ１、ｄｐ２．．．ｄｐｎごとに対応のインデックスｉ１、ｉ２．．．ｉｎが得られる。パーティション依存のデータセットｄｐｋを用いて、文書群Ｄのパーティションｄが検索される。検索エンジンはネットワーク内で接続される一連のノードを含むデータ処理ユニットを有する。
【０００２】
従来技術によるほとんどの検索エンジンは、大規模なデータセットを取り扱い、検索用に強力なコンピュータを使用する。しかし、検索はパーティショニング可能な（ｐａｒｔｉｔｉｏｎａｂｌｅ）データ処理問題であり、この事実は検索問題を多くの特定のクエリーに分割するときに利用可能であり、ネットワークで並列接続された相当数のプロセッサ上で各クエリーを同時処理することができる。特に、検索は２進パーティショニング可能なデータ処理問題と見なすことができるから、例えば、米国特許Ｎｏ．４８６０２０１（Ｓｔｏｌｆｏ  ＆  ａｌ）および国際特許出願ＰＣＴ／Ｎ０９９／００３０８で開示され、引用により本出願に包含され本出願人に帰属するマルチプロセッサ・アーキテクチャを構築するために２進木ネットワークが使用される。本出願人は正規テキスト文書で検索するための独占（ｐｒｏｐｒｉｅｔａｒｙ）技術を開発した。ｉ．ａ．これらの技術は、引用により本出願に包含され本出願人に帰属する国際特許出願ＰＣＴ／Ｎ０９９／００２３３に記述されている検索システムおよび検索方法に基づいている。検索システムは、本発明による検索エンジンに使用可能な効率的なコア検索アルゴリズムに基づいている。
【０００３】
しかし、検索する文書の増加にみあう十分な対応が益々重要になっており、また、トラフィック負荷の増加、すなわち検索システムによって毎秒処理されるクエリー数の増加に対処することが益々重要になってきた。これは、プロセッサレベルで多数のクエリーを同時処理する能力とは別に、望ましくは二次元線形スケーラビリティ、つまりデータ量と、性能すなわち非常に多数の量のクエリーを毎秒処理する能力とに関する線形スケーラビリティを考慮したアーキテクチャで検索エンジンを実現する必要性を意味する。ワールドワイドウエブの発達によりインターネット上の文書数およびユーザ数が共に著しいスピードで増加している状況では、検索エンジンのアーキテクチャにおけるスケーラビリティ問題は非常に重要になるだろう。
【０００４】
従来技術によるインターネット用の検索エンジンのソリューションでも、ある程度のスケーリングが可能であるが、ほとんどの場合、データ量あるいはデータトラフィックの増加にしたがって検索エンジンシステム費用が増加するような手段が用いられる。システムコストがデータ量またはトラフィックの２乗に比例するようなことが頻繁に起こり、その場合、データ量が２倍になると費用は４倍になる。さらに、現状では主要なインターネット検索エンジンはすべて、非常に高価なサーバ技術に基づいており、演算能力を酷使するようなアプローチ（ｂｒｕｔｅ  ｃｏｍｐｕｔｉｎｇ  ｆｏｒｃｅ−ａｐｐｒｏａｃｈ）が使われてサーバのターンアラウンドが長くなるなどの欠点が伴うことが多く、フォールトトレランス用に特別なハードウェアが要求される。システム費用は、例えば検索エンジン・ソリューションの実施に要するハードウェア量あるいはシステムに掛かる実際の費用として算出することができる。
【０００５】
したがって、本発明の目的は、同時に多数のユーザによって大量のデータが能率的かつ高速に検索できるように、検索エンジンにマルチレベルのデータと機能的平行性を施すことである。
【０００６】
特に、本発明の目的は、マルチレベルのデータと機能的平行性を備えた検索エンジンを実現するパラレルアーキテクチャーを提供することである。
【０００７】
更に、本発明の目的は、２つの次元、すなわちデータ量と、クエリーレートで表される性能との両方において、直線的にスケーラブルなパラレルアーキテクチャーを提供することである。
【０００８】
本発明による検索エンジンにより、上記目的とその他の特徴および利点が得られる。この検索エンジンの特徴は、第１ノード群がａ個のディスパッチノードを含み、第２ノード群がｂ個の検索ノードを含み、第３ノード群がｇ個のインデックスノードを含み、任意の第４ノード群がｅ個のアクイジションノードを含み、ネットワーク内においてディスパッチノードがマルチレベル構成で接続され、ネットワーク内において検索ノードがディスパッチノードとインデックスノードの間に並列接続される複数列にグループ分けされ、検索クエリーおよび検索応答を処理するようにディスパッチノードが構成され、すべての検索ノードに更に検索クエリーが送られ、アクイジションノードが存在しない場合にはディスパッチノードに検索応答が返され、検索応答がそこで最終検索結果にまとめられ、各検索ノードが検索ソフトウェアを保持するように構成され、検索ソフトウェアにインデックスｉを定常的に供給すると共に、検索プロセッサモジュールを含むノードにパーティション依存データセットｄｐ，ｋを随意に供給するようにインデックスノードが構成され、アクイジションノードが存在する場合、それらはディスパッチノードと同様にネットワーク内においてマルチレベル構成で接続され、検索クエリーに対する応答を収集してその最終結果を出力することによりディスパッチノードのタスクを軽減するように構成され、データ量のスケーリングを行うために検索ノード列の数νがパーティションｄの数ｎに応じてスケーリングされ、性能スケーリングを行うために各検索ノード列における検索ノード数が推定トラフィック負荷または予測トラフィック負荷に応じてスケーリングされ、それにより、パーティション依存データセットｄｐ，ｋの１つを保持する単一の検索ノードと、同等のパーティション依存データセットｄｐ，ｋを保持する検索ノード列における全検索ノードとによって、あらゆる場合に文書集合Ｄの検索が行われる。
【０００９】
本発明によれば、ネットワークにおいてディスパッチノードおよび随意アクイジションノードのマルチレベル構成が階層状木構造で構成され、随意アクイジションノードのマルチレベル構成がディスパッチノードのマルチレベル構成の鏡像であり、階層状木構造が２進木構造であることがそれぞれ好ましい。
【００１０】
本発明によれば、それぞれの検索ノードに検索ソフトウェアモジュールが含まれることが望ましい。
【００１１】
さらに、発明によれば、少なくともいくつかの検索ノードに少なくとも１つの専用検索プロセッサモジュールが含まれ、それぞれの専用検索プロセッサモジュールは、複数の検索クエリーを並列処理する１つ以上の専用プロセッサチップを用いて実現される。これに関連して、検索プロセッサモジュール内で専用検索プロセッサチップがｙ個のプロセッサグループに分けて設けられ、各プロセッサグループにはｚ個の検索プロセッサチップが含まれ、各プロセッサグループがそれぞれに割当てられたメモリからデータを受け取るように接続される。
【００１２】
本発明によれば、パーティション数の増設には、それに対応するディスパッチノードの増設が伴うことが好ましく、場合によってはアクイジションノードの増設、あるいは随意インデックスノードの増設を伴うこともある。
【００１４】
最後に、本発明によれば、データ通信ネットワークで接続される１つ以上のワークステーションによって個別のノード群がそれぞれ形成されることが好ましい。
【００１５】
以下に、非限定的な代表的実施例と付図に基づいて本発明の検索エンジンに関する説明を行う。
【００１６】
互いに独立した文書の集合を検索することは高度なパラレルタスクである。以下に述べるように、本発明による検索エンジンは異なるレベルにおけるパラレル関係を用いる。
【００１７】
本発明による検索エンジンは文書集合Ｄを検索する。文書はｎ個のパーティションｄ１、ｄ２．．．ｄｎに分割することができる。例えば、ここに引用として包含される本出願人による国際特許出願Ｎｏ．ＰＣＴ／Ｎ０９９／００３４４で開示されたパターンマッチングチップ（ＰＭＣ）のような専用ハードウェアを実装したハードウェアテキストフィルタリングシステムで処理できるように、各文書集合Ｄ、または文書集合のパーティションｄを前処理することができる。前処理された文書集合はＤｐで表され、それに対応する前処理文書集合パーティションｄｐはｄｐ１、ｄｐ２．．．ｄｐｎで表される。
【００１８】
ソフトウェアベースの検索システムは、文書集合から生成されるインデックスを必要とする。このインデックスはＩで表され、文書集合パーティションｄｐ１、ｄｐ２、．．．ｄｐｎに対応するインデックスはｉ１、ｉ２、．．．ｉｎで表される。
【００１９】
文書集合Ｄのパーティションｄを検索するのに必要なデータセットは、パーティション要求またはパーティション依存のデータセットと呼ばれる。ソフトウェアのみのシステム（ＳＷシステム）の場合、データセットはインデックスｉｋであり、ハードウェア（ＳＷ／ＨＷシステム）を含むシステムの場合、データセットには、対応するインデックスｉｋをもつ前処理済み文書集合パーティションｄｐ，ｋも含まれる。ただし、１≦ｋ≦ｎとする。
【００２０】
実質的にソフトウェア的に行われるパーティショニングと前処理動作を図式的表すと、＊（Ｄ）→＊（ｄ１、．．．ｄｎ）→＊（ｄｐ１、．．．ｄｐｎ）→ｄｐｋとなる。ただし、＊（Ｄ）は入力Ｄに対する演算、＊（ｄ１、．．．ｄｎ）はｄ１、．．．ｄｎに対するフィルタ動作、例えばインデックシング（ｉｎｄｅｘｉｎｇ）であり、ｄｐｋはパーティション依存のデータセットであり、ＳＷシステムの場合は単にインデックスｉｋとなる。ただし、１≦ｋ≦ｎとする。
【００２１】
検索エンジンは高性能インターコネクトバスを介して接続されるワークステーションのクラスタ上に設けられる。図示されていないが、このワークステーションは検索システム（検索サーバ）のサーバを構成する。ワークステーションは検索サーバのノードを構成する。これらノードは、発明にしたがって以下のように構成され、互いに異なるタスクを実行する。
【００２２】
各ノードはワークステーション間に分散された仮想ノードとみなすことができるが、ＳＷ／ＨＷ検索エンジンでは、ハードウェアベースの検索をサポートするために、一部のワークステーションに専用の検索処理ハードウェアを物理的に設ける必要がある。その場合も、検索ノードソフトウェアを分散させることは可能である。また、ＳＷ／ＨＷ検索エンジンの一部の検索ノードを、ソフトウェアのみを含むものとして１つ以上のワークステーション上に任意に分散させることが可能である。
【００２３】
−ディスパッチノード
0003586429.tif 000002
は入力クエリーを処理し、すべての検索ノードにクエリーを送る。ディスパッチノードは、応答、すなわちクエリーに対する検索結果を収集するアクイジッションノードとして構成することもできる。アクイジションモードのディスパッチノードは応答を受けると、検索結果を最終結果にまとめる。
【００２４】
−検索ノード
0003586429.tif 000003
はデータセットｄｐ全体の一部を保持する。検索ノードは専用検索ソフトウェアと、ハードウェア検索用の複数の上記ＰＭＣモジュールとを有する。
【００２５】
−インデックスノード
0003586429.tif 000004
は複数の検索ノードにおける専用検索ソフトウェア用インデックスの生成を受持つ。インデックスノード
0003586429.tif 000005
は、ＰＭＣモジュールのために生データのフィルタ処理と前処理も行う。
【００２６】
−アクイジションノード
0003586429.tif 000006
は、応答を収集して検索結果を最終結果にまとめるために任意に設けることが可能であり、その場合は当然、ディスパッチノード
0003586429.tif 000007
はアクイジションタスクから開放される。
【００２７】
本発明による検索エンジンの第１の実施例が図１に示されており、検索ノード
0003586429.tif 000008
は列またはグループＳの状態で設けられ、ディスパッチノード
0003586429.tif 000009
とインデックスノード
0003586429.tif 000010
の間に並列接続される。ディスパッチノード
0003586429.tif 000011
の構成は概略的に図示されているが、実際にはマルチレベル階層構成になる。
【００２８】
本発明による検索エンジンの第２の実施例が図２に示されており、ディスパッチノードの場合と同様の構成でアクイジションノード
0003586429.tif 000012
が設けられ、ディスパッチノードのアクイジションタスクは開放される。
【００２９】
特異なワークステーションでは特定タイプのノードだけを使用するかもしれないが、１つ以上のタイプのノードを使用することは可能である。言い換えれば、ワークステーションのクラスタ上に異なるタイプのノードを分散させることが可能である。その場合、図１および図２に示されるアーキテクチャはクラスタ全体によって構成され、したがって、これらの図はワークステーションも、インターコネクトバスも示してない。
【００３０】
ここでノードについて詳細に説明するが、まず本発明による検索エンジンの主要部である検索ノードから始める。
【００３１】
上述のように、検索ノード
0003586429.tif 000013
はデータセットｄｐの一部を保持する。検索ノードは図３で示されるように、ソフトウェア検索エンジンＳＷの他に、任意に複数のＰＭＣモジュールＭを有する。以下に詳細に説明するとおり、検索ノード
0003586429.tif 000014
のデータセットはインデックスノード
0003586429.tif 000015
で生成される。
【００３２】
図３に示されるように、非常に高速な検索を行うために検索ノードにｘ個のＰＭＣモジュールＭを設けることができる。図４に示されるように、各ＰＭＣモジュールＭには、ｚ個のＰＭＣからなるｙ個のグループＧが含まれ、各グループＧは単一のメモリチップＲＡＭからデータを受け取る。モジュールＭは一般的に個別の回路基板である。図５で図式的に示されるように、各チップＰＭＣはｑ個の同時クエリーを処理することができる。
【００３３】
パターンマッチングチップＰＭＣは毎秒ｔｃバイトのデータ量を処理することができる。メモリモジュールからパターンマッチングチップＰＭＣへ毎秒ｔｙバイトを送ることができると仮定すれば、与えられた時間ｔでＰＭＣが完全に検索し得るデータ量はＴｃバイト、すなわちＴｃ＝ｍｉｎ｛ｔｃ，ｔｙ｝ｔである。
【００３４】
図４に示すように、パターンマッチングチップＰＭＣはｚ個のチップＰＭＣからなるｙ個のグループＧを含むモジュールＭに配置され、各グループＧはメモリサイズＴｃの単一のメモリチップＲＡＭからデータを受け取る。このモジュールで検索可能なデータ総量は、ｚｑ個の異なるクエリーのときＴｙ＝Ｔｃである。
【００３５】
検索ノード
0003586429.tif 000016
にｘ個のモジュールＭが設けられた場合、各ＰＭＣモジュールは同じデータを検索せず、同時発生クエリー数はｚｑであるから、これらのＰＭＣモジュールＭはＴｒ＝Ｔｙ・ｘ＝ｍｉｎ｛ｔｃ，ｔｙ｝ｔｘｙに等しいデータ量を完全に検索することができる。
【００３６】
したがって、検索ノードにおけるＰＭＣモジュールの総クエリーレートは次式で表すことができる。
0003586429.tif 000017
ただし、Ｔｒはノードの総データ量を表す。これで、検索ノードの性能を算出することができる。
【００３７】
ＰＭＣモジュールＭ（あるいは同等のハードウェア）のクエリーレートをｒＨＷ、検索ノード
0003586429.tif 000018
における検索ソフトウェアのクエリーレートをｒＳＷと仮定すれば、検索ノードＮｓの合計クエリーレート
0003586429.tif 000019
は次式で表すことができる。
0003586429.tif 000020
ただし、φＳＷはソフトウェアが実行するクエリーｑの割合を表す。φＳＷの実際の値は、実行時（ランタイム）に統計モデルにより動的に更新される。
【００３８】
ディスパッチノード
0003586429.tif 000021
はすべてのクエリーを受け取り、それらをすべての検索ノード
0003586429.tif 000022
に再送する。異なる検索ノード
0003586429.tif 000023
からの応答はまとめられ、ディスパッチノード
0003586429.tif 000024
がアクイジションノードとして機能する場合は、完全な応答が返される。
【００３９】
インデックスノード
0003586429.tif 000025
は文書を収集し、それぞれ異なる検索ノード
0003586429.tif 000026
における検索ソフトウェアのために暫定（ｐｒｅｂｕｉｌｔ）インデックスを作成する。したがって、検索ノード
0003586429.tif 000027
に適切なインデックスソフトウェアを持たせれば、検索ノード
0003586429.tif 000028
にインデックスノード
0003586429.tif 000029
を組み入れることができる。ハードウェアは生データの全体集合をスキャニングすることを基本とするが、インデックスノード
0003586429.tif 000030
において何らかの前処理およびフィルタリングを生データに施すことができる。
【００４０】
インターコネクトとデータトラフィックの関連において、下記事項に基づいていくつかの一般的な考察を行うことができる。
【００４１】
異なるタイプのインターコネクトを用いてノード間を接続することができる。ローエンドシステムでは、例えば通常の１００Ｍｂｉｔファストイーサネット（登録商標）でトラフィックを処理する。
【００４２】
ノード間インターコネクトのトラフィックは次の２つのカテゴリに分割することができる。
【００４３】
−クエリートラフィック、すなわちディスパッチノード
0003586429.tif 000031
と検索ノード
0003586429.tif 000032
の間のトラフィック。このトラフィックは検索実行中に常時発生する。クエリートラフィックの特徴は、中程度以下のデータ量と高頻度である。
【００４４】
−データトラフィック、すなわちインデックスノード
0003586429.tif 000033
と検索ノード
0003586429.tif 000034
の間のトラフィック。データトラフィックの特徴は高データ量と低頻度（通常１日あたり１バッチ）である。
【００４５】
典型的なクエリーは、ディスパッチノード
0003586429.tif 000035
から検索ノード
0003586429.tif 000036
にクエリーストリングを運ぶ。検索ノード
0003586429.tif 000037
は、クエリーにマッチする一連の文書を応答として送る。また、
0003586429.tif 000038
から検索ノードに対して、文書のＵＲＬストリングを要求することが可能であるが、この文脈において重要なことではない。
【００４６】
発明による検索エンジンのアーキテクチャは上記考察事項に基づいたものであり、ここで簡単に２つの次元、すなわちデータ量と性能の各次元においてスケーリングすることができる。
【００４７】
データ量スケーリングは、より多くのデータセットパーティションｄを加えること、言い換えれば、検索ノード
0003586429.tif 000039
のグループまたは列Ｓを増やすことによって達成される。また、インデックスノード
0003586429.tif 000040
およびディスパッチノード
0003586429.tif 000041
は、より多くのデータセットパーティションｄを取り扱うために必要に応じて増設することができる。
【００４８】
図６に示された個数を増やすことにより、検索ノード
0003586429.tif 000042
の増設に対応するデータセットパーティションｄを複製して検索エンジンアーキテクチャにおける性能スケーリングを行うことができる。システム性能をスケーリングするためにデータセットパーティションの複製を使用する場合、それぞれの検索ノード
0003586429.tif 000043
は検索ノードグループＳの一部分である。したがって、検索ノード
0003586429.tif 000044
はグループ
0003586429.tif 000045
にまとめられる。ここでスケーリングファクタをｈｓで表すと、ν＝ｓ／ｈｓとなる。図８に示されるように、グループ
0003586429.tif 000046
には検索ノード
0003586429.tif 000047
が含まれる。
【００４９】
データ量のスケーリングに伴って、ディスパッチノード
0003586429.tif 000048
からブロードキャストされるクエリーを受信する検索ノード
0003586429.tif 000049
の数が非常に増加するかもしれない。この問題は、２進データ分配木（ｂｉｎａｒｙ  ｄａｔａ  ｄｉｓｔｒｉｂｕｔｉｏｎ  ｔｒｅｅ）の一部におけるノードとしてのディスパッチノード
0003586429.tif 000050
の構成を示す図７から分かるように、アーキテクチャがディスパッチノード
0003586429.tif 000051
のいくつかのレベルλを用いて解決する。２進データ分配木は容易に線形のスケーラビリティに対処できる。同様の２進データ分配木は本出願人による上記国際特許出願ＰＣＴ／Ｎ０９９／００３４４で既に明らかにされており、そこにはパターンマッチングチップＰＭＣの実用構成が開示されている。正規の２進木におけるディスパッチノード
0003586429.tif 000052
の数は、もちろん各レベルλについて
0003586429.tif 000053
である。ただし、λ＝１、２、３とする。木構造において、ディスパッチルートノードは第１レベルにあり、与えられたレベルλを含めてそのレベルまでの合計ディスパッチノード数は
0003586429.tif 000054
である。ディスパッチノード
0003586429.tif 000055
がアクイジションノードとしても使用される場合、すなわち、検索ノードから戻った応答を集める機能をディスパッチノードに持たせた場合、検索結果はディスパッチノードでまとめられ、ディスパッチルートノードからクエリーに対する最終的な応答が出力される。しかし、データ収集木すなわちデータアクイジションノード木のアクイジションルートノード上でクエリーの最終的な結果を収集、出力するアクイジションノード
0003586429.tif 000056
を含み、検索ノードに接続される別のデータ収集木を用いて本発明の検索エンジンを構成しても不都合はない。アクイジションノード木はディスパッチノード木の鏡像と考えることができる。
【００５０】
本発明によるスケーラブルな検索エンジンアーキテクチャの概要レイアウトは、ここに記述される二次元スケーリングの原則にしたがって図８に示される。ディスパッチノード
0003586429.tif 000057
は検索エンジンのフロントエンドを構成し、クエリーを検索ノード
0003586429.tif 000058
に送り、インデックス付きデータの検索が実際に行われる検索ノードから検索結果を受け取る。図９に示されるように専用のアクイジションノード
0003586429.tif 000059
を使用する場合は、もちろん、そのアクイジションノードに検索結果が返されるが、使用しない場合は図８と同様になる。ディスパッチノード
0003586429.tif 000060
を図９で示される木構造で構成する場合、検索エンジンのバックエンドとしてのアクイジションノードネットワークはディスパッチノードネットワークの鏡像を形成する。インデックス（スパイダリング「ｓｐｉｄｅｒｉｎｇ」）ノード
0003586429.tif 000061
もまた、検索エンジンのバックエンドを構成し、例えばインターネットからデータを収集して、検索可能なカタログを生成するためにデータにインデックスをつける。検索ノード
0003586429.tif 000062
あるいは検索ノードグループＳを水平に加えることによって、検索エンジンはデータ量の直線的スケーリングを行い、追加の各検索ノードまたは検索ノードグループは互いに異なるデータを保持する。検索エンジンに対する典型的な容量パラメータは、非限定インスタンス（ｎｏｎ−ｌｉｍｉｔｉｎｇ  ｉｎｓｔａｎｃｅ）として以下のように与えられる。１つの検索ノード
0003586429.tif 000063
による１日あたりの典型的な処理量は、５，０００，０００文書のカタログで８，０００，０００ページビュー（ｐａｇｅ  ｖｉｅｗｓ）である。スケーラブルな検索エンジンの場合、一般に各検索ノード
0003586429.tif 000064
は特有のインデックスをつけた５，０００，０００文書を保持することが可能であり、これは２０，００００，０００文書のカタログを維持するために１行あたり４０の検索ノードで十分であることを意味する。性能スケーリング、すなわちトラフィック容量を増すためには、単一の行またはグループＳにおける検索ノードに同じデータが含まれるように、より多くの検索ノード
0003586429.tif 000065
に同じデータを供給する必要がある。そうすれば、１０個の検索ノード
0003586429.tif 000066
を含むグループまたは列Ｓで、１日あたりの８０，０００，０００ページビューの処理が可能であり、４０列で１日あたりの処理量は合計３，２００，０００，０００ページビューになる。
【００５１】
ここに開示されるアーキテクチャを有する本発明によるスケーラブル検索エンジンに関するもう一つの重要な特長は、すべての検索ノード
0003586429.tif 000067
で各クエリーが並列に実行されるためクエリー応答時間が本質的にカタログサイズに依存しないこと、そして、本質的にアーキテクチャに障害許容性が備わっていて、個々のノードの障害がシステム障害とはならず、障害復帰までの一時的な性能低下だけで済むことである。
【００５２】
さらに、従来技術による検索エンジンでは、一般にデータまたはトラフィック量の増加に従って検索費用が指数関数的に増加し、中程度以下の量で検索エンジンの最大容量に達するが、これとは全く対照的に、本発明による検索エンジンでは原則として、データ量およびトラフィック量の無制限線形スケーラビリティが可能になる。本発明による検索エンジンでは、費用は高々容量増加に従って直線的に変化し、実際の費用は、ＳＷ検索ノードだけの付加による容量増加か、あるいはＳＷ／ＨＷ検索ノードも付加したための容量増加かに依存する。本発明による検索エンジンの利点は、標準的な市販の低価格ＰＣを用いて実際の各ノードが実現可能であり、入手可能であれば、例えばＳｕｎやＡｌｐｈａコンピュータ等の高価なＵＮＩＸ（登録商標）ベースのサーバを利用することも可能である。
【図面の簡単な説明】
【図１】本発明による検索エンジンの第１実施例のアーキテクチャを示す概要図。
【図２】本発明による検索エンジンの第２実施例のアーキテクチャを示す概要図。
【図３】検索ソフトウェアおよび専用ハードウェア検索チップを備えた検索ノードを示す概要図。
【図４】検索チップを含む単一モジュールを示す概要図。
【図５】専用検索チップにおけるクエリー処理を示す図。
【図６】性能スケーリングの原理を示す図。
【図７】２進木構造に基づいたマルチレベルディスパッチノード構成を示す図。
【図８】本発明による検索エンジンの第１実施例のアーキテクチャを二次元スケーリングの原理で示す概要図。
【図９】本発明による検索エンジンの第２実施例のアーキテクチャを二次元スケーリングの原理で示す概要図。
【図１】
0003586429.tif 000101
【図２】
0003586429.tif 000102
【図３】
0003586429.tif 000103
【図４】
0003586429.tif 000104
【図５】
0003586429.tif 000105
【図６】
0003586429.tif 000106
【図７】
0003586429.tif 000107
【図８】
0003586429.tif 000108
【図９】
0003586429.tif 000109