(57)【特許請求の範囲】
【請求項１】
パケットベースのメディア番組で１つまたは複数の時間帯にレンダリングする広告をスケジューリングするための広告プロセッサによって行われる方法であって、
（ａ）少なくとも１人のユーザに対応する１つまたは複数のインターネットセッションから少なくとも１つのキーワードを取得するステップと、
（ｂ）１つまたは複数の時間帯に使用可能な複数の広告に対応する複数の入札額を受信するステップと、
（ｃ）入札額の少なくとも１つに基づいて、１つまたは複数の時間帯に少なくとも１人のユーザにレンダリングされる、少なくとも１つのキーワードに関する広告をスケジューリングするステップとを含み、スケジューリングが入札収益を最大化するように実施される、方法。
【請求項２】
インターネットセッションが検索エンジンセッションであり、少なくとも１つのキーワードが、少なくとも１人のユーザによって検索エンジンに提供されたキーワードである、請求項１に記載の発明。
【請求項３】
少なくとも１つのキーワードが、検索エンジン宛てのトラフィックを検査することによって得られる、請求項２に記載の発明。
【請求項４】
少なくとも１つのキーワードが、少なくとも１人のユーザによって視聴されたウェブページのコンテンツを検査することによって得られる、請求項１に記載の発明。
【請求項５】
ステップ（ｃ）のスケジューリングが、少なくとも１人のユーザの視聴習慣を反映する履歴データにさらに基づく、請求項１に記載の発明。
【請求項６】
請求項１から５のいずれかに記載の方法を実施するように構成された装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、インターネットプロトコルテレビ（ＩＰＴＶ：Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  Ｔｅｌｅｖｉｓｉｏｎ）に関し、より詳細には、ＩＰＴＶシステムまたは別のパケットベースメディア配信システム内で広告を配置する方式に関する。
【背景技術】
【０００２】
ＩＰＴＶは、パケット化されたビデオサービスをブロードバンドネットワークを介して配信する複数のサービス提供を表すのに用いられる用語である。こうしたビデオサービスは、従来の放送テレビを模倣する多重チャンネルビデオサービス（スイッチドデジタルビデオ）、生のビデオオンデマンド（ＶｏＤ：ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ）、および完全にインタラクティブかつ／または拡張型のビデオサービスを含んでよい。典型的なサービス拡張は、たとえばロバストなプログラム情報、選択およびナビゲーション、ならびにマルチカメラアングル、統合デジタルビデオ録画機能、およびデータサービスと電話サービスのビデオ体験への統合を含む。
【０００３】
ＩＰＴＶプラットフォームは、複数のブロードキャストチャンネルを介してテレビコンテンツをエンドユーザにストリーミングし、またオンデマンドチャンネルを介してＶｏＤストアからエンドユーザにオンデマンドビデオコンテンツをストリーミングするための管理ソフトウェアを含む。視聴され得るＴＶまたはビデオコンテンツは、視聴および録画するビデオ番組をエンドユーザが選択することをさらに可能にする電子番組ガイドによってアクセスされ得る。
【０００４】
従来のテレビ放送の領域では、広告は、特定のチャンネルのテレビ番組の間に、特定の時間帯に配置するように選択され、これらの広告は、視聴者の地理的な位置、テレビ番組の内容、およびテレビ番組の視聴率を含めて、他の要因に基づいて配置するようにさらに選択されてよい。しかし、大きい視聴者グループは、個々の視聴者の個人的な嗜好または特定の興味に関係なく、結局は全員が必然的に同じ広告を見ることになる。ＩＰＴＶの領域では、個々のユーザの嗜好に合うように広告をカスタマイズし、したがってこうした広告をその効果を向上させ最適化するようにターゲティングおよびパーソナライズできることが望ましい。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｃｏｒｍｅｎら、「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ａｌｇｏｒｉｔｈｍｓ」（３版、１９９１年）、６００−６０４頁
【発明の概要】
【課題を解決するための手段】
【０００６】
本発明の実施形態は、ＩＰＴＶサービスプロバイダの広告収益を最大化しながら、視聴者に最も適した広告を配置するためにキーワードベースの広告入札モデルを使用する。
【０００７】
本発明の一実施形態では、パケットベースのメディア番組で１つまたは複数の時間帯にレンダリングする広告をスケジューリングするための方法が：（ａ）少なくとも１人のユーザに対応する１つまたは複数のインターネットセッションから少なくとも１つのキーワードを取得するステップと、（ｂ）１つまたは複数の時間帯に使用可能な複数の広告に対応する複数の入札額を受信するステップと、（ｃ）少なくとも１つのキーワード、および入札額のうちの少なくとも１つに基づいて、１つまたは複数の時間帯に少なくとも１人のユーザにレンダリングされる広告をスケジューリングするステップとを含む。
【０００８】
本発明の別の実施形態では、パケットベースのメディア番組で１つまたは複数の時間帯にレンダリングする広告をスケジューリングするためのシステムが、（ｉ）インターネットに接続されたコンピュータと、（ｉｉ）プロセッサとを含む。プロセッサは、（ａ）少なくとも１人のユーザに対応するコンピュータ上で１つまたは複数のインターネットセッションから少なくとも１つのキーワードを取得し、（ｂ）１つまたは複数の時間帯に使用可能な複数の広告に対応する複数の入札額を受信し、（ｃ）少なくとも１つのキーワード、および入札額のうちの少なくとも１つに基づいて、１つまたは複数の時間帯に少なくとも１人のユーザにレンダリングされる広告をスケジューリングするように構成される。
【図面の簡単な説明】
【０００９】
【図１】ＩＰＴＶサービスとインターネットサービスが同じサービスプロバイダによって提供される例示的なホームネットワークのブロック図である。
【図２】ＩＰＴＶサービスとインターネットサービスがそれぞれ異なるサービスプロバイダによって提供される例示的なホームネットワークのブロック図である。
【図３】ＩＰＴＶサービス内のプロファイル作成およびターゲティングされた広告挿入のための例示的なフレームワークのブロック図である。
【図４】本発明の一実施形態による、例示的な完全パーソナル化アルゴリズムの流れ図である。
【図５】本発明の一実施形態による、第１の例示的な部分パーソナル化アルゴリズムの流れ図である。
【図６】本発明の一実施形態による、第２の例示的な部分パーソナル化アルゴリズムの流れ図である。
【図７】本発明の一実施形態による、例示的な先読みスケジューリングアルゴリズムの流れ図である。
【発明を実施するための形態】
【００１０】
ＩＰＴＶサービス内でターゲティングおよびパーソナライズ化された広告を表示することは、視聴者の関心に基づいて、それぞれ異なる視聴者のために異なる広告をリアルタイムにまたは事前に選択することを伴う。問題は、最も関連性のある広告が視聴者にリアルタイムに表示され得るように、各視聴者の嗜好をどのように追跡するかとういうことである。
【００１１】
ＩＰＴＶ視聴者への広告をターゲティングする一方法では、視聴者プロファイルが、個々の視聴者ごとに生成される。このプロファイルは、たとえば視聴者のＴＶ視聴習慣履歴に基づいて生成されてよい。このシナリオでは、所与の視聴セッション履歴データは、たとえば、視聴者が見るＴＶ番組の識別情報、これらのＴＶ番組の日時、および視聴セッション内の視聴者の相互作用（たとえば視聴者が特定の広告を見たか、それとも別のチャンネルに切り換えたか、視聴者がＴＶ番組を最後まで見たかどうかなど）を含めた情報を含んでよい。視聴者のプロファイルは、こうした情報が使用可能になるので、各視聴セッションの視聴セッションデータ履歴で強化される。広告は、プロファイルおよびセッションコンテキストデータ履歴（たとえば時刻）に基づいて挿入される。
【００１２】
しかし、視聴者のＴＶ視聴習慣だけから構成されたプロファイルは、視聴者の真の関心を必ずしも反映しない。これは、所定の時間の間に得られるＴＶ番組にＴＶ視聴が制限されており、視聴者の望む任意の主題の任意の番組を視聴者が選ぶ自由がないということによる。
【００１３】
別法として、またはさらに、視聴者によって提供される人口調査が、視聴者プロファイルの強化のために使用されてよい。しかし、視聴者によって提供される人口調査は、得ることが難しい場合が多く、広範な傾向があり、視聴者の関心が時間と共に変化するので容易には更新され得ない。
【００１４】
そうではなく、インターネットの閲覧によって、事実上すべての主題を網羅し、事実上いつでも入手可能な巨大な情報一覧から視聴者がいつでも任意の情報を見ることを選ぶことができるので、視聴者の関心は、視聴者がインターネットを使用するやり方を観察することからよりよく理解され得る。インターネットナビゲーションで最も一般的なやり方は、関心のある所与の主題に関して入手可能な情報を見つけるのに検索エンジン、たとえばＧｏｏｇｌｅ（ｈｔｔｐ：／／ｗｗｗ．ｇｏｏｇｌｅ．ｃｏｍ）やＹａｈｏｏ（ｈｔｔｐ：／／ｗｗｗ．ｙａｈｏｏ．ｃｏｍ）を使用することである。視聴者は、主題について関連するキーワードを入力し、次いで検索エンジンは、主題に関し得るウェブサイトのリストを返す。視聴者が検索エンジンへの入力として提供するキーワードを使用して視聴者のインターネット検索パターンを追跡し、後にキーワードをマイニングすることによって、視聴者の関心に関する表示がリアルタイムに取得され得る。
【００１５】
したがって、本発明の実施形態は、視聴者のインターネット使用を追跡することによって視聴者のプロファイルをリアルタイムに強化するための解決策を提供する。たとえば、視聴者がインターネット上で車について検索している場合には、そのすぐ後に自動車関連の広告を視聴者に示すことは関連性があるということが分かる。本発明の実施形態による方法は、インターネットを検索する間に視聴者が入力するキーワードの収集を伴う。これらのキーワードは、視聴者のテレビ視聴習慣履歴を用いて強化され、より正確な視聴者プロファイルを生成し、この視聴者プロファイルは、ＩＰＴＶサービスの広告をターゲティングするために使用されてよい。さらに、検索キーワードをリアルタイムに追跡することによって、視聴者の最近の関心に一致する広告を視聴者のために配置することができ、広告がより関連性のある効果的なものになる。
【００１６】
視聴者がインターネットに入力する検索キーワードをリアルタイムに収集するための様々な方法が、ＩＰＴＶサービスプロバイダによって使用され得る。キーワード収集方法の選択は、たとえば視聴者がＩＰＴＶサービス用に使用するサービスプロバイダの数および／またはタイプ、視聴者がインターネットサービス用に使用するサービスプロバイダの数および／またはタイプ、ならびに視聴者によって使用された１つまたは複数のインターネット検索エンジンの操作上の詳細を含めて、１つまたは複数の要因に依存することがある。
【００１７】
キーワード収集のための第１の例示的な方法について、図１を参照して次に述べられ、この図１は、ＩＰＴＶサービスおよびインターネットサービスがインターネット／ＩＰＴＶネットワークの組合せにより同じサービスプロバイダによって提供されている例示的なホームネットワーク１００のブロック図を示している。ホームネットワーク１００は、テレビジョン（ＴＶ）１０２と、コンピュータ１０３と、ホームゲートウェイ１０１とを含み、このゲートウェイ１０１を介して、ＩＰＴＶサービスとインターネットサービスの両方がホームネットワーク１００に入る。ホームゲートウェイ１０１は、インターネット／ＩＰＴＶネットワークからＴＶ１０２にＩＰＴＶトラフィックのパケットをルーティングし、インターネット／ＩＰＴＶネットワークとコンピュータ１０３との間でインターネットトラフィックのパケットを双方向にルーティングする。
【００１８】
ホームゲートウェイ１０１は、１つまたは複数の検索エンジン（たとえばＧｏｏｇｌｅやＹａｈｏｏ）宛てのすべてのウェブトラフィックを検査するパケットスヌーピングモジュール１０４を含む。パケットスヌーピングモジュール１０４は、いずれかの検索エンジンに宛てられたトラフィック、あるいはパケットスヌーピングモジュール１０４によって、たとえばＩＰアドレスで識別される１つまたは複数の特定の検索エンジンに宛てられたトラフィックを検査するように構成されてよい。
【００１９】
レイヤ４スイッチは、特定のタイプのアプリケーショントラフィック、たとえばハイパーテキストトランスポートプロトコル（ＨＴＴＰ：ｈｙｐｅｒｔｅｘｔ  ｔｒａｎｓｐｏｒｔ  ｐｒｏｔｏｃｏｌ）や電子メールを識別することができるが、それを作成したアプリケーションまたはユーザによってトラフィックを分類することはできない。しかし、パケットスヌーピングモジュール１０４でレイヤ７スイッチを使用することによって、特定のアプリケーション層基準を使用して転送決定が行われ得る。レイヤ７スイッチは望ましくは、レイヤ２やレイヤ３だけでなく、トランスポート層（レイヤ４）でも、アプリケーション層（レイヤ７）に至るまでパケットヘッダコンテンツの有線高速処理を実施する。レイヤ７スイッチは、レイヤ７情報を使用してレイヤ２速度でトラフィックを転送することによって、ルーティングとスイッチングを統合する。レイヤ７スイッチを使用すると、特定のトラフィッククラス、たとえばトランスポート制御プロトコル（ＴＣＰ：ｔｒａｎｓｐｏｒｔ−ｃｏｎｔｒｏｌ  ｐｒｏｔｏｃｏｌ）宛先ポート８０を通るトラフィックに属するパケットをさらに検査することが可能となり、したがって、視聴者によって検索エンジンへの入力として提供されたキーワードが取得され得る。
【００２０】
こうした機能は、こうしたシステムが既にホームゲートウェイ１０１にインストールされている場合、既存の侵入検出システム（たとえば「スノート（ｓｎｏｒｔ）」として知られている侵入検出システム）に追加されてよい。このシナリオでは、検索エンジン宛てのポート８０トラフィックを検査し、ペイロードからキーワードを抽出するスノート内に規則が追加される。
【００２１】
これらのキーワードはリアルタイムで、サービスプロバイダによって維持されたソフトウェアモジュールに供給され、このサービスプロバイダは、下記にさらに詳細に論じられるように、視聴者のプロファイルを構築する。次いで、この情報は、その時に視聴者にとって最も関連性のある広告を見つけるために使用されてよい。サービスプロバイダがホームゲートウェイ内でパケットスヌーピング機能を提供できない、または提供しようとしない場合には、別法として、プロバイダのネットワーク内のアップストリームネットワークノードのうちの１つ（たとえばルータ）内に、視聴者によって生成されたインターネットトラフィックが常にそのノードを通過すると見なして、同じ機能が実装されてよい。
【００２２】
キーワード収集の第１の方法は、サービスプロバイダと検索エンジンプロバイダの間の事前の取決めまたは合意を必要としないが、検索エンジンプロバイダが、パケットスヌーピングが不可能となるように、ユーザから検索キーワードを受信するのにＴＣＰではなく安全なセッション（たとえば、セキュアソケットレイヤ（ＳＳＬ：ｓｅｃｕｒｅ−ｓｏｃｋｅｔ  ｌａｙｅｒ））を使用する場合には、この方法が働かないことがあることに留意されたい。検索ベンダが検索項目の入力のために安全なセッションを使用する場合、またはＩＰＴＶサービスプロバイダとインターネットサービスプロバイダがそれぞれ異なる場合、ＩＰＴＶとインターネット検索のトラフィックフローは、それぞれ異なる経路をたどる。
【００２３】
キーワード収集のための第２の例示的な方法について、図２を参照して次に述べられ、この図２は、ＩＰＴＶサービスおよびインターネットサービスがそれぞれ異なるサービスプロバイダによって提供され、したがってそれぞれ異なる経路をたどる例示的なホームネットワーク２００のブロック図を示している。ホームネットワーク２００は、ＴＶ２０２にＩＰＴＶサービスを提供するセットトップボックス（ＳＴＢ：ｓｅｔ−ｔｏｐ  ｂｏｘ）２０１と、コンピュータ２０３にインターネットサービスを提供するモデム２０４とを含む。ＳＴＢ  ２０１は、ＩＰＴＶヘッドエンド２０５とパケットを交換することによってＩＰＴＶネットワークを介して通信し、モデム２０４は、検索エンジン２０６（たとえばＧｏｏｇｌｅや  Ｙａｈｏｏ）とパケットを交換することによってインターネットを介して通信し、この検索エンジン２０６によりインターネット検索が実施される。この構成では、ＩＰＴＶサービスプロバイダは、視聴者プロファイルの作成の際に使用するＩＰＴＶ加入者の検索キーワードを取得するために検索サービス２０６の事業者との何らかの合意を有する。示されたように、キーワードは、検索サービス２０６によって、ネットワーク（たとえばインターネット）を介してＩＰＴＶヘッドエンド２０５に提供される。
【００２４】
キーワードの収集は、従来の検索エンジン（たとえばＧｏｏｇｌｅおよびＹａｈｏｏ）だけでなく、オンラインショッピングサイト（たとえばＡｍａｚｏｎおよびｅＢａｙ）、旅行予約サイト（たとえばＥｘｐｅｄｉａおよびＴｒａｖｅｌｏｃｉｔｙ）、ならびにユーザが入力としてキーワードを提供する他のタイプのウェブサイトに入力されたキーワードについても行われ得ることを理解されたい。したがって、本明細書では用語「検索エンジン」は、キーワードがそこから収集され得る任意のウェブサイトを含むように広く解釈されるべきであり、また従来の検索エンジン、たとえば  ＧｏｏｇｌｅおよびＹａｈｏｏに限定されるべきではない。
【００２５】
別法として、またはさらに、キーワードは、ユーザが自身のキーワードの検索も入力も実施しない場合でも、ユーザが訪問するウェブサイトのコンテンツに現れるテキスト、メタタグまたは他のデータから抽出され得る。たとえば、ユーザが犬に関するウェブサイトを見ている場合、キーワード「犬」は、たとえば単語「犬」がページのタイトル（または他のフィールド）に現れ、または高頻度でページ上に現れるサイトのハイパーテキストマークアップ言語（ＨＴＭＬ：  ｈｙｐｅｒｔｅｘｔ−ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）ページからを抽出されてよい。本明細書に具体的には述べられていないキーワード収集の他の方法も実行可能であることが想到される。
【００２６】
ＩＰＴＶ広告をターゲティングする際に使用するインターネット検索キーワードを収集すると、検索キーワードを使用して視聴者プロファイルをリアルタイムに構成し更新することが可能となり、したがって、視聴者の現在の関心が迅速に捕捉され決定され、それによって視聴者の関心により関連したターゲティングされた広告が可能となる。視聴者の側では能動的な関与は不要であり、視聴者のプロファイルは、視聴者がインターネットをブラウズしている間にリアルタイムに構成され更新され得る。
【００２７】
ターゲティングされた広告のためにキーワードを使用することは従来、検索エンジンセッション中に表示される広告に制限されており、この場合、広告主は、様々なキーワードへの入札を行い、各インプレッションについて（すなわち広告主に属する広告をユーザがクリックする各インスタンスについて）検索エンジンプロバイダにお金を払い、検索エンジンは、検索エンジンプロバイダの総収益を最大化しようとするやり方で、検索結果の隣りに表示する広告を選択する。しかし、検索エンジンとＩＰＴＶ広告方式の間には、下記を含めて大きな違いがある。
【００２８】
検索エンジン広告主は、ウェブブラウザ表示ウィンドウ上の事実上無制限の空間を求めて競争するが、ＩＰＴＶ広告主は、視聴者のテレビ画面上の限られた継続時間を求めて競争する。
【００２９】
検索エンジンは、視聴者の検索キーワード入力が完了すると、ターゲティングされた広告を表示するが、ＩＰＴＶは、それぞれ異なる広告が、限られた数の時間帯を求めて争うように、定義された広告時間の間だけ広告を挿入することができる。
【００３０】
検索エンジンは、ユーザが主題に関して問い合わせるときに広告を表示し、したがって、単にそれらの主題に関するキーワードだけに基づいて入札が行われるので十分であるが、ＩＰＴＶでは、広告の入札は、キーワードだけでなく、広告の表示の適時性にも基づくことができる。換言すると、広告が表示されるのがキーワード検索時間に近いほど、広告が視聴者の関心に関して関連性があり、時宜を得ている確率が高くなるので、広告主にとってより適している。また、ＩＰＴＶでは、特定のＴＶセットを特定のチャンネルに合わせているかどうかリアルタイムに決定することが可能になるので、広告を視聴者に対して、または視聴者グループに対してリアルタイムにターゲティングすることができる。
【００３１】
検索エンジンは、広告のターゲティングを向上させるために視聴者の過去の検索を使用することができるが、ＩＰＴＶサービスは、たとえばインターネットグループ管理プロトコル（ＩＧＭＰ：Ｉｎｔｅｒｎｅｔ  Ｇｒｏｕｐ  Ｍａｎａｇｅｍｅｎｔ  Ｐｒｏｔｏｃｏｌ）ログの解析によって観察され得るように、視聴者の視聴習慣履歴に基づいてさらにより適切に広告を選択することができる。
【００３２】
検索エンジンは、個人ユーザに対してしか広告をターゲティングできないが、ＩＰＴＶサービスは、視聴者グループにターゲティングされた広告を作成することを可能にする。これは、ＩＰＴＶ環境内の動的な広告挿入が追加の処理およびネットワークリソースを使用するので、複数の視聴者についての現在チャンネル情報、ならびにネットワークリソース使用可能性を考慮に入れることによって可能である。
【００３３】
上記の違いにより、検索エンジン広告配置の領域の知られている解決策は、ＩＰＴＶ番組内に配置する広告のスケジューリングには適用できない。
【００３４】
したがって、本発明の実施形態は、各広告時間帯および各視聴者についてそれぞれ異なるキーワードを使用して広告主からの広告配置への入札について考慮するＩＰＴＶサービスのための広告選択およびスケジューリングアルゴリズムを提供する。
【００３５】
一実施形態では、キーワードは、たとえば上記の方法のうちの１つを使用して、視聴者から収集される。広告主は、広告配置に使用可能な時間帯、すなわち所与の広告が視聴者に示され得るＴＶ番組が与えられる。ＩＰＴＶサービスプロバイダは、そこからの選択を行う人気のあるキーワードのリストを広告主に提供し、かつ／または広告主は、自身のキーワードを生成し供給する。この情報に基づいて、各広告に対して広告主は、特定キーワードについて時間帯ごとに各視聴者への入札を行う。入札提出プロセスは、オンライン（たとえばインターネットウェブサイトを介して）またはオフラインで行うことができ、またリアルタイムに行われてもよいし、前もって行われてもよい。
【００３６】
広告選択およびスケジューリングアルゴリズムは望ましくは、広告からの収益を最大化するために、互いに異なるサブセットに視聴者を分割し、各サブセットについて広告を示す。所定の時間帯に示され得る異なる広告の数への制約がない（すなわち、同じ時間帯に各視聴者に異なる広告を示すことができる）場合、完全パーソナル化が達成され得る。しかし、実際には、コンピューティングおよびネットワークリソースの制約により、所与の時間帯にほんの数個の異なる広告しか示すことができないことがあり、その場合、異なる広告の最大数が視聴総数未満である部分的なパーソナル化しか達成され得ない。完全パーソナル化と部分パーソナル化の両方のアルゴリズムについて、さらに詳細に以下に述べられる。
【００３７】
図３は、ＩＰＴＶサービス内のプロファイル作成およびターゲティングされた広告挿入に使用され得る例示的なフレームワークのブロック図を示している。示されたように、フレームワークは、ウェブブラウザ３０２によってインターネット検索エンジン上で検索を実施し、ＩＰＴＶシステム３０３上でテレビを見る視聴者３０１のホームネットワークを含む。
【００３８】
図３では、視聴者３０１の外部のものとして現れる要素はすべて、ＩＰＴＶネットワークサービスまたはインターネット検索サービスのいずれかに関連しており、またはその一部であり、視聴者のホームネットワーク内に物理的に常駐することも、常駐しないこともある。図１または図２のアーキテクチャ、あるいは代替アーキテクチャが、図３の実施形態に関連して使用されてよい。
【００３９】
図３は、１人の視聴者３０１しか示していないが、図３のフレームワークは、任意の数の視聴者について類似の同時処理をサポートできることを理解されたい。
【００４０】
視聴者３０１がインターネット検索エンジンに検索キーワードをタイプするとき、キーワード抽出器３０４は、出ていくネットワークパケットを検査し、たとえば図１および２に関して上述された方法のうちの１つを使用して検索キーワードを収集する。
【００４１】
キーワード抽出器３０４は、抽出された検索キーワードを視聴者関心プロファイル発生器３０５に提供し、この視聴者関心プロファイル発生器３０５は、視聴者のプロファイルを維持する。キーワード抽出器３０４は、たとえば視聴者３０１の識別情報、およびキーワードが抽出された時刻および／または日付を含めて、追加の情報を視聴者関心プロファイル発生器３０５に提供することもできる。
【００４２】
視聴者３０１がテレビを見、チャンネルを変更するとき、視聴者がどのチャンネルを見たかに関する情報、および視聴者がそれらのチャンネルを見た時間が、チャンネル使用トラッカ３０６によって収集される。この情報は、たとえばタイムスタンプ付きの参加メッセージおよび退出メッセージを含むＩＧＭＰログの形で、チャンネル使用トラッカ３０６に提供されてよい。
【００４３】
チャンネル参加／退出情報は、視聴者プロファイル発生器３０７によって、（ｉ）視聴者のＴＶがオンかどうかの判定（すなわち短期使用の追跡）、および（ｉｉ）視聴者が何時にどのチャンネル見るか予測するための視聴者モデルの作成（すなわち長期使用の追跡）のために使用される。
【００４４】
視聴者関心プロファイル発生器３０５は、広告プロセッサ３０８に視聴者プロファイルデータを提供し、視聴者チャンネルプロファイル発生器３０７は、広告プロセッサ３０８にチャンネルプロファイルデータを提供し、この広告プロセッサ３０８は、この例示的な実施形態では、広告入札器３０９と広告セレクタ３１０とを含む。
【００４５】
各広告ごとに広告主３１２は、１つまたは複数の特定キーワードについて、複数の時間帯で複数の視聴者への入札を（事前に）行う。本明細書に述べられた本発明の実施形態のために、あらゆる時間帯およびすべての広告が同じ長さをもつと仮定されるが、他の実施形態では、それぞれ異なる長さの広告および時間帯が可能であると想到される。番組内の特定の中断が複数の広告を収容することがあり、したがって、それらの広告をスケジューリングする複数の時間帯を含んでよいことを理解されたい。
【００４６】
広告入札器３０９は、（ｉ）視聴者関心プロファイル発生器３０５からの視聴者プロファイルデータ、（ｉｉ）視聴者チャンネルプロファイル発生器３０７からのチャンネルプロファイルデータ、および（ｉｉｉ）広告主３１２からの入札データを受信する。広告入札器３０９は、キーワードに基づいてそれぞれ異なる広告について視聴者および時間帯への入札を構成し、出し、この入札は、広告セレクタ３１０に提供される。所与の広告への入札は、その広告が、視聴者のインターネットセッションから抽出されたキーワードに一致し、または別のやり方でそれに対応する少なくとも１つのキーワードを有する場合にだけ出される。
【００４７】
これらの入札から、広告セレクタ３１０は、ＩＰＴＶサービスプロバイダに最も多くの収益をもたらす広告を各時間帯ごとに選択するアルゴリズムを使用し、選択された広告の識別情報を広告表示器３１１に供給する。広告セレクタ３１０は、個々の各視聴者が見ているチャンネルについての情報をチャンネル使用トラッカ３０６からリアルタイムに受信することもでき、この情報は、視聴者または視聴者グループへの広告をリアルタイムに出すために使用される。
【００４８】
当技術分野で知られている技法（たとえば広告スプライシング、マルチキャスト広告チャンネルへの切換えなど）を使用して、広告表示器３１１は、ＩＰＴＶシステム３０３によって視聴者に表示し、またはそれぞれのＩＰＴＶシステムによって視聴者グループに表示するために、広告セレクタ３１０による選択対象に識別された広告をレンダリングする。
【００４９】
ターゲティングされた広告配置からのＩＰＴＶサービスプロバイダの収益を最大化する、広告セレクタ３１０によって実施され得る２つの方式について、次に論じられる。第１の方式は、完全パーソナル化のためのものであり、この方式では、広告とチャンネルの組合せの最大数がチャンネル数によって決定付けられ、したがって、同じ時間帯にそれぞれ異なる広告が各視聴者に示され得る。第２の方式は、部分パーソナル化のためのものであり、この方式では、広告とチャンネルの組合せの最大数が、システム制限によって所与の時間帯の間に示されることが許された広告の総数によって決定付けられ、したがって、視聴者がグループに分割され、同じ時間帯に同じ広告が各グループの視聴者に示され、他のグループの視聴者には、その所与の時間帯の間に異なる広告が示される。
【００５０】
完全パーソナル化は、各広告が主要のテレビ番組ストリームにスプライスされるので、比較的に処理集約型であり得る。完全パーソナル化は、視聴者のセットトップボックス、または広告スプライシングを実施するのに十分なリソースを有するアップストリームデジタル加入者線アクセスマルチプレクサ（ＤＳＬＡＭ：ｄｉｇｉｔａｌ  ｓｕｂｓｃｒｉｂｅｒ  ｌｉｎｅ  ａｃｃｅｓｓ  ｍｕｌｔｉｐｌｅｘｅｒ）を使用して、たとえば広告をスプライスすることによって達成され得る。所与の時間帯の間にそれぞれ異なる同時の広告を受信することができる視聴者の数に制限がない場合は、広告は、各個々の視聴者についてパーソナル化されてよい。
【００５１】
完全パーソナル化は、図４の例示的なアルゴリズムなどのアルゴリズムを使用して達成されてよく、このアルゴリズムは、ＩＰＴＶサービスプロバイダの収益を最大化するように広告をスケジューリングする。ｍ個の広告があり、ｉが広告を表し、ｊが視聴者を表し、ｖｉｊが、広告主が所与の広告ｉについて所与の視聴者ｊに対して出す金銭入札を表すと仮定される。
【００５２】
まず、ステップ４０１で、上述されたように、広告主から入札が得られる。次いで、ステップ４０２で、たとえば図１および２に関して上述された方法の１つを使用して、検索キーワードが、複数の視聴者ｊについて得られる。次に、ステップ４０３で、一致する広告についてのみ入札が出され、残りの広告は無視される。次いで、ステップ４０４で、数式
【数１】
0005816611.tif 000002
によって、各視聴者ｊについて選択された広告ａ（ｊ）が得られる。この数式は、ｖｉｊを最大化するｉの値を返し、それによって、最大の金銭価値を有する広告を識別し選択する。次に、ステップ４０５で、数式Ｓ（ｉ）＝｛ｊ：ａ（ｊ）＝ｉ｝によって、各広告ｉについて視聴者のセットＳ（ｉ）が得られ、このセットは、広告ｉが選択された広告ａ（ｊ）であるすべての視聴者ｊを含む。最後に、ステップ４０６で、視聴者のセットＳ（ｉ）について、広告ｉがスケジューリングされる。
【００５３】
部分的なパーソナル化は、ＩＰＴＶサービスプロバイダの収益を最大化するように広告をスケジュールする図５の例示的なアルゴリズムなどのアルゴリズムを使用して達成されてよい。システム内にｍ個の広告およびｎ人の視聴者がおり、ｉが広告を表し、ｊが視聴者を表し、ｖｉｊが、所与の広告ｉについて所与の視聴者ｊに対して広告主が出す金銭入札を表すと仮定される。
【００５４】
スケジューリングを実施すべきＣ個のテレビチャンネルがあり、ｃ（ｊ）が、視聴者ｊが現在見ているチャンネルを表すとも仮定される。この実施形態では、広告がすべてのチャンネル上で同時に示されるように、あるチャンネル上で広告を配置する所与の時間帯が生じるとき、その同じ時間帯が他のすべてのチャンネルで同時に生じ、また同様に、それらの時間帯が生じていないときは、すべてのチャンネル上で同時に非広告番組コンテンツが示されるとさらに仮定される。別法として、この実施形態では、それぞれ異なるチャンネル上で同時に示されている番組は、これらの番組が視聴者に示されている間、番組自体の間にこれらの時間帯が必ずしも同時に生じない場合でも、同じ数の時間帯数を有すると仮定され得る。
【００５５】
部分パーソナル化方式では、所与の時間帯の間、Ｃ個のすべてのチャンネルに渡って最大数Ｋ個の広告が示され得るようにスケジューリングが制限される。このシナリオでは、広告は、Ｃ個のチャンネルのうちの１つまたは複数に示され、アルゴリズムは結局、各時間帯につき、せいぜいＫ個の広告しか選択しない。たとえば、システム内に２０個のチャンネル（ＡからＴ）があり、所与の時間帯の間、システム制限が、これらの２０個のチャンネルに渡って３つの異なる広告だけが同時に示されることを許可する（たとえば、第１の広告が、チャンネルＡおよびＳを見るユーザグループに示され、第２の広告が、チャンネルＢ−ＰおよびＴを見るユーザグループに示され、第３の広告が、チャンネルＱおよびＲを見るユーザグループに示される）場合、Ｋ＝３である。
【００５６】
図５の例示的なアルゴリズムは、すべてのチャンネルに渡って示す広告のセットを選択し、それぞれ異なる広告に視聴者を割り当てる。２分決定変数：広告ｉが所与のチャンネルｇ上に示される場合は１の値、そうでない場合は０の値を有するｙｉｇと、広告ｉが視聴者ｊに示される場合は１の値、そうでない場合は０の値を有するｘｉｊが用いられる。
【００５７】
第１に、ステップ５０１で、上述されたように、広告主から入札が得られる。次いで、ステップ５０２で、たとえば図１および２に関して上述された方法のうちの１つを使用して、検索キーワードが、複数の視聴者ｊについて得られる。次に、ステップ５０３で、一致する広告についてのみ入札が出され、残りの広告は無視される。次いで、ステップ５０４で、現在の時間帯に最適なスケジューリング解を決定するために、以下の整数計画問題が用いられ、ただし、インデックス付け変数として広告インデックスｉ、視聴者インデックスｊ、およびチャンネルインデックスｇが使用される：
【数２】
0005816611.tif 000003
【００５８】
この整数計画問題は、以下の制約に従って、すべての広告ｉおよびすべての視聴者ｊに渡って広告収益を最大化にする。制約（１）は、時間帯の間に何らかの広告が視聴者ｊに示されなければならいことを指定する。制約（２）は、視聴者ｊが現在見ているチャンネルｃ（ｊ）で視聴者ｊに広告ｉが示されなければならいことを指定する。制約（３）は、広告と時間帯の組合せの総数（すなわち所与の時間帯の間に示された一意の広告の総数）がどの時間帯についても広告の最大値Ｋを超えないことを指定する。制約（４）および（５）は、決定変数ｘｉｊおよびｙｉｇが２値であることを指定する。最後に、ステップ５０５で、整数計画問題から得られたスケジューリング解が、現在の時間帯に視聴者への広告をスケジューリングするために使用される。
【００５９】
上記の整数計画問題を使用したスケジューリングではなく、別法として、保証された性能を有するそれほど計算集約型でない組合せアルゴリズムが、部分パーソナル化スケジューリングを実施するために使用されてよい。上記の整数計画問題の解に近似する例示的な貪欲組合せアルゴリズムが、図６の流れ図に示されている。図５のステップ５０４の代わりに使用され得るこのアルゴリズムは、Ｋ回の反復の総数について、アルゴリズムの各反復で最大値を提供する広告と時間帯の組合せを選択する。貪欲アルゴリズムによって行われた割当てを追跡するために、２つのｍベクトルδおよびｕが維持され、だたし、δｊは、視聴者ｊに割り当てられた広告を表し、ｕｊは、この割当ての値（収益に関する）を表す。
【００６０】
このアルゴリズムは、ステップ６０１で開始し、広告と時間帯の組合せの総数Ｍが０に設定され、すべての視聴者ｊについて、ｕｊが０に設定される。ステップ６０２で、Ｍ＜Ｋかどうか判定され、その場合、アルゴリズムはステップ６０４に進む。ステップ６０２で、Ｍ≧Ｋと判定される場合は、アルゴリズムはステップ６０３に進む。ステップ６０４で、広告と時間帯のすべての可能な組合せ（ｉ，ｄ）について、所与の広告ｉを時間帯ｄにスケジューリングすることによって得られた増分収益θｉｄが、
【数３】
0005816611.tif 000004
を使用して計算される。増分収益θｉｄは、時間帯に現在予定されている広告からの収益額を超えた、時間帯ｄ内に広告ｉをスケジューリングすることからの収益額を表す。次に、ステップ６０５で、θｋｆが広告と時間帯のすべての組合せ（ｉ，ｄ）についてθｉｄを超え、すなわちすべての可能な広告から最大増分収益θｉｄを有する広告が選択されるように、チャンネルｆ上で広告ｋが選択される。次いで、ステップ６０６で、Ｍの値が、１だけ増分される。次に、ステップ６０７で、各視聴者ｊについて、視聴者ｊがチャンネルｆを見ている（すなわちｃ（ｊ）＝ｆ）の場合、かつ視聴者ｊに広告ｋを示すことにより得られる収益ｖｋｊが、視聴者ｊに現在割り当てられている広告の収益ｕｊより大きい（すなわち、ｖｋｊ＞ｕｊ）場合には、ｕｊに収益ｖｋｊの値が、またδｊに広告ｋの値が割り当てられ、それによって、新しい広告ｋがさらなる収益をもたらす場合、新しい広告ｋが保存される。ステップ６０７は、これまで選択された広告のすべてうちから最大の収益をもたらす広告を（すなわち、ｕｊをｖｋｊの値に設定することによって）各視聴者ｊに割り当てる。次いで、アルゴリズムは、ステップ６０２に戻る。ステップ６０３で、δｊの値を使用して、現在の時間帯内にすべての視聴者ｊへの広告がスケジューリングされる。
【００６１】
上記アルゴリズムは、視聴者のインターネット検索キーワードに基づいてＩＰＴＶ広告をリアルタイムにスケジューリングするために使用されてよい。しかし、視聴者は、インターネットの閲覧とテレビの視聴を同時に行っていないことがある。このシナリオでは、本発明のいくつの実施形態は、ＩＰＴＶ視聴セッション内の時間帯のために将来使用するインターネット閲覧情報（たとえばキーワード）を格納してよい。
【００６２】
本発明の他の実施形態は、定義された複数の将来の時間帯に広告を前もって配置するために「先読み」するＩＰＴＶ広告スケジューリングシステムを提供することによってこのシナリオに対処する。本発明の１つのこうした実施形態で先読みスケジューリング問題を解決するために、たとえば上記の方法のうちの１つを使用してキーワードが視聴者から収集される。広告主には、先読み計画対象期間（ｔｉｍｅ  ｈｏｒｉｚｏｎ）、すなわち広告配置のための複数の時間帯を含む将来の固定期間、すなわち所与の広告が視聴者に示され得るＴＶ番組が提供される。ＩＰＴＶサービスプロバイダは、そこから選択を行う人気のあるキーワードのリストを広告主に提供し、かつ／または広告主が、それ自体のキーワードを生成し供給する。この情報に基づいて、各広告について、広告主は、計画対象期間のあらゆる時間帯で、特定のキーワードに対して各視聴者への入札を行う。入札提出プロセスは、（たとえばインターネットウェブサイトを介して）オンラインに行われることも、オフラインで行われることもあり、またリアルタイム行われることも、前もって行われることもある。
【００６３】
入札は、いくつかの形をとることができる。たとえば、同じ広告が同じ視聴者に複数回表示されてよく、毎回同じ収益をもたらし、あるいは広告の最初の表示だけは収益をもたらすが、同じ広告の後続の表示はそれより少ない収益を生み、または収益を生まないことが可能であり得る。
【００６４】
先読み時間帯の間、視聴者のテレビジョンがオンかどうか知るやり方がないことに留意されたい。テレビジョンがオンの場合でも、視聴者がその時間帯の間に実際にテレビを見ているかどうか知るやり方は、やはりない。この知られていない情報を明らかにするために、視聴者の統計的なテレビ視聴習慣が、たとえばそれぞれ異なる日からのＩＧＭＰログを解析することによって観察され得る。
【００６５】
先読み広告選択およびスケジューリングは、図７の例示的な動的計画アルゴリズムなどのアルゴリズムを使用して達成されてよく、このアルゴリズムは、単一のチャンネルについて、各視聴者ごとに、ＩＰＴＶサービスプロバイダの期待収益を最大化するように計画対象期間内の各時間帯の広告を選択する。状態空間爆発問題（同時コンポーネントを備えるシステムが、同時コンポーネントの状態数の掛け算により、管理不可能なほど大きい状態数を有する場合に生じる）を回避するために、期待収益の下限を有するワンステップの先読み手順が使用される。次いで、この問題は、２つのノード列を有する２部グラフ上で最大マッチング問題を解決することになる。変数Ａは、すべての広告のセットを表し、ｂａｔが、スケジュールが計算される複数Ｔ個の時間帯を有する計画対象期間内の所与の時間帯ｔについて、広告主が広告ａ∈Ａに対して出す入札を表す。変数Ｓは、配置される適格な広告のセットを表し、ただし、適格な広告は、いずれかの時間帯にいずれかの視聴者に示されるようにまだスケジューリングされていない広告である。
【００６６】
アルゴリズムは、本明細書では「先読み」アルゴリズムと呼ばれるが、実際には各時間帯のまさに最初に実行されて、（ｉ）視聴者がその時間帯の間に視聴しているかどうか、および（ｉｉ）視聴者の過去の視聴習慣に基づいて、その時間帯、および計画対象期間の後続の時間帯に最適な広告スケジュールを絶えず再計算する。
【００６７】
まず、ステップ７０１で、このアルゴリズムは、ｔの値を１、Ｓの値をＡと設定することによって第１の時間帯から開始する。次に、ステップ７０２で、時間帯ｔの最初に、視聴者が現在視聴しているかどうか判定され、その場合、この方法は、ステップ７０３に進んで、時間帯ｔに示される広告をスケジューリングする。ステップ７０２で、時間帯ｔの最初に視聴者が視聴していないと判定される場合は、時間帯ｔの間、広告がスケジューリングされず、アルゴリズムは、ステップ７１１に進む。
【００６８】
ステップ７０３で、広告ａが時間帯ｗ≧ｔに割り当てられる場合の期待収益ｃ（ｗ，ａ）が、ｃ（ｗ，ａ）＝ｂａｗｐ（ｗ｜ｔ）として計算され、ただし、ｐ（ｔ｜ｔ）＝１であり、ｂａｗは、時間帯ｗ内の広告ａへの入札を表す。時間帯ｗの前のある点で発生する時間帯ｔ（すなわち、ｔ＜ｗ）内に視聴者が視聴していたことを考慮すると、式ｐ（ｗ｜ｔ）は、視聴者が時間帯ｗ内に視聴している確率を表し、この確率は、たとえばＩＧＭＰログから抽出された情報を使用して計算され得る。
【００６９】
次に、ステップ７０４で、完全な２部グラフが構成され、ただし、グラフは：ｔ≦ｗ≦Ｔとして（すなわち、ｗは、ｔとＴの間のどこかにある一般的な時間帯である）、各時間帯ｗに対応する第１のノード列と、各広告ａ∈Ｓに対応する第２のノード列とを含む。時間帯ｗを広告ａに接続するリンクの「重み」は、ｃ（ｗ，ａ）である。次いで、ステップ７０５で、２部グラフの両側のノード数が等しいことを保証するために、ダミーノードが追加される。
【００７０】
次に、ステップ７０６で、ダミーノードに接続する（ｉｎｃｉｄｅｎｔ  ｏｎ）すべてのリンクの重みは、０に設定される。次いで、ステップ７０７で、最大重みマッチングが２部グラフ内で計算され、それによって、すべてのリンクの重みの総計を最大にするために、広告ａ′∈Ｓは、各時間帯ｔに対応するノードにマッチングされる。例示的な最大重みマッチングアルゴリズムについては、たとえば、参照によりその全体が本明細書に組み込まれている、Ｃｏｒｍｅｎら、「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ａｌｇｏｒｉｔｈｍｓ」（３版、１９９１年）、６００−６０４頁に記載されている。
【００７１】
次に、ステップ７０８で、ａ′がダミーノードかどうか判定され、その場合は、時間ｔに広告はスケジューリングされず、アルゴリズムは、ステップ７１０に進む。ステップ７０８で、ａ′がダミーノードでないと判定される場合は、アルゴリズムは、ステップ７０９に進む。ステップ７０９で、広告ａ′が、時間ｔにスケジューリングされる。次に、ステップ７１０で、広告ａ′が、適格な広告のセットＳから取り除かれ、すなわちＳ←Ｓ＼ａ′となる。次いで、ステップ７１１で、次の時間帯が選択され、すなわちｔ＝ｔ＋１となる。次に、ステップ７１２で、ｔ＜Ｔであるかどうか判定され、その場合、アルゴリズムは、ステップ７０２に戻る。ステップ７１２で、ｔ≧Ｔであると判定される場合は、スケジューリングは完了し、アルゴリズムは、ステップ７１３で終了する。
【００７２】
図７の上記アルゴリズムは、単一のチャンネルについてだけスケジューリングを実施しているが、本発明の実施形態は、マルチチャンネル「先読み」スケジューリングアルゴリズムの使用を含むことが想到される。
【００７３】
本明細書では本発明の実施形態について、所与の世帯においてインターネット検索とＩＰＴＶ視聴の両方を実施する単一の個人だけの文脈で述べられているが、２人以上の個人が同じ世帯内でインターネット接続サービスとＩＰＴＶサービスを共有する可能性が高い。このシナリオに対処する１つのやり方は、インターネット検索を実施する個人に関係なく単一のキーワードセットだけが収集されるように、すべての個人を単一の視聴者として扱うことであり、スケジューリングされるすべてのＩＰＴＶ広告は、それらの広告を実際に見る個人に関係なく、それらのキーワードに基づく。別法として、インターネット検索キーワードと共に、どの個人が検索を実施しているか、たとえば検索エンジンにログインするのに使用したユーザ名、ホームネットワーク上の特定のコンピュータのＩＰアドレスなどを識別するため使用され得る追加の基準が受信されてよい。どんな個人がＩＰＴＶを視聴しているか識別するために、類似の基準、たとえばホームネットワーク上の特定のテレビジョンのセットトップボックスのＩＰアドレス（または他の識別情報）が使用されてもよいし、視聴されている現在のチャンネル、テレビが視聴されている時間／日付、視聴されている番組のタイプまたはコンテンツなどに基づいてどんな個人がＩＰＴＶを視聴している確率が最も高いか決定するために、過去の視聴習慣についての考察が使用されてもよい。
【００７４】
本発明の様々な実施形態において、上述された処理を行うために適切なハードウェア、ソフトウェア、またはハードウェアとソフトウェアの両方の組合せが提供されることを理解されたい。本発明の特定の実施形態は、本明細書に述べられた操作モードの必ずしもすべてではないが、これらの操作モードの１つまたは複数をサポートできることをさらに認識されたい。
【００７５】
本明細書に述べられた広告は、放送番組、オンデマンド番組、および／または録画された（たとえばデジタルビデオレコーダ）番組を含むＩＰＴＶシステム内のビデオ広告であるが、本発明は、他のメディア内の広告、たとえばＩＰ無線システム内のオーディオ広告、オンデマンドのビデオシステム内のビデオ広告、インターネットまたはウェブ配信ビデオシステム内のビデオ広告、携帯電話ベースのオンデマンドおよび／またはストリーミングメディアシステム内のオーディオまたはビデオ広告を配置する際にも有用であり得る。用語「番組」は、上記内容のすべてを含むものと広く解釈されるべきである。したがって、本明細書では用語「メディア」は、オーディオだけのコンテンツ、ビデオだけのコンテンツ、およびオーディオとビデオの両方を含むコンテンツを含むものと解釈されたい。
【００７６】
用語「視聴者」と「ユーザ」は、本明細書では区別なく用いられてよく、インターネットセッション、たとえばウェブ閲覧セッションまたは検索エンジンセッションを行う人、ならびにＩＰＴＶを見、ＩＰラジオなどを聴くことによってパケットベースのメディアコンテンツを受信した人などを含むものと定義される。本明細書では、単数形の用語「視聴者」と「ユーザ」はまとめて、ある世帯で生活している家族のメンバなど、個人のグループに言及するためにも用いられており、その場合、本発明の実施形態による方式は、これらの個人の誰がＩＰＴＶを見ているか、またはインターネットセッションを行っているか決定できないことがあり、したがって、これらの個人の誰がまたは何名がこれらの活動を実際に実施しているかに関係なく、たとえばキーワード収集および／または広告配置のために、すべての可能な個人が単一の視聴者として扱われる。
【００７７】
広告入札からのキーワードと、時間帯の間の広告への入札を出す視聴者のインターネットセッションからのキーワードとの比較に関連して、表現「一致」は本明細書では、文字ごと（ｃｈａｒａｃｔｅｒ−ｆｏｒ−ｃｈａｒａｃｔｅｒ）のキーワードの正確な一致だけではなく、ファジー理論の一致、すなわち文字ごとのキーワード一致が存在しない場合には最も確からしい単語または語句の一致に基づいて行われる一致に言及するものと広く解釈されるべきである。マッチングは、本発明の文脈では、非正確のキーワードマッチング、および他の基準およびアルゴリズムに基づくマッチング、たとえば同意語ベース、関連語ベース、または概念ベースのキーワードマッチングを含むものとも解釈すべきである。
【００７８】
本発明は、それらの方法を実施する方法および装置の形で具現化されてよい。本発明は、磁気記録媒体、光記録媒体、ソリッドステートメモリ、フロッピディスケット、ＣＤ−ＲＯＭ、ハードドライブ、または他の任意のマシン読取り可能記憶媒体など、有形媒体で具現化されたプログラムコードの形で具現化されることもでき、プログラムコードがコンピュータなどのマシンにロードされ、マシンによって実行されるとき、このマシンは、本発明を実施する装置となる。本発明は、たとえば記憶媒体に格納され、マシンにロードされかつ／またはそれによって実行されようが、電気配線またはケーブルを介して、光ファイバによって、または電磁放射によってなど、何らかの伝送媒体または搬送波を介して送信されようが、プログラムコードの形で具現化されることもでき、プログラムコードがコンピュータなどのマシンにロードされ、マシンによって実行されるとき、このマシンは、本発明を実施する装置となる。汎用プロセッサ上で実装されるとき、プログラムコードセグメントは、プロセッサと結合して、特定の論理回路に類似して動作する一意の装置を提供する。
【００７９】
本発明は、本発明の方法および／または装置を使用して生成された、媒体を介して電気的または光学的に伝送されるビットストリームまたは信号値の他のシーケンス、磁気記録媒体内に格納された磁場変形体などの形でも具現化され得る。
【００８０】
他に明示的に定められていない限り、それぞれの数値および範囲は、単語「約（ａｂｏｕｔ）」または「およそ（ａｐｐｒｏｘｉｍａｔｅｌｙ）」がその値および範囲の値の前に置かれるかのように近似すると解釈されるべきである。
【００８１】
本発明の性質について説明するために述べられ示された部分の詳細、材料および構成の様々な変更が、添付の特許請求の範囲に表された本発明の範囲から逸脱せずに当業者によって行われ得ることがさらに理解されよう。
【００８２】
本明細書に述べられた例示的な方法の諸ステップは、述べられた順番で必ずしも実施される必要はなく、こうした方法の諸ステップの順序は単に例示的なものと理解されたい。同様に、こうした方法に追加のステップが含まれてよく、本発明の様々な実施形態による方法では、特定のステップが省かれることも、組み合わされることもある。
【００８３】
添付の方法クレーム内の諸要素は、あるとすれば、対応するラベルを付けて特定のシーケンスで列挙されており、請求項の列挙がそれらの要素の一部またはすべてを実施する特定のシーケンスを他に示唆していない限り、それらの要素は、その特定のシーケンスで実施されることに制限されることが必ずしも意図されていない。
【００８４】
本明細書では、「一実施形態（ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ、ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」への言及は、実施形態に関連して述べられた特定の特徴、構造または特性が本発明の少なくとも１つの実施形態に含まれ得ることを意味する。本明細書の様々な場所に「一実施形態では」の語句が現れることは、必ずしもすべてが同じ実施形態に言及するとは限らず、また別個のまたは代替の実施形態は、他の実施形態と必ずしも相互排他的であるとは限らない。同じことが、用語「実装形態」に当てはまる。
【図１】
0005816611.tif 000005
【図２】
0005816611.tif 000006
【図３】
0005816611.tif 000007
【図４】
0005816611.tif 000008
【図５】
0005816611.tif 000009
【図６】
0005816611.tif 000010
【図７】
0005816611.tif 000011