(57)【特許請求の範囲】
【請求項１】
プロファイル・プロセッサ及びサーチ・プロセッサを含む複数のプロセッサを含み、データ網を介して受信した情報コンテンツを探索するためのサーチ装置であって：
複数のユーザから複数のユーザ・クエリを受信するためのプロファイル・プロセッサによって実行可能なロジックを有する前記プロファイル・プロセッサと；および
前記プロファイル・プロセッサに接続したサーチ・プロセッサによって実行可能なロジックを有する前記サーチ・プロセッサであって、前記ロジックは、前記データ網を介して前記情報コンテンツを受信し、前記複数のユーザ・クエリ中の数値の範囲を、それぞれが値の個別の範囲の上限及び下限を表わすものである複数の区間キーワードから１つ又は２つの区間キーワードにマッピングしてその数値の範囲を表わし、前記マッピングされたユーザ・クエリをマスタ・クエリへと結合し、前記情報コンテンツ中の数値を前記複数の区間キーワードから１つ又はそれより多くの区間キーワードにマッピングしてその数値を表し、ならびに合致コンテンツを決定するために、前記マスタ・クエリを前記情報コンテンツと照合し、前記ユーザ・クエリのいずれかが満足されたか決定するために、前記合致コンテンツを解析するためのものである、前記サーチ・プロセッサを含むサーチ装置。
【請求項２】
前記ユーザに、彼らの個別のクエリが満足されたか通知するためのロジックを有する通知プロセッサをさらに具備する、請求項１に記載のサーチ装置。
【請求項３】
前記合致コンテンツを記憶するためのメモリをさらに具備することを特徴とする、請求項１に記載のサーチ装置。
【請求項４】
前記マッピングされたユーザ・クエリは、テキスト探索文字列およびブール式（Boolean expressions）を含むことを特徴とする、請求項１に記載のサーチ装置。
【請求項５】
前記サーチ・プロセッサのロジックは、前記マッピングされたユーザ・クエリからハッシュ・テーブル（hash table）を作成し、および前記マッピングされた情報コンテンツを、前記ハッシュ・テーブルにおける情報と照合するためのロジックをさらに具備することを特徴とする、請求項１に記載のサーチ・エンジン。
【請求項６】
前記サーチ・プロセッサの前記マッピングされたユーザ・クエリを結合するロジックは、前記マッピングされたユーザ・クエリを正規化して、キーワードから形成された複数の論理積を含む正規化されたユーザ・クエリを形成し、前記論理積および前記キーワードから複数のハッシュ・テーブルを形成するロジックをさらに含むことを特徴とする、請求項１に記載のサーチ装置。
【請求項７】
前記サーチ・プロセッサの前記マスター・クエリを前記マッピングされた情報と照合し、前記キーワードのいずれかが前記マッピングされた情報コンテンツ中にあるかを決定し、前記決定の結果に基づいて前記ハッシュ・テーブルを更新するロジックをさらに含むことを特徴とする、請求項１に記載のサーチ装置。
【請求項８】
少なくとも１つのキーワードは、テキスト句を具備し、前記マスタ・クエリを照合前記マッピングされた情報と照合するための前記サーチ・プロセッサのロジックは、前記テキスト句が前記マッピングされた情報コンテンツにあるか決定するロジックをさらに含むことを特徴とする、請求項７に記載のサーチ装置。
【請求項９】
前記サーチ・プロセッサの解析するためのロジックは、どの論理積が前記マッピングされた情報コンテンツにあるかに基づいて、合致パラメータを更新するロジックをさらに含むことを特徴とする、請求項８に記載のサーチ装置。
【請求項１０】
前記通知プロセッサの通知するロジックは、前記合致パラメータに基づいて、前記ユーザに通知するロジックを含むことを特徴とする、請求項８に記載のサーチ装置。
【請求項１１】
前記サーチ・プロセッサの数値の範囲を２つの区間キーワードにマッピングするロジックは、これらの２つの区間キーワードを結合してブール式を形成するロジックをさらに含むことを特徴とする、請求項１に記載のサーチ装置。
【請求項１２】
プロファイル・プロセッサ及びサーチ・プロセッサを含む複数のプロセッサを含むサーチ装置によって実行される、データ網を介して受信された情報コンテンツを探索するための方法であって：
前記プロファイル・プロセッサによって、複数のユーザから複数のユーザ・クエリを受信し；
前記サーチ・プロセッサによって、前記データ網を介して前記情報コンテンツを受信し；
前記複数のユーザ・クエリ中の数値の範囲を、それぞれが値の個別の範囲の上限及び下限を表わすものである複数の区間キーワードから１つ又は２つの区間キーワードにマッピングしてその数値の範囲を表わし；
前記サーチ・プロセッサによって、前記マッピングされたユーザ・クエリをマスタ・クエリに結合し；
前記サーチ・プロセッサによって、前記情報コンテンツ中の数値を前記複数の区間キーワードから１つ又はそれより多くの区間キーワードにマッピングしてその数値を表し；
前記サーチ・プロセッサによって、合致コンテンツを決定するために、前記マスタ・クエリを前記マッピングされた情報コンテンツと照合し；および
前記サーチ・プロセッサによって、前記ユーザ・クエリのいずれかが満足されたかを決定するために、前記合致コンテンツを解析する
ステップを具備することを特徴とする前記方法。
【請求項１３】
前記サーチ装置の通知プロセッサによって、前記ユーザに、彼らの個別のクエリが満足されたかを通知するステップをさらに具備することを特徴とする、請求項１２に記載の方法。
【請求項１４】
前記結合ステップは：
前記サーチ・プロセッサによって、キーワードから形成された複数の論理積を含む、正規化されたユーザ・クエリを形成するために、前記ユーザ・クエリを正規化し；および
前記サーチ・プロセッサによって、前記論理積および前記キーワードから複数のハッシュ・テーブルを形成する
ステップを含むことを特徴とする、請求項１２に記載の方法。
【請求項１５】
前記照合ステップは：
前記サーチ・プロセッサによって、前記キーワードのいずれかが前記マッピングされた情報コンテンツにあるか決定し；および
前記サーチ・プロセッサによって、前記決定ステップの結果に基づいて、前記ハッシュ・テーブルを更新する
ステップを具備することを特徴とする、請求項１４に記載の方法。
【請求項１６】
少なくとも一つのキーワードが、テキスト句を具備し、および前記照合ステップは、前記サーチ・プロセッサによって、前記テキスト句が前記マッピングされた情報コンテンツにあるか決定するステップを具備することを特徴とする、請求項１５に記載の方法。
【請求項１７】
前記解析ステップは、前記サーチ・プロセッサによって、どの論理積が前記マッピングされた情報コンテンツにあるかに基づいて、合致パラメータを更新するステップを具備することを特徴とする、請求項１６に記載の方法。
【請求項１８】
前記通知ステップは、前記通知プロセッサによって、前記合致パラメータに基づいて、前記ユーザに通知するステップを含むことを特徴とする、請求項１７に記載の方法。
【請求項１９】
数値の範囲を２つの区間キーワードにマッピングするステップは、これらの２つの区間キーワードを結合してブール式を形成するステップをさらに含むことを特徴とする、請求項１に記載の方法。
【請求項２０】
前記マッピングされたユーザ・クエリは、テキスト探索文字列およびブール式を含むことを特徴とする、請求項１２に記載の方法。
【請求項２１】
前記サーチ・プロセッサによって、前記マッピングされたユーザ・クエリからハッシュ・テーブルを形成し、
前記サーチ・プロセッサによって、前記マッピングされた情報コンテンツを前記ハッシュ・テーブル中の情報と照合するステップをさらに含む、請求項１２に記載の方法。
【発明の詳細な説明】
【０００１】
（関連出願の相互参照）
本出願は、１９９９年７月１２日に提出された、同時継続アメリカ合衆国仮出願第６０／１４３，４７３号から優先権を主張し、その開示内容は、あらゆる目的のために、ここにその全部が統合されている。
【０００２】
（技術分野）
本発明は、サーチ・エンジンに関し、より特定的には、複数のユーザからの情報合致サーチ・クエリのための、情報コンテンツの様々なストリームを効率的に探索することができるサーチ・エンジンに関する。
【０００３】
（背景技術）
サーチ・エンジンとは、情報ネットワークにおいて、ユーザが情報を見つける手助けをするプログラムである。ユーザは、自分が何を探索しているかを示す単語または句を含むサーチ・クエリを提出し、前記サーチ・エンジンは、それが、前記クエリに関連すると予言するウェブ・ページのリストを返す。サーチ・エンジンによって、このリストに含まれると考えられるページは、「ターゲット・ページ（target page）」と呼ぶことができる。
【０００４】
サーチ・エンジンによって戻されたウェブ・ページのリストは、関連性によって順位付けられる。典型的には、関連性は、ほとんどがターゲット・ページの内容によって決定される。例えば、ユーザが「チョコレート・ケーキ」という句を探索する場合、典型的なサーチ・エンジンは、単に、「チョコレート」および「ケーキ」という単語を個別に含むものよりも前に、「チョコレート・ケーキ」という句を含むページを順位付け、そのようなページは同様に、前記二つの単語のうち一つを含むが他方を含まないページよりも、高く順位付けられるであろう。
【０００５】
今日、インターネット上の多くのサイトが、金融ニュース、ビジネス・ニュース、リアルタイム気象報告、および他の種類のストリーミング・メディア・コンテンツ等、時間変動しやすいコンテンツを大量に提供する。しかしながら、現行のサーチ・システムは、大量のユーザ要求を扱うときに、大変非効率的に動作しているかもしれない。その結果、ほとんどのユーザは、利用できるときに欲しい情報を見つけることに手一杯になってしまう。
【０００６】
現行のサーチ・システムの効率性に関する一つの問題は、大量の、様々な電子情報のストリームを、大量のユーザへと効率的に浸透させる問題である。例えば、何千ものユーザが、ある一定の日に、金融情報に対するサーチ・クエリを提出するかもしれない。典型的には、各ユーザのクエリは、個別に探索され、その結果は、直接前記ユーザに供給される。しかしながら、前記ユーザの多くは、重複するクエリを有するかもしれず、その結果、ただ同じ情報を入手するために反復したサーチをする。
【０００７】
現行のサーチ・システムに関する他の問題は、一以上のユーザが、入手可能になる、最新の情報を見つけるために、繰り返し周期的に、同じ、または類似の探索を実行したいときに生じる。これは「継続的クエリ（persistent query）」と称される。典型的なサーチ・システムでは、大量のユーザからの、継続的クエリを効率的に扱うことができない。
【０００８】
（発明の開示）
本発明は、情報網において、効率的に所望の情報を見つけるために、複数のユーザ・クエリのコンパクトな表示を形成するサーチ・エンジンを供給する。ユーザ・プロファイルの一部であるユーザ・クエリの各々は、特殊文字を数値および列挙データ型の代わりにするために、前処理される。サーチ・エンジンは、前処理されたユーザ・クエリをマスタ・サーチ・クエリに結合し、および前記マスタ・クエリを、データ網を介して送信されるコンテンツ・ストリームにおける情報と照合するための効率的なメカニズムを含む。このように、本発明は、それを通じて情報が流れる、ユーザ・クエリの、うまく編成された、コンパクトな表示を供給することによって、各ユーザ・クエリに関して個別にドキュメントの集まりを索引付けする、従来の情報検索アプローチを覆す。
【０００９】
サーチ・エンジンによって、ユーザは、ユーザの関心を表す、一組の長期的に存続する、または継続的なクエリを入力することができる。各個別のユーザに関する繰り返しの探索を実行する代わりに、前記サーチ・エンジンは、マスタ・サーチ・クエリを形成するために、すべてのユーザ・クエリを効率的に結合する。サーチ・エンジンによって受信された情報コンテンツは、探索結果を生成するために、マスタ・サーチ・クエリと照合される。探索結果における選択された情報は、ユーザ・コンタクト規則を含むユーザ・プロファイルに従って、各個別のユーザへと届けられる。
【００１０】
インターネットが成長し続けるにつれて、含まれているサーチ・エンジンによって処理される情報は、大変多様になりうる。例えば、オンライン案内広告は、自動的に、住む場所を探しているユーザに配信されることができる。一定の価格帯にある新製品に関する情報は、消費者が購入を決定するのを手助けするために、消費者に配信されることができる。個別化された情報の配信が、ユーザに有益である他の情報領域は、ニュース記事、天気ならびに交通情報、オンライン・オークションおよび他の時間変動しやすいポスティング（postings）を含む。
【００１１】
情報配信機構は、電子メール、インスタント・インターネット・メッセージング製品（Ｙａｈｏｏ！Ｍｅｓｓｅｎｇｅｒ、ＡＯＬ  Ｉｎｓｔａｎｔ
Ｍｅｓｓｅｎｇｅｒ等）、ワイヤレス・テキスト・メッセージング（wireless text messaging）、ファクシミリ、音声メッセージ、および個別化ウェブ・ページを含む。
【００１２】
本発明の一つの実施形態において、データ網を介して情報コンテンツを受信し、および複数のユーザと関連する複数のクエリに基づいて、前記情報コンテンツを探索するためのサーチ・エンジンが供給される。サーチ・エンジンは、ユーザからのクエリを受信するためのロジックを有するプロファイル・プロセッサと、およびサーチ・モジュールを具備する。サーチ・モジュールは、プロファイル・プロセッサに接続され、および情報コンテンツを受信し、ユーザ・クエリをマスタ・クエリに結合し、ならびに合致コンテンツを決定するために、マスタ・クエリを情報コンテンツと照合するためのロジックを有する。サーチ・エンジンはまた、前記クエリのいずれかが満足されたか決定するために、合致コンテンツを解析するためのロジックも含む。
【００１３】
本発明の特徴および効果は、本明細書の残りの部分と、および添付の図面を参照することによって、より理解されるかもしれない。
【００１４】
（発明を実施するための最良の形態）
本発明に含まれるサーチ・エンジンによって、ユーザは、ユーザ・プロファイルを確立するためのサーチ・クエリを含むパラメータを入力することができる。サーチ・エンジンは、データ網におけるストリーミング情報コンテンツの効率的なサーチを可能にするためのマスタ・クエリを形成するために、ユーザ・プロファイルにおけるクエリを結合させる。ストリーミング情報とマスタ・クエリとの間で検出された合致は、どのユーザ・クエリが満足され、そして関連する情報が関連するユーザに配信されうるかを決定するために解析される。探索結果は、後に所望の場合に検索できるようにするために、メモリにも記憶される。
【００１５】
サーチ・エンジンは、以下の三つの方法で効果がある。第一に、ユーザ・クエリは、クエリ間の共通した関心が共有される、コンパクトな表示で編成される。大きな加入者ベースに到達すると、ユーザは、典型的には共通の関心（スポーツ・チーム、交通報告）を有する。本発明は、効率的な処理を可能にするために、共通の関心を一つのエンティティへと結合することにより、共通の関心を利用する。第二に、ユーザ・クエリに見られる列挙データ型からの数値および値は、大変迅速な処理を可能にする特殊テキスト・パターンに代えられる。第三に、すべてのユーザの数値の階層的編成は、効率的な方法で合致ドキュメントを決定するために使用される。
【００１６】
図１は、本発明に従って構築されたサーチ・エンジン１０２を含むデータ網を示す。データ網１００は、情報が配分されてもよい相互接続されたネットワークを形成するために、データ・リンク（Ｌ）によって接続されたアドレス可能ルータ（Ｒ）を利用する。コンテンツ・サーバ１０４、１０６、および１０８等、一つ以上のコンテンツ・サーバは、ユーザ１１０、１１２、および１１４等のユーザによる使用のために、ネットワークを介して情報を配分する。情報コンテンツは、ニュース、ビジネスあるいは金融情報、天気予報、または他の種類の情報あるいはドキュメント・ストリームを含むがそれらに限定されない、あらゆる種類のストリーミング情報を含んでもよい。例えば、図１において、コンテンツ・サーバ１０４は、１１６で図示されているように、ニュース情報ストリームを送信する。ニュース情報ストリーム１０６は、米国連合通信社（Associated Press）のニュース・レポート等、あらゆる種類のニュース・レポートを含んでもよい。コンテンツ・サーバ１０６は、１１８で図示されているように、金融情報を送信する。金融情報は、株式相場、企業報告または他の種類の金融情報を含んでもよい。コンテンツ・サーバ１０８は、１２０で図示されているように、気象報告を送信する。前記気象報告は、天気予報または米国気象課（National Weather Service）からのそれ等、他の種類の気象報告を含んでもよい。情報ストリーム（１１６，１１８，１２０）は、サーチ・エンジン１０２を含む他のネットワーク・エンティティによって受信されうるように、ネットワーク１００の周辺で送信される。
【００１７】
実際には、図示された３の顧客よりも多くの顧客が、ネットワークに接続されるであろう。また、一のサーチ・エンジンのみが図示されているが、特定のネットワークで使用される一つ以上のサーチ・エンジンを有することも可能である。サーチ・エンジン１０２は、サーチ・エンジン１０２に接続された受信局１２２によって受信される情報のワイヤレス送信から等、他の送信方法を使用して、他のソースから情報コンテンツを受信することも可能である。
【００１８】
図１に記載のシステムにおけるいくつかのエレメントは、従来の、公知のエレメントであり、ここで詳細に説明する必要はない。例えば、ユーザ１１０、１１２および１１４は、デスクトップ・パーソナル・コンピュータ、ワークステーション、セル電話、パーソナル・デジタル・アシスタント（ＰＤＡ）、ラップトップ、またはインターネットに直接あるいは間接的に接することができるあらゆる他のコンピュータ機器を使用して、ネットワーク１００と対話してもよい。本発明は、インターネットとの使用に適しており、それはネットワークの、特定のグローバル・インターネットワークに関連する。しかしながら、本発明は、インターネットの代わりに、イントラネット、エクストラネット、仮想プライベート・ネットワーク（ＶＰＮ）、非ＴＣＰ／ＩＰベースのネットワーク、無線ネットワーク等、他のネットワークとの使用に適していることが理解されるであろう。
【００１９】
コンテンツ・サーバとサーチ・エンジンとの間の相互接続は、ネットワーク１００に関して図示されているが、これらの接続は、無線ネットワーク等、他の送信手段を介して取り扱われてもよい。ここに説明されている詳細およびその関連を除いて、サーチ・エンジンは、従来のコンテンツ・サーバとの使用に適しており、そのため、コンテンツ・サーバの正確な動作のさらなる詳細は、ここでは説明される必要はない。ユーザ１１０，１１２および１１４は、典型的には、サーチ・エンジン１０２等、ネットワーク１００のエンティティとの二方向対話を可能にするブラウジング・プログラムを実行させるハードウェアを含む。
【００２０】
図２は、本発明に従って構築されたサーチ・エンジン１０２のブロック図を示す。明確にする目的で、ネットワーク１００の詳細は、サーチ・エンジン１０２が、ユーザ１１０，１１２ならびに１１４および情報コンテンツ・ストリーム２０２とどのように対話するかわかるようにする図２には図示されていない。
【００２１】
サーチ・エンジン１０２は、プロファイル・プロセッサ２０４、サーチ・プロセッサ２０６、通知プロセッサ２０８、およびメモリ２１０を含む。プロファイル・プロセッサ２０４は、ユーザ・クエリおよびユーザ・コンタクト情報からユーザ・プロファイルを作成するために、ユーザ１１０，１１２および１１４と対話する。ユーザ１１０、１１２、および１１４は、２１２に図示されたパスを介してプロファイル・プロセッサと対話する。プロファイル・プロセッサ２０４は、プロファイル情報を記憶するための内部メモリ（図示されていない）を含んでもよく、またはメモリ２１０等、外部メモリを使用してもよい。
【００２２】
サーチ・プロセッサ２０６は、プロファイル・プロセッサからユーザ・クエリを受信し、および特殊文字を、数値ならびに列挙データ型の代わりとするために、ユーザ・クエリを前処理する。サーチ・プロセッサはそれから、入ってくる情報ストリーム２０２と照合されるマスタ・クエリを作成する。照合動作の結果は、どのユーザ・クエリが満足されたか決定するために解析される。照合動作の結果は、メモリ２１０にも記憶され、および通知プロセッサ２０８に送信される。
【００２３】
通知プロセッサ２０８は、サーチ・プロセッサ２０６から結果を受信し、それはクエリ合致および関連する合致ドキュメントに関する表示を含む。通知プロセッサ２０８は、パス２１２に記載されたとおり、プロファイル・プロセッサからユーザに関連する通知コンタクト情報を受信する。通知コンタクト情報を使用して、通知プロセッサ２０８は、サーチから検索された情報を、適切なユーザに送信する。前記送信は、２１４に図示されたように、ネットワーク・パスを介してもよく、またはファクシミリや音声メール等、ユーザによって特定された他の送信パスを介してしてもよい。
【００２４】
メモリ２１０は、ユーザによる後の検索のために、サーチ・プロセッサによって作成された結果を記憶するために使用される。例えば、ユーザ１１０は、朝、継続的クエリを入力する場合、その結果は、ユーザに報告されるべき結果があるか決定するために、ユーザ１１０が通知プロセッサ２０８と接触し、同様に、パス２１６を介してメモリ２１０を調べるとき、検索することができる。
【００２５】
本発明の一つの実施形態は、情報コンテンツに含まれるテキスト・ドキュメント（ニュース記事、製品説明、案内広告）が、ユーザによって与えられる、従来のキーワードに基づいたクエリを使用して探索されるという前提の下に動作する。さらに、各情報ドキュメントは、一組の数値（製品価格等）および列挙データ型（色あるいはサイズ等）を含むことができる。ユーザ・クエリは、届けられたドキュメントと合致しなければならない一定の範囲の値（例えば、価格帯）を含んでもよい。このように、ある実施形態において、本発明は、列挙データ型と同様に、テキスト・データ、数値を合致させるための効率的な機構との使用のために、ユーザ・クエリのコンパクトな表示を形成する。本システムは、ユーザ・クエリ間の共通の関心を利用して、類似のクエリをマスタ・クエリに統合する。
【００２６】
ユーザ・クエリ生成は、対話型インターフェースによって容易になる。例えば、本システムは、ユーザが現在見ているニュース記事に基づいた継続的クエリに関する一組のキーワードを提示する。個人的関心プロファイルもまた、ショッピング・リスト（shopping list）やギフト・レジストリ（gift registry）等、オンライン・アプリケーションから抽出されてもよい。
【００２７】
図３は、本発明に従ったサーチ・エンジン１０２を動作する方法３００を図示する。
【００２８】
ブロック３０２において、方法３００は、一以上のユーザから一以上のクエリを受信するサーチ・エンジンで開始する。クエリは、キーワードおよびＯＲ、ＡＮＤ、ならびにＮＯＴ演算子等の、論理積演算子を使用したブール式の形式でもよい。ユーザ・クエリのより詳細な説明は、本明細書の他の章で提供される。
【００２９】
ブロック３０４において、ユーザ・クエリは、コンタクト情報に沿って、プロファイル・プロセッサによって受信される。コンタクト情報は、クエリの結果が適切に報告されるように、各ユーザによって供給される。ブロック３０６においては、特殊文字が数値および列挙データ型の代わりをするように、クエリは前処理される。前処理されたクエリは、マスタ・サーチ・クエリを形成するために結合される。
【００３０】
ブロック３０８において、情報コンテンツ・ストリームは、マスタ・サーチ・クエリに照合される。この処理の間、コンテンツ・ストリームにおける各ドキュメントまたは情報アイテムは、マスタ・サーチ・クエリと比較され、前記情報がユーザ・クエリのいずれかと合致するか決定するための解析が実行される。解析の詳細な説明は、本明細書の他の章で提供される。
【００３１】
ブロック３１０において、マスタ・サーチ・クエリとのあらゆる合致は、後の検索のために、メモリに記憶される。ブロック３１２において、あらゆる合致はまた、ユーザ・コンタクト情報が、プロファイル・プロセッサから検索され、および提出されたクエリと合致する情報を、ユーザに通知するために使用されうるように、通知プロセッサへも報告される。
【００３２】
ブロック３１４においては、ユーザが通知情報を受信することができない場合、あらゆる合致情報が、ユーザにとってより都合のよいときに、結果記憶装置から検索することができるように、ユーザ・インターフェースが供給される。
【００３３】
クエリ言語
サーチ・エンジンは、他の種類のインターネット・サーチ・エンジンで使用される典型的なクエリ言語と類似したクエリ言語を使用する。例えば、ＡＮＤ（＋）、ＯＲおよびＮＯＴ（−）等のブール演算子がサポートされる。さらに、引用文字列を探索することができるようにするために、句照合がサポートされる。例えば、以下のクエリがサポートされる
１．  ｐｏｌｉｃｅ＋ｓｔｉｎｇ  キーワード「ｐｏｌｉｃｅ」と、キーワード「ｓｔｉｎｇ」とを含むすべての情報コンテンツを見つけるために使用される
２．  ｐｙｔｈｏｎ−ｍｏｎｔｙ  キーワード「ｐｙｔｈｏｎ」を含むがキーワード「ｍｏｎｔｙ」は含まないすべての情報コンテンツを見つけるために使用される
３．  「ｇｒｅａｔ  ｂａｒｒｉｅｒ  ｒｅｅｆ」
「ｇｒｅａｔ  ｂａｒｒｉｅｒ  ｒｅｅｆ」という句を含むすべての情報コンテンツを見つけるために使用される
【００３４】
ユーザ・プロファイル
図４は、ユーザからプロファイル・プロセッサ２０４に供給される情報から構築されるユーザ・プロファイル４００のブロック図を示す。ユーザ・プロファイル４００は、ユーザに関する数種類の情報およびユーザの所望のサーチ基準を含む。例えば、ユーザ・プロファイル４００は、ユーザのネットワーク・アドレスおよびユーザ・プロファイルに含まれる一以上のクエリに関するタイム・スタンプ（time stamp）を含んでもよいユーザ識別情報４０２を含む。
【００３５】
ユーザ・プロファイル４００はまた、ユーザ・コンタクト情報４０４も含む。ユーザ・コンタクト情報４０４は、特定のクエリの結果に関してユーザに接触するために使用される規則を含んでもよい。例えば、ユーザは、クエリを提出し、およびファクシミリ、電子メールによって、あるいは自動化音声メッセージによって、地上線またはワイヤレス電話へと結果を通知されるように要求してもよい。探索結果に関してユーザに接触するために、あらゆる種類の通信機構が使用されてもよい。コンタクト情報に含まれる規則は、探索結果を報告するための時間を特定してもよい。例えば、ユーザは、一時間以内に、その日のもっと後で、または毎日周期的に探索結果に関して通知されることを希望してもよい。このように、ユーザは、特定のクエリの結果に関する様々な通知シナリオを設定するために、特定のコンタクト規則を入力することができる。
【００３６】
ユーザ・プロファイル４００は、ユーザ・クエリ４０６も含む。ユーザ・クエリは、ユーザが所望する情報を特定するキーワードおよびブール式を含む文字列の形式である。
【００３７】
クエリ前処理
照合文字列に加えて、サーチ・エンジンは量または価格を示す数字を比較する。例えば、ユーザは、オークション商品が一定の価格に到達したとき、またはショッピング商品が一定の価格より下がったとき、警告することを希望してもよい。例えば、ユーザが、商品価格が２５ドルより低くなるときに照会したい場合、クエリは以下のように作成されうる：
ｐｒｉｃｅ＜２５．００
多数のユーザに関する正確な価格照合は、計算上費用がかかる動作であるため、本発明の一つの実施形態は、ある場合における正確な価格照合を、価格帯の照合に変える。各価格帯は、上記のキーワード照合技術が適用される、予め定義されたキーワードによって表示される。価格帯照合は、さらなる精度が相応でなく、よって正確さを損なわずに効率性を維持するクエリ・プロパティに適用されてもよい。
【００３８】
数字および価格を照合する
ある製品カテゴリにおける商品の価格は、通常は、一般的な価格帯に入る。例えば、デスクトップ・コンピュータは、５００ドル乃至２５００ドルの範囲にあるかもしれない。価格帯は、（Ｎ＋２）区間へと区分されてもよく、Ｎは、相応に小さい数字（例えば、１０）であればよい。例えば、Ｎが４である場合、デスクトップ・コンピュータの価格帯に関する価格付けの６の区間は、［０，５００］、［５００，１０００］、［１０００，１５００］、［１５００，２０００］、［２０００，２５００］、［２５００、無限］であろう。
【００３９】
特定の価格より上または下の価格帯等、他の数値的特性は、（２Ｎ＋２）キーワードでコード化することができ、各キーワードは区間限界を含む。例えば、区間限界（ｂｅｌｏｗ＿１０００）は、価格が１０００ドルか、またはそれより下であり、区間限界（ａｂｏｖｅ＿１０００）は、価格が１０００ドルか、またはそれより上であることを意味する。そのため、デスクトップ・コンピュータの例を参照すると、Ｎが４である場合、以下のように、デスクトップ・コンピュータに関する１０の価格帯を表示するための（２Ｎ＋２）キーワードを形成することが可能である。
１．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿５００
２．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿１０００
３．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿１５００
４．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿２０００
５．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿２５００
６．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿５００
７．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿１０００
８．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿１５００
９．ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿２０００
10. ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿２５００
ユーザが、デスクトップ・コンピュータの価格帯が１０００から１５００の間にあるときに通知されることを選択したと仮定する。以下のように、ブールＡＮＤ演算子によって接続された二つのキーワードのみで形成されるユーザ・プロファイルを作成することが可能である：
computer_desktop_price_above_1000 AND computer_desktop_price_below_1500
【００４０】
そのため、ある（Ｎ）に関して、サーチ・システムに入ってくる各製品の価格は、（Ｎ＋１）または（Ｎ＋２）キーワードに拡張することができる。例えば、デスクトップ・コンピュータが１３９５ドルで売られる場合、それは自動的に、以下のように、（Ｎ＋１）キーワードに拡張することができる。
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿５００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿１０００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿１５００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿２０００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿２５００
その結果、１３９５ドルのデスクトップ・コンピュータは、特定されたキーワードの両方、すなわち
computer_desktop_price_above_1000 AND computer_desktop_price_below_1500
を含むので、例のユーザ基準に合致する。
【００４１】
価格が、特定された範囲の境界上にある場合には、該価格を（Ｎ＋２）キーワードに拡張することができる。例えば、上述の例におけるデスクトップ・コンピュータの価格が１０００ドルである場合、以下の（Ｎ＋２）キーワードが抽出される：
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿５００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ａｂｏｖｅ＿１０００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿１０００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿１５００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿２０００
ｃｏｍｐｕｔｅｒ＿ｄｅｓｋｔｏｐ＿ｐｒｉｃｅ＿ｂｅｌｏｗ＿２５００
上述の、ユーザ・クエリへの拡張を行う一つの効果は、それが照合時間中は動的に生じうる一方で、プロファイルにおけるクエリ・サイズは、小さいままであることである。そのため、必要とされる拡張スペースのコストは、定数のままである：それは常に（Ｎ＋１）または（Ｎ＋２）キーワードである。要約すると、一度（Ｎ）が選択されると、価格区間キーワードを定義することができる。受信されたドキュメントにおけるユーザ・クエリおよび商品の価格の両方が、前記区間キーワードにマッピングされることができるので、価格およびクエリ・キーワードが合致するときを検出することができる。
【００４２】
クエリ正規化
本発明の一つの実施形態は、前処理段階の一部として、ユーザによって入力されるクエリを正規化するように動作する。正規化は、上述の価格付けの例において記述されたように拡張されたクエリでも生じうる。一般的に、あらゆるクエリは、ブールＯＲ演算子によって接続された一連の「論理積」によって表すことができる。例えば、以下のサーチ・クエリがある：
ｋｅｙｗｏｒｄ１  ＡＮＤ  （ｋｅｙｗｏｒｄ２  ＯＲ  ｋｅｙｗｏｒｄ３）
二つの論理積を含む、以下の正規化されたクエリが作成されうる：
（ｋｅｙｗｏｒｄ１  ＡＮＤ  ｋｅｙｗｏｒｄ２）ＯＲ  （ｋｅｙｗｏｒｄ１
ＡＮＤ  ｋｅｙｗｏｒｄ３）
括弧内の正規化されたクエリの部分は、論理積部分を表す。クエリによって、論理積部分は、一以上のキーワードを含み、およびブール演算子ＡＮＤまたはＮＯＴを含んでもよい。
【００４３】
サーチ・プロセッサ・オペレーション
図５は、本発明に従って構築されたサーチ・プロセッサ２０６の詳細なブロック図を示す。サーチ・プロセッサは、すべてのユーザ・クエリをマスタ・クエリに処理するために使用され、それは入ってくる情報コンテンツ・ストリームと照合される。
【００４４】
サーチ・プロセッサ２０６は、プロセッサ５０２、クエリ・ハッシュ５０４、キーワード・ハッシュ５０６、および論理積ハッシュ５０８を含み、そのすべては共有メモリ５１０にある。サーチ・プロセッサ２０６はまた、プライベート・クエリ・ハッシュ５１２およびプライベート論理積ハッシュ５１４も含み、そのすべてはプライベート・メモリ５１６にある。共有メモリおよびプライベート・メモリは、異なるメモリから、または単一のメモリから形成されてもよい。
【００４５】
クエリ・ハッシュ
プロセッサ５０２は、入力５１８を介してプロファイル・プロセッサ２０４からユーザ・クエリを受信し、必要に応じてクエリ拡張ならびに正規化を実行し、および共有メモリ５１０ならびにプライベート・メモリ５１６におけるハッシュ・テーブル（５０６、５０４、５０８、５１２、５１４）を埋めることによって、マスタ・クエリを作成する。マスタ・クエリが作成された後、プロセッサ５０２は、入力５２０を介して情報コンテンツを受信し、前記情報コンテンツをマスタ・クエリと照合する。その結果は、出力５２２を介して、メモリ２１０および通知プロセッサ２０８へと出力される。以下の説明は、４のユーザからの以下の例示的なユーザ・クエリを参照し、それらはキーワード「ｋｗ」エントリを有する論理積として下に示されている。例えば、ｋｗ１およびｋｗ２は、上述のとおり、価格区間キーワードを表すことができる一方で、
ｑｕｅｒｙ４はｋｗ５の正確な数値合致を探索する。
Ｕｓｅｒ１（ｑｕｅｒｙ１）：  （ｋｗ１  ＡＮＤ  ＮＯＴ  ｋｗ２）  ＯＲ  ｋｗ６
Ｕｓｅｒ２（ｑｕｅｒｙ２）：  （ｋｗ２  ＡＮＤ  ｋｗ３）
Ｕｓｅｒ３（ｑｕｅｒｙ３）：  （ｋｗ２  ＡＮＤ“ｐｗ１ｐｗ２ｐｗ３”）
Ｕｓｅｒ４（ｑｕｅｒｙ４）：  （ｋｗ＜１００）
【００４６】
キーワード・ハッシュ・テーブル
図６は、上で定義された例示的ユーザ・クエリ６０２から完成する共有メモリ５１０およびプライベート・メモリ５１６におけるハッシュ・テーブルを示す。キーワード・ハッシュ・テーブル５０６は、ユーザ・クエリにおける各キーワードが入力されるキーワード・コラム６０４を含む。キーワード・ハッシュ・テーブルにおける各キーワードは、ConjunctionPtrListコラム６０６に見られる論理積ポインタと関連する。論理積ポインタは、その特定のキーワードを使用するすべてのクエリ論理積を指す。論理積ポインタは、特定の論理積におけるキーワードが、ＮＯＴ属性とともに使用されたかを示す、ＮＯＴフラグ・インジケータとも関連する。この場合、０は、キーワードがＮＯＴ属性を無くして使用されたことを意味する一方で、１はキーワードがＮＯＴ属性とともに使用されたことを示す。さらに、値６０７パラメータは、各論理積と関連しており、値は正確な数字照合のために含まれる。例えば、query4 conjunction1は、６０９に記載されたとおり、ｋｗ５に対応し、値１００を含む。
【００４７】
キーワード・コラム６０４における各キーワードは、さらに、タイプ・コラム６０８に記載された５種類の異なるキーワード・タイプのうちの一つと関連する。キーワード・タイプは：
−  regular(r)    このタイプのキーワードは、論理積ポインタの、オーダされていないリストを有する。
−  lessThan(lt)  このタイプのキーワードは、値の小さい順に分類された論理積ポインタを有する。
−  lessOrEqual(le) このタイプのキーワードは、値の小さい順に分類された論理積ポインタを有する。
−  greaterThan(gt) このタイプのキーワードは、値の大きい順に分類された論理積ポインタを有する。
−  greaterOrEqual(ge)  このタイプのキーワードは、値の小さい順に分類された論理積ポインタを有する。
−  null          このタイプのキーワードは、句の最初の単語である。
【００４８】
Query4に関して、ｋｗ５に関するタイプは、６１１に記載のとおり“ｌｔ”である。キーワード・コラムにおける各キーワードは、さらに、MaxPhraseLengthコラム６１０に記載されたフレーズ長値と関連する。このコラムは、１単語キーワード句に割り当てられた０のフレーズ長値と、および２単語キーワード句に割り当てられた１のフレーズ長値、等を有するキーワード句に、いくつの単語が含まれるかを表すエントリを有する。
【００４９】
図６は、クエリ・ハッシュ・テーブル５０４も示す。クエリ・ハッシュ・テーブル５０４は、クエリＩＤコラム６１２におけるユーザ・クエリを、ConjunctionPtrコラム６１４における論理積と関連付ける。
【００５０】
図６はまた、論理積ハッシュ・テーブル５０８も示しており、それはすべての論理積に関する情報をアセンブルするために使用される。すべての論理積は、ConjunctionID 616で表され、それは各論理積でのキーワードの数を記憶するカウンタ・デフォルト６１８と関連している。WordPointerListコラム６２０は、各論理積に関して、WordsHashテーブル５０６におけるキーワードへのポインタを含む。
【００５１】
キーワード・ハッシュ、クエリ・ハッシュ、および論理積ハッシュは、共有メモリ５１０に記憶することができるので、いくつかの照合処理は、同時にハッシュ・コンテンツを読み取ることができる。クエリ・ハッシュおよび論理積ハッシュは、プライベート・メモリ５１６に対応するテーブルを有する。プライベート・クエリ・ハッシュ６２６は、クエリＩＤコラム６２９におけるクエリが、入ってくる情報コンテンツと合致するとき示すための処理中に使用される、合致コラム６２８を含む。プライベート論理積ハッシュ６３０は、各論理積に関して、入ってくる情報コンテンツに見られるキーワードの数を追跡するための処理中に使用される、Ｅｖａｌカウンタ・コラム６３２を含む。プライベート・メモリにおける記録は、各処理の実行に対してローカルである状態情報を含むので、本発明の実行中に使用中のいくつかのプライベート・メモリを有することができる。
【００５２】
各照合処理は、マスタ・クエリに対する、入ってくるドキュメントとの照合を実行し、および照合中に、その関連するプライベート・メモリに情報を記憶する。照合プロセッサのスループットを増加させるために、複数の照合処理が、同時に実行されうる。この場合、各処理は、そのプライベート・メモリを、共有不可能状態情報に関して使用する。
【００５３】
サーチ・プロセッシング（キーワードおよび句照合）
図７は、本発明に従って、入ってくる情報コンテンツを探索するための探索方法７００を示す。入ってくる各ドキュメントに関する照合処理を開始するとき、プライベート・クエリ・ハッシュ６２６およびプライベート論理積ハッシュ６３０は、以下の方法で作成される：
−  プライベート・メモリ作成中の変更を防止するために、クエリ・ハッシュ・テーブル５０４をリード・ロック（read lock）する；
−  すべてのクエリを繰り返し、および各論理積に関して、プライベート論理積ハッシュ６３０を作成する；および
−  クエリ・ハッシュ５０４のリード・ロックを解除する。
【００５４】
プライベート・メモリを作成した後、図７に記載の探索方法は、すべてのユーザ・クエリを、入ってくる情報コンテンツの各ドキュメントと照合するために使用される。
【００５５】
ブロック７０２において、探索方法７００は、例えば、リアル・タイム気象報告またはオークション情報に関するドキュメントのストリームを具備してもよい情報コンテンツを受信することによって開始する。ブロック７０４において、入ってくるドキュメントは、重複する単語を除去するために、フィルタにかけられる。ブロック７０６において、EvalCounter６３２は、すべてのクエリ論理積エントリに関して０に設定され、合致フラグ６２８は、すべてのクエリに関して０に設定される。
【００５６】
ブロック７０８において、照合されるべき単語がまだあるか決定するための検査がされる。この検査は、ドキュメント全体が検査された状態を決定し、検査されるべき単語がない場合、ブロック７１０へと分岐し、その内容は後述される。
【００５７】
ブロック７１２においては、照合のために、フィルタにかけられたドキュメントから単語を検索する。ブロック７１４においては、検索された単語が、単語ハッシュ・テーブル５０６にあるか決定するための検査が実行される。前記単語が、単語ハッシュ・テーブルにない場合、前記方法は、次の単語を探すために、ブロック７０８へと進む。前記単語が単語ハッシュ・テーブルにあった場合、前記方法はブロック７３６へと進む。
【００５８】
ブロック７３６において、前記キーワードが句の一部であるかを決定するための検査が実行される。キーワードと関連するmaxphraselengthパラメータが０である場合、前記キーワードは句の一部ではなく、前記方法はブロック７１６へと進む。Maxphraselengthが０より大きい場合、前記キーワードは句の一部であり、前記方法はブロック７３８へと進む。
【００５９】
ブロック７３８において、句は、現在のキーワードから開始し、前記句が前記キーワードと関連するmaxphraselengthと等しい長さを有するまで、追加の単語を含むことによって、本来の、フィルタにかけられていないドキュメントから構築される。前記方法はそれから、ブロック７４０へと進む。
【００６０】
ブロック７４０においては、新しく構築された句は、ブロック７１２において、フィルタにかけられたドキュメントから検索された単語に代わる。前記方法はそれから、ブロック７１４へと進み、そこでは、そのブロックにおけるテストによって、前記句が、キーワード・ハッシュにあるか決定される。前記句が見つかった場合、関連するmaxphraselengthは０になり、前記方法は、ブロック７３６におけるテストを通過して、ブロック７１６へと進む。
【００６１】
ブロック７１６において、キーワード（または句）と関連する論理積ポインタ・リスト６０６における第一のエントリが検索される。ブロック７１８において、論理積ポインタと関連するＮＯＴフラグが検査される。ｎｏｔフラグが設定されている場合、前記方法は、ブロック７２０へと進み、そこでは論理積に関するＥｖａｌカウンタ・エントリが、２５５に設定される。このことは、この論理積が合致しなかったことを示す。
【００６２】
ブロック７２２においては、論理積と関連するＮＯＴフラグが設定されていない場合、Ｅｖａｌカウンタは１増加し、それはキーワードと論理積との間に合致が生じたことを示す。
【００６３】
ブロック７２４において、キーワードと関連する論理積エントリがさらにあるかを決定するための検査が実行される。さらなる論理積エントリがない場合は、前記方法はブロック７０８へと進み、ドキュメントにおける次の単語を検索する。追加の論理積エントリがある場合、前記方法はブロック７１６へと進み、リストにおける次のエントリを入手する。受信されたアーティクルにおける単語、または各単語に関して、当該単語がキーワード・ハッシュ・テーブルにあるか決定するための検査が実行される。
【００６４】
ブロック７１０においては、ドキュメントにおける各単語が照合処理を通過した後、前記方法はここでその結果を解析するために進む。このブロックにおいて、選択されたクエリと関連する選択された論理積に関する論理積Ｅｖａｌカウンタおよびデフォルト値が検索される。例えば、クエリ・ハッシュ・テーブルにおけるｑｕｅｒｙ１を参照すると、論理積Ｑｕｅｒｙ１＿Ｃｏｎｊ１に関するＥｖａｌカウンタおよびデフォルト・カウンタが検索される。
【００６５】
ブロック７２６において、Ｅｖａｌカウンタがカウンタ・デフォルトに等しいか決定するための検査が実行される。Ｅｖａｌカウンタがカウンタ・デフォルトに等しくない場合、論理積は満足されておらず、前記方法はブロック７３０に進む。Ｅｖａｌカウンタがカウント・デフォルトと合致する場合、論理積は満足されており、前記方法はブロック７２８へと進む。
【００６６】
ブロック７２８において、論理積によって特定されるキーワードは、ドキュメントにおいて合致したので、クエリに関する合致フラグは１に設定される。このように、クエリは、ドキュメントにおける情報に合致する、少なくとも一つの論理積を有する。前記方法はそれから、ブロック７３２に進む。
【００６７】
ブロック７３０において、Ｅｖａｌカウンタがデフォルト・カウンタに合致しなかった場合、さらなる論理積が現在のクエリと関連しているか決定するための検査が実行される。検査されるべき論理積がさらにある場合、前記方法はブロック７１０へと進み、これらの論理積を検査する。クエリと関連する論理積がさらにない場合は、前記方法はブロック７３２へと進み、他のクエリを処理する。
【００６８】
ブロック７３２において、検査されるべき追加のクエリがあるか決定するための検査が実行される。検査されるべき追加のクエリがあれば、前記方法はブロック７１０に進む。すべてのクエリが検査されていた場合、前記方法はブロック７３４へと進む。
【００６９】
ブロック７３４において、１に等しい照合値を有するクエリを有するユーザに、通知メッセージが送信される。前記通知は、本明細書の他の章で説明されたとおり、通知規則によって要求されるように迅速にしたり、遅延させたりすることができる。
【００７０】
正確な数字照合
ユーザ・クエリが、特定の範囲内にある価格の代わりに、正確な価格を探索するときに、正確な数字照合が使用されうる。一つの実施形態において、分類されたリストが、正確な数字照合に使用される。前記リストが小さい順に分類されている場合、所望の正確な値（ほとんどの場合、その値は価格であろう）を見つけたときに、警告をするよう登録したすべてのユーザを判断するために、最初から前記リストを通過することは簡単である。大きな、分類されたリストに関する問題は、クエリが追加されたり除去されたりすると、ＩＮＳＥＲＴおよびＤＥＬＥＴＥオペレーションが、計算上高価になることである。
【００７１】
高い計算コストについての問題を軽減するために、データ・ツリー構造が使用される。ｈの高さを有するバイナリ・サーチ・ツリー（binary search tree）は、Ｏ（ｈ）時間で、基本セット・オペレーション−ＩＮＳＥＲＴおよび
ＤＥＬＥＴＥ等−のどれかを実行することができる。前記サーチ・ツリーの高さが小さい場合、セット・オペレーションは迅速であるが、前記サーチ・ツリーの高さが小さい場合、それらの性能はリンクされたリストに劣るかもしれない。
【００７２】
赤−黒ツリーは、基本セット・オペレーションが、最悪の場合に、
Ｏ（ｌｏｇ  ｎ）時間かかることを保証するために「バランスがとれた」、多くのサーチ・ツリーの一つである。赤−黒ツリーは、１ノード――その色であり、赤でも黒でもよい――につき、余分な１ビットを有するバイナリ・サーチ・ツリーである。根から葉へのあらゆるパスで、ノードが色付けられる方法を抑制することによって、赤−黒ツリーは、他の２倍以上長いパスはないことを確証するので、前記ツリーはほぼバランスがとれている。
【００７３】
本発明の一つの実施形態において、ConjunctionPointerList６０６を規制し、および維持するために、赤−黒ツリーが使用される。赤−黒ツリーは、あらゆる値（価格）に関して周囲の区間のセットを戻すことができ、および上述の方法７００の実行中、プライベートConjunctionsHashにおけるEvalcounter変数６３２は、合致が生じるときに増加することができる。
【００７４】
自動中止警告
一つの実施形態においては、通知警告は、それらが作動した後、一定期間、中止されてもよい。例えば、ＸＹＺ＞８０に関する株価警告は、前記株式がある特定の日に最初に８０ドルを超える価格で取引された後、中止される必要があるであろう。ユーザは、価格が８０ドルを超えたままである場合、その取引日の残りの時間、繰り返し警告されたくないであろう。この場合、警告は、それが作動した後、その取引日の残りの時間中、中止される。
【００７５】
自動削除警告
一つの実施形態において、通知警告は、警告が作動した後、除去される。例えば、「映画カサ・ブランカがＤＶＤで発売されたら警告せよ」等のサーチ・クエリが、ほんの一時的に生じるであろう。そのため、通知警告は、前記警告が作動した後は必要ない。この場合、警告を作動させる結果、前記システムからの警告を除去するための動作をする。
【００７６】
入ってくるアーティクルを索引付けする
サーチ・エンジンの照合性能をさらに向上させるために、本発明に含まれる一つの実施形態は、入ってくるアーティクルを、あらかじめ編成されたセットに索引付けし、それは次の方法で処理されうる。一組のｎアーティクル（Ａ１からＡ４の、４つのアーティクル）が集められる。アーティクルのセットにおける各単語は、長さｎを有するビット・ベクトルを割り当てられる。前記ビット・ベクトルに一つのビットが設定されるとき、特定の単語が対応するアーティクルに存在する。前記ビット・ベクトルは、探索方法７００が実行される前に、初期化される。キーワード・ハッシュ・テーブルにおけるキーワード・エントリが、個別の単語に関するビット・ベクトルへの追加的ポインタを有するように、キーボード・ハッシュ・テーブル５０６における他のコラムが含まれる。
【００７７】
方法７００が実行された後、単一のユーザに戻される必要があるドキュメントのセットを決定するために、さらに一つの追加的ステップが必要となる。その個別のCounterdefaultに等しいEvalcounterを有するすべてのConjunctionIDに関して、論理積におけるすべてのキーワードに関するビットベクトルへのポインタを入手するために、WordPointerListポインタに従う。すべてのビットベクトルは、論理積と合致したすべてのアーティクルのビットマスク（bitmask）を生成するためにＡＮＤで結ばれる。
【００７８】
例えば、４つのアーティクルを索引付けするために、次の二つのクエリを検討する：
ＣｏｎｊＩｄ１＝ｂｌｕｅ  ＡＮＤ  ｂｌａｃｋ
ＣｏｎｊＩｄ２＝ｓｕｎｎｙｖａｌｅ  ＡＮＤ  Ｒｅｎｔ＿６００
アーティクルの集まりにおける各単語に関するビットベクトルは、次のように表現することができる：
0004593855.tif 000002
上記に基づいて、キーワード・ハッシュ・テーブルは、次の情報を含むであろうドキュメント・ビット・ベクトル・ポインタ・コラムを含むであろう。
キーワード・ハッシュ・テーブル
キーワード DocumentBitvectorPtr ConjunctionsPointerList
ｂｌｕｅ            ００１１                ＣｏｎｊＩｄ１
ｂｌａｃｋ          １０１０                ＣｏｎｊＩｄ１
ｓｕｎｎｙｖａｌｅ  ０１１０                ＣｏｎｊＩｄ２
ｒｅｎｔ＿６００    ＮＵＬＬ                ＣｏｎｊＩｄ２
【００７９】
キーワード「青」および「黒」が探索される場合、対応するビット・ベクトルをＡＮＤで結合させることによって、アーティクル３が両方を含むことを決定することができ、そのためクエリへの合致を提示することができる。そのため、上述のアーティクル索引付けによって、複数のアーティクルが同時に編成され、および探索されることができ、それによって処理コストを低減させる。
例：ショッピング／案内広告／オークション
ユーザ・インターフェース
ほとんどの場合、本発明の実施形態において使用されるブール・クエリ言語は、ユーザが一組のあらかじめ定義された選択肢から選択するＨＴＭＬ形式によって隠されるかもしれない。代替的には、継続的クエリは、ユーザが入った通常のサーチ・クエリから、またはユーザが現在ブラウズしているカテゴリから引き出すことができる。
【００８０】
コンピュータのショッピング
コンピュータ・カテゴリに関するＨＴＭＬインターフェースは、次の属性を有してもよい：
銘柄：ＸＸＸ，ＹＹＹ，ＺＺＺ，ＸＹＺ，ＹＹＺ，ＺＺＸ
プロセッサ（最小）：４８６、Ｐｅｎｔｉｕｍ，Ｐｅｎｔｉｕｍ  Ｐｒｏ
最低価格：  ８００，１０００，１２００，１４００
最高価格：  ８００，１０００，１２００，１４００
メモリ（最小）：８，１６，３２，４８，６４，１２８
ハードディスク（最小）：１，１．５，２，３，４，６，８
ＣＤＲｏｍ（最小）：２ｘ、４ｘ、６ｘ、８ｘ、１０ｘ
ＤＶＤ（最小）：２ｘ、４ｘ、６ｘ、８ｘ、１０ｘ
モデム（最小）：１４．４，１９．２，２８．８，３３．６，５６
上述の情報から、サーチ・クエリが生成されうる。例えば、ユーザが、１２００ドル乃至１４００ドルの価格帯で、少なくともＰｅｎｔｉｕｍプロセッサを有するＸＸＸコンピュータを探している場合、ＨＴＭＬクエリ・システムは、次のクエリを生成するであろう：
Shopping_Computer AND Brand_XXX AND Proc_Pentium AND
ShopPrice_above_1200;
Shopping_Computer AND Brand_XXX AND Proc_Pentium AND
ShopPrice_below_1400;
Shopping_Computer AND Brand_XXX AND Proc_PentiumPro AND
ShopPrice_above_1200;
Shopping_Computer AND Brand_XXX AND Proc_PentiumPro AND
ShopPrice_below_1400.
【００８１】
案内広告
案内広告は、自動車の型、モデル、場所、電話地域コード、価格帯、年、マイレージ、（所有者／ディーラー）による販売等、価格以外の属性を含んでもよい。これらの他の属性に対応するために、通知エンジンの実施形態によって、“２０００ドル乃至５０００ドルの価格帯で、湾岸地域にある車を探せ”等のクエリを次のように処理することができる：
Classifieds_Car AND Location_CA_SFO AND CarPrice_above_2000
Classifieds_Car AND Location_CA_SFO AND CarPrice_below_5000
【００８２】
オークション
オークションは、正確な数字照合を適用するのに好適である。正確な数字照合を用いて、ユーザの現在のつけ値より高い値がついた場合に、すぐに通知することができる。例えば、付け値が超えられたと自動的に決定するためのクエリを、例えば以下のように構築することができる：
Auction_Toy AND blue AND eye AND furby AND CurrentBid>51.75
上述の説明は、例示的であり、制限的ではない。本発明の多くの変更が、この開示を検討することによって、当業者に明らかになるであろう。ゆえに、本発明の範囲は、上述の説明を参照することで決定されるのではなく、その代わりに、特許請求の範囲を、その関連のすべての範囲とともに参照することによって、決定されるべきである。
【図面の簡単な説明】
【図１】  図１は、本発明に従ったサーチ・エンジンを含むデータ網の一部を示す。
【図２】  図２は、図１に記載のサーチ・エンジンの詳細なブロック図を示す。
【図３】   図３は、本発明に従った図２に記載のサーチ・エンジンの動作方法を示す。
【図４】  図４は、本発明に従って構築されたユーザ・プロファイルを示す。
【図５】  図５は、本発明に従って構築されたサーチ・プロセッサの詳細な図を示す。
【図６】  図６は、本発明に従って作成されたハッシュ・テーブルを示す。
【図７】  図７は、本発明に従った図２に記載のサーチ・エンジンの動作方法を示す。
【図１】
0004593855.tif 000003
【図２】
0004593855.tif 000004
【図３】
0004593855.tif 000005
【図４】
0004593855.tif 000006
【図５】
0004593855.tif 000007
【図６】
0004593855.tif 000008
【図７】
0004593855.tif 000009