(57)【特許請求の範囲】
【請求項１】
コンピュータによって実行されるオンライン広告の方法であって、
売り手によって提供された複数の広告ソースの中から、所定の条件を満たす複数の選択済み広告ソースを選択し、
前記複数の選択済み広告ソースに対応する複数のキーワードセットを生成し、
前記複数の選択済み広告ソースおよび前記複数のキーワードセットの適合を表す計画モデルを１組の所定の制約条件に従って確立し、
前記複数の広告ソースの少なくともいくつかと、前記複数のキーワードセットとの間の実質的に最適な適合を前記計画モデルの解を求めることによって決定すること、
を備え、
前記１組の所定の制約条件に従って前記計画モデルを確立することは、
行列Ｘを構築し、前記行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースに適合するか否かを表し、
前記１組の所定の制約条件を条件とする目的関数を
【数４】
0005575270.tif 000008
として確立すること、
を含み、
Ｐijは、前記ｉ番目のキーワードおよび前記ｊ番目の広告ソースの間の適合による売り手利益を表し、Ｘijは、前記ｉ番目のキーワードが前記ｊ番目の広告ソースと適合するか否かを表し、Ｎjは、前記ｊ番目の広告ソースが持つことを許されるキーワードの最大数を表し、ｎは、前記キーワードの総数を表し、ｍは、前記選択済み広告ソースの総数を表す、方法。
【請求項２】
請求項１に記載の方法はさらに、
潜在的な買い手によって入力されたキーワードセットを受信し、
前記受信されたキーワードセットに基づく前記実質的に最適な適合に従って対応する広告ソースを検索すること、
を備える、方法。
【請求項３】
請求項１に記載の方法はさらに、
前記検索された対応する広告ソースを前記潜在的な買い手に対してウェブページで表示することを備える、方法。
【請求項４】
請求項１に記載の方法はさらに、
所定の分類基準に従って前記売り手によって提供された前記複数の広告ソースを分類することを備える、方法。
【請求項５】
請求項４に記載の方法であって、前記所定の条件を満たす前記複数の選択済み広告ソースの選択は、分類された１組の広告ソースと関連して実行される、方法。
【請求項６】
請求項５に記載の方法であって、カテゴリと関連して、前記所定の条件を満たす前記売り手によって提供された前記広告ソースを選択することは、
カテゴリに従って、前記売り手によって提供された前記複数の広告ソースの分布を取得し、
前記分布に従ってそれぞれのカテゴリから所定の数の広告ソースを選択すること、
を含み、
前記所定の数は、キーワードセットと適合される広告ソースの数に対する売り手指定の制約条件よりも大きい、方法。
【請求項７】
請求項１に記載の方法であって、前記１組の所定の制約条件は、キーワードセットと適合される前記広告ソースの数を含む、方法。
【請求項８】
請求項１に記載の方法であって、前記１組の所定の制約条件は、前記広告ソースの各々に対するキーワードセットの最大数を含む、方法。
【請求項９】
請求項１に記載の方法であって、前記目的関数は、検索ベースの解法を用いて解かれる、方法。
【請求項１０】
請求項１に記載の方法であって、前記目的関数を解くことは、
前記１組の所定の制約条件を満たす適合組み合わせを取得することであって、
前記キーワードの各々と前記選択済み広告ソースの各々との間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さをそれぞれ取得し、
最大の広告ソースの利益を有する複数の適合組み合わせの中で、前記売り手に対する前記複数の適合組み合わせから複数の売り手利益を計算し、
最大の売り手利益を有する１または複数の適合組み合わせを決定し、
現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達しているか否かを判定し、
現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達している場合に前記適合組み合わせの対応付けを削除し、達していない場合に前記適合組み合わせを格納すること、
を含む、前記１組の所定の制約条件を満たす適合組み合わせを取得することと、
前記選択済み広告ソースすべてが前記最大数のキーワードに適合するまで、前記キーワードの各々と前記広告ソースの各々との間の他の適合から前記１組の所定の制約条件を満たす適合組み合わせを繰り返し取得し、
前記広告ソースの各々の総利益に従って、前記取得した適合組み合わせをソートし、
前記取得した適合組み合わせから前記１組の所定の制約条件を満たす適合組み合わせを前記目的関数の解として選択すること、
を備える、方法。
【請求項１１】
オンライン広告システムであって、
１または複数のプロセッサであって、
売り手によって提供された複数の広告ソースの中から、所定の条件を満たす複数の選択済み広告ソースを選択し、
前記複数の選択済み広告ソースに対応する複数のキーワードセットを生成し、
前記複数の選択済み広告ソースおよび前記複数のキーワードセットの適合を表す計画モデルを１組の所定の制約条件に従って確立し、
前記複数の広告ソースの少なくともいくつかと、前記複数のキーワードセットとの間の実質的に最適な適合を、前記計画モデルの解を求めることによって決定することを実行するように構成されている１または複数のプロセッサと、
前記１または複数のプロセッサに接続され、前記プロセッサに命令を提供するよう構成されている１または複数のメモリと、
を備え、
前記１組の所定の制約条件に従って前記計画モデルを確立することは、
行列Ｘを確立し、前記行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースに適合するか否かを表し、
目的関数を
【数５】
0005575270.tif 000009
として確立すること、
を含み、
Ｐijは、前記ｉ番目のキーワードおよび前記ｊ番目の広告ソースの間の適合による売り手利益を表し、Ｘijは、前記ｉ番目のキーワードが前記ｊ番目の広告ソースと適合するか否かを表し、Ｎjは、前記ｊ番目の広告ソースが持つことを許されるキーワードの最大数を表し、ｎは、前記キーワードの総数を表し、ｍは、前記選択済み広告ソースの総数を表す、システム。
【請求項１２】
請求項１１に記載されたシステムであって、前記プロセッサは、さらに、
潜在的な買い手によって入力されたキーワードセットを受信し、
前記受信されたキーワードセットに基づいた前記実質的に最適な適合に従って対応する広告ソースを検索するように構成されている、システム。
【請求項１３】
請求項１１に記載のシステムであって、前記プロセッサは、さらに、前記検索された対応する広告ソースを前記潜在的な買い手に対してウェブページで表示するように構成されている、システム。
【請求項１４】
請求項１１に記載のシステムであって、前記プロセッサは、さらに、所定の分類基準に従って、前記売り手によって提供された前記複数の広告ソースを分類するように構成されている、システム。
【請求項１５】
請求項１４に記載のシステムであって、前記所定の条件を満たす前記複数の選択済み広告ソースの選択は、分類された１組の広告ソースと関連して実行される、システム。
【請求項１６】
請求項１５に記載のシステムであって、カテゴリと関連して、前記所定の条件を満たす前記売り手によって提供された前記広告ソースを選択することは、
カテゴリに従って、前記売り手によって提供された前記複数の広告ソースの分布を取得し、
前記分布に従ってそれぞれのカテゴリから所定の数の広告ソースを選択すること、
を含み、
前記所定の数は、キーワードセットと適合される広告ソースの数に対する売り手指定の制約条件よりも大きい、システム。
【請求項１７】
請求項１１に記載のシステムであって、前記制約条件は、キーワードセットと適合される前記広告ソースの数を含む、システム。
【請求項１８】
請求項１１に記載のシステムであって、前記制約条件は、前記広告ソースの各々に対するキーワードセットの最大数を含む、システム。
【請求項１９】
請求項１１に記載のシステムであって、前記目的関数は、検索ベースの解法を用いて解かれる、システム。
【請求項２０】
請求項１１に記載のシステムであって、前記目的関数を解くことは、
前記１組の所定の制約条件を満たす適合組み合わせを取得することであって、
前記キーワードの各々と前記選択済み広告ソースの各々との間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さをそれぞれ取得し、
最大の広告ソースの利益を有する複数の適合組み合わせの中で、前記売り手に対する前記複数の適合組み合わせから複数の売り手利益を計算し、
最大の売り手利益を有する１または複数の適合組み合わせを決定し、
現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達しているか否かを判定し、
現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達している場合に、前記適合組み合わせの対応付けを削除し、達していない場合に、前記適合組み合わせを格納すること、
を含む、前記１組の所定の制約条件を満たす適合組み合わせを取得することと、
前記選択済み広告ソースすべてが前記最大数のキーワードに適合するまで、前記キーワードの各々と前記広告ソースの各々との間の他の適合から前記１組の所定の制約条件を満たす適合組み合わせを繰り返し取得し、
前記広告ソースの各々の総利益に従って、前記取得した適合組み合わせをソートし、
前記取得した適合組み合わせから前記１組の所定の制約条件を満たす適合組み合わせを前記目的関数の解として選択すること、
を備える、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
他の出願の相互参照
本願は、すべての目的のために参照により本明細書に組み込まれる、２０１０年１月１３日付け出願の発明の名称を「ＲＥＴＲＩＥＶＡＬ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＹＳＴＥＭ  ＴＨＥＲＥＯＦ  ＦＯＲ  ＯＮＬＩＮＥ  ＴＲＡＤＩＮＧ  ＰＬＡＴＦＯＲＭ（オンライン商取引プラットフォームのための検索方法および検索システム）」とする中国特許出願第２０１０１０００３９２８．７号に基づく優先権を主張する。
【０００２】
本発明は、ウェブサイトデータ処理の分野に関し、特に、インターネット広告の管理に関する。
【背景技術】
【０００３】
オンライン商取引プラットフォームは、オンライン商取引を容易にするためにプラットフォームサービスプロバイダによって提供されるコンピュータ情報システムである。オンライン商取引プラットフォームは、売り手と買い手との間のオンライン商取引を実現することができる。オンライン商取引プラットフォーム上で、潜在的な買い手は、特定のキーワードを入力することによって、売り手が提供した広告ソースを検索（リトリーブ）しうる。インターネット上の入札ランキングモデルの下では、売り手によって提供された広告ソース（例えば、テキストファイル、画像など）と、対応するキーワード（すなわち、購入した単語またはユニット）との間の対応付けを、広告ソースとキーワードとの間の適合（一致、マッチ）と呼ぶ。売り手は、特定のキーワードの代金を支払うことにより、１または複数の広告ソースを含む広告を表示することができる。例えば、売り手がキーワード「本」の代金を支払った場合、潜在的な買い手が入力した検索ワードが特定のルールの下でキーワード「本」に対応付けられると、売り手によって指定された広告ソース（例えば、テキストファイル、画像など）が、潜在的な売り手に対して表示されることになる。売り手は、キーワードと広告ソースとの間のかかる適合から恩恵を受ける。潜在的な買い手による広告のクリックスルー、潜在的な買い手による問い合わせ、または、潜在的な買い手との取引など、結果として売り手に恩恵を与える活動を、売り手の利益と呼ぶこととする。
【０００４】
既存のオンライン商取引プラットフォームでは、潜在的な買い手が１セットのクエリキーワードを入力した時に、売り手によって提供された広告ソースが特定の適合に基づいて検索される。適合は、通常、広告ソースがどれだけ新しいか（最新の広告ソースが通常は優先される）、および、広告ソースとキーワードとの間の適合が広告ソースに最大の利益をもたらしうるか否かに基づいて生成される。例えば、売り手は、２つの広告ソース、「各種携帯電話の販売」および「輸入携帯電話の販売」を有し、それらは、３つのキーワードセット「携帯電話」、「ノキア携帯電話」、および、「アップル携帯電話」と関連付けられる。各広告ソースが多くとも２つのキーワードセットとのみ関連付けられうると仮定すれば、異なる関連度が、１〜１０の段階で以下の利益レベルを売り手にもたらしうる。「各種携帯電話の販売」が「携帯電話」に適合された場合：１０、「各種携帯電話の販売」が「ノキア携帯電話」に適合された場合：７、「各種携帯電話の販売」が「アップル携帯電話」に適合された場合：６、「輸入携帯電話の販売」が「携帯電話に適合された場合：９、「輸入携帯電話の販売」が「ノキア携帯電話」に適合された場合：７、「輸入携帯電話の販売」が「アップル携帯電話」に適合された場合：５。既存技術に従って生成された広告ソースおよびキーワードセットの間のマッチについて、広告ソース「各種携帯電話の販売」がキーワード「携帯電話」（利益１０）および「ノキア携帯電話」（利益７）に適合され、広告ソース「輸入携帯電話の販売」がキーワード「アップル携帯電話」（利益５）に適合されると仮定すれば、その適合は、２２（すなわち、１０＋７＋５）の総利益を売り手にもたらすことになる。
【０００５】
しかしながら、上述の例において、「各種携帯電話の販売」を「携帯電話」（利益１０）および「アップル携帯電話」（利益６）に関連付け、「輸入携帯電話の販売」を「ノキア携帯電話」（利益７）に関連付ける広告ソースおよびキーワードセットの間の適合もある。この適合は、総利益２３を売り手にもたらすことになる。実際には、売り手によって提供された広告ソースが適合するキーワードセットの数が限られる時には、最新の広告ソースのみを考慮する場合、または、適合が現在の広告ソースまたは一群の同様の広告ソースに最大の利益をもたらしうるか否かにのみ基づいて広告ソースとキーワードとの間の適合を設定する場合、売り手によって提供されたあらゆる製品分野を必ずしも表さない広告ソースおよびキーワードの間の適合を得る可能性があることがわかる。結果として、売り手の提供する製品分野の一部は、キーワードセットに適合する広告ソースを全くまたはほとんど持たない場合がある。かかる場合、潜在的な買い手は、製品の検索を実行するためにキーワードセットを入力した時に、対応する適切な広告ソースを取得しえない。潜在的な買い手が検索を繰り返した場合、オンライン商取引プラットフォームサーバの検索性能の低下も起きる。さらに、広告ソースとキーワードとの間の適合を生成するための既存の方法は、売り手にとって最大の利益をもたらさない場合がある。
【図面の簡単な説明】
【０００６】
以下の詳細な説明と添付の図面において、本発明の様々な実施形態を開示する。
【０００７】
【図１】広告ソースとキーワードセットと間の適合を生成するための処理の一実施形態を示すフローチャート。
【０００８】
【図２】図１に示した処理１００に従って構成されたオンライン商取引プラットフォームから広告ソースを検索するための処理の一実施形態を示すフローチャート。
【０００９】
【図３】広告ソースとキーワードとの間の適合を生成するための処理の一実施形態を示すフローチャート。
【００１０】
【図４】広告ソースとキーワードとの間の適合を生成するためのデバイスの一実施形態を示すブロック図。
【００１１】
【図５】オンライン商取引プラットフォームにおける検索システムの一実施形態を示すブロック図。
【００１２】
【図６】広告ソースとキーワードとの間の適合を生成するためのシステムの別の実施形態を示すブロック図。
【発明を実施するための形態】
【００１３】
本発明は、処理、装置、システム、物質の組成、コンピュータ読み取り可能な格納媒体上に具現化されたコンピュータプログラム製品、および／または、プロセッサ（プロセッサに接続されたメモリに格納および／またはそのメモリによって提供される命令を実行するよう構成されたプロセッサ）を含め、様々な形態で実装されうる。本明細書では、これらの実装または本発明が取りうる任意の他の形態を、技術と呼ぶ。一般に、開示された処理の工程の順序は、本発明の範囲内で変更されてもよい。特に言及しない限り、タスクを実行するよう構成されるものとして記載されたプロセッサまたはメモリなどの構成要素は、ある時間にタスクを実行するよう一時的に構成された一般的な構成要素として、または、タスクを実行するよう製造された特定の構成要素として実装されてよい。本明細書では、「プロセッサ」という用語は、１または複数のデバイス、回路、および／または、コンピュータプログラム命令などのデータを処理するよう構成された処理コアを指すものとする。
【００１４】
以下では、本発明の原理を示す図面を参照しつつ、本発明の１または複数の実施形態の詳細な説明を行う。本発明は、かかる実施形態に関連して説明されているが、どの実施形態にも限定されない。本発明の範囲は、特許請求の範囲によってのみ限定されるものであり、多くの代替物、変形物、および、等価物を含む。以下の説明では、本発明の完全な理解を提供するために、多くの具体的な詳細事項が記載されている。これらの詳細事項は、例示を目的としたものであり、本発明は、これらの具体的な詳細事項の一部または全てがなくとも特許請求の範囲に従って実施可能である。簡単のために、本発明に関連する技術分野で周知の技術事項については、本発明が必要以上にわかりにくくならないように、詳細には説明していない。
【００１５】
本願は、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたは携帯型デバイス、フラットパネルデバイス、マルチプロセッサデバイスなどを含む様々な汎用または専用のコンピュータデバイス環境または構成で、ならびに、上述のようなデバイスを含む分散型コンピュータ環境で実施されてよい。
【００１６】
本願は、コンピュータによって実行されるコンピュータ実行可能な命令（例えば、プログラムモジュール）の一般的な文脈で記載されうる。一般に、プログラムモジュールは、特定のタスクの実行または特定の抽象データ型の実装のためのルーチン、プログラム、オブジェクト、アセンブリ、データ構造などを含みうる。本願は、分散型コンピュータ環境で実施されてもよい。分散型コンピュータ環境では、通信ネットワークを介して接続されたリモート処理デバイスによって、タスクが実行される。分散型コンピュータ環境において、プログラムモジュールは、記憶デバイスなど、ローカルまたはリモートコンピュータの記憶媒体に格納されてよい。
【００１７】
本願に記載の実施形態において、売り手は、特定のカテゴリに対応する広告ソースを提供する。複数の広告ソースが、それぞれのカテゴリの下で売り手によって提供された広告ソースの分布に従って取得される。広告ソースはこれらのカテゴリにおける広告ソースの分布に従って取得されるので、選択された広告ソースは、売り手によって提供された製品分野をできる限り多く網羅することが好ましい。対応するキーワードセットが、これらの広告ソースに基づいて生成される。選択された広告ソースおよびキーワードセットの実質的に最適な適合を探すために、線形計画技術が用いられる。計画（programming）モデルが、目的関数と１組の制約条件とを含むように確立される。検索ベースの技術を用いて目的関数の解が求められる。広告ソースと、適合される対応するキーワードとの間の実質的に最適な適合が取得される。結果として得られる適合は、特定の制約条件下で、売り手の最大利益を表しうる。その後、潜在的な買い手は、所望の製品を検索するキーワードセットを入力した時に、上記で確立された適合に基づいて、売り手によって提供された最も関連性の高い広告ソースを検索できる。したがって、潜在的な買い手の購入体験および売り手の販売体験が両方とも改善される。また、この技術は、他の既存のシステムによって生成された広告ソースおよびキーワードの間の適合によって引き起こされる検索の繰り返しという問題を回避し、オンライン商取引プラットフォームサーバの性能の低下を防ぐ。
【００１８】
図１は、広告ソースとキーワードセットと間の適合を生成するための処理の一実施形態を示すフローチャートである。処理１００は、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたは携帯型デバイス、フラットパネルデバイス、マルチプロセッサデバイスなどを含む様々な汎用または専用のコンピュータデバイス環境または構成において、ならびに、上述のようなデバイスを含む分散型コンピュータ環境において実装、実行されてよい。
【００１９】
工程１０１では、特定の売り手によって提供され所定の条件を満たす広告ソースが選択される。いくつかの実施形態において、この選択は、広告ソースのカテゴリと関連して行われる。
【００２０】
売り手によって提供された広告ソースは、テキスト、画像、ビデオ、音声ファイル、および、ユーザに提示するのに適した任意の他の適切なフォーマットなど、様々なフォーマットを有しうる。いくつかの実施形態では、売り手によって提供された広告ソースが、特定のルールに従って分類される。例えば、広告ソースのカテゴリは、ルートノードが衣料品であり、サブノードが男性衣料、女性衣料、および、子ども服を含むツリーとして組織化されてよい。サブノード「男性衣料」は、異なるスタイル、異なる季節などに対応する衣料をさらに含みうる。広告ソースを分類するためのアプローチは、よく知られている。特定の条件を満たす同じタイプの広告ソースが、同じカテゴリに含まれる限りは、売り手によって提供された広告ソースを分類するために、様々な技術が用いられてよい。したがって、広告ソースは、それぞれのカテゴリに関連して選択される。
【００２１】
所定の条件は、どの広告ソースが選択されるかを特定する。例えば、売り手は、かかる適合がなされる前に、キーワードと適合される広告ソースの数を設定してよい。所定の条件は、選択される広告ソースの数が、キーワードと適合される広告ソースの数よりも多くなることを求めてよく、そうすれば、すべての広告ソースが少なくとも１つのキーワードセットと適合される。いくつかの実施形態において、広告ソースの選択基準は、広告ソースがいつ作成されたか、広告ソースがすでに以前に用いられたか否か、などを含む。
【００２２】
工程１０２では、対応するキーワードセットが、売り手によって提供された選択済み広告ソースに基づいて生成される。見出し語選択および拡張適合など周知の技術が、キーワードを生成するために用いられてよい。キーワードセットを生成するための基準は、生成されたキーワードセットが、ある程度のレベルで広告ソースに関連し、潜在的な買い手の購入意図を表すことを求める。例えば、売り手によって提供された広告ソースが、テキスト「各種ノキア携帯電話の販売」である場合、生成されたキーワードセットは、「携帯電話」、「ノキア携帯電話」、および、「各種携帯電話」を含みうる。
【００２３】
工程１０３では、計画モデルが確立される。計画モデルは、１または複数の所定の制約条件に従う目的関数を含む。計画モデルは、売り手によって提供された選択済み広告ソースと生成されたキーワードセットとの間の適合を表す。適合は、売り手によって提供された広告ソースおよび対応するキーワードセットの対応付けと呼ばれる場合もある。
【００２４】
この実施形態において、所定の制約条件は、キーワードセットと適合される広告ソースの数、各広告ソースが対応するキーワードセットの数、などを含む。別の実施形態では、別の制約条件が事前設定されてもよい。制約条件の値は、通常は、売り手によって事前設定される。広告ソースの数と、各広告ソースが対応するキーワードの数は限られているため、上記の制約条件を満たす計画モデルを確立する際には、特定の広告ソースが特定のキーワードセットに対応付けられるか否かを表すために、０または１の値を有する整数変数が導入される。この例において、値１を持つエントリは「対応」を表し、値０を持つエントリは「対応なし」を表す。以下で詳述するように、売り手の利益を最大化するための目的関数が、所定の制約条件下で設定される。本明細書で用いられているように、売り手の利益とは、特定の広告ソースと特定のキーワードセットとの間に確立された適合によって売り手にもたらされる利益を表す。例えば、売り手についてのクリックスルーレートを用いて、利益を測ることができる。以下では、計画モデルを確立するための詳細な処理について説明する。
【００２５】
工程１０４では、目的関数は、広告ソースとキーワードセットとの間の実質的に最適な適合（対応）を得るために、検索ベースの解法を用いて解を求められる。
【００２６】
計画モデルが工程１０３において確立された後、検索ベースの解法が、計画モデルの目的関数を解くために用いられてよく、その結果は、広告ソースとキーワードとの間の実質的に最適な適合である。検索ベースの解法を用いて目的関数を解く方法の詳細について以下で説明する。適合内の広告ソースの総数は、キーワードセットと適合される広告ソースの数と呼ばれ、売り手によって予め指定される。売り手によって予め指定される制約条件は、キーワードセットと適合される広告ソースの数と、各広告ソースが適合するキーワードセットの数の上限とを含む。
【００２７】
いくつかの実施形態において、広告ソースとキーワードとの間の適合は、生成されると売り手に送信され、売り手は、その適合が自身の要件を満たすか否かを決定し、その適合を受け入れる、拒否する、および／または、修正することを許される。
【００２８】
この用途で解かれた適合は、繰り返し利用できる。広告ソースとキーワードセットとの間の適合は、一旦確立されると、様々な用途で利用されてよい。一般に、潜在的な買い手がキーワードを入力した時に、オンライン商取引プラットフォームサーバは、予め生成された適合に基づいて、売り手によって提供された広告ソースを検索してよく、潜在的な買い手に広告ソースのコンテンツを戻す。本願の実施形態において確立された適合は、売り手の製品情報を表すため、潜在的な買い手が広告によって購入を行う可能性を高める。
【００２９】
図２は、図１に示した処理１００に従って構成されたオンライン商取引プラットフォームから広告ソースを検索するための処理の一実施形態を示すフローチャートである。すなわち、この例では、売り手のための広告ソースおよびキーワードセットの適合が生成されると、オンライン商取引プラットフォームサーバ側に格納される。
【００３０】
工程２０１では、クエリキーワードセットが潜在的な買い手によって入力される。
【００３１】
工程２０２では、対応する広告ソースが、図１に示した処理１００に従って予め確立されたキーワードセットおよび広告ソースの間の適合に基づいて検索される。
【００３２】
潜在的な買い手がキーワードセット（すなわち、所望の製品または品物のキーワードセット）を入力すると、対応する広告ソースが、処理１００の結果として得られた適合に基づいてサーバによって検索される。この実施形態で格納された適合に基づいて検索された広告ソースは、売り手の実際の製品情報および潜在的な買い手の購入意図を正確に反映する。したがって、この技術によると、潜在的な買い手は、検索を繰り返したりクエリキーワードを変更したりする必要なしに、より正確に所望の製品を見つけ出すことができる。さらに、本願の実施形態で確立された適合内の広告ソースはカテゴリに従って選択されるため、オンライン商取引プラットフォームサーバは、広告ソースが属するカテゴリに従って検索を実行するだけでよい。したがって、オンライン商取引プラットフォームサーバによって実行される検索の回数が低減され、それにより、オンライン商取引プラットフォームサーバの検索性能が改善される。
【００３３】
工程２０３では、検索された広告ソースが、潜在的な買い手に対して表示される。いくつかの実施形態において、サーバは、広告ソースに基づいて、潜在的な買い手に対して表示される広告を構成し、ウェブページに広告を表示するため、その結果として、潜在的な買い手は、広告をクリックすることによって、特定の製品の情報の取得および／または購入を行うことができる。
【００３４】
図３は、広告ソースとキーワードとの間の適合を生成するための処理の一実施形態を示すフローチャートである。
【００３５】
工程３０１では、現行のオンライン商取引プラットフォームシステムにおいて売り手によって提供された広告ソースが、所定の分類基準に従って分類される。任意の適切な分類技術が用いられてよい。分類された広告ソースは、後に特定のカテゴリの広告ソースから広告ソースを容易に選択できるように格納される。
【００３６】
工程３０２では、それぞれのカテゴリの下で売り手によって提供された広告ソースの分布が取得される。工程３０３では、所定の数の広告ソースが、分布に従ってそれぞれのカテゴリから選択される。
【００３７】
分布は、後に、各カテゴリ内の広告ソースの数に比例して広告ソースを選択するために用いられる。それぞれのカテゴリの下で広告ソースの分布に従って広告ソースを選択することにより、１つのカテゴリも除外せずに、各カテゴリから、少なくともいくつかの広告ソースが選択され、クエリと適合される。このように、売り手によって提供された適切な広告ソースが、潜在的な買い手に対して提示されるため、ユーザクリックスルーおよび／または購入の可能性が向上される。いくつかのオンライン商取引プラットフォームにおいて、正のユーザフィードバックが対応付けを強化する。したがって、潜在的な買い手が後に同じ検索キーワードを入力した場合、オンライン商取引プラットフォームサーバが、広告ソースに対するキーワードの同じ適合を見出す可能性が高くなる。
【００３８】
例えば、カテゴリＡおよびカテゴリＢの下で売り手によって提供された広告ソースの分布が１：２である場合、カテゴリＡおよびカテゴリＢから選択される広告ソースも１：２の比を有する。
【００３９】
いくつかの実施形態において、選択される広告ソースの総数は、特定の条件を満たす必要がある。この例において、選択される広告ソースの数は、複数の広告ソースが１つのキーワードセットに対応しうるため、キーワードセットの適合に用いられる広告ソースの数よりも大きい必要がある。いくつかの実施形態において、システムは、キーワード適合に必要な数の２倍の広告ソースを選択する。しかしながら、一般に、オンライン商取引プラットフォームサーバの検索速度および性能を考慮すると、通常、１つのキーワードが、１つの広告ソースまたは１群の広告ソースに対応する。したがって、後にキーワードに基づいて広告ソースを検索する際に、すべての広告ソースをトラバースする必要がない。各キーワードが、異なる広告ソースを検索しうることにより、オンライン商取引プラットフォームサーバの検索速度が向上する。例えば、広告ソース「各種携帯電話の販売」は、キーワードセット「携帯電話」に対応付けられ、広告ソース「携帯電話の販売」も、キーワードセット「携帯電話」に対応付けられる。２つの広告ソースおよびそれぞれの適合関係は、それらが同じキーワードセットに対応しうるように共存できる。
【００４０】
キーワード適合のために、売り手によって提供された広告ソースを選択した後、工程３０４において、計画モデルが、売り手の利益を最大化する目的で確立される。特に、ｎ行ｍ列の行列Ｘが確立される。行列の行はキーワードセットに対応し、列は広告ソースに対応する。したがって、行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースと適合するか否か、すなわち、ｉ番目のキーワードとｊ番目の広告ソースとの間の対応が存在するか否かを意味しており、ここで、ｉ＝１、・・・、ｎであり、ｊ＝１、・・・、ｍである。
【００４１】
工程３０５では、行列はベクトルに変換され、変換後にベクトルに基づいて、０−１型整数計画モデルが確立される。
【００４２】
行列からベクトルへ変換するために、行列の第２列が第１列の後ろに結合され、第３列が第２列の後ろに結合され、以下同様に結合が行われ、最後に、行列の最後の列が最後から２番目の列の後ろに結合される。このように、行列は、ｎ＊ｍの成分を持つベクトルに変換される。計画モデルは、ベクトルおよび制約条件に基づいて以下の目的関数を確立する。
【数１】
0005575270.tif 000002
ここで、Ｐijはｉ番目のキーワードがｊ番目の広告ソースに適合する場合の利益を表し、Ｘijはｉ番目のキーワードがｊ番目の広告ソースに適合するか否かについて、１で適合を表し、０で非適合を表し、Ｎjはｊ番目の広告ソースが持ちうるキーワードの最大数を表し、ｎはキーワードの総数を表し、ｍは選択された広告ソースの総数を表す。
【００４３】
目的関数は、制約条件下で、最大の売り手利益を提供する選択済み広告ソースおよびキーワードセットの間の適合の解を見出すために、検索ベースの技術を用いて解かれる。
【００４４】
ｉ番目のキーワードとｊ番目の広告ソースとの間の適合は、１組の値で表される。いくつかの実施形態において、広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さが、適合を表すために用いられる。工程３０６では、それぞれのキーワードと広告ソースとの間の各適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さが取得される。
【００４５】
この例では、行列Ｘのｉ番目のキーワードとｊ番目の広告ソースとの間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さが取得される。広告ソースの幅とは、１つのキーワードセットが広告ソースに適合する最大の範囲を表す。広告ソースの深さとは、１つの広告ソースがキーワードセットに適合する最大の範囲を表す。
【００４６】
実際的には、利益、類似度、広告ソースの幅、および、広告ソースの深さは、本願の実施形態で見られる数値である。類似度は、広告ソースとキーワードとの間の類似性を表しており、周知の技術を用いて計算できる。
【００４７】
いくつかの実施形態において、広告ソースの幅および広告ソースの深さは、以下のように計算される。
広告ソースの幅＝（１つの広告ソースに対して制限されたキーワードの数）−（現在広告ソースに適合しているキーワードの数）、
広告ソースの深さ＝１つの広告ソースに対して制限されたキーワードの数。
【００４８】
工程３０７では、広告ソースにとっての最大の利益を有する複数の適合組み合わせの中で、これらの適合組み合わせによって達成される売り手の利益が、それぞれ計算される。
【００４９】
最初に、ベクトル内のすべての適合組み合わせが、広告ソースの利益に従ってソートされる。広告ソースに対する最大の利益を有する最上位の適合組み合わせが決定される。それぞれの最上位の適合組み合わせによる売り手の利益が計算される。売り手の利益は以下のように計算される。
売り手の利益＝（特定の広告ソースおよびキーワードセットの適合の最大利益）−（適合によって引き起こされる売り手の損失）。
ここで、特定の適合によって引き起こされる売り手の損失は、同じキーワードセットに対する別の広告ソースの適合による最大利益、として定義される。
【００５０】
売り手の利益は、評価関数を用いて計算でき、すなわち、特定の適合による売り手の利益は評価関数を構築することによって得られることに注意されたい。一例において、評価関数は以下のように定義される。
特定の適合による売り手の利益＝（広告ソースとキーワードとの間の適合からの最大利益）−（適合によって引き起こされる売り手の損失）。
【００５１】
工程３０８では、最大の売り手利益を有する複数の適合組み合わせが存在するか否かが判定され、存在する場合、最大の売り手利益を有する複数の適合組み合わせは類似度、広告ソースの幅、および／または、広告ソースの深さに従ってソートされ、最上位の適合組み合わせが最終的なソート結果から選択され、存在しない場合、最大の売り手利益を有する１つの適合組み合わせが直接取得される。
【００５２】
この工程において、最大の売り手利益を有する適合組み合わせが１つだけ存在する場合、最大の売り手利益を有する１つの適合組み合わせが取得され、次の工程が実行される。最大の売り手利益を有する適合組み合わせが複数存在する場合、最大の売り手利益を有する複数の適合組み合わせは類似度に従ってソートされ、最大の類似度を有する適合組み合わせがソートの結果に従って取得される。さらに、最大の類似度を有する適合組み合わせが１つだけ存在する場合、最大の売り手利益を有する１つの適合組み合わせが取得され、最大の類似度を有する適合組み合わせが複数存在する場合、最大の類似度を有する複数の適合組み合わせが広告ソースの幅に従ってソートされ、最上位の適合組み合わせがこの工程の結果として取得される。この工程において、最適な適合組み合わせの関係性が、利益、類似度、広告ソースの幅、および／または、広告ソースの深さの順に取得される。
【００５３】
工程３０９では、現在取得されている適合組み合わせにおける広告ソースが適合するキーワードの数が、上限に達しているか否かが判定される。上限に達している場合、その適合組み合わせの対応付けが削除され、上限に達していない場合、その適合組み合わせは格納される。
【００５４】
この例では、各広告ソースが適合を許されるキーワードの数に所定の制約条件があるため、この工程において、前の工程で取得された適合がこの制約条件に対して検証される。換言すると、適合内の広告ソースが適合するキーワードの数が閾値に達するか否かが確認される；閾値に達する場合、適合組み合わせの対応付けが削除されて、次の工程が実行され；閾値に達しない場合、適合によって示される広告ソースおよびキーワードの間の対応付けが格納され、次のトラバースでその適合を再び検索できないことが求められるため、適合の対応関係も削除されることが好ましく、そして、次の工程が実行される。
【００５５】
工程３１０では、選択された広告ソースすべてが上限の数のキーワードに適合するまで、制約条件を満たす適合組み合わせが、キーワードセットと広告ソースとの間の他の適合から取得され続ける。
【００５６】
広告ソースとキーワードセットとの間の適合を取得した後、別のキーワードと別の広告ソースとの間の他の適合が、行列をトラバースすることによって見出される。トラバースを通して適合を取得するアプローチは、工程３０２において選択された広告ソースすべてが上限の数のキーワードに適合するまでは、工程３０６〜工程３０９と同じであってよい。
【００５７】
工程３１１では、取得された適合組み合わせは各広告ソースの総利益に従ってソートされ、ソート後に制約条件を満たす適合組み合わせが解と見なされる。
【００５８】
次いで、選択された広告ソースの総利益が計算される。例えば、広告ソースが２つのキーワードに適合する場合、総利益は、広告ソースが２つのキーワードのそれぞれに適合する場合の利益の合計に等しい。次いで、結果として得られた適合組み合わせは、総利益に従ってソートされ、特定の数の適合組み合わせが、ソートの結果から解として選択される。適合組み合わせの数は、適合のために用いられた広告ソースの数に等しい。
【００５９】
潜在的な買い手によって入力されたキーワードセットに基づいて処理２００で生成された適合に基づき、売り手によって提供された広告ソースを検索するために、工程３１１の後に、処理２００の工程２０１および２０２を備えてもよい。この検索方法を用いることによって、表示される広告ソースは、売り手によって提供された製品分野をよりよく網羅しつつ、潜在的な買い手の購入意図に近いものになりうる。したがって、オンライン商取引プラットフォームでの商取引において潜在的な買い手が、検索のために繰り返しキーワードを入力する必要がなくなる。これは、オンライン商取引プラットフォームサーバの検索の回数を削減し、検索の速度および性能を向上しうる。
【００６０】
説明のために、処理３００と関連して詳細な例を示す。所与の売り手によって提供された広告ソースがすでに分類されており、ソースの分布が処理工程３０１および３０２に従って取得されているとする。
【００６１】
工程３０３では、売り手によって提供され所定の条件を満たす広告ソースが、カテゴリに関連して取得される。
【００６２】
この例では、所定の条件は、少なくとも３つの適合する広告ソースが、少なくとも２つのキーワードを各々有することを求める。この例では、売り手Ａによって提供された１００の広告ソースがあり、選択された広告ソースは、１、２、３、４、５、および、６としてラベルをつけられる。
【００６３】
次に、対応するキーワードセットが、取得された広告ソースから生成される。この例では、広告ソース１によって生成されるキーワードセットはａ、ｂおよびｃであり、広告ソース２によって生成されるキーワードセットはｃ、ｄおよびｅであり、広告ソース３によって生成されるキーワードセットはｄおよびｅであり、広告ソース４によって生成されるキーワードセットはａおよびｄであり、広告ソース５によって生成されるキーワードセットはａ、ｄおよびｅであり、広告ソース６によって生成されるキーワードセットはａ、ｂおよびｄである。
【００６４】
工程３０４では、行列Ｘが確立される。この例において、行列の行はキーワードに対応し、行列の列は広告ソースに対応する。行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースに適合するか否かを示す。
【００６５】
工程３０５では、行列はベクトルに変換され、以下の計画モデルがベクトルに従って確立される。
【数２】
0005575270.tif 000003
【００６６】
計画モデルは、変換後のベクトルに従って確立される。いくつかの実施形態では、各キーワードと各広告ソースとの間の適合の特定の状況を参照しつつ検索ベースの解法を用いて、計画モデルの目的関数の実質的に最適な結果が計算される。以下では、検索ベースの解法の計算処理について説明する。
【００６７】
工程３０６では、各キーワードと各広告ソースとの間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さがそれぞれ取得される。
【００６８】
この例において、６つの広告ソースの各々と５つのキーワードの各々との間の適合の利益、類似度、広告ソースの幅、および、広告ソースの深さを表１に示す。ここで、各入力ボックスの４つの連続した数字は、利益、類似度、広告ソースの幅、および、広告ソースの深さをそれぞれ表す。
【表１】
0005575270.tif 000004
【００６９】
工程３０７では、最大の広告ソース利益を有する複数の適合組み合わせの中で、複数の適合組み合わせによる売り手についての複数の売り手利益がそれぞれ計算される。
【００７０】
適合組み合わせは、広告ソースの利益に従ってソートされる。最大の広告ソースの利益「５」を有する適合組み合わせは、以下を含む。キーワードａと広告ソース１との適合：５、３、２、１、キーワードａと広告ソース５との適合：５、２、１、４、キーワードａと広告ソース６との適合：５、２、１、３、キーワードｃと広告ソース１との適合：５、３、２、４、キーワードｄと広告ソース２との適合：５、３、５、３、キーワードｅと広告ソース２との適合：５、３、３、１。
【００７１】
各キーワードに対する適合組み合わせによってもたらされる売り手に対する売り手利益が計算される。売り手利益は、広告ソースとキーワードとの間の適合の最大の利益から、適合によって引き起こされる売り手の損失を減算することによって計算される。したがって、この工程において、各適合による売り手についての売り手利益は、以下のように計算される。
キーワードａと広告ソース１との適合：５−５＝０
キーワードａと広告ソース５との適合：５−５＝０
キーワードａと広告ソース６との適合：５−５＝０
キーワードｃと広告ソース１との適合：５−４＝１
キーワードｄと広告ソース２との適合：５−４＝１
キーワードｅと広告ソース２との適合：５−４＝１
【００７２】
工程３０８では、最大の売り手利益を有する複数の適合組み合わせは、類似度、広告ソースの幅、および／または、広告ソースの深さに従って順番に再びソートされ、最終的なソートの結果から最上位の適合組み合わせが選択される。
【００７３】
最大の売り手利益を有する適合組み合わせは、前の工程における売り手利益の順に選択される。最大の売り手利益を提供する３つの適合関係は、ｃ：１、ｄ：２、ｅ：２である。次いで、他の３つの値に従って、さらにソートを実行すると、以下が得られる。キーワードｄと広告ソース２との適合：１、３、５、３、キーワードｅと広告ソース２との適合：１、３、３、１、キーワードｃと広告ソース１との適合：１、３、２、４。
【００７４】
工程３０９では、現在取得されている適合における広告ソースが適合するキーワードの数が、上限に達しているか否かが判定される。上限に達している場合、その適合組み合わせの対応付けは削除され、上限に達していない場合、その適合組み合わせは格納される。
【００７５】
複数の適合が同じ売り手利益および類似度を有するため、第１の適合が広告ソース２とキーワードセットｄとの間の適合として選択されるが、２−ｄの適合は、残りの適合に比べて最大の幅の値を有する。広告ソース２が適合するキーワードの数が限界（この場合、２）に達したか否かがさらに判定される。限界に達していない場合、その適合は格納され、限界に達している場合、後に処理が繰り返された時に同じ適合が再び見出されないように広告ソース２とキーワードセットｄとの間の適合が削除される（すなわち、キーワードｄおよび広告ソース２のためのすべての対応する値が０に設定される）。
【００７６】
工程３１０では、結果として得られた適合組み合わせは各広告ソースの総利益に従ってソートされ、ソート後に制約条件を満たす適合組み合わせが解と見なされる。
【００７７】
工程３１１では、６つの広告ソースについて得られたすべての適合組み合わせが、６つの広告ソースの総利益、すなわち、６つの広告ソースに対応するそれぞれの２つのキーワードについての利益の合計、に従ってソートされる。次いで、ソート後の上位３つの広告ソースが、解と見なされる。解は、さらに、広告ソースとキーワードとの間の適合として売り手に戻されてよい。
【００７８】
実際には、アルゴリズムの性能を考慮すると、最大の売り手利益を有する適合組み合わせ内で選択を行うために、欲張りアルゴリズムが用いられてよい。実際の状況に応じて、異なるアルゴリズムおよび実装プロセスが用いられてよい。本願の広告ソースの検索は、本願によって生成される特定の適合に基づいてなされるため、検索された広告ソースは、潜在的な買い手が、より少ないクエリで、より正確な広告ソースを検索することを可能にし、したがって、オンライン商取引プラットフォームによる検索の回数を削減し、オンライン商取引プラットフォームの検索性能を高めることができる。
【００７９】
説明の簡単のため、上述の方法の実施形態は、一連の動作の組み合わせとして説明されている。しかしながら、工程のいくつかは本願に従って別の順番でまたは同時に実行されてもよいため、本願は、記載されている動作の順番に限定されないことを当業者は理解すべきである。さらに、本明細書に示した実施形態は好ましい実施形態であること、および、それらに関連する動作およびモジュールが本願の実施に必須ではないことも理解されたい。
【００８０】
図４は、広告ソースとキーワードとの間の適合を生成するためのデバイスの一実施形態を示すブロック図である。この例において、デバイスは、売り手によって提供され所定の条件を満たす広告ソースを、カテゴリに関連して選択するよう適合された選択モジュール４０１と、売り手によって提供された選択済み広告ソースから対応するキーワードを生成するよう適合されたキーワード生成モジュール４０２と、所定の制約条件に従った目的関数を含み、売り手によって提供された選択済み広告ソースと生成されたキーワードとの間の適合を表す計画モデルを確立するよう適合された計画モデル確立モジュール４０３と、広告ソースと、適合されるキーワードとの間の適合を取得するために、検索ベースの解法を用いて目的関数を解くよう適合された適合取得モジュール４０４と、を備える。
【００８１】
図５は、オンライン商取引プラットフォームにおける検索システムの一実施形態を示すブロック図である。システムは、適合生成部５０３を備えており、適合生成部５０３は、売り手によって提供され所定の条件を満たす広告ソースを、カテゴリに関連して選択し、売り手によって提供された選択済み広告ソースから対応するキーワードを生成し、所定の制約条件に従った目的関数を含み、売り手によって提供された選択済み広告ソースと生成されたキーワードとの間の適合を表す計画モデルを確立し、広告ソースと、適合されるキーワードとの間の適合を取得するために、検索ベースの解法を用いて目的関数を解くよう適合されている。システムは、さらに、潜在的な買い手によって入力され受信されたキーワードに基づいた適合に従って、対応する広告ソースを検索するよう適合された検索ユニット５０１と、検索された対応する広告ソースを潜在的な買い手に対してウェブサイトページで表示するよう適合された表示ユニット５０２と、を備える。表示ユニットは、音声、ビデオ、または、潜在的な買い手が知覚できる任意のその他の適切な情報を表示してもよい。
【００８２】
この実施形態で提供されたデバイスは、検索エンジンサーバに統合されてもよいし、別個のデバイスとして検索エンジンサーバに接続されてもよい。本願の方法がソフトウェアに実装される場合、検索エンジンサーバに新たに追加された機能として実装されてもよいし、別個のコンポーネントとして実装されてもよい。本願は、記載されている方法およびデバイスの実装例に限定されない。
【００８３】
図６は、広告ソースとキーワードとの間の適合を生成するためのシステムの別の実施形態を示すブロック図である。この例において、デバイスは、所定の分類基準に従って現在のオンライン商取引プラットフォームシステムにおいて売り手によって提供されたすべての広告ソースを分類するよう適合された分類モジュール６０１と、それぞれのカテゴリの下で売り手によって提供されたすべての広告ソースの分布を取得するよう適合された分布取得サブモジュール６０２と、分布に従って各カテゴリの下で所定の数の広告ソースを選択するよう適合された選択サブモジュール６０３と、ここで、所定の数は適合される広告ソースの数よりも大きい、行列Ｘを確立するよう適合された行列確立サブモジュール６０４と、ここで、行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースと適合するか否かを表す、列によって行列をベクトルに変換し、ベクトルに従って以下の目的関数を持つ計画モデルを確立するよう適合された変換サブモジュール６０５と、を備える。
【数３】
0005575270.tif 000005
【００８４】
システムは、さらに、各キーワードと各広告ソースとの間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さをそれぞれ取得するよう適合されたパラメータ取得サブモジュール６０６を備える。
【００８５】
システムは、さらに、最大の広告ソースの利益を有する複数の適合組み合わせの中で、売り手に対する複数の適合組み合わせによる複数の売り手利益を計算するよう適合された計算サブモジュール６０７と、最大の売り手利益を有する複数の適合組み合わせが存在するか否かを判定し、存在する場合には、類似度、広告ソースの幅、および／または、広告ソースの深さに従って最大の売り手利益を有する複数の適合組み合わせをソートして、最終的なソート結果の中で最上位の適合組み合わせを選択し、存在しない場合には、最大の売り手利益を有する１つの適合組み合わせを直接的に取得するよう適合された第１の適合取得サブモジュール６０８と、を備える。
【００８６】
システムは、さらに、現在取得されている適合組み合わせにおける広告ソースが適合するキーワードの数が上限に達しているか否かを判定して、上限に達している場合には、その適合組み合わせの対応付けを削除し、上限に達していない場合には、その適合組み合わせを格納するよう適合された判定サブモジュール６０９を備える。
【００８７】
システムは、さらに、選択された広告ソースすべてが上限の数のキーワードに適合するまで、キーワードの各々と広告ソースの各々との間の他の適合から、制約条件を満たす適合組み合わせを連続的に取得するよう適合された第２の適合取得サブモジュール６１０を備える。
【００８８】
システムは、さらに、広告ソースの各々の総利益に従って、取得された適合組み合わせをソートし、ソート後に制約条件を満たす適合組み合わせを解とするよう適合された順序付けサブモジュール６１１を備える。
【００８９】
上述のモジュールおよび／またはユニットは、１または複数の汎用プロセッサ上で実行されるソフトウェアコンポーネントとして、特定の機能を実行するよう設計されたプログラム可能論理デバイスおよび／または特定用途向け集積回路などのハードウエアとして、もしくは、それらの組み合わせとして実装することができる。いくつかの実施形態において、モジュールは、コンピュータデバイス（パーソナルコンピュータ、サーバ、ネットワーク装置など）に本発明の実施形態に記載された方法を実行させるための複数の命令など、不揮発性記憶媒体（光学ディスク、フラッシュ記憶装置、携帯用ハードディスクなど）に格納することができるソフトウェア製品の形態で具現化されてよい。モジュールおよび／またはユニットは、単一のデバイス上に実装されてもよいし、複数のデバイスにわたって分散されてもよい。モジュールおよびユニットの機能は、互いに統合されてもよいし、複数のサブモジュールまたはサブユニットにさらに分割されてもよい。
【００９０】
最後に、第１および第２などの関係語は、１つの物または動作を別の物または動作と区別するために使われているに過ぎず、これらの物または動作間の実際の関係性または順番を主張するものでも示唆するものでもないことに注意されたい。さらに、「備える」、「含む」、または、それらの変化形は、非排他的な包含を意図しているため、一連の要素を備える処理、方法、物品、または、装置は、これらの要素を含むだけでなく、明示的に列挙されていない要素、もしくは、処理、方法、物品、または、装置に元より備えられている要素を含む他の要素をも含む。さらなる限定が与えられない限り、「（単数形の要素を）備える」という表現によって規定される要素は、その要素を含む処理、方法、物品、または、装置内にさらなる同一の要素が存在することを排除するものではない。
【００９１】
上述の実施形態は、理解しやすいようにいくぶん詳しく説明されているが、本発明は、提供された詳細事項に限定されるものではない。本発明を実施する多くの代替方法が存在する。開示された実施形態は、例示であり、限定を意図するものではない。
適用例１：オンライン広告の方法であって、売り手によって提供された複数の広告ソースの中から、所定の条件を満たす複数の選択済み広告ソースを選択し、前記複数の選択済み広告ソースに対応する複数のキーワードセットを生成し、前記複数の選択済み広告ソースおよび前記複数のキーワードセットの適合を表す計画モデルを１組の所定の制約条件に従って確立し、前記複数の広告ソースの少なくともいくつかと、前記複数のキーワードセットとの間の実質的に最適な適合を前記計画モデルの解を求めることによって決定すること、を備える、方法。
適用例２：適用例１に記載の方法であって、前記計画モデルは前記１組の所定の制約条件を条件とする目的関数を含み、前記計画モデルの解を求めることは前記目的関数の解を求めるために検索を行うことを含む、方法。
適用例３：適用例１に記載の方法はさらに、潜在的な買い手によって入力されたキーワードセットを受信し、前記受信されたキーワードセットに基づく前記実質的に最適な適合に従って対応する広告ソースを検索すること、を備える、方法。
適用例４：適用例１に記載の方法はさらに、前記検索された対応する広告ソースを前記潜在的な買い手に対してウェブページで表示することを備える、方法。
適用例５：適用例１に記載の方法はさらに、所定の分類基準に従って前記売り手によって提供された前記複数の広告ソースを分類することを備える、方法。
適用例６：適用例５に記載の方法であって、前記所定の条件を満たす前記複数の選択済み広告ソースの選択は、分類された１組の広告ソースと関連して実行される、方法。
適用例７：適用例６に記載の方法であって、カテゴリと関連して、前記所定の条件を満たす前記売り手によって提供された前記広告ソースを選択することは、カテゴリに従って、前記売り手によって提供された前記複数の広告ソースの分布を取得し、前記分布に従ってそれぞれのカテゴリから所定の数の広告ソースを選択すること、を含み、前記所定の数は、キーワードセットと適合される広告ソースの数に対する売り手指定の制約条件よりも大きい、方法。
適用例８：適用例１に記載の方法であって、前記１組の所定の制約条件は、キーワードセットと適合される前記広告ソースの数を含む、方法。
適用例９：適用例１に記載の方法であって、前記１組の所定の制約条件は、前記広告ソースの各々に対するキーワードセットの最大数を含む、方法。
適用例１０：適用例１に記載の方法であって、前記１組の所定の制約条件に従って前記計画モデルを確立することは、行列Ｘを構築し、前記行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースに適合するか否かを表し、前記１組の所定の制約条件を条件とする目的関数を
【数４】
0005575270.tif 000006
として確立すること、を含み、
Ｐijは、前記ｉ番目のキーワードおよび前記ｊ番目の広告ソースの間の適合による売り手利益を表し、Ｘijは、前記ｉ番目のキーワードが前記ｊ番目の広告ソースと適合するか否かを表し、Ｎjは、前記ｊ番目の広告ソースが持つことを許されるキーワードの最大数を表し、ｎは、前記キーワードの総数を表し、ｍは、前記選択済み広告ソースの総数を表す、方法。
適用例１１：適用例１０に記載の方法であって、前記目的関数は、検索ベースの解法を用いて解かれる、方法。
適用例１２：適用例１０に記載の方法であって、前記目的関数を解くことは、前記１組の所定の制約条件を満たす適合組み合わせを取得することであって、前記キーワードの各々と前記選択済み広告ソースの各々との間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さをそれぞれ取得し、  最大の広告ソースの利益を有する複数の適合組み合わせの中で、前記売り手に対する前記複数の適合組み合わせから複数の売り手利益を計算し、最大の売り手利益を有する１または複数の適合組み合わせを決定し、現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達しているか否かを判定し、現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達している場合に前記適合組み合わせの対応付けを削除し、達していない場合に前記適合組み合わせを格納すること、を含む、前記１組の所定の制約条件を満たす適合組み合わせを取得することと、前記選択済み広告ソースすべてが前記最大数のキーワードに適合するまで、前記キーワードの各々と前記広告ソースの各々との間の他の適合から前記１組の所定の制約条件を満たす適合組み合わせを繰り返し取得し、前記広告ソースの各々の総利益に従って、前記取得した適合組み合わせをソートし、前記取得した適合組み合わせから前記１組の所定の制約条件を満たす適合組み合わせを前記目的関数の解として選択すること、を備える、方法。
適用例１３：オンライン広告システムであって、１または複数のプロセッサであって、売り手によって提供された複数の広告ソースの中から、所定の条件を満たす複数の選択済み広告ソースを選択し、前記複数の選択済み広告ソースに対応する複数のキーワードセットを生成し、前記複数の選択済み広告ソースおよび前記複数のキーワードセットの適合を表す計画モデルを１組の所定の制約条件に従って確立し、前記複数の広告ソースの少なくともいくつかと、前記複数のキーワードセットとの間の実質的に最適な適合を、前記計画モデルの解を求めることによって決定することを実行するように構成されている１または複数のプロセッサと、前記１または複数のプロセッサに接続され、前記プロセッサに命令を提供するよう構成されている１または複数のメモリと、を備える、システム。
適用例１４：適用例１３に記載されたシステムであって、前記プロセッサは、さらに、
潜在的な買い手によって入力されたキーワードセットを受信し、前記受信されたキーワードセットに基づいた前記実質的に最適な適合に従って対応する広告ソースを検索するように構成されている、システム。
適用例１５：適用例１３に記載のシステムであって、前記プロセッサは、さらに、前記検索された対応する広告ソースを前記潜在的な買い手に対してウェブページで表示するように構成されている、システム。
適用例１６：適用例１３に記載のシステムであって、前記プロセッサは、さらに、所定の分類基準に従って、前記売り手によって提供された前記複数の広告ソースを分類するように構成されている、システム。
適用例１７：適用例１６に記載のシステムであって、前記所定の条件を満たす前記複数の選択済み広告ソースの選択は、分類された１組の広告ソースと関連して実行される、システム。
適用例１８：適用例１７に記載のシステムであって、カテゴリと関連して、前記所定の条件を満たす前記売り手によって提供された前記広告ソースを選択することは、カテゴリに従って、前記売り手によって提供された前記複数の広告ソースの分布を取得し、前記分布に従ってそれぞれのカテゴリから所定の数の広告ソースを選択すること、を含み、前記所定の数は、キーワードセットと適合される広告ソースの数に対する売り手指定の制約条件よりも大きい、システム。
適用例１９：適用例１３に記載のシステムであって、前記制約条件は、キーワードセットと適合される前記広告ソースの数を含む、システム。
適用例２０：適用例１３に記載のシステムであって、前記制約条件は、前記広告ソースの各々に対するキーワードセットの最大数を含む、システム。
適用例２１：適用例１３に記載のシステムであって、前記１組の所定の制約条件に従って前記目的関数を確立することは、行列Ｘを確立し、前記行列の成分Ｘi,jは、ｉ番目のキーワードがｊ番目の広告ソースに適合するか否かを表し、前記目的関数を
【数５】
0005575270.tif 000007
として確立すること、を含み、
Ｐijは、前記ｉ番目のキーワードおよび前記ｊ番目の広告ソースの間の適合による売り手利益を表し、Ｘijは、前記ｉ番目のキーワードが前記ｊ番目の広告ソースと適合するか否かを表し、Ｎjは、前記ｊ番目の広告ソースが持つことを許されるキーワードの最大数を表し、ｎは、前記キーワードの総数を表し、ｍは、前記選択済み広告ソースの総数を表す、システム。
適用例２２：適用例２１に記載のシステムであって、前記目的関数は、検索ベースの解法を用いて解かれる、システム。
適用例２３：適用例２１に記載のシステムであって、前記目的関数を解くことは、前記１組の所定の制約条件を満たす適合組み合わせを取得することであって、前記キーワードの各々と前記選択済み広告ソースの各々との間の適合に対応する広告ソースの利益、類似度、広告ソースの幅、および、広告ソースの深さをそれぞれ取得し、最大の広告ソースの利益を有する複数の適合組み合わせの中で、前記売り手に対する前記複数の適合組み合わせから複数の売り手利益を計算し、最大の売り手利益を有する１または複数の適合組み合わせを決定し、現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達しているか否かを判定し、現行の適合組み合わせにおける前記広告ソースが適合するキーワードの数が前記最大数に達している場合に、前記適合組み合わせの対応付けを削除し、達していない場合に、前記適合組み合わせを格納すること、を含む、前記１組の所定の制約条件を満たす適合組み合わせを取得することと、前記選択済み広告ソースすべてが前記最大数のキーワードに適合するまで、前記キーワードの各々と前記広告ソースの各々との間の他の適合から前記１組の所定の制約条件を満たす適合組み合わせを繰り返し取得し、前記広告ソースの各々の総利益に従って、前記取得した適合組み合わせをソートし、前記取得した適合組み合わせから前記１組の所定の制約条件を満たす適合組み合わせを前記目的関数の解として選択すること、を備える、システム。
【図１】
0005575270.tif 000010
【図２】
0005575270.tif 000011
【図３】
0005575270.tif 000012
【図４】
0005575270.tif 000013
【図５】
0005575270.tif 000014
【図６】
0005575270.tif 000015