(57)【特許請求の範囲】
【請求項１】
オンライン・システムのユーザによって用いられる複数のユーザ・デバイスから位置情報を受信する工程であって、前記位置情報は前記複数のユーザ・デバイスの各々が位置した複数の異なる位置を識別する、工程と、
前記オンライン・システムの複数のユーザの各々が訪問した位置に関する複数のチェーンを前記位置情報から抽出する工程であって、位置に関する各チェーンは、それぞれのユーザが訪問した２つ以上の位置を含み、前記複数のチェーンの抽出は、
２つ以上の位置について、（１）前記ユーザが前記２つ以上の位置の両方について第１の最大しきい値長さの時間内で位置した場合、かつ、（２）前記ユーザが前記２つ以上の位置の各々に第２の最小しきい値量以上にわたり位置した場合に、それら２つの位置を識別することと、
前記２つ以上の位置を前記ユーザが訪問した位置に関するチェーンとして抽出することと、を含む、抽出工程と、
位置に関する前記チェーンを用いて１以上の位置ペアを生成する工程であって、各位置ペアは第１の位置および第２の位置を含み、前記１以上の位置ペアの生成は、
抽出された位置に関する前記複数のチェーンのうちの共通するチェーンにおける前記第１の位置と前記第２の位置との出現数に基づき、位置に関する前記チェーンにおける２つの位置の関連付けを行うことと、
前記関連付けが第３のしきい値より大きいことに応じて、前記２つの位置をペアにすることと、を含む、生成工程と、
閲覧ユーザが位置ペアにおける前記位置のうちの一方を以前に訪問したと決定する工程と、
前記決定に応じて、前記ユーザに対する提示用に前記位置の他方についてのコンテンツ・アイテムを選択する工程と、を備える方法。
【請求項２】
前記複数のユーザに関する１以上の人口統計学的特性に基づき、抽出された位置に関する前記チェーンをフィルタリングする工程をさらに備え、前記生成工程はフィルタリングされた位置の前記チェーンのみに基づく、請求項１に記載の方法。
【請求項３】
各チェーンにおいて対応するユーザが前記位置を訪問したコンテキストに基づき、抽出された位置に関する前記チェーンをフィルタリングする工程をさらに備え、前記生成工程はフィルタリングされた位置の前記チェーンのみに基づく、請求項１に記載の方法。
【請求項４】
前記ユーザに対する提示用のコンテンツ・アイテムを選択する工程は、前記ユーザが位置ペアにおける前記位置のうちの一方に位置することに応じて、前記ユーザに対する提示用に前記位置ペアにおける他方の位置についてのコンテンツ・アイテムを選択する工程を含む、請求項１に記載の方法。
【請求項５】
前記ユーザに対する提示用のコンテンツ・アイテムを選択する工程は、前記ユーザに対する提示用に位置ペアにおける前記第１の位置および前記第２の位置についてのコンテンツ・アイテムを選択する工程を含む、請求項１に記載の方法。
【請求項６】
前記第１の最大しきい値は、前記チェーンにおける前記位置のうちの１つ以上の種類に応じて調節される、請求項１に記載の方法。
【請求項７】
命令が符号化された非一時的なコンピュータ可読記憶媒体であって、前記命令はプロセッサによる実行時、前記プロセッサに、
オンライン・システムのユーザによって用いられる複数のユーザ・デバイスから位置情報を受信する工程であって、前記位置情報は前記複数のユーザ・デバイスの各々が位置した複数の異なる位置を識別する、工程と、
前記オンライン・システムの複数のユーザの各々が訪問した位置に関する複数のチェーンを前記位置情報から抽出する工程であって、位置に関する各チェーンは、それぞれのユーザが訪問した２つ以上の位置を含み、前記複数のチェーンの抽出は、
２つ以上の位置について、（１）前記ユーザが前記２つ以上の位置の両方について第１の最大しきい値長さの時間内で位置した場合、かつ、（２）前記ユーザが前記２つ以上の位置の各々に第２の最小しきい値量以上にわたり位置した場合に、それら２つの位置を識別することと、
前記２つ以上の位置を前記ユーザが訪問した位置に関するチェーンとして抽出することと、を含む、抽出工程と、
位置に関する前記チェーンを用いて１以上の位置ペアを生成する工程であって、各位置ペアは第１の位置および第２の位置を含み、前記１以上の位置ペアの生成は、
抽出された位置に関する前記複数のチェーンのうちの共通するチェーンにおける前記第１の位置と前記第２の位置との出現数に基づき、位置に関する前記チェーンにおける２つの位置の関連付けを行うことと、
前記関連付けが第３のしきい値より大きいことに応じて、前記２つの位置をペアにすることと、を含む、生成工程と、
閲覧ユーザが位置ペアにおける前記位置のうちの一方を以前に訪問したと決定する工程と、
前記決定に応じて、前記ユーザに対する提示用に前記位置の他方についてのコンテンツ・アイテムを選択する工程と、を行わせる、コンピュータ可読記憶媒体。
【請求項８】
前記プロセッサによる実行時、前記プロセッサに、前記複数のユーザに関する１以上の人口統計学的特性に基づき、抽出された位置に関する前記チェーンをフィルタリングする工程を行わせる命令を含み、
前記プロセッサは、フィルタリングされた位置の前記チェーンのみに基づき１以上の位置ペアを生成する、請求項７に記載のコンピュータ可読記憶媒体。
【請求項９】
前記プロセッサによる実行時、前記プロセッサに、各チェーンにおいて対応するユーザが前記位置を訪問したコンテキストに基づき、抽出された位置に関する前記チェーンをフィルタリングする工程を行わせる命令を含み、
前記プロセッサは、フィルタリングされた位置の前記チェーンのみに基づき１以上の位置ペアを生成する、請求項７に記載のコンピュータ可読記憶媒体。
【請求項１０】
前記ユーザに対する提示用のコンテンツ・アイテムを選択する工程を前記プロセッサに行わせる前記命令は、前記プロセッサによる実行時、前記プロセッサに、
前記ユーザが位置ペアにおける前記位置のうちの一方に位置することに応じて、前記ユーザに対する提示用に前記位置ペアにおける他方の位置についてのコンテンツ・アイテムを選択する工程を行わせる命令を含む、請求項７に記載のコンピュータ可読記憶媒体。
【請求項１１】
前記ユーザに対する提示用のコンテンツ・アイテムを選択する工程を前記プロセッサに行わせる前記命令は、前記プロセッサによる実行時、前記プロセッサに、
前記ユーザに対する提示用に位置ペアにおける前記第１の位置および前記第２の位置についてのコンテンツ・アイテムを選択する工程を行わせる命令を含む、請求項７に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記第１の最大しきい値は、前記チェーンにおける前記位置のうちの１つ以上の種類に応じて調節される、請求項７に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に位置サービスに関し、特に、オンライン・システムの１組のユーザの以前の位置および動きのパターンとの相関に基づきユーザの位置を予測することに関する。
【背景技術】
【０００２】
企業は、その顧客に対し提供されるサービスに影響を及ぼすために、顧客の挙動をしばしば利用する。特に、企業は、顧客が以前にどこに位置したかを決定し、顧客が将来どこに位置するかを予測することによって、所与の位置における顧客に対する価値のある洞察を獲得する。例えば、将来どこに位置するかを予測することによって、企業は、その企業に関連付けられている位置を通じる顧客の流れを予測したり、顧客に対する広告またはプロモーションのターゲットを決定したり、特定の位置における顧客サービスの需要を予想したりすることが可能である。しかしながら、企業において以前に顧客が訪れた位置を決定することは難しい。したがって、企業が顧客にサービスを提供するために顧客の将来の位置を正確に予測することは難しい。
【図面の簡単な説明】
【０００３】
【図１】本発明の一実施形態による、ソーシャル・ネットワーキング・システムが動作するシステム環境のブロック図。
【図２Ａ】本発明の一実施形態による、ソーシャル・ネットワーキング・システムのブロック図。
【図２Ｂ】ソーシャル・ネットワーキング・システムのユーザが訪問する位置の例を示す図。
【図３】本発明の一実施形態による、位置のペアリングを行う処理を示すフローチャート。
【発明を実施するための形態】
【０００４】
オンライン・システムは、オンライン・システムのユーザによって訪問された位置のペアの相関を決定する。オンライン・システムは、オンライン・システムのユーザによって用いられる複数のユーザ・デバイスから位置情報を受信する。この位置情報によって、複数のユーザ・デバイスの各々が位置した複数の異なる位置が識別される。オンライン・システムは、ユーザが訪問した位置と各位置でユーザが費やした時間の量とを決定するために、この位置情報を用いる。ここで、ユーザは、そのユーザのユーザ・デバイスがしきい値長さ以上の時間ある位置に位置した場合、その位置を訪問したと判定されてよい。この位置情報を用いて、オンライン・システムは、オンライン・システムのユーザが訪問した位置に関する複数のチェーンを抽出する。各チェーンは、ユーザが訪問した位置の並び（シーケンス）のリストであり、同様の種類の１つまたは複数の位置を含んでよい（ユーザが訪問した都市のリスト、ユーザが訪問した店のリスト、またはユーザが訪問した建物内の領域のリストなど）。位置のチェーンに基づき、オンライン・システムは１つまたは複数の位置ペアを生成する。時間において遠く離れている（例えば、しきい値時間を越えて）１つのペアの位置が訪問された場合、システムはそのペアを無視してもよい。各位置ペアは、第１の位置と、ユーザが第１の位置に位置する場合にそのユーザが訪れる確率が高い第２の位置とを含む。位置の予測は、第１の位置が第２の位置より前に訪問されたときのみ第２の位置を予測するように順序付けられてもよく、順序付けられておらず、第１の位置が第２の位置の前または後に訪問される場合に訪問される第２の位置を予測してもよい。
【０００５】
この位置予測は様々なアプリケーションに用いられてもよい。例えば、オンライン・システムは、位置ペアに基づきユーザに対する提示用の広告を選択する。例えば、ユーザが１つのペアにおける位置のうちの一方に位置する場合、オンライン・システムはペアにおける他方の位置に関連付けられている広告を選択する。位置予測では、広告主に対するサーフェシングが行われてもよく、広告主は自身の広告についてターゲティング基準を作成するために位置予測を用いる（例えば、関連する営業所への続く訪問と高い相関を有する特定の位置にいるユーザを広告のターゲットとする）。オンライン・システムは、これに加えてまたはこれに代えて、位置に関連付けられているエンティティに位置ペアリングに関する情報を送信し、そのエンティティの位置とペアにされている１つまたは複数の他の位置に基づきそのエンティティがビジネスまたはマーケティング上の決定を行うことを可能とする。例えば、位置がデパート内の領域である場合、店長は現在の顧客位置に基づき顧客サービスの将来の需要を予測することが可能である。
【０００６】
図では、単に例示の目的で本発明の様々な実施形態を示す。当業者には、本明細書に記載の発明の原理から逸脱することなく、本明細書に示した構造および方法の代替の実施形態が用いられ得ることが、以下の説明から容易に認められる。
【０００７】
システム・アーキテクチャ
図１は、オンライン・システム１４０用のシステム環境１００の高位ブロック図である。図１によって示すシステム環境１００は、１つ以上のクライアント・デバイス１１０と、ネットワーク１２０と、１つ以上のサードパーティ・システム１３０と、オンライン・システム１４０とを備える。代替の構成では、異なるおよび／または追加の構成要素がシステム環境１００に含まれてもよい。本明細書に記載の実施形態は、ソーシャル・ネットワーキング・システムでないオンライン・システムに適用されることも可能である。
【０００８】
クライアント・デバイス１１０は、ユーザ入力を受信することと、ネットワーク１２０を介してデータの送信、受信、またはその両方を行うこととが可能な１以上のコンピューティング・デバイスである。一実施形態では、クライアント・デバイス１１０は、デスクトップまたはラップトップ・コンピュータなど、従来のコンピュータ・システムである。これに代えて、クライアント・デバイス１１０は、携帯情報端末（ＰＤＡ）、移動体電話、スマートフォン、又は別の適切なデバイスなど、コンピュータ機能を有するデバイスであってよい。クライアント・デバイス１１０は、ネットワーク１２０を介して通信を行うように構成される。一実施形態では、クライアント・デバイス１１０は、クライアント・デバイス１１０のユーザがオンライン・システム１４０と対話することを可能とするアプリケーションを実行する。例えば、クライアント・デバイス１１０は、ネットワーク１２０を介するクライアント・デバイス１１０とオンライン・システム１４０との間の対話を可能とするために、ブラウザ・アプリケーションを実行する。別の実施形態では、クライアント・デバイス１１０は、ＩＯＳ（登録商標）またはＡＮＤＲＯＩＤ（商標）など、クライアント・デバイス１１０のネイティブ・オペレーティング・システム上で動作するアプリケーション・プログラム・インタフェース（ＡＰＩ）を通じてオンライン・システム１４０と対話する。一部の実施形態では、クライアント・デバイス１１０は位置トラッキング機能を備え、グローバル・ポジショニング（地球側位）、ＩＰアドレス、近くのセル・タワーに対する三角測量、または他の機構に基づき、デバイスの位置を識別することが可能である。一実施形態では、クライアント・デバイス１１０のユーザはデバイス上の位置トラッキングを無効（ディセーブル）とするまたはオプトアウトすることが可能であり、クライアント・デバイス１１０はデバイスの位置を追跡しない。他の場合では、クライアント・デバイス１１０はユーザが位置トラッキングをオプトインする場合のみ位置を追跡する。
【０００９】
クライアント・デバイス１１０は、ネットワーク１２０を介して通信を行うように構成されており、ネットワーク１２０は、有線および／または無線通信システムの両方を用いて、ローカル・エリア・ネットワークおよび／またはワイド・エリア・ネットワークの任意の組み合わせを含んでよい。一実施形態では、ネットワーク１２０は、標準的な通信技術および／またはプロトコルを用いる。例えば、ネットワーク１２０は、イーサネット（登録商標）、８０２．１１、ＷｉＭＡＸ（ｗｏｒｌｄｗｉｄｅ  ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  ｍｉｃｒｏｗａｖｅ  ａｃｃｅｓｓ  ）、３Ｇ、４Ｇ、ＣＤＭＡ（ｃｏｄｅ  ｄｉｖｉｓｉｏｎ  ｍｕｌｔｉｐｌｅ  ａｃｃｅｓｓ）、ＤＳＬ（ｄｉｇｉｔａｌ  ｓｕｂｓｃｒｉｂｅｒ  ｌｉｎｅ）などの技術を用いる通信リンクを含む。ネットワーク１２０を介する通信のために用いられるネットワーク・プロトコルの例は、ＭＰＬＳ（ｍｕｌｔｉｐｒｏｔｏｃｏｌ  ｌａｂｅｌ  ｓｗｉｔｃｈｉｎｇ）、ＴＣＰ／ＩＰ（ｔｒａｎｓｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌ  ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  ｐｒｏｔｏｃｏｌ）、ＨＴＴＰ（ｈｙｐｅｒｔｅｘｔ  ｔｒａｎｓｐｏｒｔ  ｐｒｏｔｏｃｏｌ）、ＳＭＴＰ（ｓｉｍｐｌｅ  ｍａｉｌ  ｔｒａｎｓｆｅｒ  ｐｒｏｔｏｃｏｌ）、およびＦＴＰ（ｆｉｌｅ  ｔｒａｎｓｆｅｒ  ｐｒｏｔｏｃｏｌ）を含む。ネットワーク１２０を通じて交換されるデータは、ＨＴＭＬ（ｈｙｐｅｒｔｅｘｔ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）またはＸＭＬ（ｅｘｔｅｎｓｉｂｌｅ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）など、任意の適切なフォーマットを用いて表現されてよい。いくつかの実施形態では、ネットワーク１２０の通信リンクの全部または一部が任意の適切な１以上の技術を用いて暗号化されてもよい。
【００１０】
オンライン・システム１４０と通信するために、１または複数のサードパーティ・システム１３０がネットワーク１２０に結合されてもよく、これについて図２Ａに関連して以下でさらに述べる。一実施形態では、サードパーティ・システム１３０は、クライアント・デバイス１１０によって実行するためのアプリケーションを表す情報を伝達する、またはクライアント・デバイス１１０上で実行されるアプリケーションによって使用するためにデータをクライアント・デバイス１１０に伝達するアプリケーション・プロバイダである。他の実施形態では、サードパーティ・システム１３０は、クライアント・デバイス１１０を介して提示するためのコンテンツまたは他の情報を提供する。また、サードパーティ・ウェブサイト１３０は、広告、コンテンツ、またはサードパーティ・ウェブサイト１３０によって提供されるアプリケーションについての情報など、情報をオンライン・システム１４０に伝達してもよい。他のサードパーティ・システム１３０は、オンライン・システム１４０のユーザが訪問し得る物理的な位置を有するエンティティに関連付けられている。
【００１１】
オンライン・システム１４０として動作する一例のシステムは、ソーシャル・ネットワーキング・システムである。図２Ａは、ソーシャル・ネットワーキング機能を有するオンライン・システム１４０のアーキテクチャの一例のブロック図である。図２Ａに示すオンライン・システム１４０は、ユーザ・プロフィール・ストア２０５、コンテンツ・ストア２１０、アクション・ロガー２１５、アクション・ログ２２０、エッジ・ストア２２５、アド・ストア２３０、認証サーバ２３５、位置モジュール２４０、位置ストア２４５、位置ペアリング・モジュール２５０、広告ターゲティング・モジュール２５５、およびウェブ・サーバ２６０を備える。他の実施形態では、オンライン・システム１４０は、様々なアプリケーション用の追加の構成要素、より少ない構成要素、または異なる構成要素を含んでもよい。ネットワーク・インタフェース、セキュリティ機能、ロードバランサ、フェイルオーバ・サーバ、管理およびネットワーク操作コンソールなど、従来の構成要素は、システム・アーキテクチャの詳細を不明瞭にしないことを目的として、示していない。
【００１２】
オンライン・システム１４０の各ユーザは、ユーザ・プロフィールに関連付けられており、このユーザ・プロフィールはユーザ・プロフィール・ストア２０５に記憶されている
。ユーザ・プロフィールは、複数のユーザによって明示的に共有された、ユーザに関する宣言的な情報を含んでおり、また、オンライン・システム１４０によって推論されるプロフィール情報も含んでよい。一実施形態では、ユーザ・プロフィールは、対応するオンライン・システム１４０のユーザの１以上の属性について各々記述する複数のデータ・フィールドを含む。ユーザ・プロフィールに記憶されている情報の例は、職歴、学歴、ジェンダー、趣味または嗜好、ロケーションなど、個人の伝記的なもの、人口統計学的なもの、および他の種類の記述的情報を含む。ユーザ・プロフィールは、ユーザによって提供される他の情報（例えば、画像（イメージ）、映像（ビデオ））も記憶してよい。一定の実施形態では、ユーザのイメージは、イメージに表示されるオンライン・システム１４０のユーザの識別情報によってタグ付けされてもよい。ユーザ・プロフィール・ストア２０５におけるユーザ・プロフィールは、コンテンツ・ストア２１０におけるコンテンツ・アイテムに対し実行され、アクション・ログ２２０に記憶される、対応するユーザによるアクションに対する参照も維持してよい。さらにまた、ユーザ・プロフィール・ストア２０５のユーザ・プロフィールは、対応するユーザが訪問する物理的な位置の識別子も記憶してよい。
【００１３】
ユーザ・プロフィール・ストア２０５におけるユーザ・プロフィールは個人に関連付けられていることが多くあり、個人がオンライン・システム１４０を介して互いと対話することを可能とするが、ユーザ・プロフィールは企業または団体などのエンティティのために記憶されてもよい。これによって、エンティティが他のソーシャル・ネットワーキング・システム・ユーザとのコンテンツの接続および交換を行うためにオンライン・システム１４０上にプレゼンスを確立することが可能となる。エンティティは、それ自体に関する情報、その製品に関する情報をポストしてもよく、エンティティのユーザ・プロファイルに関連付けられているブランドのページを用いて、ソーシャル・ネットワーキング・システムのユーザに他の情報を提供してもよい。ソーシャル・ネットワーキング・システムの他のユーザは、ブランド・ページにポストされた情報を受信するために、又はブランド・ページから情報を受信するために、ブランド・ページに接続してよい。ブランド・ページに関連付けられているユーザ・プロフィールは、エンティティ自体に関する情報を含み、エンティティに関する背景または情報のデータをユーザに提供してよい。
【００１４】
コンテンツ・ストア２１０はオブジェクトを記憶し、各オブジェクトは様々な種類のコンテンツを表す。オブジェクトによって表されるコンテンツの例は、ページ・ポスト、状態アップデート、写真、ビデオ、リンク、共有されるコンテンツ・アイテム、ゲーム・アプリケーションの業績（ａｃｈｉｅｖｅｍｅｎｔ）、地域ビジネスのチェックイン・イベント、ブランド・ページ、または任意の他のタイプのコンテンツを含む。ソーシャル・ネットワーキング・システム・ユーザは、状態アップデート、ソーシャル・ネットワーキング・システムにおける他のオブジェクトに関連付けられているユーザによってタグ付けされる写真、イベント、グループ、またはアプリケーションなど、コンテンツ・ストア２１０によって記憶されるオブジェクトを作成することができる。いくつかの実施形態では、オブジェクトはサードパーティ・アプリケーションから、またはオンライン・システム１４０とは別のサードパーティ・アプリケーションから受信される。一実施形態では、コンテンツ・ストア２１０におけるオブジェクトは、コンテンツの１つ１つのピース、すなわち、コンテンツ「アイテム」を表す。このように、オンライン・システム１４０のユーザは、様々な通信チャネルを通じて様々なタイプのテキストおよびコンテンツ・アイテムを投稿することによって、互いに通信することを促される。これによってユーザの互いとの対話の量が増加し、オンライン・システム１４０内においてユーザが対話を行う頻度が増加する。
【００１５】
アクション・ロガー２１５は、オンライン・システム１４０の内部および／または外部のユーザ・アクションに関する通信を受信して、ユーザ・アクションに関する情報によっ
てアクション・ログ２２０を満たす。アクションの例は、特に、別のユーザに対するつながりを追加すること、別のユーザに対しメッセージを送ること、イメージをアップロードすること、別のユーザからのメッセージを読むこと、別のユーザに関連付けられているコンテンツを閲覧すること、および別のユーザによってポストされたイベントに出席することを含む。加えて、複数のアクションは、オブジェクトおよび１以上の特定のユーザを含んでもよく、したがって、それらのアクションはそれらのユーザに関連付けられているとともに、アクション・ログ２２０に記憶される。
【００１６】
アクション・ログ２２０は、オンライン・システム１４０に対するユーザ・アクションや、オンライン・システム１４０に情報を通信するサードパーティ・システム１３０に対するアクションを追跡するためにオンライン・システム１４０よって用いられてもよい。ユーザは、オンライン・システム１４０上の様々なオブジェクトと対話することができ、それらの対話について記述する情報はアクション・ログ２１０に記憶される。オブジェクトとの対話の例は、ポストに対しコメントすること、リンクを共有すること、モバイル・デバイスを介して物理的なロケーションにチェックインすること、コンテンツ・アイテムにアクセスすること、および任意の他の対話を含む。アクション・ログ２２０に含まれるオンライン・システム１４０上のオブジェクトとの対話の追加の例は、フォトアルバムに対しコメントすることと、ユーザと通信を行うことと、オブジェクトとのつながりを確立することと、カレンダーにイベントを加えることと、グループに参加することと、イベントを作成することと、アプリケーションを認可することと、アプリケーションを使用することと、オブジェクトに対する嗜好を示すこと（そのオブジェクトに「いいね」すること）と、トランザクションに関わることと、を含む。これに加えて、アクション・ログ２２０は、ユーザのオンライン・システム１４０上の広告や、オンライン・システム１４０上で動作する他のアプリケーションとの対話を記録してよい。いくつかの実施形態では、アクション・ログ２２０からのデータを用いて、ユーザの関心または嗜好を推測し、そのユーザのユーザ・プロフィールに含まれる関心を拡張して、ユーザの嗜好についてより完全な理解を可能とする。
【００１７】
また、アクション・ログ２２０は、サードパーティ・システム１３０（外部ウェブサイトなど）に対して取られ、オンライン・システム１４０に対し通信されるユーザ・アクションを記憶することもできる。例えば、主としてバーゲン価格でスポーツ用品を販売する電子商取引ウェブサイトは、電子商取引ウェブサイトがオンライン・システム１４０のユーザを識別することを可能にするソーシャル・プラグ・インを通じて、オンライン・システム１４０のユーザを認識してもよい。オンライン・システム１４０のユーザがユニークに識別されることが可能であるので、電子商取引ウェブサイトは、このスポーツ用品小売業者など、ユーザとの関連付けのために、オンライン・システム１４０の外部のユーザ・アクションに関する情報をオンライン・システム１４０に通信することができる。したがって、アクション・ログ２２０は、ユーザがサードパーティ・システム１３０に対し行うアクションに関する情報（ウェブ・ページ閲覧履歴、関わった広告、行われた購入、およびショッピングおよび購入による他のパターンを含む）を記録することができる。
【００１８】
一実施形態では、エッジ・ストア２２５は、オンライン・システム１４０上のユーザおよび他のオブジェクトの間のつながりをエッジとして記述する情報を記憶する。いくつかのエッジはユーザによって定義されてよく、ユーザが他のユーザとの自身の関係を指定することを可能とする。例えば、ユーザは、友達、同僚、パートナーなど、ユーザの実生活の関係に相当する他のユーザとのエッジを生成してもよい。他のエッジは、ソーシャル・ネットワーキング・システム上のページに関心を表明する、ソーシャル・ネットワーキング・システムの他のユーザとリンクを共有する、ソーシャル・ネットワーキング・システムの他のユーザによってなされたポストに関してコメントするなど、ユーザがオンライン・システム１４０におけるオブジェクトと対話するときに生成される。
【００１９】
一実施形態では、エッジは、ユーザ間の対話、ユーザとオブジェクトとの間の対話、またはオブジェクト間の対話の特性を各々表す、様々なフィーチャを含むことができる。例えば、１つのエッジに含まれるフィーチャは、２人のユーザ間の対話のレート、どのくらい最近に２人のユーザが互いに対話したか、１つのオブジェクトについて１人のユーザによって取り出される情報のレートまたは量、または１つのオブジェクトについて１人のユーザによってポストされるコメントの数および種類を記述する。また、フィーチャは、特定のオブジェクトまたはユーザを記述する情報も表してよい。例えば、フィーチャは、ユーザが特定のトピックにおいて有する関心のレベル、ユーザがオンライン・システム１４０にログインするレート、またはユーザについての人口統計学的情報を記述する情報を表してよい。各フィーチャは、ソース・オブジェクトまたはユーザと、ターゲット・オブジェクトまたはユーザと、フィーチャ値とに関連付けられてよい。フィーチャは、ソース・オブジェクトまたはユーザ、ターゲット・オブジェクトまたはユーザ、またはソース・オブジェクトまたはユーザとターゲット・オブジェクトまたはターゲット・ユーザとの間の対話を記述する値に基づく表現として指定されることができ、したがって、エッジは１つ以上のフィーチャ表現として表されることができる。
【００２０】
エッジ・ストア２２５は、オブジェクト、関心、および他のユーザに対する親和性スコアなど、エッジに関する情報を記憶する。親和性スコアまたは「アフィニティ」は、そのユーザによって実行されたアクションに基づき、オブジェクト、関心、およびオンライン・システム１４０における他のユーザに対するユーザの親和性を近似するために、時間を通じてオンライン・システム１４０によって計算されてもよい。ユーザの親和性は、そのユーザによって実行されたアクションに基づき、オブジェクト、関心、およびオンライン・システム１４０における他のユーザに対するユーザの親和性を近似するために、時間を通じてオンライン・システム１４０によって計算されてもよい。親和性の計算は、２０１０年１２月２３日に出願された米国特許出願第１２／９７８，２６５号、２０１２年１１月３０日に出願された米国特許出願第１３／６９０，２５４号、２０１２年１１月３０日に出願された米国特許出願第１３／６８９，９６９号、および２０１２年１１月３０日に出願された米国特許出願第１３／６９０，０８８号にさらに記述されている。それらの各々について、その全体を引用によって本明細書に援用する。ユーザと特定のオブジェクトとの間の複数の対話は、一実施形態では、エッジ・ストア２２５に１つのエッジとして記憶されてよい。これに代えて、ユーザと特定のオブジェクトとの間の各対話は、個別のエッジとして記憶される。いくつかの実施形態では、ユーザ間のつながりがユーザ・プロフィール・ストア２０５に記憶されてもよく、ユーザ・プロフィール・ストア２０５がユーザ間のつながりを決定するためにエッジ・ストア２２５にアクセスしてもよい。
【００２１】
１つまたは複数の広告の要求（「アド・リクエスト（ａｄ  ｒｅｑｕｅｓｔ）」）が、広告要求ストア２３５に含まれる。広告の要求は、広告コンテンツ及び入札額を含む。広告コンテンツは、テキスト、イメージ、オーディオ、ビデオ、又はユーザに対し提示される任意の他の適切なデータである。様々な実施形態では、広告コンテンツは、広告がアクセスされるときにユーザに対し送られるネットワーク・アドレスを指定するランディング・ページも含む。一実施形態では、入札額は、広告主によって広告に関連付けられており、広告がユーザに対し提示される場合、広告がユーザ対話を受け取る場合、又は任意の他の適切な条件に基づいて、広告主がオンライン・システム１４０に提供する金銭的報酬などの期待値を決定するために用いられる。例えば、入札額は、広告が表示される場合にオンライン・システム１４０が広告主から受け取る金銭額を指定し、期待値は、入札額に広告がアクセスされる確率を乗じることによって決定される。
【００２２】
これに加えて、広告要求は、広告主によって指定される１以上のターゲティング基準を含むことができる。広告要求に含まれるターゲティング基準は、広告要求におけるコンテ
ンツが提示されるのに適格なユーザの１以上の特性を指定する。例えば、ターゲティング基準は、ターゲティング基準のうちの１以上を満たすユーザ・プロフィール情報を有するユーザ、エッジ、またはアクションを識別するために、ユーザ・プロフィールのフィールド、エッジ、および／またはユーザに関連付けられているアクションに適用するためのフィルタである。したがって、ターゲティング基準は、広告主が特定のターゲティング基準にマッチするユーザのグループを識別することを可能とし、続いてコンテンツをユーザのグループに配信することを単純化する。
【００２３】
一実施形態において、ターゲティング基準は、ユーザと別のユーザまたはオンライン・システム１４０のオブジェクトとの間におけるアクションまたはつながりの種類を指定することができる。また、ターゲティング基準は、サードパーティ・システム１３０上など、オンライン・システム１４０の外部で行われるユーザとオブジェクトとの間の対話も指定することができる。例えば、ターゲティング基準は、別のユーザにメッセージを送信すること、アプリケーションを使用すること、グループに参加すること、グループから離脱すること、イベントに参加すること、イベント記述を生成すること、オンライン・マーケットプレイスを用いて製品またはサービスの購入または閲覧を行うこと、サードパーティ・システム１３０からの情報を要求すること、または任意の他の適切なアクションなど、特定のアクションを行ったユーザを識別する。ターゲティング基準にアクションを含めることによって、広告要求からのコンテンツが提示されるのに適格なユーザを広告主がさらに精選することが可能となる。別の例として、ターゲティング基準は、別のユーザまたはオブジェクトに対するつながりを有するユーザや、別のユーザまたはオブジェクトに対する特定の種類のつながりを有するユーザを識別してもよい。さらにまた、ターゲティング基準は、ユーザが訪問する位置を指定してもよい。例えば、ターゲティング基準は、ユーザが位置するまたは位置した都市、建物、または部屋を識別する。
【００２４】
認証サーバ２３５は、オンライン・システム１４０のユーザの１つまたは複数のプライバシ設定を強化する。ユーザのプライバシ設定は、ユーザに対して関連付けられる特定の情報がどのように共有され得るかを決定し、ユーザ・プロフィール・ストア２０５のユーザのユーザ・プロフィールに記憶されてもよく、認証サーバ２３５に記憶され、ユーザ・プロフィールに関連付けられてもよい。一実施形態では、プライバシ設定は、ユーザに関連付けられている特定の情報を指定し、指定された情報が共有され得る１つまたは複数のエンティティを識別する。情報が共有され得るエンティティの例は、他のユーザ、アプリケーション、サードパーティ・システム１３０、または、その情報に潜在的にアクセスし得る任意のエンティティを含み得る。ユーザによって共有可能な情報の例は、プロフィール写真などのユーザ・プロフィール情報、ユーザに関連付けられている電話番号、ユーザのつながり、つながりを追加すること、ユーザ・プロフィール情報を変更することなどユーザによって行われるアクション、ユーザが訪問する位置等を含む。
【００２５】
プライバシ設定仕様は、異なるレベルの粒度で提供され得る。一実施形態では、プライバシ設定は、他のユーザと共有されるべき具体的な情報を識別し得る。例えば、プライバシ設定は、職場電話番号、または、プロフィール写真、自宅電話番号、およびステータスを含む個人情報などの関連情報の具体的なセットを識別する。代替的に、プライバシ設定は、ユーザに対して関連付けられる全ての情報に対して適用されてもよい。特定の情報にアクセスすることができるエンティティのセットの仕様も、様々なレベルの粒度で特定され得る。情報が共有され得るエンティティの様々なセットは、例えば、ユーザにつながっているすべてのユーザ、ユーザにつながっている１組のユーザ、ユーザのすべてのアプリケーションにつながっているユーザにつながっている追加のユーザ、すべてのサードパーティ・システム１３０、特定のサードパーティ・システム１３０、またはすべての外部システムを含み得る。
【００２６】
一実施形態では、識別された情報にアクセスすることを許可されるエンティティを指定するためまたは異なるエンティティに対し提示される情報の種類を識別するために、エンティティの一覧を用いる。例えば、ユーザは、他のユーザに対し通信されるまたは指定されたユーザのグループに対し通信されるアクションの種類を指定してもよい。これに代えて、ユーザは、他のユーザに対し公開されないもしくは提示されないアクションまたは他の情報の種類を指定してもよい。
【００２７】
認証サーバ２３５は、ユーザに対して関連付けられる一定の情報がユーザの友達、サードパーティ・システム１３０、ならびに／または他のアプリケーションおよびエンティティによってアクセスされ得るかを決定するためのロジックを含む。例えば、サードパーティ・システム１３０に関連付けられている統一資源識別子（ＵＲＬ）についてのユーザのコメントにアクセスすることを試みるサードパーティ・システム１３０は、ユーザに関連付けられている情報にアクセスするために、認証サーバ２３５から認可を得る必要がある。ユーザのプライバシ設定に基づいて、認証サーバ２３５は、別のユーザ、サードパーティ・システム１３０、アプリケーション、または別のエンティティが、ユーザによって行われるアクションに関する情報を含む、ユーザに対して関連付けられる情報に対してアクセスすることを許可されているかを決定する。例えば、認証サーバ２３５は、サードパーティ・システム１３０に関連付けられているＵＲＬについてのユーザのコメントがサードパーティ・システム１３０に対し提示されることが可能であるか否かまたは別のユーザに対し提示されることが可能であるか否かを判定するために、ユーザのプライバシ設定を用いる。これによって、ユーザのプライバシ設定により、そのユーザのアクションについてのデータまたはそのユーザに関連付けられている他のデータを受信することをいずれの他のユーザ（すなわち、他のエンティティ）が許可されるかを指定することが可能となる。
【００２８】
位置モジュール２４０は、クライアント・デバイス１１０の位置を決定し、その位置をユーザのユーザ・プロフィールに記憶する。クライアント・デバイス１１０のユーザが位置トラッキングをオプトインしている場合、位置モジュール２４０はデバイスの現在の位置を決定するために、クライアント・デバイス１１０によって決定される位置にアクセスする。一実施形態では、位置モジュール２４０は、定期的に（例えば、１５分毎に）クライアント・デバイス１１０の位置をサンプリングし、その位置をユーザのユーザ・プロフィールに記憶する。位置モジュール２４０は、例えば、ＧＰＳ、ＩＰアドレス、および携帯電話タワーの三角測量を含むクライアント・デバイス１１０の任意の位置感知性能からデバイスの位置を取り出してよい。
【００２９】
一実施形態では、位置モジュール２４０は、クライアント・デバイス１１０から受信された未処理の位置データを、ユーザが訪問した位置であると決定される関心のエンティティまたはオブジェクトに変換するように構成される。例えば、位置モジュール２４０は、クライアント・デバイス１１０から受信された位置に対応する住所をリバース・ジオコーディングによって識別するために、地図データにアクセスしてもよい。住所は、番地（ｓｔｒｅｅｔ  ａｄｄｒｅｓｓ）、都市、郡、州、および／または国を含んでよい。また、位置モジュール２４０は、その住所にあるエンティティの名前を識別してもよい。例えば、位置モジュール２４０は、クライアント・デバイス１１０のユーザが訪問した住所を店の住所であると識別し、その住所の店の名前を決定する。建物内の位置（例えば、デパート内の売場）について、位置モジュール２４０は、その建物に関連付けられているエンティティによって提供される地図データ（クライアント・デバイス１１０から受信される位置を建物内の位置に変換する）にアクセスしてもよい。したがって、位置モジュール２４０は、都市、建物、および建物内の位置を含む様々な異なる粒度にて、ユーザが訪問した位置を定義することができる。さらにまた、未処理の位置データを関心のエンティティかまたはオブジェクトに変換することによって、位置モジュール２４０は、同じ位置から収集されるユーザ・デバイス１１０の位置の複数のサンプルを集約する。
【００３０】
同じ位置にて収集された複数のサンプルに基づき、位置モジュール２４０は、ユーザがその位置で費やした時間の量を決定してもよい。一実施形態では、位置モジュール２４０は、ユーザが訪問した位置を、タイムスタンプ、その位置で費やされた時間の量、およびそのユーザのユーザ識別子に関連付けて、位置ストア２４５に記憶する（住所として、クライアント・デバイス１１０から受信される未処理の位置データとして、または両方）。
【００３１】
位置ペアリング・モジュール２５０は、位置間のペアリングを生成するために、オンライン・システム１４０の複数のユーザから集約された位置データを用いる。一実施形態では、第１の位置および第２の位置は、ユーザが第１の位置に位置する場合にそのユーザが第２の位置を訪れる高い確率が存在すると位置ペアリング・モジュール２５０が決定する場合、ペアにされる。ペアリングを生成するために、位置ペアリング・モジュール２５０は、ユーザの位置履歴からオンライン・システム１４０の複数のユーザの各々が訪問した位置のチェーンを抽出する。位置の各チェーンは、オンライン・システム１４０のユーザが訪問した位置のシーケンスを表し、ユーザが訪問した２つ以上の位置を含む。位置のチェーンは、ユーザが訪問した２つ以上の都市またはユーザが訪問した２つ以上の建物（例えば、店舗）など、同じ種類の位置を含んでもよい。位置ペアリング・モジュール２５０は、同じ未処理の位置データに対応する複数の位置のチェーンを抽出してもよい。例えば、ユーザが都市Ａの空港から都市Ｂの空港へ飛行する場合、位置ペアリング・モジュール２５０は、都市Ａの空港および都市Ｂの空港を含む位置の１つのチェーンを抽出するとともに、都市Ａおよび都市Ｂを含む位置の別のチェーンを抽出してもよい。
【００３２】
一実施形態では、位置ペアリング・モジュール２５０は、ユーザがしきい値長さの時間より長く位置した位置を選択し、ユーザがしきい値長さより短い時間においてその２つの位置を訪問した場合、同じチェーンにそれら２つの位置を配置する。一実施形態では、チェーンに位置を含めるか否かを判定するための時間のしきい値長さは、そのチェーンにおける位置の種類に応じて調節される。都市など、より大きな位置については、チェーンに位置を含めるためのしきい値は、建物など、より小さな位置についてのしきい値より長くてもよい。例えば、位置モジュール２４０は、ある都市にユーザが１２時間以上位置した場合、そのユーザがその都市を訪問したと判定する。したがって、ユーザが１２時間未満しか都市に位置しなかった場合（例えば、ユーザが２つの他の都市間を飛行する間に、ある都市に２時間立ち寄った場合）、位置ペアリング・モジュール２４０は、位置のチェーンにその都市を含めない。対照的に、より小さな位置についてのチェーンに位置を含めるためのしきい値は、より短い時間の長さであってもよい。例えば、位置ペアリング・モジュール２５０は、ユーザが建物における部屋か領域に５分間以上位置した場合、そのユーザがその部屋または領域を訪問したと判定し、ユーザがより短い期間しかその部屋または領域にいない場合（例えば、ユーザが別の部屋に到るためにその部屋を歩いて通る場合）、位置のチェーンにその部屋を含めない。
【００３３】
同様に、同じチェーンに２つの位置を含めるか否かを判定するためのしきい値は、異なる種類の位置について調節されてもよい。より近くにある位置については、位置ペアリング・モジュール２５０は、より遠くに離れている位置についてよりも、２つの位置の間の経過時間により小さなしきい値を設定してもよい。例えば、ユーザが互いに１日以内に２つの都市を訪問した場合、位置ペアリング・モジュール２５０は、チェーンに２つの都市を含める。別の例として、位置ペアリング・モジュール２５０は、ユーザが互いに３時間以内に２つの店を訪問した場合、チェーンにその２つの店を含めるが、ユーザが連続する日に２つの店を訪問した場合、チェーンにそれらの店を含めない。
【００３４】
位置ペアリング・モジュール２５０は、オンライン・システム１４０の複数のユーザが訪問した位置のチェーンを集約する。一実施形態では、位置ペアリング・モジュール２５
０は、特定の種類の複数の位置または共通のエンティティに加盟した複数の位置を含むチェーンを選択するために、位置チェーンをフィルタリングする。例えば、位置ペアリング・モジュール２５０は、指定された都市内のまたは指定された地理的領域内の店に対応する位置を含むチェーンを選択するために、位置チェーンをフィルタリングする。別の例では、位置ペアリング・モジュール２５０は、テーマパークのライドなど、共通のエンティティに加盟した複数の位置を含むチェーンを選択するために、位置チェーンをフィルタリングする。さらに別の例では、位置ペアリング・モジュール２５０は、デパート内の売場またはカジノ内の領域など、特定の建物内の複数の位置を含むチェーンを選択する。さらにまた別の例では、位置ペアリング・モジュール２５０は、複数の都市に対応する複数の位置を含むチェーンを選択する。位置ペアリング・モジュール２５０は、これに代えて、位置の他のパラメータに基づき、位置をフィルタリングしてもよい。
【００３５】
一実施形態では、位置ペアリング・モジュール２５０は、これに加えてまたはこれに代えて、ユーザの人口統計（ユーザの年齢、ジェンダー、または収入など）によって位置チェーンをフィルタリングし、同様の人口統計グループに属するユーザが訪問した位置のチェーンを集約する。また、位置モジュール２４０は、昨年など、同様の期間内に訪問された位置のチェーンを集約してもよい。別の実施形態では、位置ペアリング・モジュール２５０は、ユーザが旅行中であるか否かなど、ユーザが位置を訪問したコンテキストによって、位置チェーンをフィルタリングする。例えば、位置ペアリング・モジュール２５０は、所与の地理的領域（例えば、都市）を訪問中のユーザ（その領域に駐在する（すなわち、頻繁に位置する）ユーザではなく）によって訪問されるその領域における位置を選択するために、位置チェーンをフィルタリングする。この場合、位置ペアリング・モジュール２５０は、しきい値距離以上を最近移動したユーザまたはより頻繁にそのチェーンにおける位置からしきい値距離以上離れて位置するユーザに関連付けられているチェーンを選択するために、位置チェーンをフィルタリングしてもよい。ユーザの他の特性を用いて位置チェーンをフィルタリングしてもよい。
【００３６】
オンライン・システム１４０のユーザが訪問した位置の集約されたチェーンに基づき、位置ペアリング・モジュール２５０は、ユーザがペアにおける第１の位置を訪問した場合にそのユーザがそのペアにおける第２の位置を訪れる高い確率が存在する、ペアの位置を識別する。すなわち、位置ペアリング・モジュール２５０は、ユーザが第１の位置を訪問した場合にそのユーザが第２の位置を訪問することの条件付き確率を決定する。一実施形態では、位置ペアリング・モジュール２５０はマルコフ連鎖として各位置チェーンをモデル化し、その場合、チェーンにおけるある位置をユーザが訪問する確率は、そのチェーンにおけるその位置の直前の位置のみに依存する。この条件付き確率がしきい値より大きい場合、位置ペアリング・モジュール２５０は、第２の位置を第１の位置とペアとする。
【００３７】
一般に、位置ペアリング・モジュール２５０は、オンライン・システム１４０のユーザが訪問した１組の位置チェーンにおける位置の出現数に基づき、位置をペアにする。一実施形態では、位置ペアリング・モジュール２５０は、ユーザが第１の位置を訪問した場合に第２の位置を訪問する条件付き確率を決定するために、支持度および信頼度など１つまたは複数のアソシエーション・ルールを用いる。位置Ａが与えられると、位置モジュール２４０は、位置Ａを含む集約された位置チェーンの百分率を決定することによって、集約された位置チェーンにおける位置Ａの支持度を決定する。同様に、位置ＡおよびＢが与えられると、位置モジュール２４０は、位置Ａおよび位置Ｂの両方を含むチェーンの百分率を決定することによって、集約された位置チェーンにおける両方の位置の支持度を決定する。位置ペアリング・モジュール２５０は、集約された位置チェーンにおける位置ＡおよびＢの支持度（すなわち、位置Ａおよび位置Ｂの両方を含む位置チェーンの百分率）を計算し、ＡおよびＢの和集合の支持度を集約されたチェーンにおける位置Ａの支持度で除すことによって、位置ＡおよびＢの間のペアリングのための信頼度を決定する。一実施形態
では、ＡおよびＢの信頼度がしきい値より大きい場合、位置ペアリング・モジュール２５０は、位置ＡおよびＢをペアにする。これに代えて、位置ペアリング・モジュール２５０は、位置Ａを含む位置チェーンのセットにおける位置Ｂの支持度を決定し、Ａを含むチェーンにおけるＢの支持度がしきい値より大きい場合、位置ＡおよびＢをペアにしてもよい。他のアソシエーション・ルールが、これに加えてまたはこれに代えて、位置間のペアリングを決定するために用いられてもよい。
【００３８】
２つの位置の支持度および信頼度を決定するために用いられる位置チェーンの集約されたセットは、オンライン・システム１４０のユーザの位置履歴から抽出される位置チェーンの完全なセットであってもよく、チェーンのフィルタリングされたセットであってもよい。上述の通り、位置ペアリング・モジュール２５０は、特定の特性を有するユーザに関連付けられているまたは特定の特性を有する位置を含むチェーンのセットを選択するために、位置チェーンをフィルタリングしてもよい。ユーザの人口統計の特徴または位置の特徴によって位置チェーンをフィルタリングした後、位置ペアリング・モジュール２５０は、フィルタリングされたセットにおける位置の出現数に基づき位置間の関連付けを決定する。したがって、位置ペアリング・モジュール２５０は、位置間の複数のペアリングを決定してもよく、その場合、各ペアリングは、位置またはその位置を訪問するユーザの特徴に関連付けられる。例えば、特定のユーザの人口統計の特性に関連付けられている位置ペアについては、ペアは、第１の位置と、ユーザが第１の位置に位置する場合にその特定の人口統計の特性を有するユーザが訪れる確率が高い第２の位置とを含む。
【００３９】
位置ペアリング・モジュール２５０によって生成される位置間のペアリングは、順序付けられたペアリングであっても順序付けられていないペアリングであってもよい。例えば、位置ペアリング・モジュール２５０の一実施形態は、オンライン・システム１４０のユーザが位置Ａを訪問した後に位置Ｂを訪問する第１の確率を決定するとともに、ユーザが位置Ｂを訪問した後に位置Ａを訪問する第２の確率を決定する。この場合、位置ペアリング・モジュール２５０は、位置Ａの後に位置Ｂを含む位置の集約されたチェーンの百分率と、位置Ｂの後に位置Ａを含む集約されたチェーンの百分率とを決定してよい。別の実施形態では、位置ペアリング・モジュール２５０は、位置ＡおよびＢが同じチェーンに出現する１つの確率を決定する（それらが出現する順序にかかわらず）。この場合、位置ペアリング・モジュール２５０は、位置ＡおよびＢの両方を含む（いずれの順序でも）集約されたチェーンの百分率を決定してよい。
【００４０】
さらにまた、位置ペアリング・モジュール２５０は、ペアリングを決定するために同じチェーンにおける２つの位置の任意の出現を用いてもよく、ペアリングを決定するために直ぐに続く位置のみを考慮してもよい。例えば、位置チェーンが、位置Ａ，Ｃ，Ｂをこの順序で含む場合、位置ペアリング・モジュール２０は、位置ＡおよびＢが連続して訪問されなかったので、この位置チェーンを位置ＡおよびＢの出現として数えない。別の実施形態では、位置ペアリング・モジュール２５０は、ユーザがしきい値量の時間内に位置ＡおよびＢを訪問した場合、位置ＡおよびＢを含むとして位置チェーンを数える（位置Ａ，Ｂの間に位置Ｃを訪問するにもかかわらず）。
【００４１】
図２Ｂは、オンライン・システム１４０の２つのユーザが訪問する位置の例を示す。図２Ｂの例では、ユーザ１は、他の位置に加え、位置Ａ，Ｂ，Ｃをこの順序で訪問しており、ユーザ１は、他の位置に加え、位置Ｂ，Ａ，Ｃをこの順序で訪問している。したがって、位置ペアリング・モジュール２５０は、ユーザ１の位置履歴からチェーン｛Ａ，Ｂ，…，Ｃ｝を抽出し、ユーザ２の位置履歴からチェーン｛Ｂ，Ａ，…，Ｃ｝を抽出する。チェーンに含めるために選択される位置は、位置のサイズ、ユーザ１および２の人口統計、または他の因子によってフィルタリングされてもよい。一実施形態では、位置ペアリング・モジュール２５０は、抽出されたチェーンにおけるそれぞれの位置の存在に基づき、位置
ＡとＢ、ＢとＣ、ＡとＣをペアにする。別の実施形態では、位置ペアリング・モジュール２５０は、位置ＡとＢを、両方のユーザがそれらの位置を連続して訪問しているので、ペアとするが、しかしながら、各ユーザが位置Ｃを訪問する前に異なる位置を訪問しているので、位置Ｃを位置Ａまたは位置Ｂとペアにしない。
【００４２】
広告ターゲティング・モジュール２５５は、位置ペアリング・モジュール２５０によって生成される位置ペアに基づき、オンライン・システム１４０のユーザに送るために広告を選択する。例えば、ユーザが１つのペアにおける第１の位置に位置する場合、広告ターゲティング・モジュール２５５は、そのペアにおける第２の位置の広告をユーザに送信する。これに代えて、ユーザが以前に第１の位置を訪問している場合、広告ターゲティング・モジュール２５５がペアにおける第２の位置の広告をユーザに送信してもよい。別の例では、ユーザがペアにおける位置のうちの一方を訪問している場合、広告ターゲティング・モジュール２５５は、ユーザに対する提示用にペアにおける２つの位置についてのグループ・クーポンを選択する。さらに別の例では、広告ターゲティング・モジュール２５５は、ペアにおける第１の位置を訪問したユーザに対する広告のターゲティングを行う広告主に、ペアにおける第２の位置を訪問したユーザもターゲットとすることを提案する。
【００４３】
一実施形態では、位置ペアリング・モジュール２５０が異なるユーザ特性に関連付けられているペアリングを生成した場合、広告ターゲティング・モジュール２５５は、ユーザに対する広告を選択するためにそのユーザの特性も用いる。例えば、位置ペアリング・モジュール２５０が特定の人口統計特性に関連付けられている位置のペアを決定した場合、広告ターゲティング・モジュール２５５は、ユーザの人口統計特性を識別し、そのユーザの人口統計特性に関連付けられている位置の１つまたは複数のペアを決定し、ユーザに対する提示用の広告を選択するために決定したペアを用いる。一実施形態では、選択された広告は、ウェブ・サーバ２６０によってユーザに対し提供される。
【００４４】
ウェブ・サーバ２６０は、オンライン・システム１４０を、ネットワーク１２０を介して１つ以上のクライアント・デバイス１１０や１つ以上のサードパーティ・システム１３０にリンクさせる。ウェブ・サーバ１４０は、ウェブ・ページや他のウェブ関連コンテンツ（ＪＡＶＡ（登録商標）、ＦＬＡＳＨ（登録商標）、ＸＭＬなど）を提供する。ウェブ・サーバ２６０は、例えば、インスタント・メッセージ、キュー・メッセージ（例えば、電子メール）、テキスト・メッセージ、ＳＭＳ（ショート・メッセージ・サービス）メッセージ、または任意の他の適切なメッセージ技術を用いて送られるメッセージなど、オンライン・システム１４０とクライアント・デバイス１１０との間におけるメッセージの受信およびルーティングを行うことができる。ユーザは、コンテンツ・ストア２１０に記憶される情報（例えば、イメージまたはビデオ）をアップロードするためにウェブ・サーバ２６０にリクエストを送ることができる。これに加えて、ウェブ・サーバ２６０は、ＩＯＳ（登録商標）、ＡＮＤＲＯＩＤ（商標）、ＷＥＢＯＳ（登録商標）、またはＲＩＭ（登録商標）など、ネイティブ・クライアント・デバイス・オペレーティング・システムにデータを直接送信するためにアプリケーションプログラムインターフェイス（ＡＰＩ）機能を提供してもよい、
一実施形態では、ウェブ・サーバ２６０は、位置ペアリングについての情報を、位置に関連付けられているシステム（例えば、サードパーティ・システム１３０）に送信する。例えば、ウェブ・サーバ２６０は、ある位置に、その位置とペアにされている他の位置の識別子を送信する。共通のエンティティに関連付けられている複数の位置（デパート内の売場など）については、ウェブ・サーバ２６０は、ペアになった位置の識別子をエンティティに送信してもよい。エンティティは、販売する製品を選択する、そのエンティティの位置の有効なレイアウトを決定する、またはそのエンティティの広告キャンペーンを通知するなど、ビジネス上のまたはマーケティング上の決定を行うために、このペアリングを用いることが可能である。
【００４５】
ペアになった位置に基づく広告のターゲティング
図３は、ペアになった位置に基づきユーザに対して広告をターゲティングするための処理の一実施形態を示すフローチャートである。一実施形態では、この処理の工程はオンライン・システム１４０によって実行される。この処理の他の実施形態は、異なる工程、より少数の工程、または追加の工程を含んでもよく、それらの工程を異なる順序で実行してもよい。
【００４６】
オンライン・システム１４０は、オンライン・システム１４０のユーザによって用いられる複数のユーザ・デバイス１１０から位置履歴を受信する（３０２）。ユーザが位置トラッキングをオプトインしている場合、オンライン・システム１４０は、そのユーザのユーザ・デバイス１１０の位置を（ユーザ・デバイス１１０によって用いられる様々な位置センサのいずれかによって検出されるにしたがって）定期的に受信し、そして、その位置をそのユーザのプロフィールに記憶する。一実施形態では、オンライン・システム１４０は、サンプリングされた位置データを集約し、各サンプルに位置するエンティティまたはオブジェクトを識別する。オンライン・システム１４０は、したがって、ユーザ・デバイス１１０が位置した位置のリストを生成し、サンプルのタイムスタンプに基づき、そのデバイスが各位置にどれくらい長く位置したかを決定する。
【００４７】
オンライン・システム１４０は、位置履歴からユーザが訪問した位置のチェーンを抽出する（３０４）。位置のチェーンは、ユーザが訪問した位置の並び（シーケンス）のリストであり、同様の種類の１つまたは複数の位置を含んでよい。一実施形態では、オンライン・システム１４０は、しきい値長さの時間内にオンライン・システムのユーザが訪問した１つまたは複数の位置を識別し、その１つまたは複数の位置をそのユーザが訪問した位置のチェーンとして抽出する。ユーザは、そのユーザのデバイスがしきい値量以上の時間、特定の位置に位置した場合、その位置を位置したと判定されてよい。
【００４８】
位置のチェーンに基づき、オンライン・システム１４０は位置の間のペアリングを生成する（３０６）。あるユーザが第１の位置を訪問した場合にそのユーザが第２の位置を訪れる高い確率が存在する場合、２つの位置はペアにされる。一実施形態では、オンライン・システム１４０は、２つの位置の間の関連付けを、複数の位置のチェーンにおけるそれら２つの位置の出現数に基づき決定する。例えば、ユーザが特定のジムを訪問した後に特定の食料雑貨店を訪問する場合、オンライン・システム１４０は、その体育館を訪問するユーザはその食料雑貨店も訪問する確率が高いと決定してもよい。オンライン・システム１４０は、位置の種類、位置チェーンに関連付けられているユーザの人口統計、またはユーザがチェーンにおける位置を訪問したコンテキストなど、様々な因子に基づき位置チェーンをフィルタリングしてよく、あるユーザが両方の位置を訪問する確率を決定するためにフィルタリングされた位置チェーンのセットにおける２つの位置の出現を用いてよい。
【００４９】
オンライン・システムは、位置ペアに基づき１つまたは複数の位置予測を出力する。一実施形態では、オンライン・システム１４０は、ユーザに対する提示用の広告を選択する（３０８）ために位置間のペアリングを用い、選択した広告をユーザに送信する（３１０）。一実施形態では、位置Ａが位置Ｂとペアにされる場合、オンライン・システム１４０は、位置Ａに現在位置するユーザに位置Ｂの広告を提示する（あるいは、位置Ｂに現在位置するユーザに位置Ａの広告を提示する）。例えば、オンライン・システム１４０が特定の食料雑貨店を特定のジムとペアにする場合、オンライン・システム１４０は、そのジムに位置するユーザに食料雑貨店の広告を提示してもよい。これに代えて、ユーザが以前にそのジムを訪問していた場合、オンライン・システム１４０はそのユーザに食料雑貨店の広告を提示してもよい。別の実施形態では、オンライン・システム１４０は、ペアになった位置の広告をユーザに送信する。例えば、オンライン・システム１４０がユーザに対す
る提示用に位置Ａの広告を選択する場合（例えば、広告のターゲティング基準に基づき）、オンライン・システム１４０は、位置Ａとペアになっている位置Ｂの広告もユーザに送信する。この例では、オンライン・システム１４０が都市Ａにおけるホテルの広告を選択し（例えば、ユーザが都市Ａへの旅行を計画していると判定されるので）、都市Ａが都市Ｂとペアにされる場合、オンライン・システム１４０は、ユーザに対する提示用に都市Ｂの広告も選択する。別の例として、オンライン・システム１４０は位置ＡおよびＢについてのジョイント・クーポンをユーザに送信する。この例では、デパートの２つの売場がペアにされる場合、オンライン・システム１４０は、ユーザに送信するために、それらの２つの売場において有効なクーポンを選択してもよい。さらに別の例では、オンライン・システム１４０は、ペアにおける第１の位置を訪問したユーザに対する広告のターゲティングを行う広告主に、ペアにおける第２の位置を位置したユーザもターゲットとすることを提案する。この例では、レストランと映画館とがペアにされる場合、オンライン・システム１４０は、その映画館を訪問するユーザに対する広告のターゲティングを行う広告主に、そのレストランを訪問するユーザもターゲットとするように提案する。
【００５０】
一実施形態では、オンライン・システム１４０は、位置に関連付けられているエンティティに位置ペアについての情報を（例えば、サードパーティ・システム１３０を介して）送信する（３１２）。このエンティティは、販売戦略を通知するため、広告ターゲティングの詳細を作成するためなどに、位置ペアを用いてもよい。例えば、オンライン・システム１４０は、デパートに、そのデパートを訪問するオンライン・システム１４０のユーザが訪問した位置のペアについての情報を提供する。位置ペアによって、顧客が店を通じてどのように動くかについての情報（例えば、家庭用品売場を訪問した後に靴売場を訪問する）がデパートに対し提供され、デパートが店のレイアウトを改良したり、顧客に対する製品のマーケティングを行ったりすることが可能となる。
【００５１】
まとめ
先の本発明の実施形態の記載は例示の目的で示されており、網羅的なものであったり、本発明を開示の形態そのものに限定したりといったことは意図していない。当業者には、上述の開示に鑑みて多くの修正および変更が可能であることが認められる。
【００５２】
本記載のいくつかの部分では、情報に関する演算のアルゴリズムおよび記号表現に関して本発明の実施形態を説明する。これらのアルゴリズムに関する説明および表現は、データ処理技術分野における当業者が自らの作業内容を他の当業者に有効に伝えるべく一般に用いられる。それらの演算は、機能的、計算的、または論理的に記載されているが、コンピュータ・プログラムまたは等価な電気回路、マイクロコードなどによって実装されることが理解される。さらにまた、それらの演算の構成を、一般性を損なうことなく、モジュールと呼ぶことが場合によっては簡便であることも分かっている。記載の演算およびそれに関連するモジュールは、ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組み合わせによって実装され得る。
【００５３】
本明細書に記載の工程、演算、および処理のいずれも、１つ以上のハードウェア・モジュールまたはソフトウェア・モジュールを、単独でまたは他のデバイスとの組み合わせにより用いて、実行または実装されることが可能である。一実施形態では、ソフトウェア・モジュールは、記載の工程、演算、および処理のいずれかまたはすべてを実行するべくコンピュータ・プロセッサによって実行可能なコンピュータ・プログラム・コードを含むコンピュータ可読媒体を備えるコンピュータ・プログラム製品によって実装される。
【００５４】
また本発明の実施形態は、本明細書における演算を実行するための装置に関する場合もある。この装置は、要求される目的のために特別に構築されてもよく、および／または、この装置は、コンピュータに格納されたコンピュータ・プログラムによって選択的にアク
ティブ化または再構成される汎用コンピューティング・デバイスを含んでもよい。そのようなコンピュータ・プログラムは、非一時的な有形のコンピュータ可読記憶媒体、または電子命令を格納するのに適し、コンピュータ・システム・バスに結合され得る任意の種類の媒体に格納されてよい。さらに、本明細書に記載のコンピュータ・システムは、単一のプロセッサを備えてもよく、より高い計算性能のためにマルチプロセッサ設計を用いたアーキテクチャであってもよい。
【００５５】
本発明の実施形態は、本明細書に記載のコンピューティング処理によって製造される製品にも関係し得る。そのような製品は、コンピューティング処理から得られる、非一時的な有形のコンピュータ可読記憶媒体に記憶される情報を含んでもよく、本明細書に記載のコンピュータ・プログラム製品または他のデータの組み合わせの任意の実施形態も含む。
【００５６】
最後に、本明細書で使用される用語は主に可読性および教示の目的で選択されており、発明の主題の線引きや限定を行うようには選択されていない場合がある。したがって、本発明の範囲は、この詳細な説明によってではなく、本明細書に基づく出願に関して生じる特許請求の範囲によって限定されることが意図される。したがって、本発明の実施形態の開示は、添付の特許請求の範囲に記載される本発明の範囲を例示することを意図しており、限定することは意図していない。
【図１】
0006629330.tif 000002
【図２Ａ】
0006629330.tif 000003
【図２Ｂ】
0006629330.tif 000004
【図３】
0006629330.tif 000005