(57)【要約】  要求元デバイスに位置ベースの広告を提供する方法及びシステムを提供する。広告システムは、複数の広告ソースから広告を収集し、収集された広告からデータを抽出し、抽出されたデータを共通フォーマットで格納することによって広告を集約する。広告を集約した後に、広告システムは、各広告をさまざまなデバイスタイプによってサポートされるプロトコルに固有である複数の広告フォーマットに変換する。広告システムは、広告に関するクエリを受け取る時に、一致する広告を識別し、これらを位置に基づいてランク付けする。広告システムは、要求元デバイスのために適当な広告フォーマットを選択する。
2010503071.tif 000002
【特許請求の範囲】
【請求項１】
要求元デバイスに位置ベースの広告を提供するコンピュータシステムであって、
複数の広告ソースから広告を収集し、前記収集された広告からデータを抽出し、前記広告の前記抽出されたデータを共通フォーマットで格納する集約コンポーネント（１４２）と、
広告の前記抽出されたデータをデバイスタイプに固有である複数の広告フォーマットに変換する変換コンポーネント（１４３）と、
要求元デバイスに関連するクエリ及びクエリ位置に一致する広告を識別し、前記広告に関連する位置に基づいて前記広告をランク付けし、前記要求元デバイスのデバイスタイプに基づいて前記広告の広告フォーマットを選択する検索コンポーネント（１５２）と
を含むことを特徴とするコンピュータシステム。
【請求項２】
前記集約コンポーネントは、前記広告の会社名、会社位置、キーワード、及び会社カテゴリを抽出することを特徴とする請求項１に記載のコンピュータシステム。
【請求項３】
前記集約コンポーネントは、位置及びキーワードに基づくハイブリッドインデックスを使用して前記抽出されたデータを格納することを特徴とする請求項１に記載のコンピュータシステム。
【請求項４】
前記デバイスタイプは、前記デバイスによってサポートされるデータプロトコルに基づくことを特徴とする請求項１に記載のコンピュータシステム。
【請求項５】
データプロトコルは、ＳＭＳ、ＷＡＰ、ＸＭＬ、ＭＭＳ、及びＨＴＭＬからなる一群から選択されることを特徴とする請求項４に記載のコンピュータシステム。
【請求項６】
要求元デバイスから受け取られたクエリと一致するコンテンツを検索するコンテンツコンポーネントを含むことを特徴とする請求項１に記載のコンピュータシステム。
【請求項７】
前記検索コンポーネントは、広告に関連するサービングエリアに基づいて前記広告をランク付けすることを特徴とする請求項１に記載のコンピュータシステム。
【請求項８】
そのサービングエリアが前記要求元デバイスの位置を含む広告は、他の広告より高くランク付けされることを特徴とする請求項７に記載のコンピュータシステム。
【請求項９】
そのサービングエリアが前記要求元デバイスの前記位置を含まない広告は、前記要求元デバイスの前記位置と前記サービングエリアとの間の距離に基づいてランク付けされることを特徴とする請求項８に記載のコンピュータシステム。
【請求項１０】
前記集約コンポーネントは、各広告の会社名、会社位置、キーワード、及び会社カテゴリを抽出し、
前記集約コンポーネントは、位置及びキーワードに基づくハイブリッドインデックスを使用して前記抽出されたデータを格納し、
前記デバイスタイプは、前記デバイスによってサポートされるデータプロトコルに基づき、前記検索コンポーネントは、広告に関連するサービングエリアに基づいて広告をランク付けすることを特徴とする請求項１に記載のコンピュータシステム。
【請求項１１】
複数の広告ソースから広告を提供するステップ（１４１）と、
収集された広告からデータの共通セットを抽出するステップ（１４２）と、
各広告の前記抽出されたデータをデバイスタイプに固有の複数の広告フォーマットに変換するステップ（１４３）と、
要求元デバイスからクエリを受け取るステップ（１５１）と、
前記クエリに関連する位置を識別するステップ（１５４）と、
前記クエリ及び識別された位置と一致する候補広告を識別するステップ（１５５）と、
前記識別された位置及び前記広告に関連する位置に基づいて前記候補広告をランク付けするステップ（１５６）と、
広告ごとに、前記要求元デバイスのデバイスタイプに基づいて広告フォーマットを選択するステップ（６０６）と
を含む方法によって、要求元デバイス用の広告を選択するためにコンピューティングシステムを制御する命令を含むことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１２】
前記識別された位置は、前記クエリから導出されることを特徴とする請求項１１に記載のコンピュータ読み取り可能な記録媒体。
【請求項１３】
前記識別された位置は、前記要求元デバイスの位置に基づくことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記録媒体。
【請求項１４】
広告の前記ランク付けするステップは、前記広告に関連するサービングエリアに基づくことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記録媒体。
【請求項１５】
前記ランク付けするステップは、前記要求元デバイスに表示される地図区域に基づくことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記録媒体。
【請求項１６】
位置及びキーワードに基づくハイブリッドインデックスを使用して前記抽出されたデータを格納するステップを含むことを特徴とする請求項１１に記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
前記識別された位置は、前記クエリから導出され、
広告の前記ランク付けするステップは、前記広告に関連するサービングエリアに基づき、
前記抽出されたデータは、位置及びキーワードに基づくハイブリッドインデックスを使用して格納されることを特徴とする請求項１１に記載のコンピュータ読み取り可能な記録媒体。
【請求項１８】
要求元デバイスに広告を提供するコンピュータシステムであって、
広告からデータを抽出し、位置及びキーワードに基づく前記広告のインデックスを生成する、集約コンポーネント（１４２）と、
広告の前記抽出されたデータをデバイスタイプに固有の複数の広告フォーマットに変換する変換コンポーネント（１４３）と、
クエリ及び位置と一致する広告を前記インデックスから識別し、前記広告に関連する位置に基づいて前記識別された広告をランク付けし、識別された広告ごとに前記要求元デバイスのデバイスタイプに基づいて広告フォーマットを選択する、検索コンポーネント（１５２）と
を含むことを特徴とするコンピュータシステム。
【請求項１９】
前記生成されるインデックスは、ハイブリッドインデックスであることを特徴とする請求項１８に記載のコンピュータシステム。
【請求項２０】
前記検索コンポーネントは、前記広告に関連するサービングエリアに基づいて広告をランク付けすることを特徴とする請求項１８に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、要求元デバイスに位置ベースの広告を提供するコンピュータシステム及びその方法に関する。
【背景技術】
【０００２】
多数のユーザが、携帯情報端末（ＰＤＡ）及び携帯電話機などのモバイルデバイスを使用して、さまざまなインターネットベースのサービスと対話する。一般的なインターネットベースのサービスには、地図サービス、ナビゲーションサービス及び検索サービスが含まれる。地図サービスは、ウェブサービスとして提供できるが、ユーザによる要求に従ってさまざまな位置の地図を提供する。例えば、車両を運転しているユーザが、携帯電話機を使用して、地図サービスが周囲の区域の地図を提供することを要求する場合がある。地図サービスは、携帯電話機によって提供される全地球測位システム（ＧＰＳ）座標に基づいてユーザの現在位置を判定し、携帯電話機に周囲の区域の地図をダウンロードすることができ、その結果、その地図をユーザに表示できるようになる。地図サービスは、ユーザの現在位置以外の位置に基づいて地図を提供することができる。例えば、ユーザは、遠くの都市での休暇を計画する時に地図サービスを使用する場合がある。その場合に、地図サービスは、遠くの都市の地図を提供することができる。地図サービスは、モバイルデバイスだけではなく、任意のコンピューティングデバイス（例えば、デスクトップコンピュータ）によってアクセス可能とすることができる。
【０００３】
ナビゲーションサービスは、ある位置とある位置の間の旅行の道案内を提供する。例えば、車両を運転しているユーザは、ＰＤＡを使用して目的地を指定し、ユーザの現在位置からその目的地への道案内を提供するようにナビゲーションサービスに要求することができる。ナビゲーションサービスは、（例えば、ＧＰＳ情報を使用して）ユーザの現在位置を判定した後に、道案内を準備し、ユーザへの提示のためにユーザのＰＤＡに道案内をダウンロードする。この道案内は、さまざまなフォーマットとすることができる。例えば、道案内を、地図を強調表示することによって、または曲がり角の指示の書かれたリストもしくは可聴リストを提供することによって提示することができる。
【０００４】
検索サービスは、検索要求またはクエリを満たす企業（例えば、小売りアウトレット、政府機関及び学校）をユーザが検索することを可能にすることができる。例えば、車両を運転しているユーザは、ＰＤＡを使用して、近くにあるレストランを識別するように検索サービスに要求することができる。ユーザは、クエリ「nearby restaurants（近くにあるレストラン）」を入力することができる。検索サービスは、ユーザの現在位置の近くにあるレストランを識別し、ユーザのＰＤＡに、それらのレストランのリストまたはそれらのレストランの位置を示す地図を提供する。
【０００５】
地図サービス、ナビゲーションサービス及び検索サービスなどの多くのインターネットベースのサービスは、その唯一の収入源として、または他の収入源を補うために、広告収入に頼る。あるサービスが要求を受け取る時に、そのサービスは、その要求に対する応答と一緒に広告を提供することができる。ナビゲーションサービスは、目的地に何らかの形で関係する広告を提供することができる。例えば、目的地が米国のワシントン特別州である場合に、ナビゲーションサービスは、ワシントン特別州のサービスを提供する旅行会社、レストラン、航空会社などの広告を提供することができる。地図サービスは、同様に、表示される区域に何らかの形で関係する広告を提供することができ、検索サービスは、検索用語及びユーザの現在位置に関係する広告を提供することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許出願第１１／４６７８１０号明細書
【特許文献２】米国特許出願第１１／２７８３０１号明細書
【特許文献３】米国特許出願第１１／０８１０１４号明細書
【特許文献４】米国特許出願第１１／２７７７０４号明細書
【特許文献５】米国特許出願第１１／１３８６８５号明細書
【非特許文献】
【０００７】
【非特許文献１】Beckman, N., Kriegel, H., Schneider, R., and Seeger, B., "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles, " ACM, May 1990, pp. 322-331
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、何らかの形で位置に関係する広告の提供に関する問題は、広告が、しばしば、広告されるサービスからユーザの現在位置までの距離に基づいてランク付けされることである。例えば、米国のシアトルにいるユーザが「nearby restaurants」を入力する場合に、検索サービスは、ユーザの現在位置から半径５マイル（８ｋｍ）にあるコーヒー系列販売店、ファストフード系列販売店及びフルサービスレストランの広告を識別する可能性がある。この検索サービスは、８軒のコーヒー系列販売店がユーザに最も近い（例えば、ユーザから１マイル（１．６ｋｍ以内））ので、これらの店をランク付けし、２マイル（３．２ｋｍ）離れたコーヒー系列販売店を３マイル（４．８ｋｍ）離れたレストランより高くランク付けする可能性がある。しかし、ユーザは、２マイル（３．２ｋｍ）離れたコーヒー系列販売店に関心を持つ可能性は低いが、３マイル（４．８ｋｍ）離れたレストランに関心を持つ可能性が高い。その場合、距離に基づくランキングは、ユーザの観点からの正しいランキングを必ずしも反映していない。
【０００９】
これらのインターネットベースのサービスの多くは、提供される広告に対する広告サービスに頼る可能性がある。広告サービスは、通常、その広告主によって提供された広告のデータベースを有する。従って、インターネットベースのサービスは、広告サービスによって提供される広告に制限される。しかし、広告する会社に関する情報の多数の他の潜在的なソースがある。例えば、ある会社が、イエローページの電子版に広告を出すことができ、商工会議所が、地方の会社の電子リストを提供することができるなどである。通常、インターネットベースのサービスは、広告の掲示をサポートするためにビジネス情報のこれらのさまざまなソースを利用することはできない。
【００１０】
これらのインターネットベースのサービスの多くは、ワールドワイドウェブ（ＷＷＷ）プロトコルだけをサポートして、それらが広告を提供できるタイプのデバイスに制限されてもいる。例えば、ＨＴＭＬプロトコルまたはＨＴＴＰプロトコルをサポートしない携帯電話機は、これらのプロトコルに基づく広告を表示することができない。さらに、あるデバイスが、インターネットベースのサービスのプロトコルをサポートする場合であっても、広告がそのデバイスに適当ではない場合がある。例えば、そのデバイスが非常に小さいディスプレイを有する場合に、より大きいディスプレイ用に設計された広告は、小さいディスプレイで提示された時に効果的でない可能性が高い。
【課題を解決するための手段】
【００１１】
要求元デバイスに位置ベースの広告を提供する方法及びシステムを提供する。広告システムは、複数の広告ソースから広告を収集し、収集された広告からデータを抽出し、抽出されたデータを共通フォーマットで格納することによって広告を集約する。広告システムは、広告の「サービングエリア（serving area）」を識別することもできる。広告を集約した後に、広告システムは、各広告をさまざまなタイプのデバイスによってサポートされるプロトコルに固有である複数の広告フォーマットに変換する。広告システムは、広告のクエリを受け取った後に、そのクエリと一致する広告を検索する。一致する広告を候補広告として識別した後に、広告システムは、クエリに関連する位置及び広告に関連する位置に基づいて候補広告をランク付けする。広告システムは、高くランク付けされた広告のそれぞれについて要求元デバイスにとって適当な広告フォーマットを選択し、広告の要求に応答してこれらの広告を提供する。
【００１２】
この「課題を解決するための手段」は、下の「発明を実施するための形態」でさらに説明される概念の選択物を単純化された形で紹介するために提供されたものである。この「課題を解決するための手段」は、特許請求の範囲に記載される主題の主要な特徴または本質的な特徴を特定することを意図したものではないし、特許請求の範囲に記載される主題の範囲を判定する際の助けとして使用することを意図したものでもない。
【図面の簡単な説明】
【００１３】
【図１】一実施形態の広告システムのコンポーネントを示すブロック図である。
【図２】一実施形態のプライマリインデックスとしてのキーワードインデックスを伴うハイブリッドインデックスを示す図である。
【図３】一実施形態の広告システムの広告集約コンポーネントの処理を示す流れ図である。
【図４】一実施形態の広告システムの広告変換コンポーネントの処理を示す流れ図である。
【図５】一実施形態の広告システムの広告インデクシングコンポーネントの処理を示す流れ図である。
【図６】一実施形態の広告システムの広告検索コンポーネントの処理を示す流れ図である。
【図７】一実施形態の広告システムのクエリ位置識別コンポーネントの処理を示す流れ図である。
【図８】一実施形態の広告システムの候補広告識別コンポーネントの処理を示す流れ図である。
【図９】一実施形態の広告システムの候補広告ランク付けコンポーネントの処理を示す流れ図である。
【発明を実施するための形態】
【００１４】
要求元デバイスに位置ベースの広告を提供する方法及びシステムを提供する。一実施形態で、広告システムは、複数の広告ソースから広告を収集することによって広告を集約する。例えば、広告システムは、ペイフォークリック（pay for click）広告システムからの広告、電子版イエローページからの広告及び電子会社リスティングから生成された広告を収集することができる。広告システムは、収集された広告からデータを抽出し、抽出されたデータを共通フォーマットで格納する。例えば、広告システムは、会社名、会社位置、キーワード及び会社カテゴリを含むデータを抽出することができる。広告システムは、広告の「サービングエリア」を識別することもできる。サービングエリアは、広告される会社がそこから顧客を引き寄せる可能性が高い地理的区域を表す。例えば、コーヒー系列販売店の広告のサービングエリアは、そのコーヒー系列販売店を中心とする半径３ブロックのエリアであるが、自動車販売代理店のサービングエリアは、半径５０マイル（８０ｋｍ）のエリアとすることができる。広告システムは、広告に関連する明示的メタデータからまたは広告の内容の分析からなど、さまざまな形でサービングエリアを判定することができる。広告を集約した後に、広告システムは、各広告をさまざまなタイプのデバイスによってサポートされるプロトコルに固有な複数の広告フォーマットに変換する。例えば、広告システムは、ショートメッセージサービス（ＳＭＳ）プロトコルまたはＷＡＰ（Wireless Application Protocol）プロトコルをサポートするデバイス用のフォーマットに広告を変換することができる。広告システムは、広告のクエリを受け取る時に、そのクエリに一致する広告を検索する。デバイスのユーザは、コンテンツを検索するために、クエリをコンテンツサービス（例えば、地図サービス）にサブミットすることができる。コンテンツサービスは、そのクエリに一致する広告を識別するために、そのクエリを広告システムにサブミットすることができる。一致する広告を候補広告として識別した後に、広告システムは、クエリに関連する位置及び広告に関連する位置に基づいて候補広告をランク付けする。クエリに関連する位置は、デバイスの位置によって表されるユーザの現在位置またはクエリ自体から導出されるクエリ位置とすることができる。例えば、広告システムは、そのサービングエリアがユーザの現在位置またはクエリ位置を含む広告を、そうでない広告より高くランク付けすることができる。次に、広告システムは、高くランク付けされた広告のそれぞれの要求元デバイスに適当な広告フォーマットを選択し、広告の要求に応答してこれらの広告を提供する。
【００１５】
一実施形態で、広告システムは、広告のサービングエリアに基づいてユーザに表示すべき広告を選択する。サービングエリアに基づいて広告を選択するシステムの一例は、特許文献１に記載されている。広告システムは、さまざまな広告ソースから広告を集約する時に広告のサービングエリアを確立することができる。広告システムは、最初に、ユーザに提供すべき候補広告を識別することができ、その後、サービングエリアに基づいてこれらの広告をフィルタリングすることができる。広告検索システムは、サブミットされたクエリに関連する広告を検索する。広告システムは、これらの関連する広告を候補広告と考える。広告システムは、そのサービングエリアがユーザの現在位置を含む候補広告だけを選択することができる。例えば、小規模コーヒー系列販売店のサービングエリアが２ブロックであり、大規模コーヒー系列販売店のサービングエリアが５ブロックであり、ユーザが、小規模コーヒー系列販売店から３ブロック、大規模コーヒー系列販売店から４ブロックの場所に位置する場合に、広告システムは、小規模コーヒー系列販売店がユーザにより近い場合であっても、小規模コーヒー系列販売店の広告ではなく大規模コーヒー系列販売店の広告を選択するはずである。その代わりに、広告システムが、サービングエリアを使用して、そのサービングエリアがユーザの現在位置を含む広告を、そのサービングエリアがユーザの現在位置を含まない広告より高くランク付けすることができる。広告システムは、そのサービングエリアがユーザの現在位置を含まない広告を、ユーザの現在位置からそのサービングエリアまでの距離に基づいてランク付けすることができる。
【００１６】
一実施形態で、広告システムは、現在ユーザに表示されている地図区域に基づいてユーザに提示すべき広告を選択する。地図区域に基づいて広告を選択するシステムの一例は、特許文献１に記載されている。広告システムは、最初に、ユーザに提供される候補広告を識別することができ、その後、「プロバイダ位置」に基づいてこれらの広告をフィルタリングすることができる。広告システムは、広告のプロバイダ位置を判定することができ、このプロバイダ位置は、その広告によって広告されるサービスが提供される物理的位置を表す。例えば、コーヒー系列販売店の広告のプロバイダ位置は、その系列販売店の位置であり、銀行の場合には支店オフィスとすることができる。広告システムは、広告に関連する明示的メタデータからまたは広告の内容の分析からなど、さまざまな形でプロバイダ位置を判定することができる。広告システムは、さまざまな広告ソースから広告を集約する時に広告のプロバイダ位置を確立することができる。広告システムは、そのプロバイダ位置が現在ユーザに表示されている地図区域内にあるか、またはそれに含まれる候補広告を選択する。
【００１７】
一実施形態で、広告システムは、広告の位置属性とキーワード属性の両方をインデクシングするハイブリッドインデックスを使用して広告の位置ベース検索を実行する。ハイブリッドインデックスの例は、特許文献２に記載されている。広告システムは、主インデックスとしての位置属性または主インデックスとしてのキーワード属性のいずれかを使用してハイブリッドインデックスを生成する。位置属性が主インデックスである時にはキーワード属性が副インデックスであり、キーワード属性が主インデックスである時には位置属性が副インデックスである。ハイブリッドインデックスを生成するために、広告システムは、各広告のキーワード属性及び位置属性の値を識別する。広告システムは、広告から導出された位置名をベクトルベースの位置にマッピングすることができ、このベクトルベースの位置は、インデクシングに使用される。広告システムは、各マッピング先の位置を、その対角線上の角の座標によって識別される長方形区域として表すことができる。広告システムは、第１属性の各値を副インデックスにマッピングするために主インデックスを生成することができる。従って、広告システムは、第１属性の値ごとに副インデックスを生成して、副属性の値を、第１属性及び第２属性の関連する値を有する広告にマッピングする。次に、広告システムは、ハイブリッドインデックスを使用して位置ベースの検索を実行する。位置ベースのクエリは、クエリ用語及び位置を含み、この位置は、クエリ用語から導出することができる。広告を識別するために、広告システムは、第１属性のクエリ値を使用して主インデックスを検索して、関連する副インデックスを突き止める。次に、広告システムは、第２属性のクエリ値の関連する副インデックスを検索して、第１属性と第２属性との両方のクエリ値に関連する広告を識別する。次に、広告システムは、識別された広告を候補広告として返す。
【００１８】
広告システムは、広告のプロバイダ位置及びサービングエリアを判定するシステムを含むか、そのシステムと相互作用することができる。プロバイダ位置及びサービングエリアを判定するさまざまな技法は、特許文献３及び特許文献４に記載されている。例えば、広告システムは、ウェブリソース（例えば、広告される会社のウェブサイト）にアクセスするユーザのアドレス（例えば、ＩＰアドレス）に基づいてそのウェブリソースのサービングエリアを判定する位置システムと相互作用することができる。位置システムは、ウェブアクセスログ、クリックスルー（click through）ログなどのウェブアクセス情報を分析することによって、ウェブリソースへのアクセスを識別することができる。ウェブアクセスログは、ウェブサイトによって生成することができ、そのウェブサイトへのユーザによるアクセスごとに１つのエントリを含むことができる。各エントリは、ユーザのＩＰアドレスを含むことができる。クリックスルーログは、検索エンジンによって生成することができ、一般に「クリックスルー」と称する、クエリ結果に含まれるウェブサイトへの参照の選択ごとに１つのエントリを含むことができる。位置システムは、ウェブアクセス情報からＩＰアドレスを取り出して、そのＩＰアドレスに関連する地理的位置を判定する。Hexasoft Development社による「IP2Location」及びQuova社による「GeoPoint」など、ＩＰアドレスから地理的位置へのマッピングを提供する多くの市販製品が入手可能である。位置システムは、ウェブサイトへの各ユーザアクセスの位置を識別した後に、ウェブリソースのサービングエリアを判定するために、識別された位置を分析する。位置システムは、大陸、国、州、及び都市によって編成されたものなどの位置の階層を使用することができる。位置システムは、その位置内のユーザによるウェブリソースのアクセスの回数に基づいて、及び階層的にその位置に含まれる位置内のユーザによるウェブリソースのアクセスの回数の分布に基づいて、サービングエリアの位置を選択することができる。位置システムは、その代わりに、プロバイダ位置及び会社カテゴリに基づいてサービングエリアを判定することができる。各会社カテゴリは、異なるサービング半径のエリアを有することができる。例えば、コーヒー系列販売店カテゴリのサービング半径を３ブロックとすることができ、自動車販売代理店カテゴリのサービング半径を５０マイル（８０ｋｍ）とすることができる。サービングエリアは、プロバイダ位置からサービング半径まで延びる円形の区域をカバーすることができる。
【００１９】
図１は、一実施形態の広告システムのコンポーネントを示すブロック図である。広告システム１３０は、通信リンク１２０を介してユーザデバイス１１０に接続され、通信リンク１２０は、無線ネットワークとすることができる。広告システム１３０は、広告を前処理する広告プロセッサ１４０を含む。広告プロセッサ１４０は、さまざまな広告ソース１４１とインターフェースすることができる。広告プロセッサ１４０は、広告集約コンポーネント１４２、広告変換コンポーネント１４３、及び広告インデクシングコンポーネント１４４をさらに含む。広告集約コンポーネント１４２は、広告ソースから広告を収集し、収集された広告からデータを抽出し、広告の抽出されたデータを共通のフォーマットで格納する。広告変換コンポーネント１４３は、広告の抽出されたデータを、さまざまなプロトコルまたはデバイスタイプに固有の複数の広告フォーマットに変換する。広告インデクシングコンポーネント１４４は、位置及びキーワードに基づいてハイブリッドインデックスを生成する。当業者は、位置のみに基づくインデクシングまたはキーワードのみに基づくインデクシングなど、他のインデクシング技法を使用できることを了解するであろう。さらに、生成されたインデックスを、ハッシュテーブル、リンクリスト、ツリーデータ構造など、さまざまなデータ構造を使用して格納することができる。広告システム１３０は、集約され、変換され、インデクシングされた広告を含む広告ストア１３１をも含む。広告システム１３０は、ユーザによって要求されたコンテンツを提供するために、地図サービスまたはナビゲーションサービスなどのさまざまなコンテンツサービス１３２とインターフェースすることができる。コンテンツサービスは、広告システムと同一のコンピュータシステム上でまたは別々のコンピュータシステム上で実施することができる。広告システム１３０は、要求受信／応答送信コンポーネント１５１、広告検索コンポーネント１５２、コンテンツ検索コンポーネント１５３、クエリ位置識別コンポーネント１５４、候補広告識別コンポーネント１５５、及び候補広告ランク付けコンポーネント１５６を含む。要求受信／応答送信コンポーネント１５１は、コンテンツに関するクエリを受信し、コンテンツサービスを呼び出すことによってそのクエリと一致するコンテンツを検索し、広告検索コンポーネント１５２を呼び出すことによってそのクエリと一致する広告を検索し、コンテンツと広告との両方を含む、そのクエリに対する応答を送信する。広告検索コンポーネント１５２は、クエリ位置識別コンポーネント１５４を呼び出してクエリのクエリ位置を識別し、候補広告識別コンポーネント１５５を呼び出して候補広告を識別し、候補広告ランク付けコンポーネント１５６を呼び出して、位置に基づいて候補広告をランク付けする。
【００２０】
広告システム１３０が実施されるコンピューティングデバイスには、中央処理装置（ＣＰＵ）、メモリ、入力デバイス（例えば、キーボード及びポインティングデバイス）、出力デバイス（例えば、ディスプレイデバイス）、及びストレージデバイス（例えば、ディスクドライブ）を含めることができる。メモリ及びストレージデバイスは、広告システムを実施する命令を含むことができるコンピュータ可読媒体である。さらに、命令、データ構造、及びメッセージ構造を、格納するか、通信リンク上の信号などのデータ伝送媒体を介して伝送することができる。インターネット、ローカルエリアネットワーク、広域ネットワーク、ポイントツーポイントダイヤルアップ接続、携帯電話網など、さまざまな通信リンクを使用することができる。
【００２１】
広告システムの実施形態は、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラマブル消費者エレクトロニクス、ディジタルカメラ、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などを含むさまざまなオペレーティング環境で実施することができる。広告システムと相互作用するコンピューティングデバイスは、携帯電話機、ＰＤＡ、スマートホン、パーソナルコンピュータ、プログラマブル消費者エレクトロニクス、ディジタルカメラなどとすることができる。
【００２２】
広告システムを、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の全体的な文脈で説明することができる。一般に、プログラムモジュールは、特定のタスクを実行するか特定の抽象データ型を実施する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。通常、プログラムモジュールの機能性は、さまざまな実施形態で望み通りに組み合わせるか分散させることができる。例えば、広告システムを、地図サービス、ナビゲーションサービス、またはその広告システムが広告を提供する他のサービスとは別々のコンピュータシステム上で実施することができる。
【００２３】
図２は、一実施形態のプライマリインデックスとしてのキーワードインデックスを伴うハイブリッドインデックスを示す図である。ハイブリッドインデックス２００は、キーワードごとに１つのエントリを有するキーワードインデックス２０１を含む。キーワードの各エントリは、位置インデックス２０２〜２０４への参照を含む。一実施形態で、広告システムは、Ｒ*ツリーデータ構造を使用して位置インデックスを実施する。広告システムは、代替として、Ｒツリーデータ構造、Ｂ＋ツリーデータ構造、ハッシュベースのデータ構造など、他のタイプのデータ構造を使用することができる。Ｒ*ツリーデータ構造は、非特許文献１に記載されている。広告システムは、ハッシュテーブル、プレフィックステーブルなどの反転されたファイルデータ構造としてキーワードインデックスを実施することができる。各位置インデックスは、少なくとも１つの広告が対応するキーワードを有する位置ごとに１つのエントリを有する。各エントリ（すなわち、葉ノード）は、対応する広告への参照を有する。この例では、位置インデックス２０２は、広告リスト２０５〜２０７をポイントするエントリを有し、位置インデックス２０３は、広告リスト２０８〜２０９をポイントするエントリを有し、位置インデックス２０４は、広告リスト２１０をポイントするエントリを有する。各広告は、さまざまなプロトコル用の広告フォーマットを識別する、関連する広告フォーマットテーブル２１１を有することができる。例えば、ＳＭＳプロトコル用の広告フォーマットは、会社の名前及びその会社の電話番号を含むことができ、ＸＭＬプロトコル用の広告フォーマットは、会社の名前ならびにその会社の住所及びロゴを含むことができる。
【００２４】
図３は、一実施形態の広告システムの広告集約コンポーネントの処理を示す流れ図である。コンポーネント３００は、広告を収集し、広告からデータを抽出し、そのデータを共通のフォーマットで格納する。ブロック３０１で、このコンポーネントは、次の広告ソースを選択する。ブロック３０２で、すべての広告ソースが既に選択済みである場合には、このコンポーネントはリターンを返し、そうでない場合には、このコンポーネントはブロック３０３で継続する。ブロック３０３では、このコンポーネントは、選択された広告ソースの次の広告を選択する。ブロック３０４で、すべての広告が既に選択済みである場合に、このコンポーネントは、ブロック３０１にループして次の広告ソースを選択し、そうでない場合には、このコンポーネントは、ブロック３０５で継続する。ブロック３０５では、このコンポーネントは、選択された広告から会社の名前を抽出する。ブロック３０６では、このコンポーネントは、選択された広告から会社の位置を抽出する。ブロック３０７では、このコンポーネントは、選択された広告からキーワードを抽出する。ブロック３０８では、このコンポーネントは、選択された広告の会社のカテゴリを抽出する。ブロック３０９では、このコンポーネントは、選択された広告から、電話番号、ロゴ及びＵＲＬなど、追加情報を抽出する。ブロック３１０では、このコンポーネントは、抽出されたデータを一定のフォーマットで格納し、ブロック３０３にループして次の広告を選択する。
【００２５】
図４は、一実施形態の広告システムの広告変換コンポーネントの処理を示す流れ図である。コンポーネント４００は、ＭＭＳ（Multimedia Messaging Service）プロトコル、ＨＴＭＬ（Hypertext Markup Language）プロトコル、ＸＭＬ（eXtensible Markup Language）プロトコル、ショートメッセージサービス（ＳＭＳ）プロトコル、ＷＡＰ（Wireless Application Protocol）プロトコルなどのサポートされるプロトコルに基づいて、広告をさまざまな広告フォーマットに変換する。ブロック４０１で、このコンポーネントは、次の広告を選択する。ブロック４０２で、すべての広告が既に選択済みである場合には、このコンポーネントはリターンを返し、そうでない場合には、このコンポーネントは、ブロック４０３で継続する。ブロック４０３で、このコンポーネントは、次のプロトコルを選択する。ブロック４０４で、選択された広告のすべてのプロトコルが既に選択済みである場合には、このコンポーネントは、ブロック４０１にループして次の広告を選択し、そうでない場合には、このコンポーネントは、ブロック４０５で継続する。ブロック４０５で、このコンポーネントは、そのプロトコル用の広告を作成する。ブロック４０６で、このコンポーネントは、作成された広告フォーマットを広告ストアに格納し、ブロック４０３にループして、次のプロトコルを選択する。
【００２６】
図５は、一実施形態の広告システムの広告インデクシングコンポーネントの処理を示す流れ図である。コンポーネント５００は、主インデックスとしてキーワードを使用して広告のハイブリッドインデックスを生成する。ブロック５０１〜５０９では、このコンポーネントは、インデクサによって識別されるキーワードを選択し、キーワードインデックスにエントリを追加してループする。ブロック５０１で、このコンポーネントは、次のキーワードを選択する。ブロック５０２で、すべてのキーワードが既に選択済みである場合には、このコンポーネントはリターンを返し、そうでない場合には、このコンポーネントはブロック５０３で継続する。ブロック５０３〜５０７で、このコンポーネントは、選択されたキーワードの位置インデックスを投入してループする。ブロック５０３で、このコンポーネントは、選択されたキーワードに関連する次の広告を選択する。ブロック５０４で、すべての広告が既に選択済みである場合には、このコンポーネントはブロック５０８で継続し、そうでない場合には、このコンポーネントは、ブロック５０５で継続する。ブロック５０５〜５０７で、このコンポーネントは、選択された広告に関連する位置を識別してループする。ブロック５０５で、このコンポーネントは、選択された広告の次の位置を選択する。ブロック５０６で、すべての位置が既に選択済みである場合には、このコンポーネントは、ブロック５０３にループして次の広告を選択し、そうでない場合には、このコンポーネントは、ブロック５０７で継続する。ブロック５０７で、このコンポーネントは、位置インデックスを作成する時に使用するために位置／広告の対（pair）を格納し、ブロック５０５にループして次の位置を選択する。ブロック５０８で、このコンポーネントは、ブロック５０７で格納された位置／広告の対を使用して位置インデックスを作成する。ブロック５０９で、このコンポーネントは、作成された位置インデックスへの参照を含む選択されたキーワードのキーワードインデックスにエントリを追加する。その後、このコンポーネントは、ブロック５０１にループして次のキーワードを選択する。
【００２７】
図６は、一実施形態の広告システムの広告検索コンポーネントの処理を示す流れ図である。コンポーネント６００は、クエリ、要求元デバイスの表示、デバイス位置の表示、及びデバイス時刻を渡される。デバイス時刻は、現在営業していない会社の広告をフィルタアウトするのに使用することができる。このコンポーネントは、クエリに関連する広告を検索し、識別する。ブロック６０１で、このコンポーネントは、クエリに関連するクエリ位置を識別するためにクエリ位置識別コンポーネントを呼び出す。ブロック６０２で、このコンポーネントは、広告位置をセットする。広告の位置には、１つまたは複数のクエリ位置あるいはデバイス位置をセットすることができる。ブロック６０３で、このコンポーネントは、候補広告識別コンポーネントを呼び出して、クエリと一致する候補広告を識別する。ブロック６０４で、このコンポーネントは、候補広告ランク付けコンポーネントを呼び出して、位置に基づいて候補広告をランク付けする。ブロック６０５で、このコンポーネントは、最高ランキングの候補広告を選択する。ブロック６０６で、このコンポーネントは、要求元デバイスに適当な広告フォーマットの選択された広告を取り出す。その後、このコンポーネントは、取り出された広告を返す。
【００２８】
図７は、一実施形態の広告システムのクエリ位置識別コンポーネントの処理を示す流れ図である。コンポーネント７００は、渡されたクエリに関連するクエリ位置を識別する。そのようなクエリ位置を識別するシステムの一例は、特許文献５に記載されている。ブロック７０１で、このコンポーネントは、検索エンジンサービスにクエリをサブミットすることによって、渡されたクエリと一致するウェブページを検索する。ブロック７０２〜７０６で、このコンポーネントは、検索結果の要約部分から候補位置を識別し、候補位置をスコアリングしてループする。ブロック７０２で、このコンポーネントは、検索結果内のウェブページの次の要約を選択する。ブロック７０３で、すべてのウェブページの要約が既に選択済みである場合には、このコンポーネントは、ブロック７０７で継続し、そうでない場合には、このコンポーネントは、ブロック７０４で継続する。ブロック７０４で、このコンポーネントは、選択された要約内の次の候補位置を識別する。ブロック７０５で、すべての候補位置が既に識別済みである場合には、このコンポーネントは、ブロック７０２にループして次の要約を選択し、そうでない場合には、このコンポーネントは、ブロック７０６で継続する。ブロック７０６で、このコンポーネントは、識別された候補位置のスコアを調節し、ブロック７０４にループして次の候補位置を識別する。このコンポーネントは、その中で候補位置が識別された要約ごとにスコアを１つ増やすことによって、候補位置のスコアを調節することができる。ブロック７０７で、このコンポーネントは、より高いスコアを有する候補位置を選択する。その後、このコンポーネントは、クエリ位置の名前として、選択された位置を返す（例えば、ニューヨーク市）。
【００２９】
図８は、一実施形態の広告システムの候補広告識別コンポーネントの処理を示す流れ図である。コンポーネント８００は、クエリ用語及びクエリ位置名を受け取り、主インデックスとしてキーワードインデックスを有するハイブリッドインデックスを使用して候補広告を識別する。ブロック８０１〜８０３で、このコンポーネントは、地名辞典を使用して位置名を位置にマッピングしてループする。ブロック８０１で、このコンポーネントは、次の位置名を選択する。判断ブロック８０２で、すべての位置名が既に選択済みである場合に、このコンポーネントは、ブロック８０４で継続し、そうでない場合に、このコンポーネントは、ブロック８０３で継続する。ブロック８０３で、このコンポーネントは、位置名を位置にマッピングし、その後、ブロック８０１にループして次の位置名を選択する。ブロック８０４〜８１０で、このコンポーネントは、候補広告を識別してループする。ブロック８０４で、このコンポーネントは、クエリの次のキーワードまたは用語を選択する。ブロック８０５で、クエリのすべてのキーワードまたは用語が既に選択済みである場合に、このコンポーネントは、リターンを返し、そうでない場合に、このコンポーネントは、ブロック８０６で継続する。ブロック８０６で、このコンポーネントは、選択されたキーワードのキーワードインデックスを検索し、位置インデックスを識別する。ブロック８０７で、このコンポーネントは、クエリの次の位置を選択する。ブロック８０８で、すべての位置が既に選択済みである場合に、このコンポーネントは、ブロック８０４にループしてクエリの次のキーワードを選択し、そうでない場合に、このコンポーネントは、ブロック８０９で継続する。ブロック８０９で、このコンポーネントは、選択された位置の位置インデックスを検索する。ブロック８１０で、選択された位置に対応するエントリが見つかった場合には、このコンポーネントは、候補広告としてキーワード／位置／広告参照を追加し、その後、ブロック８０７にループして次の位置を選択する。
【００３０】
図９は、一実施形態の広告システムの候補広告ランク付けコンポーネントの処理を示す流れ図である。コンポーネント９００は、サービングエリア及び営業時間など、さまざまな判断基準に基づいて候補広告をランク付けする。ブロック９０１で、このコンポーネントは、次の候補広告を選択する。ブロック９０２で、すべての候補広告が既に選択済みである場合に、このコンポーネントは、ブロック９０７で継続し、そうでない場合に、このコンポーネントは、ブロック９０３で継続する。ブロック９０３で、このコンポーネントは、サービングエリアに基づいて選択された候補広告のスコアを調節する。ブロック９０４で、このコンポーネントは、選択された候補広告に関連する営業時間に基づいてスコアを調節する。例えば、このコンポーネントは、現在のデバイス時間に会社が閉まっていることを営業時間が示す場合に、スコアを負の数に調節する。ブロック９０５で、このコンポーネントは、会社カテゴリに基づいてスコアを調節する。例えば、会社カテゴリがクエリ内で使用される場合に、このコンポーネントは、スコアを増やす。ブロック９０６で、このコンポーネントは、潜在的収入に基づいてスコアを調節する。例えば、このコンポーネントは、広告主が広告を掲載させるために支払うつもりがある金額に基づいてスコアを増やすことができる。次に、このコンポーネントは、ブロック９０１にループして次の候補広告を選択する。ブロック９０７で、このコンポーネントは、計算されたスコアに基づいて候補広告を順序付ける。次に、このコンポーネントは、順序付けられた広告を返す。
【００３１】
本主題を、構造的特徴及び／または方法論的動作に固有の言葉で説明してきたが、添付の特許請求の範囲で定義される本主題が、上記で説明した特定の特徴または動作に必ずしも限定されないことを理解されたい。そうではなく、上記で説明した特定の特徴及び動作は、特許請求の範囲を実施する例の形として開示されたものである。例えば、当業者は、提示のために選択される候補広告が少なすぎる場合に、広告システムが、候補広告を識別するのに使用されるクエリを緩和するか、広告のサービングエリアを広げることができることを了解するであろう。従って、本発明は、添付の特許請求の範囲によるものを除いて、限定されない。
【図１】
2010503071.tif 000003
【図２】
2010503071.tif 000004
【図３】
2010503071.tif 000005
【図４】
2010503071.tif 000006
【図５】
2010503071.tif 000007
【図６】
2010503071.tif 000008
【図７】
2010503071.tif 000009
【図８】
2010503071.tif 000010
【図９】
2010503071.tif 000011
【国際調査報告】
2010503071.tif 000012
2010503071.tif 000013