図面 (/)

技術 場所のポリゴンベースの索引作成

出願人 フェイスブック,インク.
発明者 バソフニク、スタニスラフヴォラ、アビナブエイ.
出願日 2014年4月25日 (3年8ヶ月経過) 出願番号 2016-558000
公開日 2017年6月8日 (7ヶ月経過) 公開番号 2017-515201
状態 特許登録済
技術分野 検索装置 無線による位置決定 移動無線通信システム
主要キーワード 取外し式 シングルポート型 シングルボード 非相互的 加入者関係 外部境界 タイルベース グラフ要素

この技術の活用可能性のある市場・分野

関連する未来課題
重要な関連分野

この技術に関連する成長市場

関連メディア astavision

  • 3Dプリンター医学応用

    3Dプリンタ、正しくは、積層造形(AM:Additive Manufacturing)技術は、今や家…

  • 燃料電池車

    水素を燃料とし、空気中から取り込んだ酸素と反応させることで生み出した電気エネルギーを駆動力に利用する…

  • 生体情報デバイス・バイオセンサ

    「音楽を学習した人工知能は、人間を感動させることができるか?」をテーマに、クラブイベント「2045」…

後で読みたい技術情報を見つけたら、ブックマークしておきましょう!

ページの右上にあるブックマークボタンからこのページをブックマークできます。
あなたがブックマークした技術情報は、いつでもマイページのリストから閲覧することが出来ます。

この項目の情報は公開日時点(2017年6月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (11)

課題・解決手段

1つの実施形態において、方法は、位置の識別受信することを含む。本方法は、複数のレコードを含む逆索引アクセスすることであって、各レコードは、地図タイルに対応し、地図タイルに対応する1つまたは複数の場所を識別する、アクセスすることをさらに含む。逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、地図タイルは、場所を囲む領域を集合的に定義する。本方法は、位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別することも含む。

概要

背景

ソーシャルネットワーキングウェブサイトを含むソーシャル・ネットワーキング・システムは、そのユーザ(人または組織)がソーシャル・ネットワーキング・システムと、またソーシャル・ネットワーキング・システムを通じて互いに対話することを可能にする。

ソーシャル・ネットワーキング・システムは、ユーザからの入力と共に、ソーシャル・ネットワーキング・システム内でそのユーザに関連付けられているユーザ・プロフィール作成記憶する。ユーザ・プロフィールは、人口統計情報通信チャネル情報、およびユーザの個人的関心に関する情報を含んでもよい。また、ソーシャル・ネットワーキング・システムは、ユーザからの入力と共に、ソーシャル・ネットワーキング・システムの他のユーザとのユーザの関係の記録を作成および記憶し、サービス(たとえば、ウォール投稿写真共有イベントの主催、メッセージング、ゲーム、または広告)を提供し、ユーザ間またはユーザの間でのソーシャル対話を容易にする。

ソーシャル・ネットワーキング・システムは、1または複数のネットワークを通じて、そのサービスに関係するコンテンツまたはメッセージをユーザの移動体コンピューティングデバイスまたは他のコンピューティング・デバイスに送信する。ユーザは、ソーシャル・ネットワーキング・システム内のそのユーザのユーザ・プロフィールおよび他のデータにアクセスするために、ユーザの移動体コンピューティング・デバイスまたは他のコンピューティング・デバイス上にソフトウェアアプリケーションインストールしてもよい。ソーシャル・ネットワーキング・システムは、ユーザに接続された他のユーザの集約されたストーリニュースフィードなど、コンテンツ・オブジェクトパーソナライズされたセット生成し、ユーザに対して表示してもよい。

モバイル・コンピューティング・デバイス、例えば、スマートフォンタブレットコンピュータ、またはラップトップ・コンピュータなどは、その位置、方向、または向きを決定するための機能性、例えば、GPS受信器コンパスジャイロスコープ、または加速度計などを含み得る。そのようなデバイスは、無線通信、例えば、ブルートゥース通信近距離無線通信(NFC:near−field communication)、または赤外線(IR)通信、または無線ローカルエリア・ネットワーク(WLAN)もしくは携帯電話ネットワークとの通信などのための機能性も含み得る。そのようなデバイスは、1つまたは複数のカメラスキャナタッチスクリーンマイクロフォン、またはスピーカも含み得る。モバイル・コンピューティング・デバイスは、ソフトウェア・アプリケーション、例えば、ゲーム、ウェブブラウザ、またはソーシャル・ネットワーキング・アプリケーションなども実行し得る。ソーシャル・ネットワーキング・アプリケーションを用いれば、ユーザは、ユーザのソーシャル・ネットワーク内で、他のユーザと接続し、通信し、情報を共有し得る。

概要

1つの実施形態において、方法は、位置の識別受信することを含む。本方法は、複数のレコードを含む逆索引にアクセスすることであって、各レコードは、地タイルに対応し、地タイルに対応する1つまたは複数の場所を識別する、アクセスすることをさらに含む。逆索引において識別される場所のうちの少なくとも1つは、複数の地タイルに対応する複数のレコードにおいて識別され、地タイルは、場所を囲む領域を集合的に定義する。本方法は、位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別することも含む。

目的

限定としてではなく例として、ユーザは、自身の位置を、その位置に対してチェックインすることによって、または、さもなければ、自身の位置の標識もしくは識別を他の方法で提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

方法であって、コンピューティングデバイスによって、位置の識別受信すること、コンピューティング・デバイスによって、複数のレコードを含む逆索引アクセスすることであって、各レコードは、地図タイルに対応し、該地図タイルに対応する1つまたは複数の場所を識別し、該逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、該複数の地図タイルは、該場所を囲む領域を集合的に定義する、前記逆索引にアクセスすること、コンピューティング・デバイスによって、該位置に対して関連付けられた1つまたは複数の場所を該逆索引に基づいて識別すること、コンピューティング・デバイスによって、該位置に対して関連付けられたものとして識別される場所のうちの1つに対応する順索引にアクセスすることであって、該順索引は、該場所を囲む該領域を集合的に定義する地図タイルの位置識別子を含む、前記順索引にアクセスすること、コンピューティング・デバイスによって、該順索引に基づいて、該位置と該場所との間の最短距離を決定すること、を備える方法。

請求項2

前記位置が、前記場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つの地図タイル内に位置する場合、該場所は、前記位置に対して関連付けられる、請求項1に記載の方法。

請求項3

前記位置が、前記場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つまたは複数の所定の閾値距離内に位置する場合、該場所は、前記位置に対して関連付けられる、請求項1に記載の方法。

請求項4

前記位置の識別を受信することは、前記位置を識別するクエリを受信することを含む、請求項1乃至3のいずれか1項に記載の方法。

請求項5

前記クエリが、前記位置に加えて、特定の場所を識別する、請求項4に記載の方法。

請求項6

前記位置に対して関連付けられた1つまたは複数の場所を前記逆索引に基づいて識別することは、前記特定の場所の少なくとも一部が、前記位置に対して関連付けられた地図タイル内に位置するかを決定することを含む、請求項5に記載の方法。

請求項7

コンピューティング・デバイスによって、前記位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することをさらに備え、場所のスコアは、前記位置と該場所との間の距離に少なくとも部分的に基づく、請求項1乃至6のいずれか1項に記載の方法。

請求項8

コンピューティング・デバイスによって、前記位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することをさらに備え、場所のスコアは、該場所に対して関連付けられたソーシャルグラフ情報に少なくとも部分的に基づく、請求項1乃至7のいずれか1項に記載の方法。

請求項9

実行されると、請求項1乃至8のいずれか1項に記載の方法を実行するように動作可能であるソフトウェア具現化する1つまたは複数のコンピュータ読取可能な非一時的な記憶媒体

請求項10

システムであって、1つまたは複数のプロセッサと、該プロセッサに対して結合され、該プロセッサによって実行可能な命令を含むメモリと、を備え、該プロセッサは、該命令を実行する場合に、請求項1乃至8のいずれか1項に記載の方法を実行するように動作可能である、システム。

請求項11

方法であって、コンピューティング・デバイスによって、位置の識別を受信すること、コンピューティング・デバイスによって、複数のレコードを含む逆索引にアクセスすることであって、各レコードは、地図タイルに対応し、該地図タイルに対応する1つまたは複数の場所を識別し、該逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、該複数の地図タイルは、該場所を囲む領域を集合的に定義する、前記アクセスすること、コンピューティング・デバイスによって、該位置に対して関連付けられた1つまたは複数の場所を該逆索引に基づいて識別すること、を備える方法。

請求項12

前記位置が、前記場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つの地図タイル内に位置する場合、該場所は、前記位置に対して関連付けられる、請求項11に記載の方法。

請求項13

前記位置が、前記場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つまたは複数の所定の閾値距離内に位置する場合、該場所は、前記位置に対して関連付けられる、請求項11に記載の方法。

請求項14

コンピューティング・デバイスによって、前記位置に対して関連付けられたものとして識別される場所のうちの1つに対応する順索引にアクセスすることをさらに備え、該順索引は、前記場所を囲む領域を集合的に定義する地図タイルの位置識別子を含む、請求項11に記載の方法。

請求項15

コンピューティング・デバイスによって、前記順索引に基づいて、前記位置と前記場所との間の最短距離を決定することをさらに備える請求項14に記載の方法。

請求項16

前記位置の識別を受信することは、前記位置を識別するクエリを受信することを含む、請求項11に記載の方法。

請求項17

前記クエリが、前記位置に加えて、特定の場所を識別する、請求項16に記載の方法。

請求項18

前記位置に対して関連付けられた1つまたは複数の場所を前記逆索引に基づいて識別することは、前記特定の場所の少なくとも一部が、前記位置に対して関連付けられた地図タイル内に位置するかを決定することを含む、請求項17に記載の方法。

請求項19

コンピューティング・デバイスによって、前記位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することをさらに備え、場所のスコアは、前記位置と該場所との間の距離に少なくとも部分的に基づく、請求項11に記載の方法。

請求項20

コンピューティング・デバイスによって、前記位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することをさらに備え、場所のスコアは、該場所に対して関連付けられたソーシャル・グラフ情報に少なくとも部分的に基づく、請求項11に記載の方法。

請求項21

ソフトウェアを具現化する1つまたは複数のコンピュータ読取可能な非一時的な記憶媒体であって、該ソフトウェアは、実行されると、位置の識別を受信すること、複数のレコードを含む逆索引にアクセスすることであって、各レコードは、地図タイルに対応し、該地図タイルに対応する1つまたは複数の場所を識別し、該逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、該複数の地図タイルは、該場所を囲む領域を集合的に定義する、前記逆索引にアクセスすること、該位置に対して関連付けられた1つまたは複数の場所を該逆索引に基づいて識別すること、を実行するように動作可能である、1つまたは複数のコンピュータ読取可能な非一時的な記憶媒体。

請求項22

前記位置が、前記場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つの地図タイル内に位置する場合、該場所は、前記位置に対して関連付けられる、請求項21に記載の記録媒体

請求項23

前記位置が、前記場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つまたは複数の所定の閾値距離内に位置する場合、該場所は、前記位置に対して関連付けられる、請求項21に記載の記録媒体。

請求項24

前記ソフトウェアは、実行されると、前記位置に対して関連付けられたものとして識別される場所のうちの1つに対応する順索引にアクセスすることを実行するようにさらに動作可能であり、該順索引は、前記場所を囲む領域を集合的に定義する地図タイルの位置識別子を含む、請求項21に記載の記憶媒体。

請求項25

前記ソフトウェアは、実行されると、前記順索引に基づいて、前記位置と前記場所との間の最短距離を決定することを実行するようにさらに動作可能である、請求項24に記載の記憶媒体。

請求項26

前記位置の識別を受信することは、前記位置を識別するクエリを受信することを含む、請求項21に記載の記憶媒体。

請求項27

前記クエリが、前記位置に加えて、特定の場所を識別する、請求項26に記載の記憶媒体。

請求項28

前記ソフトウェアは、実行されると、前記位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することを実行するようにさらに動作可能であり、場所のスコアは、前記位置と該場所との間の距離に少なくとも部分的に基づく、請求項21に記載の記憶媒体。

請求項29

前記ソフトウェアは、実行されると、前記位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定するようにさらに動作可能であり、場所のスコアは、該場所に対して関連付けられたソーシャル・グラフ情報に少なくとも部分的に基づく、請求項21に記載の記憶媒体。

請求項30

システムであって、1つまたは複数のプロセッサと、該プロセッサに対して結合され、該プロセッサによって実行可能な命令を含むメモリと、を備え、該プロセッサは、該命令を実行する場合に、位置の識別を受信すること、複数のレコードを含む逆索引にアクセスすることであって、各レコードは、地図タイルに対応し、該地図タイルに対応する1つまたは複数の場所を識別し、該逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、該複数の地図タイルは、該場所を囲む領域を集合的に定義する、前記逆索引にアクセスすること、該位置に対して関連付けられた1つまたは複数の場所を該逆索引に基づいて識別すること、を実行するように動作可能である、システム。

技術分野

0001

開示は、一般に、ユーザの位置を決定し、ユーザの位置に対して関連付けられた場所識別することに関する。

背景技術

0002

ソーシャルネットワーキングウェブサイトを含むソーシャル・ネットワーキング・システムは、そのユーザ(人または組織)がソーシャル・ネットワーキング・システムと、またソーシャル・ネットワーキング・システムを通じて互いに対話することを可能にする。

0003

ソーシャル・ネットワーキング・システムは、ユーザからの入力と共に、ソーシャル・ネットワーキング・システム内でそのユーザに関連付けられているユーザ・プロフィール作成記憶する。ユーザ・プロフィールは、人口統計情報通信チャネル情報、およびユーザの個人的関心に関する情報を含んでもよい。また、ソーシャル・ネットワーキング・システムは、ユーザからの入力と共に、ソーシャル・ネットワーキング・システムの他のユーザとのユーザの関係の記録を作成および記憶し、サービス(たとえば、ウォール投稿写真共有イベントの主催、メッセージング、ゲーム、または広告)を提供し、ユーザ間またはユーザの間でのソーシャル対話を容易にする。

0004

ソーシャル・ネットワーキング・システムは、1または複数のネットワークを通じて、そのサービスに関係するコンテンツまたはメッセージをユーザの移動体コンピューティングデバイスまたは他のコンピューティング・デバイスに送信する。ユーザは、ソーシャル・ネットワーキング・システム内のそのユーザのユーザ・プロフィールおよび他のデータにアクセスするために、ユーザの移動体コンピューティング・デバイスまたは他のコンピューティング・デバイス上にソフトウェアアプリケーションインストールしてもよい。ソーシャル・ネットワーキング・システムは、ユーザに接続された他のユーザの集約されたストーリニュースフィードなど、コンテンツ・オブジェクトパーソナライズされたセット生成し、ユーザに対して表示してもよい。

0005

モバイル・コンピューティング・デバイス、例えば、スマートフォンタブレットコンピュータ、またはラップトップ・コンピュータなどは、その位置、方向、または向きを決定するための機能性、例えば、GPS受信器コンパスジャイロスコープ、または加速度計などを含み得る。そのようなデバイスは、無線通信、例えば、ブルートゥース通信近距離無線通信(NFC:near−field communication)、または赤外線(IR)通信、または無線ローカルエリア・ネットワーク(WLAN)もしくは携帯電話ネットワークとの通信などのための機能性も含み得る。そのようなデバイスは、1つまたは複数のカメラスキャナタッチスクリーンマイクロフォン、またはスピーカも含み得る。モバイル・コンピューティング・デバイスは、ソフトウェア・アプリケーション、例えば、ゲーム、ウェブブラウザ、またはソーシャル・ネットワーキング・アプリケーションなども実行し得る。ソーシャル・ネットワーキング・アプリケーションを用いれば、ユーザは、ユーザのソーシャル・ネットワーク内で、他のユーザと接続し、通信し、情報を共有し得る。

課題を解決するための手段

0006

特定の実施形態において、場所、例えば、空港公園ショッピングモール、企業キャンパス、大学キャンパス、スタジアム博物館近所都市映画館レストラン、またはランドマークなどは、ポリゴンとしてモデリングされる。ポリゴンは、場所を囲み、または場所に近接して囲む領域を定義し得る。境界ボックスは、ポリゴンの周り構築され、次いで、N×Nグリッドサンプル点が、この境界ボックス上に重ね合わせられる。ここで、Nは、任意の適切な正の整数(例えば、10、20、30等)である。ポリゴン外に位置するサンプル点は破棄され、ポリゴン内またはポリゴンの境界上に位置するサンプル点は保持される。残りのサンプル点は、場所に対して関連付けられ、各サンプル点は、特定の地図タイルに対して関連付けられる。ここで、各地図タイルは、一意タイルIDを有する。

0007

地図、地理的領域、または場所についての逆索引は、サンプル点および地図タイルのグリッドに少なくとも部分的に基づいて決定される。逆索引は、レコードまたはエントリ体系化され、各レコードは、タイル識別子を、タイルに対して関連付けられた場所またはオブジェクトの1つまたは複数の識別子と共に含み得る。逆索引は、ユーザの位置の取得に関連して使用される。

0008

場所に対して関連付けられた順索引は、ポリゴンおよび場所の周りの境界ボックスの構築に少なくとも部分的に基づいて決定される。場所についての順索引は、その場所に対して関連付けられたサンプル点の1つまたは複数のジオロケーション識別子を含み得る。順索引は、どこにユーザが位置するか、ユーザが特定の場所内もしくは特定の場所の近くに位置するか、1つもしくは複数のどの場所がユーザのすぐ近くに存在するか、または、ユーザから1つもしくは複数の場所への距離を決定するように使用される。例えば、順索引は、ユーザの位置とある場所との間の距離を、ユーザからその場所に対して関連付けられた各サンプル点までの距離を計算することによって決定するように使用される。その結果、ユーザと場所との間の距離は、計算された距離のうちの最小値となる。また、順索引は、ユーザの近くに位置する場所をスコア付けし、ランク付けする際に使用されてもよい。

0009

本発明に係る実施形態は、具体的には、方法記憶媒体およびシステムを対象とする添付の特許請求の範囲において開示されており、特許請求の範囲において、1つの請求項カテゴリにおいて述べられる任意の特徴、例えば、方法は、別の請求項カテゴリ、例えば、システムにおいても、同様に特許請求される。添付の特許請求の範囲における従属関係または参照は、形式上の理由で選ばれているものにすぎない。ただし、(具体的には、多数項従属関係において)任意の先行する請求項への任意的な参照から結果として生じる任意の主題も、同様に特許請求され、それにより、請求項の任意の組み合わせおよびその特徴は、添付の特許請求の範囲において選ばれた従属関係に関わらず、開示され、特許請求される。

0010

本発明の一実施形態において、方法は、
コンピューティング・デバイスによって、位置の識別を受信すること、
コンピューティング・デバイスによって、複数のレコードを含む逆索引にアクセスすることであって、
各レコードは、地図タイルに対応し、地図タイルに対応する1つまたは複数の場所を識別し、
逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、複数の地図タイルは、場所を囲む領域を集合的に定義する、アクセスすること、
コンピューティング・デバイスによって、位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別すること、を含む。

0011

位置が、場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つの地図タイル内に位置する場合、この場所は、位置に対して関連付けられる。
位置が、場所を囲む領域を集合的に定義する複数の地図タイルのうちの1つまたは複数の所定の閾値距離内に位置する場合、この場所は、位置に対して関連付けられる。

0012

さらなる実施形態において、本方法は、コンピューティング・デバイスによって、位置に対して関連付けられたものとして識別される場所のうちの1つに対応する順索引にアクセスすることであって、順索引は、場所を囲む領域を集合的に定義する地図タイルの位置識別子を含む、アクセスすることを含み得る。

0013

さらなる実施形態において、本方法は、コンピューティング・デバイスによって、順索引に基づいて、位置と場所との間の最短距離を決定することを含み得る。
位置の識別を受信することは、位置を識別するクエリを受信することを含み得る。

0014

クエリは、位置に加えて、特定の場所を識別し得る。
位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別することは、特定の場所の少なくとも一部が、位置に対して関連付けられた地図タイル内に位置するかを決定することを含み得る。

0015

さらなる実施形態において、本方法は、コンピューティング・デバイスによって、位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することであって、場所のスコアは、位置とこの場所との間の距離に少なくとも部分的に基づく、決定することを含み得る。

0016

さらなる実施形態において、本方法は、コンピューティング・デバイスによって、位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定することであって、場所のスコアは、この場所に対して関連付けられたソーシャル・グラフ情報に少なくとも部分的に基づく、決定することを含み得る。

0017

同様に特許請求される本発明に係るさらなる実施形態において、1つまたは複数のコンピュータ読取可能な非一時的な記憶媒体は、ソフトウェアを具現化し、このソフトウェアは、実行されると、
位置の識別を受信し、
複数のレコードを含む逆索引にアクセスし、
各レコードは、地図タイルに対応し、地図タイルに対応する1つまたは複数の場所を識別し、
逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、複数の地図タイルは、場所を囲む領域を集合的に定義し、
位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別するように動作可能である。

0018

さらなる実施形態において、ソフトウェアは、実行されると、位置に対して関連付けられたものとして識別される場所のうちの1つに対応する順索引にアクセスするように動作可能であってもよく、順索引は、場所を囲む領域を集合的に定義する地図タイルの位置識別子を含む。

0019

さらなる実施形態において、ソフトウェアは、実行されると、順索引に基づいて、位置と場所との間の最短距離を決定するように動作可能であってもよい。
さらなる実施形態において、ソフトウェアは、実行されると、位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定するように動作可能であってもよく、場所のスコアは、位置とこの場所との間の距離に少なくとも部分的に基づく。

0020

さらなる実施形態において、ソフトウェアは、実行されると、位置に対して関連付けられた1つまたは複数の場所の各々のスコアを決定するように動作可能であってもよく、場所のスコアは、この場所に対して関連付けられたソーシャル・グラフ情報に少なくとも部分的に基づく。

0021

同様に特許請求される本発明に係るさらなる実施形態において、システムは、
1つまたは複数のプロセッサと、
プロセッサによって実行可能な命令を含む、プロセッサに対して結合されたメモリと、からなり、プロセッサは、命令を実行する場合に、
位置の識別を受信し、
複数のレコードを含む逆索引にアクセスし、
各レコードは、地図タイルに対応し、地図タイルに対応する1つまたは複数の場所を識別し、
逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別され、複数の地図タイルは、場所を囲む領域を集合的に定義し、
位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別するように動作可能である。

0022

本発明のさらなる実施形態において、1つまたは複数のコンピュータ読取可能な非一時的な記憶媒体は、ソフトウェアを具現化し、このソフトウェアは、実行されると、本発明に係る方法または上述された実施形態のうちのいずれかを実行するように動作可能である。

0023

本発明のさらなる実施形態において、システムは、1つまたは複数のプロセッサと、プロセッサによって実行可能な命令を含む、プロセッサに対して結合されたメモリと、からなり、プロセッサは、命令を実行する場合に、本発明に係る方法または上述された実施形態のうちのいずれかを実行するように動作可能である。

0024

上記に開示された実施形態は、例にすぎず、本開示の範囲は、開示された実施形態に限定されない。特定の実施形態は、上記に開示された実施形態の構成要素要素、特徴、機能、動作、または工程の全部を含んでも、一部を含んでも、または、全く含まなくてもよい。

図面の簡単な説明

0025

ソーシャル・ネットワーキング・システムに対して関連付けられた例示的なネットワーク環境を例示する図。
例示的なソーシャル・グラフを例示する図。
例示的な地図タイルを有する例示的な地図を例示する図。
例示的なポリゴンによって囲まれた例示的な場所を例示する図。
例示的なポリゴンの周りに構築された例示的な境界ボックスを例示する図。
図5の例示的なポリゴンを、例示的な地図タイルおよびサンプル点と共に例示する図。
例示的な地図タイルおよび8つの周囲の地図タイルを例示する図。
例示的な場所、および図4の例示的なポリゴン、および例示的な地図タイルを例示する図。
位置に対して関連付けられた場所を識別するための例示的な方法を例示する図。
例示的なコンピュータ・システムを例示する図。

実施例

0026

特定の実施形態では、特定のユーザ特性を有する可能性の高いソーシャル・ネットワーキング・システムのユーザを推測するための方法について記載する。特定の実施形態では、最初機械学習アルゴリズムまたは他の適切な方法を用いて、ソーシャル・ネットワーキング・システムのソーシャル・グラフにおいて、特定のユーザ特性を有するユーザに対応する1組のユーザ・ノードを識別し、各識別されたユーザ・ノードにスコアを割り当てる。特定の実施形態では、次いで、ソーシャル・グラフにおける他のユーザ・ノードについてのスコアを推定するために、識別されたユーザ・ノードをシードとして用いてよい。ユーザ・ノードのスコアは、割り当てられたスコアを有するユーザ・ノードに対するソーシャル・グラフにおけるそのユーザ・ノードのつながりに基づいて推定されてもよい。ユーザ・ノードについての推定されたスコアの値は、そのユーザ・ノードが特定のユーザ特性を有するユーザに対応する見込みを示してもよい。

0027

図1は、ソーシャル・ネットワーキング・システムに関連付けられている例示的なネットワーク環境100を示す。ネットワーク環境100は、互いにネットワーク110によって接続されたユーザ101、クライアント・システム130、ソーシャル・ネットワーキング・システム160、およびサードパーティ・システム170を含む。図1は、ユーザ101、クライアント・システム130、ソーシャル・ネットワーキング・システム160、サードパーティ・システム170、およびネットワーク110の特定の構成を示すが、この開示は、ユーザ101、クライアント・システム130、ソーシャル・ネットワーキング・システム160、サードパーティ・システム170、およびネットワーク110の任意の好適な構成を企図する。限定するものとしてではなく一例として、クライアント・システム130、ソーシャル・ネットワーキング・システム160、およびサードパーティ・システム170の2以上は、ネットワーク110をバイパスして互いに直接的に接続されてもよい。別の例として、クライアント・システム130、ソーシャル・ネットワーキング・システム160、およびサードパーティ・システム170の2以上が、全体として、または部分的に互いに物理的に、または論理的に同じ場所にあってもよい。さらに、図1は、特定の数のユーザ101、クライアント・システム130、ソーシャル・ネットワーキング・システム160、サードパーティ・システム170、およびネットワーク110を示すが、この開示は、任意の好適な数のユーザ101、クライアント・システム130、ソーシャル・ネットワーキング・システム160、サードパーティ・システム170、およびネットワーク110を企図する。限定するものとしてではなく一例として、ネットワーク環境100は、複数のユーザ101、クライアント・システム130、ソーシャル・ネットワーキング・システム160、サードパーティ・システム170、およびネットワーク110を含んでもよい。

0028

特定の実施形態では、ユーザ101は、ソーシャル・ネットワーキング・システム160と、またはソーシャル・ネットワーキング・システム160を通じて対話、すなわち通信する個人(人間のユーザ)、エンティティ(たとえば、企業、事業者、またはサードパーティ・アプリケーション)、または(たとえば、個人またはエンティティの)グループであってよい。特定の実施形態では、ソーシャル・ネットワーキング・システム160は、オンライン・ソーシャル・ネットワークをホストするネットワークアドレス指定可能なコンピューティング・システムであってよい。ソーシャル・ネットワーキング・システム160は、たとえばユーザプロフィール・データ、コンセプトプロフィール・データ、ソーシャル・グラフ情報、またはオンライン・ソーシャル・ネットワークに関係する他の好適なデータなど、ソーシャル・ネットワーキング・データを生成、記憶、受信、および送信する。ソーシャル・ネットワーキング・システム160は、ネットワーク環境100の他の構成要素によって、直接的に、またはネットワーク110を通じてアクセスされてもよい。特定の実施形態では、ソーシャル・ネットワーキング・システム160は、ユーザ101がたとえば適切なプライバシ設定を設定することによってなど、自分達アクションをソーシャル・ネットワーキング・システム160によって記録させる、または他のシステム(たとえば、サードパーティ・システム170)と共有させることについてオプトインまたはオプトアウトすることを可能にする認可サーバ(または他の適切な構成要素)を含んでもよい。ユーザのプライバシ設定は、そのユーザに関連付けられているどの情報が記録されるか、そのユーザに関連付けられている情報がどのように記録されるか、そのユーザに関連付けられている情報がいつ記録されるか、そのユーザに関連付けられている情報を誰が記録するか、そのユーザに関連付けられている情報が誰と共有されるか、およびそのユーザに関連付けられている情報が何の目的で記録され共有されるかを決定することができる。認可サーバは、ブロッキング、データのハッシュ化、匿名化、または他の適切な技術を通じて、ソーシャル・ネットワーキング・システム160のユーザの1以上のプライバシ設定を適切に実施するために用いられる。特定の実施形態では、サードパーティ・システム170は、場所のポリゴンベース索引(polygon-based indexing)に少なくとも部分的に基づく1つ又は複数の順索引又は逆索引をホストするネットワークアドレス指定可能なコンピューティング・システムであってよい。サードパーティ・システム170は、たとえば、ユーザの近くに位置するユーザが要求した場所からクエリなど、順索引又は逆索引を含む位置ベース・クエリ(location-based query)の結果を生成、記憶、受信、および送信する。サードパーティ・システム170は、ネットワーク環境100の他の構成要素によって、直接的に、またはネットワーク110を通じてアクセスされてもよい。特定の実施形態では、1または複数のユーザ101が1または複数のクライアント・システム130を使用し、ソーシャル・ネットワーキング・システム160またはサードパーティ・システム170にアクセスし、データを送り、それらからデータを受信してもよい。クライアント・システム130は、ソーシャル・ネットワーキング・システム160またはサードパーティ・システム170に直接的に、ネットワーク110を通じて、またはサードパーティ・システムを通じてアクセスしてもよい。限定するものとしてではなく一例として、クライアント・システム130は、サードパーティ・システム170にソーシャル・ネットワーキング・システム160を通じてアクセスしてもよい。クライアント・システム130は、たとえばパーソナル・コンピュータ、ラップトップ・コンピュータ、携帯電話、スマートフォン、またはタブレット・コンピュータなど、任意の好適なコンピューティング・デバイスであってよい。

0029

この開示は、任意の好適なネットワーク110を企図する。限定するものとしてではなく一例として、ネットワーク110の1または複数の部分は、アドホック・ネットワーク、イントラネットエクストラネット仮想プライベート・ネットワーク(VPN)、ローカル・エリア・ネットワーク(LAN)、無線LAN(WLAN)、ワイド・エリア・ネットワーク(WAN)、無線WAN(WWAN)、メトロポリタン・エリア・ネットワーク(MAN)、インターネットの一部分、公衆交換電話網(PSTN)の一部分、携帯電話ネットワーク、またはこれらの2以上の組合せを含んでもよい。ネットワーク110は、1または複数のネットワーク110を含んでもよい。

0030

リンク150は、クライアント・システム130、ソーシャル・ネットワーキング・システム160、およびサードパーティ・システム170を通信ネットワーク110に、または互いに接続する。この開示は、任意の好適なリンク150を企図する。特定の実施形態では、1または複数のリンク150は、1または複数の有線(たとえば、デジタル加入者線(DSL)またはDOCSIS(Data Over Cable Service Interface Specification)など)、無線(たとえば、Wi−FiまたはWiMAX(Worldwide interoperability for Microwave Access)など)、または光(たとえば、同期光ネットワーク(SONET)または同期デジタルハイアラーキSDH)など)リンクを含む。特定の実施形態では、1または複数のリンク150は、それぞれ、アドホック・ネットワーク、イントラネット、エクストラネット、VPN、LAN、WLAN、WAN、WWAN、MAN、インターネットの一部分、PSTNの一部分、セルラ技術ベースのネットワーク、衛星通信技術ベースのネットワーク、別のリンク150、または2以上のそのようなリンク150の組合せを含む。リンク150は、必ずしもネットワーク環境100全体を通じて同じであることを必要としない。1または複数の第1のリンク150は、1または複数の点で1または複数の第2のリンク150と異なってもよい。

0031

図2は、例示的なソーシャル・グラフ200を示す。特定の実施形態では、ソーシャル・ネットワーキング・システム160は、1または複数のソーシャル・グラフ200を1または複数のデータ・ストア内に記憶する。特定の実施形態では、ソーシャル・グラフ200は、複数のノード(複数のユーザ・ノード202または複数のコンセプト・ノード204を含んでもよい)と、それらのノードを接続する複数のエッジ206とを含んでもよい。図2に示されている例示的なソーシャル・グラフ200は、説明のために、2次元視覚マップ表現で示されている。特定の実施形態では、ソーシャル・ネットワーキング・システム160、クライアント・システム130、またはサードパーティ・システム170は、適切な用途のためにソーシャル・グラフ200および関連するソーシャル・グラフ情報にアクセスする。ソーシャル・グラフ200のノードおよびエッジは、データ・オブジェクトとして、たとえばデータ・ストア(ソーシャル・グラフ・データベースなど)内に記憶されてもよい。そのようなデータ・ストアは、ソーシャル・グラフ200のノードまたはエッジの、1または複数の検索可能または照会可能なインデックスを含んでもよい。

0032

特定の実施形態では、ユーザ・ノード202は、ソーシャル・ネットワーキング・システム160のユーザに対応する。限定するものとしてではなく一例として、ユーザは、ソーシャル・ネットワーキング・システム160と、またはソーシャル・ネットワーキング・システム160を通じて対話または通信する個人(人間のユーザ)、エンティティ(たとえば、企業、事業者、またはサードパーティ・アプリケーション)、または(たとえば、個人またはエンティティの)グループであってよい。特定の実施形態では、ユーザがアカウントをソーシャル・ネットワーキング・システム160に登録するとき、ソーシャル・ネットワーキング・システム160は、そのユーザに対応するユーザ・ノード202を作成し、そのユーザ・ノード202を1または複数のデータ・ストア内に記憶する。本明細書に記載のユーザおよびユーザ・ノード202は、適切な場合、登録されたユーザ、および登録されたユーザに関連付けられているユーザ・ノード202に及ぶ。それに加えて、または代替として、本明細書に記載のユーザおよびユーザ・ノード202は、適切な場合、ソーシャル・ネットワーキング・システム160に登録しなかったユーザに及ぶ。特定の実施形態では、ユーザ・ノード202は、ユーザによって提供された情報、またはソーシャル・ネットワーキング・システム160を含む様々なシステムによって収集された情報に関連付けられてもよい。限定するものとしてではなく一例として、ユーザは、自分の名前、プロフィール写真、連絡先情報誕生日性別婚姻状態、家族状態、雇用、学歴、好み、関心、または他の人口統計情報を提供してもよい。特定の実施形態では、ユーザ・ノード202は、ユーザに関連付けられている情報に対応する1または複数のデータ・オブジェクトに関連付けられてもよい。特定の実施形態では、ユーザ・ノード202は、1または複数のウェブ・ページに対応してもよい。

0033

特定の実施形態では、コンセプト・ノード204は、コンセプトに対応する。限定するものとしてではなく一例として、コンセプトは、場所(たとえば、空港、公園、ショッピング・モール、企業キャンパス、大学キャンパス、スタジアム、博物館、近所、都市、映画館、レストラン、ランドマーク、または任意の他の適切な場所もしくは適切な場所の組み合わせなど)、ウェブサイト(たとえば、ソーシャル・ネットワーキング・システム160に関連付けられているウェブサイト、またはウェブアプリケーションサーバに関連付けられているサードパーティウェブサイトなど)、エンティティ(たとえば、人、事業者、グループ、スポーツチーム、または有名人など)、ソーシャル・ネットワーキング・システム160内、またはウェブアプリケーションサーバなど外部サーバ上に位置するリソース(たとえば、オーディオファイル映像ファイルデジタル写真テキストファイル構造化文書、またはアプリケーションなど)、実際の財産または知的財産(たとえば、彫刻絵画映画、ゲーム、楽曲、着想、写真、または書物など)、ゲーム、アクティビティ、着想もしくは理論、別の好適なコンセプト、または2以上のそのようなコンセプトに対応してもよい。コンセプト・ノード204は、ユーザによって提供されたコンセプトの情報、またはソーシャル・ネットワーキング・システム160を含む様々なシステムによって収集された情報に関連付けられてもよい。限定するものとしてではなく一例として、コンセプトの情報は、名前もしくはタイトル、1または複数の画像(たとえば、本の表紙の画像)、ロケーション(たとえば、住所または地理的ロケーション)、(URLに関連付けられる)ウェブサイト、連絡先情報(たとえば、電話番号または電子メール・アドレス)、他の好適なコンセプト情報、またはそのような情報の任意の好適な組合せを含んでもよい。特定の実施形態では、コンセプト・ノード204は、コンセプト・ノード204に関連付けられている情報に対応する1または複数のデータ・オブジェクトに関連付けられてもよい。特定の実施形態では、コンセプト・ノード204は、1または複数のウェブ・ページに対応してもよい。

0034

特定の実施形態では、ソーシャル・グラフ200内のノードは、ウェブ・ページを表しても、ウェブ・ページによって表されてもよい(「プロフィール・ページ」と呼ばれる)。プロフィール・ページは、ソーシャル・ネットワーキング・システム160によってホストされ、またはそこからアクセス可能であってもよい。また、プロフィール・ページは、サードパーティ・システム170に関連付けられているサードパーティウェブサイト上でホストされてもよい。限定するものとしてではなく一例として、特定の外部ウェブ・ページに対応するプロフィール・ページは、その特定の外部ウェブ・ページであってもよく、プロフィール・ページが、特定のコンセプト・ノード204に対応してもよい。プロフィール・ページは、他のユーザのすべてまたは選択されたサブセットによって閲覧可能であってもよい。限定するものとしてではなく一例として、ユーザ・ノード202は、対応するユーザがコンテンツを追加し、宣言をし、または他の方法で自分を表現する、対応するユーザプロフィールページを有してもよい。限定するものとしてではなく別の例として、コンセプト・ノード204は、1または複数のユーザがコンセプト・ノード204に対応するコンセプトに特に関連してコンテンツを追加し、宣言をし、またはユーザ自身を表現する、対応するコンセプトプロフィールページを有してもよい。

0035

特定の実施形態では、コンセプト・ノード204は、サードパーティ・システム170によってホストされるサードパーティウェブページまたはリソースを表す。サードパーティウェブページまたはリソースは、要素の中でもとりわけ、コンテンツ、選択可能なアイコンもしくは他のアイコン、またはアクションもしくはアクティビティを表す(たとえば、JavaScript(登録商標)、AJAX、またはPHPコードにより実装される)他の対話可能なオブジェクトを含んでもよい。限定するものとしてではなく一例として、サードパーティウェブページは、「いいね」、「チェックイン」、「食べる」、「推奨する」、または別の好適なアクションまたはアクティビティなど、選択可能なアイコンを含んでもよい。サードパーティウェブページを閲覧するユーザは、アイコンの1つ(たとえば、「食べる」)を選択することによって、アクションを行う。これによって、クライアント・システム130は、ユーザのアクションを示すメッセージをソーシャル・ネットワーキング・システム160へ送信する。ソーシャル・ネットワーキング・システム160は、メッセージに応答して、ユーザに対応するユーザ・ノード202とサードパーティウェブページまたはリソースに対応するコンセプト・ノード204との間にエッジ(たとえば、「食べる」エッジ)を作成し、エッジ206を1または複数のデータ・ストア内に記憶する。

0036

特定の実施形態では、ソーシャル・グラフ200内の1対のノードが、1または複数のエッジ206によって互いに接続されてもよい。1対のノードを接続するエッジ206は、その対のノード間の関係を表す。特定の実施形態では、エッジ206は、1対のノード間の関係に対応する1または複数のデータ・オブジェクトまたは属性を含み、または表してもよい。限定するものとしてではなく一例として、第1のユーザは、第2のユーザが第1のユーザの「友達」であることを示してもよい。この示したことに応答して、ソーシャル・ネットワーキング・システム160は、「友達要求」を第2のユーザに送信してもよい。第2のユーザが「友達要求」を確認した場合、ソーシャル・ネットワーキング・システム160は、ソーシャル・グラフ200内で第1のユーザのユーザ・ノード202を第2のユーザのユーザ・ノード202に接続するエッジ206を作成し、エッジ206をソーシャル・グラフ情報としてデータ・ストア164の1または複数に記憶してもよい。図2の例では、ソーシャル・グラフ200は、ユーザ「A」とユーザ「B」とのユーザ・ノード202間の友達関係を示すエッジ206と、ユーザ「C」とユーザ「B」とのユーザ・ノード202間の友達関係を示すエッジとを含む。本開示は特定のユーザ・ノード202を接続する特定の属性を有する特定のエッジ206について記載し示しているが、本開示は、ユーザ・ノード202を接続する任意の好適な属性を有する任意の好適なエッジ206を企図する。限定するものとしてではなく一例として、エッジ206は、友達関係、家族関係仕事関係もしくは雇用関係、ファン関係、フォロワー関係、ビジタ関係、加入者関係主従関係相互的関係、非相互的関係、別の好適なタイプの関係、または2以上のそのような関係を表してもよい。さらに、本開示は一般にノードを接続されているものとして記載しているが、本開示は、ユーザまたはコンセプトも接続されているものとして記載している。本明細書では、接続されているユーザまたはコンセプトへの言及は、適切な場合、ソーシャル・グラフ200内で1または複数のエッジ206によって接続されているユーザまたはコンセプトに対応するノードに及ぶ。

0037

特定の実施形態では、ユーザ・ノード202とコンセプト・ノード204との間のエッジ206は、コンセプト・ノード204に関連付けられているコンセプトに向かってユーザ・ノード202に関連付けられているユーザによって行われる特定のアクションまたはアクティビティを表してもよい。限定するものとしてではなく一例として、図2に示されているように、ユーザは、コンセプトに対して「いいね」と表明することができ、コンセプトに「通った」、コンセプトを「プレイした」、「聴いた」、「調理した」、コンセプトに「勤務した」、またはコンセプトを「見た」のであり、コンセプトのそれぞれは、エッジタイプまたはサブタイプに対応する。コンセプト・ノード204に対応するコンセプトプロフィールページは、たとえば、選択可能な「チェックイン」アイコン(たとえば、クリッカ可能な「チェックイン」アイコン)または選択可能な「お気に入りに追加」アイコンを含んでもよい。同様に、ユーザがこれらのアイコンをクリックした後、ソーシャル・ネットワーキング・システム160は、それぞれのアクションに対応するユーザのアクションに応答して「お気に入り」エッジ、または「チェックイン」エッジを作成する。限定するものとしてではなく別の例として、ユーザ(ユーザ「C」)は、特定のアプリケーション(オンラインミュージックアプリケーションであるSPOTIFY)を使用して特定の楽曲(「イマジン」)を聴く。この場合には、ソーシャル・ネットワーキング・システム160は、ユーザに対応するユーザ・ノード202と楽曲およびアプリケーションに対応するコンセプト・ノード204との間に「聴いた」エッジ206および「使用した」エッジ(図2に図示)を作成し、ユーザがその楽曲を聞き、そのアプリケーションを使用したことを示す。さらに、ソーシャル・ネットワーキング・システム160は、楽曲およびアプリケーションに対応するコンセプト・ノード204間に「プレイした」エッジ206(図2に図示)を作成し、特定の楽曲が特定のアプリケーションによってプレイされたことを示す。この場合には、「プレイした」エッジ206は、外部アプリケーション(SPOTIFY)によって外部オーディオファイル(楽曲「イマジン」)に対して行われたアクションに対応する。本開示は、ユーザ・ノード202とコンセプト・ノード204とを接続する特定の属性を有する特定のエッジ206について記載しているが、本開示は、ユーザ・ノード202とコンセプト・ノード204とを接続する任意の好適な属性を有する任意の好適なエッジ206を企図する。さらに、本開示は、ユーザ・ノード202とコンセプト・ノード204の間の単一の関係を表すエッジについて記載しているが、本開示は、ユーザ・ノード202とコンセプト・ノード204との間の1または複数の関係を表すエッジを企図する。限定するものとしてではなく一例として、エッジ206は、ユーザが「いいね」と表明したこと、および特定のコンセプトを使用したことの両方を表してもよい。あるいは、別のエッジ206が、ユーザ・ノード202とコンセプト・ノード204(図2に示されているように、ユーザ「E」に関するユーザ・ノード202と「SPOTIFY」に関するコンセプト・ノード204)との間の関係の各タイプ(または単一の関係の複数)を表してもよい。

0038

特定の実施形態では、ソーシャル・ネットワーキング・システム160は、ソーシャル・グラフ200内でユーザ・ノード202とコンセプト・ノード204との間にエッジ206を作成する。限定するものとしてではなく一例として、(たとえば、ウェブブラウザまたはユーザのクライアント・システム130によってホストされる専用アプリケーションを使用することによってなど)コンセプトプロフィールページを閲覧するユーザは、「いいね」アイコンをクリックまたは選択することによって、ユーザがコンセプト・ノード204によって表されたコンセプトに対して「いいね」と表明することを示す。これによって、ユーザのクライアント・システム130は、コンセプトプロフィールページに関連付けられているコンセプトに対してユーザが「いいね」と表明することを示すメッセージをソーシャル・ネットワーキング・システム160へ送信する。ソーシャル・ネットワーキング・システム160は、そのメッセージに応答して、ユーザとコンセプト・ノード204との間の「いいね」エッジ206によって示されているように、ユーザに関連付けられているユーザ・ノード202とコンセプト・ノード204との間にエッジ206を作成してもよい。特定の実施形態では、ソーシャル・ネットワーキング・システム160は、エッジ206を1または複数のデータ・ストア内に記憶してもよい。特定の実施形態では、エッジ206は、特定のユーザ・アクションに応答してソーシャル・ネットワーキング・システム160によって自動的に形成されてもよい。限定するものとしてではなく一例として、第1のユーザが写真をアップロードし、映画を見たか、または楽曲を聴いた場合、エッジ206は、第1のユーザに対応するユーザ・ノード202とそれらのコンセプトに対応するコンセプト・ノード204との間に形成されてもよい。本開示は、特定のエッジ206を特定の方法で形成することについて記載しているが、本開示は、任意の好適なエッジ206を任意の好適な方法で形成することを企図する。

0039

特定の実施形態において、ソーシャル・ネットワーキング・システム160は、オブジェクト(例えば、ユーザ、概念、または、ユーザもしくは概念に対して関連付けられたクライアント・システム130)の地理的位置(以下、「位置」ともいう)を決定し得る。オブジェクトの位置は、番地(例えば、「ウィロー・ロード 1601」)、地理的座標のセット(例えば、緯度および経度)、別の位置もしくはオブジェクトへの参照(例えば、「鉄道の隣の喫茶店」)、地図タイル(map tile)への参照(例えば、「地図タイル312」)として、または別の適切な識別子を使用して、識別され、記憶される。特定の実施形態において、オブジェクトの位置は、オンライン・ソーシャル・ネットワークのユーザによって提供される。限定としてではなく例として、ユーザは、自身の位置を、その位置に対してチェックインすることによって、または、さもなければ、自身の位置の標識もしくは識別を他の方法で提供することによって入力し得る。限定としてではなく別の例として、ユーザは、概念(例えば、場所または会場)の位置を、その概念についてのプロフィール・ページにアクセスし、その概念の位置情報(例えば、番地)を打ち込むことによって入力してもよい。

0040

特定の実施形態において、セルラ、Wi−Fi、全地球測位システム(GPS)、または他の適切な機能を備えたクライアント・システム130の位置は、地理測位信号を用いて識別される。限定としてではなく例として、クライアント・システム130は、システムのジオロケーション(geo-location)機能性を促進し得る1つまたは複数のセンサを含む。1つまたは複数のセンサ・デバイスを有するクライアント・システム130によるセンサ入力の処理(例えば、GPSセンサ信号を処理し、デバイスのグラフィカル・ユーザ・インターフェース内に、GPSセンサ信号に対応する位置の地図を表示すること)は、ハードウェア、ソフトウェア、および/またはファームウェア(もしくはデバイス・ドライバ)の組み合わせによって実装される。地理的測位信号は、携帯電話基地局三角測量、Wi−Fi測位、またはGPS測位によって取得される。特定の実施形態において、インターネットにより接続されたコンピュータの地理的位置は、そのコンピュータのIPアドレスによって識別される。クライアント・システム130は、デバイスの地理的位置データを組み込む付加的な機能性、例えば、運転方向を提供すること、現在の位置の地図を表示すること、または、レストラン、ガソリンスタンド、公園等など、すぐ近くの関心地点の情報を提供することなども有し得る。限定としてではなく例として、クライアント・システム130上のウェブ・ブラウザ・アプリケーションは、GPSセンサからのGPS信号判断するデバイス・ドライバによって取得されたGPS位置を含む地図を生成するマッピングライブラリに対して(例えば、関数呼び出しを介して)アクセスし、その地図をウェブ・ブラウザ・アプリケーションのグラフィカル・ユーザ・インターフェース内に表示してもよい。特定の実施形態において、ユーザの位置は、ユーザに対して関連付けられた検索履歴から決定される。限定としてではなく例として、特定のユーザが、特定の位置におけるオブジェクトについて過去にクエリを行っていた場合、ソーシャル・ネットワーキング・システム160(または検索エンジン・システム170)は、ユーザがその特定の位置に今もなお存在すると仮定し得る。本開示は、オブジェクトの位置を特定の手法で決定することを説明するが、本開示は、オブジェクトの位置を任意の適切な手法で決定することを予期する。

0041

特定の実施形態において、ソーシャル・ネットワーキング・システム160は、位置または場所に関連する情報のデータベースを維持し得る。ソーシャル・ネットワーキング・システム160は、特定の位置または場所についてのメタ情報、例えば、位置の写真、広告、ユーザ・レビューコメント、「チェックイン」アクティビティ・データ、「いいね」アクティビティ・データ、営業時間、または、位置に関連する他の適切な情報なども維持し得る。特定の実施形態において、位置または場所は、ソーシャル・グラフ200内の概念ノード204に対応し得る。ソーシャル・ネットワーキング・システム160は、ユーザがクライアント・システム130によってホストされるクライアント・アプリケーション(例えば、ウェブ・ブラウザまたは他の適切なアプリケーション)を使用して、位置または場所に関する情報にアクセスすることを可能にし得る。限定としてではなく例として、ソーシャル・ネットワーキング・システム160は、位置または場所についての情報を要求するユーザに対して、ウェブページ(または、他の構造化ドキュメント)を供給し得る。ユーザ・プロフィールおよび位置情報に加えて、システムは、ユーザについての他の情報を追跡し、または維持し得る。限定としてではなく例として、ソーシャル・ネットワーキング・システム160は、ユーザの位置を記憶する1つまたは複数の位置ベースのサービスを含む、ジオ・ソーシャル・ネットワーキング(geo-social-networking)機能性をサポートし得る。限定としてではなく例として、ユーザは、ユーザのクライアント・システム130によってホストされる専用クライアント・アプリケーション(または、ブラウザ・クライアントを使用するウェブベースのアプリケーションもしくはネットワークベースのアプリケーション)を使用して、ジオ・ソーシャル・ネットワーキング・システムにアクセスし得る。クライアント・アプリケーションは、クライアント・システム130によってサポートされるGPSまたは他のジオロケーション機能に対して自動的にアクセスし、ユーザの現在の位置をジオ・ソーシャル・ネットワーキング・システムへ報告し得る。また、クライアント・アプリケーションは、ユーザが様々な位置または場所において「チェックインし」、この位置を他のユーザへ通信することを可能にするジオ・ソーシャル・ネットワーキング機能性をサポートし得る。所与の位置または場所に対するチェックインは、ユーザが、ある位置または場所に物理的に位置し、クライアント・システム130を使用しており、その位置または場所におけるユーザの存在を登録するためにジオ・ソーシャル・ネットワーキング・システムにアクセスする場合に発生し得る。ソーシャル・ネットワーキング・システム160は、ユーザの現在の位置データおよび過去の位置データに基づいて、ユーザを位置または場所に自動的にチェックインさせてもよい。特定の実施形態において、ソーシャル・ネットワーキング・システム160は、特定の位置または場所に関する他のタイプの関係、例えば、「いいね」、「ファン(fan)」、「過去の勤務先(worked at)」、「おすすめ」、「参加しました(attended)」、または別の適切なタイプの関係などをユーザが示すことを可能にし得る。特定の実施形態において、「チェックイン」情報および他の関係情報は、ソーシャル・グラフ200内で、ユーザのユーザ・ノード202を位置または場所の概念ノード204に対して接続するエッジ206として表される。

0042

図3は、例示的な地図タイルを有する例示的な地図を例示する。特定の実施形態において、地図は、地理的領域、例えば、全世界またはその一部、建物、キャンパス、公園、または、任意の他の適切な場所もしくは領域などを表すように使用される。地図は、地図タイル(以下、「タイル」ともいう)へ分割される。ここで、各タイルは、地図の特定の地理的領域を表す。したがって、特定の位置または場所は、地図の特定のタイル内に存在し得る。限定としてではなく例として、位置Xは、第1のタイル内に存在し得、位置Yおよび位置Zは、第2のタイル内に存在し得る。特定の実施形態において、タイルベースの地図は、ツリーデータ構造において体系化される。このデータ構造内のルート・ノードは、地図に対応し、このデータ構造内の子ノードは、タイルに対応し得る。ツリー・データ構造は、複数のレベルへ体系化されたタイルを有し得る。ここで、第1のレベルは、ルート・ノード(すなわち、地図)に対応し、後続のレベルは、後続の世代の子ノードに対応する。特定の実施形態において、地図は、複数のレベルのタイルを備え得る。各レベルのタイルは、親ノードが子ノードよりも地図の大きな部分を表した状態で、地図の異なるサイズの部分を表し得る。換言すれば、より高いレベルのタイルは、ツリー・データ構造内で、より高く(すなわち、ルート・ノードに対して近く)なるのに対して、より低いレベルのタイルは、ツリー・データ構造内で、より低くなる。限定としてではなく例として、地図は、レベル1からレベルMとラベリングされるM個のレベルのタイルを備えてもよい。レベル1は、ツリー・データ構造内のルート・ノードに対応する地図(例えば、全世界)を表す単一のタイルを備える。

0043

特定の実施形態において、特定のレベルは、各々がおおよそ同じサイズおよび形状を有する均一なタイルを含んでもよく、または、特定のレベルは、複数のサイズまたは形状を有するタイルを含んでもよい。特定の実施形態において、特定のレベルは、グリッド・パターンに配置された正方形のタイルを含み得る。特定の実施形態において、タイルは、実質的に正方形であってもよく、特定のレベルのタイルは、おおよそ同じサイズを有してもよい。特定の実施形態において、レベルmは、合計22×(m−1)個のタイルを有して、2(m−1)×2(m−1)グリッドのタイルを含んでもよい。限定としてではなく例として、レベル5は、各タイルがおおよそ同じサイズを有する合計256個の正方形状のタイルを有して、16×16グリッドを含み得る。図3の例において、レベル2は、各々が世界地図の1つの象限を表す4個のタイルを含む。特定の実施形態において、地図の特定のレベルにおける各タイルは、一意のタイル識別子(tile identifier)またはタイル識別(tile identification)を有し、一意のタイル識別子またはタイル識別は、タイルIDと称される。図3において、レベル2の4つのタイルは、それぞれタイルID0、1、2、および3を有する。図3におけるレベル3は、16個のタイルを含む4×4グリッドであり、ここで、レベル2からの各タイルは、象限(quadrant)へ分割されて、レベル3における4つの付加的なタイルを形成する。例として、レベル2からのタイル2は、レベル3において、タイルID20、21、22、および23をそれぞれ有する4つのタイルへサブ分割される(subdivided)。レベル4は、64個のタイルを含む8×8グリッドであり、ここで、レベル3からの各タイルは、象限へ分割されて、レベル4における4つの付加的なタイルを形成している。例として、レベル3からのタイル31は、レベル4において、タイルID310、311、312、および313をそれぞれ有する4つのタイルへサブ分割される。あるレベルのタイルを分割して、後続のレベルのより小さなタイルを定義するこの方法は、レベルMに至るまで繰り返される。ツリー・データ構造内のリーフ・ノードは、それ以上サブ分割されないタイルに対応する。したがって、前述の例でいえば、レベルMのタイルが、タイルを表すツリー・データ構造内のリーフ・ノードに対応する。同様に、レベルmにおける第1のタイルに対応する子ノードは、ツリー・データ構造内で、レベルm−1における第2のタイルに対応する親ノードへ接続される。ここで、第1のタイルは、第2のタイル内に位置する。本開示は、あるレベルのタイルを特定の手法で分割して、付加的なタイルを形成することを説明するが、本開示は、タイルを任意の適切な手法で分割して、付加的なタイルを形成することを予期する。さらに、本開示は、特定のタイルを有する特定の地図を説明し、例示するが、本開示は、任意の適切なタイルを有する任意の適切な地図を予期する。

0044

特定の実施形態において、地図内のタイルは、そのタイル内に位置を有する1つまたは複数のオブジェクトまたは場所を含み得る。タイルが特定の地理的領域を表す場合、その地理的領域内に位置を有するオブジェクトまたは場所は、そのタイル内に存在するとみなされる。特定の実施形態において、特定のタイル内に位置を有するオブジェクトまたは場所は、そのタイルに対して関連付けられたものとみなされる。これらのオブジェクトまたは場所は、地図タイルに対応するツリー・データ構造においても表される。この場合、各オブジェクトまたは各場所は、そのオブジェクトまたはその場所を含むタイルを表すリーフ・ノードへ接続されるサブ・リーフ・ノードに対応し得る。本開示は、地図内に位置する特定のオブジェクトまたは場所を有する特定の地図を説明し、例示するが、本開示は、地図内に位置する任意の適切なオブジェクトまたは場所を有する任意の適切な地図を予期する。

0045

特定の実施形態において、場所は、大きな領域、または構造、または1つもしくは複数の大きな領域もしくは1つもしくは複数の構造の組み合わせを指す。限定としてではなく例として、場所は、空港、公園、ショッピング・モール、企業キャンパス、大学キャンパス、スタジアム、博物館、近所、都市、映画館、レストラン、ランドマーク、または任意の他の適切な場所もしくは適切な場所の組み合わせを含み得る。特定の実施形態において、場所は、約10メートル、100メートル、1キロメートル、10キロメートル、または任意の他の適切な距離程度のサイズまたは寸法を有し得る。特定の実施形態において、場所は、その場所の全部または一部が特定の地図タイル内に位置する場合、その特定の地図タイルに対して関連付けられる。特定の実施形態において、場所は、その場所の少なくとも一部が特定の地図タイルの所定の閾値距離内に位置する場合、その特定の地図タイルに対して関連付けられてもよい。特定の実施形態において、特定の場所の複数の部分が複数のタイル内に位置してもよく、この場所は、これらの複数のタイルの各々に対して関連付けられてもよい。特定の実施形態において、特定のタイルは、複数の場所の全部または一部を含んでもよく、この特定のタイルは、これらの複数の場所の各々に対して関連付けられてもよい。限定としてではなく例として、特定のタイルは、レストラン、博物館、および大学キャンパスのうちの全部または一部を含む特定の地理的領域を表してもよく、この特定のタイルは、これらの場所の各々に対して関連付けられてもよい。特定の実施形態において、場所は、1つまたは複数のタイルに対して関連付けられてもよく、タイルは、1つまたは複数の場所に対して関連付けられてもよい。本開示は、特定のタイルに対して関連付けられた特定の場所を説明し、例示したが、本開示は、任意の適切なタイルに対して関連付けられた任意の適切な場所を予期する。

0046

特定の実施形態において、タイルは、サンプル点を含み、またはサンプル点に対して関連付けられ得る。この場合、サンプル点は、ジオロケーション座標、例えば、緯度座標と経度座標の対などに対して関連付けられる。特定の実施形態において、特定のタイルに対して関連付けられたサンプル点は、そのタイルの位置を識別し得る。特定の実施形態において、特定のタイルに対して関連付けられたサンプル点は、中心、縁、角、またはタイル上もしくはタイル内の任意の他の適切な位置に位置付けられる。限定としてではなく例として、サンプル点は、37.485°および−122.148°の緯度および経度の対を有してもよく、サンプル点は、地図タイルID12345を有する特定の地図タイルの中心に対して関連付けられ、かつ、位置してもよい。タイルID12345を有するそのような例示的な地図タイルは、上記のサンプル点に対して関連付けられた位置を有するものとして参照される。本開示は、特定のタイルに対して関連付けられた特定のサンプル点を説明し、例示するが、本開示は、任意の適切なタイルに対して関連付けられた任意の適切なサンプル点を予期する。

0047

図4は、例示的なポリゴン410によって囲まれた例示的な場所400を例示する。特定の実施形態において、場所は、その場所を囲み、包み込み、または包含する領域を定義するポリゴンとしてモデリングされる(modeled)。図4において、場所400は、ポリゴン410としてモデリングされ、ポリゴン410は、6つの直線セグメントを含む。特定の実施形態において、場所を囲むポリゴンは、場所を近接して囲み、または場所の周りに境界を形成するポリゴンを指す。特定の実施形態において、囲むポリゴン410を構成する1本または複数の線は、場所400の外部境界を形成する1本または複数の線または頂点に接触し、重複し、または交差し得る。本開示は、特定の場所および特定の場所を囲む特定のポリゴンを説明し、例示するが、本開示は、任意の適切な場所および任意の適切な場所を囲む任意の適切なポリゴンを予期する。

0048

図5は、例示的なポリゴン410の周りに構築される例示的な境界ボックス500を例示する。特定の実施形態において、境界ボックス500は、正方形状、長方形状、または任意の他の適切な形状を有し、境界ボックス500は、ポリゴン410を包含し、または囲い得る。図5において、破線によって表される境界ボックス500は、正方形状を有する。特定の実施形態において、サンプル点510のグリッドは、境界ボックス500の領域上へ重ね合わせられる。特定の実施形態において、サンプル点510は、N×Nグリッドの等間隔ポイントへ配置される。ここで、Nは、10、20、30、または任意の適切な正の整数である。図5の例において、サンプル点510は、8×8グリッドの64個の等間隔のポイントへ配置されている。特定の実施形態において、上述されたように、各サンプル点510は、ジオロケーション識別子、例えば、緯度および経度の対などに対して関連付けられた位置を表し得る。特定の実施形態において、ポリゴン410外に位置するサンプル点510は破棄され、ポリゴン410内またはポリゴン410の境界上に位置するサンプル点510は保持される。図5においては、ポリゴン410外に位置する28個のサンプル点は破棄され、ポリゴン410内またはポリゴン410の境界上に位置する36個のサンプル点は保持される。限定としてではなく例として、ポリゴン410外に位置するサンプル点510Cは破棄され、ポリゴン410内またはポリゴン410の境界上にそれぞれ位置するサンプル点510Aおよび510Bは保持される。本開示は、特定のポリゴンに関して構築される特定の境界ボックスおよび特定のサンプル点を説明し、例示するが、本開示は、任意の適切なポリゴンに関して構築される任意の適切な境界ボックスおよび任意の適切なサンプル点を予期する。

0049

図6は、図5の例示的なポリゴン410を、例示的な地図タイル600およびサンプル点510と共に例示する。図6において、ポリゴン410外に位置するサンプル点は除去されており、残りのサンプル点510は、ポリゴン410上またはポリゴン410内に位置する36個のサンプル点510である。特定の実施形態において、各サンプル点510は、特定の地図タイル600に対して関連付けられ、各地図タイル600は、一意の地図タイルIDを有する。図6において、各地図タイル600は、地図タイルの中心に位置する関連付けられたサンプル点510を有する。特定の実施形態において、いくつかの地図タイル(例えば、地図タイル600Aなど)は、ポリゴン410内に完全に含まれ、いくつかの地図タイル(例えば、地図タイル600Bなど)は、ポリゴン410内に部分的に含まれる。特定の実施形態において、地図タイルのグループは、場所または場所を表すポリゴンを囲む領域を、集合的に定義する。場所またはポリゴンを囲む領域は、その場所またはポリゴンを包含し、カバーし、または包む込む領域を指し得る。図6における36個のタイル600のグループは、場所400およびポリゴン410を囲む領域を定義する。特定の実施形態において、場所は、その場所を囲む地図タイルのグループの各地図タイルに対して関連付けられる。図6において、場所400は、場所400を囲む36個の地図タイル600に対して関連付けられる。本開示は、特定のサンプル点を有する特定の地図タイルによってカバーされる特定のポリゴンを説明し、例示するが、本開示は、任意の適切なサンプル点を有する任意の適切な地図タイルによってカバーされる任意の適切なポリゴンを予期する。

0050

特定の実施形態において、地図、地理的領域、または場所についての逆索引(inverted index)は、上述されたサンプル点およびタイルのグリッドに少なくとも部分的に基づいて決定される。特定の実施形態において、上述されたサンプル点およびタイルのグリッドに少なくとも部分的に基づいて逆索引を決定することは、場所のポリゴンベースの索引作成と称される。特定の実施形態において、逆索引は、タイルIDと、タイルIDに対して関連付けられた場所またはオブジェクトとを含み得る。逆索引は、レコードまたはエントリへ体系化され、各レコードは、タイルIDを、このタイルIDによって表されるタイルに対して関連付けられた場所の1つまたは複数のオブジェクトIDまたは場所IDと共に含み得る。特定の実施形態において、場所IDは、特定の場所に対して関連付けられた、または特定の場所を識別するために使用される、一意の識別子であり、場所IDは、場所識別子または場所識別と称される。限定としてではなく例として、図4における場所400は、「400」という場所IDを有する公園であり得る。特定の実施形態において、特定のタイルに対して関連付けられた場所は、この特定のタイルの所定の閾値距離内に少なくとも部分的に位置し、またはこの特定のタイルの所定の閾値距離内に位置する場所に対応し得る。限定としてではなく例として、図6のタイル600Aについての逆索引・レコードは、「tile 600A: 400」として表現される。ここで、600Aは、タイルIDであり、400は、タイル600Aに対して関連付けられた場所についての場所IDである。同様に、別の例として、タイル600Bについての逆索引・レコードは、「tile 600B: 400」として表現される。図6において、タイル600Bは、場所400に対して、および、1つまたは複数の他の場所、オブジェクト、または概念に対して、関連付けられる。限定としてではなく例として、タイル600Bは、場所400に対して、ならびに、ID9876を有するレストラン、ID54321を有する店舗、およびID6565を有する別の場所に対して、関連付けられる。別の例として、タイル600Bについての逆索引・レコードは、「tile 600B: 400、9876、54321、6565」として表現される。

0051

図7は、例示的な地図タイル303と、8個の周囲のタイル(300、301、310、312、330、321、320、および302)とを例示する。特定の実施形態において、特定のタイルについての逆索引・レコードは、この特定のタイル内に少なくとも部分的に位置し、または、この特定のタイルに隣接して、もしくはこの特定のタイルの周りに位置する1つもしくは複数のタイル内に少なくとも部分的に位置する1つまたは複数の場所についての場所IDを含み得る。特定の実施形態において、逆索引・レコードは、特定のタイルの所定の閾値距離内に少なくとも部分的に、または特定のタイルの所定の閾値距離内に位置する場所を含み得る。図7において、タイル303についての逆索引・レコードは、タイル303内または8個の周囲のタイルのうちのいずれかの内に少なくとも部分的に位置する場所についての場所IDを含み得る。限定としてではなく例として、場所710の一部がタイル303内に位置し、場所720の一部がタイル320内に位置する場合、タイル303についての逆索引・レコードは、「tile 303: 710、720」として表現される。また、タイル303が、ID7676を有するカフェに対して関連付けられ、タイル300が、ID4545を有する店舗に対して関連付けられる場合、別の例として、タイル303についての逆索引・レコードは、「tile 303: 710、720、7676、4545」として表現される。本開示は、タイルおよび場所についての特定の情報を有する特定のレコードを含む特定の逆索引を説明し、例示するが、本開示は、タイルまたは場所についての任意の適切な情報を有する任意の適切な記録を含む任意の適切な逆索引を予期する。

0052

特定の実施形態において、逆索引は、ユーザの位置の取得に関連して使用される。特定の実施形態において、コンピューティング・システムは、ユーザから、位置の識別を受信し得る。限定としてではなく例として、コンピューティング・システムは、ソーシャル・ネットワーキング・システム160であってもよく、ユーザの位置は、クライアント・システム130によってソーシャル・ネットワーキング・システム160へ送信されてもよく、ユーザの位置の識別は、地理的座標のセット(例えば、緯度および経度の対)を含んでもよい。特定の実施形態において、コンピューティング・システムは、逆索引にアクセスし、ユーザの位置と逆索引に含まれる情報とに基づいて、コンピューティング・システムは、ユーザの位置に対して関連付けられた1つまたは複数の場所、オブジェクト、または地図タイルを識別し得る。限定としてではなく例として、ユーザの位置と逆索引内の情報とに基づいて、コンピューティング・システムは、ユーザが公園などの特定の場所に位置すると決定し得る。限定としてではなく別の例として、ユーザの位置と逆索引内の情報とに基づいて、コンピューティング・システムは、ユーザが1つまたは複数の場所、例えば、公園およびショッピング・モールの近くに位置すると決定し得る。特定の実施形態において、ユーザの位置に基づいて、コンピューティング・システムは、ユーザが位置する地図タイルについてのタイルIDを決定し得る。特定の実施形態において、本システムは、ユーザの地図タイルに隣接して位置し、またはユーザの地図タイルの所定の閾値距離内に位置する地図タイルについての1つまたは複数のタイルIDを決定し得る。本開示は、逆索引がユーザの位置に関連して使用される特定の手法を説明し、例示するが、本開示は、逆索引がユーザの位置に関連して使用される任意の適切な手法を予期する。

0053

特定の実施形態において、場所に対して関連付けられた順索引(forward index)は、上述されたポリゴンおよび境界ボックスの構築に少なくとも部分的に基づいて決定される。特定の実施形態において、上述されたポリゴンおよび境界ボックスの構築に少なくとも部分的に基づいて順索引を決定することは、場所のポリゴンベースの索引作成と称される。特定の実施形態において、逆索引が、タイルIDと、そのタイルに対して関連付けられた場所とを含み得るのに対して、順索引は、場所IDと、その場所に対して関連付けられたタイルとを含み得る。特定の実施形態において、順索引は、特定の場所について生成され、1つもしくは複数のジオロケーション識別子、または、その場所に対して関連付けられた1つもしくは複数のタイルIDを含み得る。限定としてではなく例として、特定の場所についての順索引は、1つまたは複数の緯度および経度の対を含み得る。ここで、各緯度および経度の対は、特定の場所に対して関連付けられたサンプル点に対応する。限定としてではなく別の例として、特定の場所についての順索引は、この特定の場所に対して関連付けられたタイルに対応する1つまたは複数のタイルIDを含み得る。特定の実施形態において、順索引によって場所に対して関連付けられた地図タイルのグループは、この場所を囲む領域を集合的に定義する地図タイルのグループを指し得る。図6において、場所400に対して関連付けられたポリゴン410は、合計36個のタイル600を含み、または部分的に含み、これらの36個のタイル600は、場所400およびポリゴン410を囲む。場所400についての順索引は、図6に例示される36個のサンプル点510の各々に対して関連付けられたジオロケーション識別子(例えば、緯度と経度の対)を含み得る。場所400についての順索引は、図6に例示される36個のタイル600のタイルIDを含み得る。限定としてではなく例として、場所400についての順索引内のエントリは、「place 400: lat−long_1、...、lat−long_n、...、lat−long_36」として表現される。ここで、lat−long_nは、n番目のサンプル点に対応する緯度および経度の対である。限定としてではなく別の例として、場所400についての順索引内のエントリは、「place 400: tileID_1、...、tileID_n、...、tileID_36」として表現される。ここで、tileID_nは、n番目のタイルのタイルIDである。本開示は、特定の場所ID、位置識別子、またはタイルIDを含む特定の順索引を説明し、例示するが、本開示は、任意の適切な場所ID、位置識別子、またはタイルIDを含む任意の適切な順索引を予期する。

0054

特定の実施形態において、逆索引および順索引は、N×Nグリッドのサンプル点を有するポリゴンベースの索引作成に少なくとも部分的に基づいて決定される。特定の実施形態において、順索引および逆索引について使用されるグリッドは、同じ数のサンプル点を有し得る。限定としてではなく例として、順索引および逆索引について使用されるグリッドは、30×30グリッドの900個のサンプル点に基づいてもよい。特定の実施形態において、順索引および逆索引について使用されるグリッドは、異なる数のサンプル点を有し得る。限定としてではなく例として、逆索引について使用されるグリッドは、30×30グリッドの900個のサンプル点に基づいてもよく、順索引について使用されるグリッドは、10×10グリッドの100個のサンプル点に基づいてもよい。本開示は、特定の数のサンプル点を有する特定のグリッドに基づく特定の順索引および逆索引を説明し、例示するが、本開示は、任意の適切な数のサンプル点を有する任意の適切なグリッドに基づく任意の適切な順索引および逆索引を予期する。

0055

図8は、図4の例示的な場所400および例示的なポリゴン410、ならびに例示的な地図タイル600を例示する。図8において、ポリゴン410は、場所400を表し、5つの地図タイル600V、600W、600X、タイル600Y、および600Zによって囲まれている。場所400は、これらの5つの地図タイルに対して関連付けられており、各地図タイル600は、その地図タイルの位置識別子を表すサンプル点510に対して関連付けられる。特定の実施形態において、場所400についての順索引エントリまたは順索引レコードは、5つのサンプル点510V〜510Z(例えば、各サンプル点についての緯度および経度の対)または5つの地図タイル600V〜600Z(例えば、各地図タイルについてのタイルID)に関連する情報を含み得る。限定としてではなく例として、図8の場所400についての順索引内のエントリは、場所400に対して関連付けられた各地図タイルについてのタイルIDを含んでもよく、「place 400: 600V、600W、600X、600Y、600Z」として表現される。限定としてではなく別の例として、場所400についての順索引レコードは、場所400に対して関連付けられた5つのサンプル点510V〜510Zについての位置識別子(例えば、緯度および経度の対)を含んでもよく、「place 400: lat−long_510V、lat−long_510W、lat−long_510X、lat−long_510Y、lat−long_510Z」として表現される。本開示は、特定のポリゴンおよび特定の地図タイルに基づく特定の順索引を説明し、例示するが、本開示は、任意の適切なポリゴンおよび任意の適切な地図タイルに基づく任意の適切な順索引を予期する。

0056

特定の実施形態において、場所と、この場所に対して関連付けられたサンプル点とについての情報を含み得る順索引は、どこにユーザが位置するか、ユーザが特定の場所内もしくは特定の場所の近くに位置するか、1つもしくは複数のどの場所がユーザのすぐ近くに存在するか、または、ユーザから1つもしくは複数の場所への距離を決定するように使用される。特定の実施形態において、どこにユーザが位置するか、ユーザが特定の場所内もしくは特定の場所の近くに位置するか、1つもしくは複数のどの場所がユーザのすぐ近くに存在するか、または、ユーザから1つもしくは複数の場所への距離の決定は、コンピューティング・システムによって、位置の識別(例えば、クライアント・システム130から受信される緯度および経度の対)に少なくとも部分的に基づいて実行される。特定の実施形態において、コンピューティング・システムは、ユーザ800Aと、場所400に対して関連付けられた各サンプル点510または各地図タイル600との間の距離を決定することによって、ユーザ800Aから場所400までの距離を決定し得る。特定の実施形態において、ユーザ800Aと場所400との間の距離は、ユーザ800Aと場所400に対して関連付けられた各サンプル点510または各地図タイル600との間の距離の最小値とし得る。図8において、ユーザ800Aは、場所400の近くに位置しており、ユーザ800Aとサンプル点510V〜510Zの各々との間のそれぞれの距離810V〜810Zが決定される。ユーザ800Aと場所400との間の距離810は、ユーザ800Aと場所400に対して関連付けられたサンプル点510の各々との間の最小距離である、距離810Zであると決定される。本開示は、ユーザと場所との間の特定の距離を特定のサンプル点または地図タイルに少なくとも部分的に基づいて決定することを説明し、例示するが、本開示は、ユーザと場所との間の任意の適切な距離を任意の適切なサンプル点または地図タイルに少なくとも部分的に基づいて決定することを予期する。

0057

ユーザの位置を決定し、ユーザの位置に対して関連付けられた場所を識別することに関連する従来の技法は、場所(例えば、ゴールデンゲートパーク)を単一のポイント(例えば、緯度座標と経度座標の単一の対)としてモデリングし得る。しかしながら、場所を単一のポイントとしてモデリングすることは、ユーザの位置に対して関連付けられた距離、位置、または場所の不正確な決定または非最適な決定につながり得る。例として、ゴールデン・ゲート・パークを単一の緯度および経度の対に対して関連付けられた場所としてモデリングする従来の技法は、ユーザが実際にはこのパークから通りを隔てて位置し、または、このパークの30.48メートル(100フィート)以内に位置し得る場合に、ユーザがこのパークから約1609メートル(1マイル)に位置すると決定することがある。本開示の特定の実施形態は、場所をポリゴンとしてモデリングすることによって、従来の技法の欠点のうちの一部に対処する。ここで、各場所は、その結果、単一のサンプル点よりはむしろ、複数のサンプル点に対して関連付けられる。

0058

特定の実施形態において、コンピューティング・システムは、順索引にアクセスし、どこにユーザが位置するか、または、ユーザが特定の場所内もしくは特定の場所の近くに位置するかを決定し得る。限定ではなく例として、ユーザ800Aのクライアント・システム130によってソーシャル・ネットワーキング・システム160へ送信される位置識別子に基づいて、ソーシャル・ネットワーキング・システム160は、ユーザ800Aが場所400の所定の閾値距離の近く、または場所400の所定の閾値距離内に位置すると決定し得る。特定の実施形態において、コンピューティング・システムは、ユーザが特定のタイル内に位置すると決定してもよく、その特定のタイルが、特定の場所に対して関連付けられている場合、コンピューティング・システムは、ユーザがその特定の場所またはその特定の場所内に位置すると決定してもよい。限定としてではなく例として、図8におけるユーザ800Bからのクエリに応じて、コンピューティング・システムは、場所400に対して関連付けられたタイル600V内にユーザ800Bが位置すると決定し得る。このクエリに応じて、コンピューティング・システムは、ユーザ800Bが場所400に位置することを示す応答を返し得る。限定としてではなく別の例として、図8におけるユーザ800Cからのクエリに応じて、コンピューティング・システムは、場所400に対して関連付けられたタイル600W内にユーザ800Cが位置すると決定し得る。このクエリに応じて、コンピューティング・システムは、ユーザ800Cが場所400に位置することを示す応答を返し得る。また、このクエリに応じて、コンピューティング・システムは、タイル600W内または1つもしくは複数の隣接するタイル(例えば、タイル600Vもしくはタイル600X)内に位置する、1つまたは複数のオブジェクト(例えば、書店または喫茶店)を示す応答を返し得る。本開示は、特定の位置または順索引に基づいて決定された特定の距離または場所を説明し、例示するが、本開示は、任意の適切な位置または順索引に基づいて決定された任意の適切な距離または場所を予期する。

0059

特定の実施形態において、ユーザからのクエリに応じて、コンピューティング・システムは、1つまたは複数の場所またはオブジェクトに対して関連付けられた、1つまたは複数のスコアを決定し得る。特定の実施形態において、場所またはオブジェクトは、ユーザの位置に、ユーザの所定の閾値距離内に、またはユーザのタイルに対して関連付けられたタイル内もしくはユーザのタイルに隣接するタイル内に位置し得る。特定の実施形態において、場所またはオブジェクトのスコアは、順索引内の情報、逆索引内の情報、ユーザの位置、または、ユーザから場所もしくはオブジェクトまでの距離に少なくとも部分的に基づき得る。特定の実施形態において、場所のスコアは、その場所からのユーザの距離に少なくとも部分的に基づいてもよく、ユーザがその場所に近いほど、そのスコアは高くなり得る。限定としてではなく例として、ユーザからのクエリに応じて、コンピューティング・システムは、ユーザが場所400Aからは約50メートル、場所400Bからは約100メートルに位置すると決定してもよく、これらの決定された距離に基づいて、コンピューティング・システムは、ユーザに対して、場所400Aが0.9というスコアを有し、場所400Bが0.7というスコアを有することを示す応答を送信し得る。特定の実施形態において、1つまたは複数の場所またはオブジェクトの1つまたは複数のスコアは、ユーザまたは1つもしくは複数の場所もしくはオブジェクトに対して関連付けられたソーシャル・グラフ情報に少なくとも部分的に基づき得る。本開示は、特定のユーザ情報に関して決定される特定のスコアを説明するが、本開示は、任意の適切なユーザ情報に関して決定される任意の適切なスコアを予期する。

0060

特定の実施形態において、クライアント・システム130のユーザは、特定の主題(例えば、人物、場所、コンテンツ、またはリソース)に関連する情報を、「検索クエリ」と称されることも多い、その主題を説明する短い語句を検索エンジンへ提供することによって検索し得る。検索エンジンは、様々な検索アルゴリズムを使用して、クエリの語句に基づいて検索を行い、検索クエリに最も関連しそうなリソース(例えば、ウェブページ、コンテンツ、または他の情報)を識別する検索結果を生成し得る。検索を行うためには、ユーザは、検索エンジン・システム170によってホストされる検索エンジンに対して、検索クエリを入力し、または送信し得る。応答して、検索エンジンは、検索クエリに関連しそうな1つまたは複数のリソースを識別し、この1つまたは複数のリソースは、その検索クエリについて識別された「検索結果」と集合的に称される。検索結果は、多くの場合、識別されたリソースまたはコンテンツのうちの一部を含む異なるウェブページに対して各リンクが関連付けられた、検索結果ウェブページのリンクのリストの形式でユーザに対して提示される。特定の実施形態において、検索結果における各リンクは、対応するウェブページがどこに位置するか、および、対応するウェブページを取得するためのメカニズムを特定するユニフォーム・リソース・ロケータ(URL)の形式であり得る。その結果、ユーザは、URLリンクをクリックして、対応するウェブページに含まれる特定のリソースをユーザが望むように見ることが可能となり得る。リソースは、検索結果に対するリソースの相対的な関連度に応じてランク付けされ、ユーザに対して提示される。検索結果も、ユーザに対する検索結果の相対的な関連度に応じてランク付けされ、ユーザに対して提示される。換言すれば、検索結果は、例えば、ソーシャル・グラフ情報、ユーザ情報、ユーザの検索履歴もしくはブラウジング履歴、またはユーザに関連する他の適切な情報に基づいて、クエリをするユーザのためにパーソナライズされる。特定の実施形態において、リソースのランク付けは、検索エンジンによって実装されるランク付けアルゴリズムによって決定される。限定としてではなく例として、検索クエリまたはユーザに対して相対的に関連性がより高いリソースは、検索クエリまたはユーザに対して相対的に関連性がより低いリソースよりも、高くランク付けされる。特定の実施形態において、検索エンジンは、その検索をオンライン・ソーシャル・ネットワーク上のリソースおよびコンテンツに限定してもよい。ただし、特定の実施形態において、検索エンジンは、他のソース、例えば、サードパーティ・システム、インターネットもしくはワールド・ワイド・ウェブ、または他の適切なソース上などのリソースも検索し得る。

0061

特定の実施形態において、検索エンジン・システム170は、ユーザから受信された検索クエリに応じて検索結果を生成する場合に、順索引、逆索引、またはユーザに対して関連付けられた位置情報を使用し得る。クライアント・システム130を用いるユーザは、検索クエリを検索エンジン・システム170へ送信し得る。ユーザは、特定の場所、オブジェクト、または場所もしくはオブジェクトのタイプを検索中であり得る。特定の実施形態において、ユーザは、オンライン・ソーシャル・ネットワークのユーザであってもよく、ソーシャル・グラフ200上のソーシャル・グラフ・エンティティとして表される場所、位置、または人物を検索中であり得る。また、クライアント・システム130は、位置情報も検索エンジン・システム170へ送信し得る。ユーザの位置は、検索クエリと共に、または別個に、送信される。ユーザの位置は、地図の特定のタイル内に位置し得る。特定の実施形態において、ユーザは、こうしたサービスに対してオプトイン(opt in)してもよい。このサービスは、クライアント・アプリケーションに、ユーザの位置データをソーシャル・ネットワーキング・システム160または検索エンジン・システム170へ自動的に送信させる。このようにして、検索エンジン・システム170は、クライアント・システム130の位置(および、したがって、ユーザの位置)を追跡し、ユーザの現在の位置に基づいてユーザのためにカスタマイズされた検索結果を提供し得る。次いで、検索エンジン・システム170は、ユーザの検索クエリに対応する場所またはオブジェクトを識別し得る。次いで、識別された場所またはオブジェクトは、クエリに対するそれらの関連性、社会的関連性、ユーザからの距離、他の適切な要因、または、これらの任意の組み合わせに基づいて、スコア付けされ、および/またはランク付けされる。ユーザと同じ地図タイル内または同じ地図タイルの近くの位置を有する場所またはオブジェクトは、より関連性があるとみなされ、したがって、生成される検索結果の品質改善するために、検索エンジン・システム170は、ユーザと同じタイルに位置するオブジェクトを優先的に列挙する検索結果を生成し得る。ユーザの現在のタイル内に利用可能な検索結果が十分に存在しない場合、検索エンジン・システム170は、その検索を近隣のタイルまで、または、ユーザが存在するタイルに関連付けられた親タイルまで拡張し得る。ユーザの現在のタイル(および、場合により、近隣のタイル/親タイル)における結果を最初に検索することによって、検索エンジン・システム170は、生成される検索結果の効率と品質との両方を改善し得る。これは、検索情報の効率的な索引作成も可能にし得る。本開示は、特定の手法でタイル地図および位置情報に基づく特定の検索結果を生成することを説明するが、本開示は、任意の適切な手法でタイル地図および位置情報に基づく任意の適切な検索結果を生成することを予期する。

0062

特定の実施形態において、検索エンジン・システム170は、クライアント・システム130からのクエリに対応する、1つまたは複数の場所またはオブジェクトを識別し得る。上述されたように、クエリをするユーザは、第1のタイルにおける第1の位置を有し得る。同様に、各場所または各オブジェクトは、(例えば、第1のタイルまたは別のタイルにおける)第2の位置を有し得る。人物などの一定のオブジェクトの場合には、オブジェクトの位置が固定されないことがあることに留意されたい。換言すれば、オブジェクトは、可動であってもよく、そのオブジェクトの位置は、前述されたように、第1のユーザに対してアナログ的に決定される。限定としてではなく例として、第1のユーザは、「最も近い公園を教えて」というクエリを入力し得る。検索エンジン・システム170は、(例えば、1つまたは複数のnグラムを識別し、対応するオブジェクトおよび検索フィルタを識別することなどによって)このテキストクエリ構文解析し、第1のタイル内に位置する公園を検索し得る。検索エンジン・システム170は、第1のタイル内で十分な数の場所またはオブジェクトを識別することができない場合、検索エンジン・システム170は、その検索を近隣のタイルまで、または第1のタイルの親タイルまで拡張し、それらのタイル内の場所またはオブジェクトを識別し得る。特定の実施形態において、検索エンジン・システム170は、第1の位置から各第2の位置までの距離を計算し、第1のユーザから閾値距離未満の距離を有する場所またはオブジェクトのみを識別し得る。したがって、一定の距離を超える場所またはオブジェクトは、それらがどのタイルに位置するかに関わらず、検索結果から除去される。特定の実施形態において、検索エンジン・システム170は、次いで、識別された場所またはオブジェクトの各々を、クエリまたはユーザに対するそれらの関連性に基づいて、スコア付けし得る。本開示は、特定の検索クエリに対応する特定の場所またはオブジェクトを識別することを説明するが、本開示は、任意の適切な検索クエリに対応する任意の適切な場所またはオブジェクトを識別することを予期する。

0063

特定の実施形態において、検索エンジン・システム170は、検索クエリに対応する識別された各場所またはオブジェクトのスコアを、第1の位置(例えば、クエリをするユーザの位置、またはユーザのクライアント・システム130)からのその場所またはオブジェクトの距離に基づいて決定し得る。特定の場所またはオブジェクトを検索する場合、ユーザは、ユーザの現在の位置に対して、より近い場所またはオブジェクトの位置を突き止めることに、一層の興味を持ち得る。したがって、ユーザに対してより近位にある場所またはオブジェクトは、ユーザからより離れた場所またはオブジェクトよりも、高くスコア付けされる。本開示は、特定の手法で場所またはオブジェクトのスコアを決定することを説明するが、本開示は、任意の適切な手法で場所またはオブジェクトのスコアを決定することを予期する。

0064

特定の実施形態において、検索エンジン・システム170は、識別された場所またはオブジェクトのスコアを、その場所またはオブジェクトに対応するソーシャル・グラフ情報に基づいて決定し得る。特定の場所またはオブジェクトは、ソーシャル・グラフ・エンティティ、例えば、ユーザ・ノード202または概念ノード204などに対応し得る。したがって、検索クエリに応じて、検索エンジン・システム170は、ソーシャル・ネットワーキング・システム160上のソーシャル・グラフ200にアクセスし得る。次いで、検索エンジン・システム170は、第1のクエリに対応するユーザ・ノード202または概念ノード204を識別し得る。次いで、検索エンジン・システム170は、識別された場所またはオブジェクトのスコアを、それらの場所またはオブジェクトに対応するソーシャル・グラフ情報に基づいて決定し得る。限定としてではなく例として、検索クエリに対応する場所またはオブジェクトのスコアsを決定する場合、スコアの計算は、ソーシャル・グラフ情報も考慮し得る。したがって、特定のソーシャル・グラフ・エンティティkについて決定されるスコアは、特定の検索クエリX、およびソーシャル・グラフ情報Gが与えられると、s=(k|X,G)として計算される。特定の実施形態において、検索エンジン・システム170は、第1のユーザの社会的つながりのうちの1人または複数の場所またはオブジェクトに対する近接性に基づいて、場所またはオブジェクトをスコア付けし得る。限定ではなく例として、検索エンジン・システム170は、ソーシャル・ネットワーキング・システム160と、ソーシャル・ネットワーキング・システム160の他のユーザの位置データを含む位置データベースとにアクセスし、(例えば、チェックイン・データ、GPS座標、または他の位置データに基づいて)第1のユーザの第1級の友達のうちの1人または複数が現在最も近くに存在する、第1のユーザからの検索クエリに対応する1つまたは複数の場所またはオブジェクトを識別し得る。次いで、検索エンジン・システム170は、場所またはオブジェクトが第1のユーザの友達の近くに存在する場合には、場所またはオブジェクトをより高くスコア付けし、場所またはオブジェクトが第1のユーザの友達から離れて存在する場合には、場所またはオブジェクトをより低くスコア付けし得る。限定としてではなく別の例として、検索エンジン・システム170は、場所またはオブジェクトに対して関連付けられた、第1のユーザの1人または複数の社会的つながり、例えば、その場所もしくはオブジェクトに対して過去に「チェックイン」した社会的つながり、その場所もしくはオブジェクトに関してレビューし、もしくはコメントし、または、その場所もしくはオブジェクトと別の方法でインタラクションした社会的つながりなどを識別し得る。次いで、検索エンジン・システム170は、第1のユーザの社会的つながりに対して、より低く関連付けられた場所またはオブジェクトよりも、第1のユーザの社会的つながりに対して、より密接に関連付けられた場所またはオブジェクトを、より高くスコア付けし得る。特定の実施形態において、識別された場所またはオブジェクトのスコアは、第1のユーザのユーザ・ノード202と、識別された場所またはオブジェクトに対応する特定のソーシャル・グラフ・エンティティとの間の分離度に基づき得る。クエリをするユーザに対してソーシャル・グラフ200内でより近くに存在するソーシャル・グラフ・エンティティに対応する(すなわち、その要素と第1のユーザのユーザ・ノード202との間の分離度がより低い)場所またはオブジェクトは、ユーザからより遠くに存在する(すなわち、分離度がより高い)ソーシャル・グラフ・エンティティよりも、高いスコアを与えられる。本開示は、特定の手法で特定のソーシャル・グラフ情報に基づいて特定の場所またはオブジェクトのスコアを決定することを説明するが、本開示は、任意の適切な手法で任意の適切なソーシャル・グラフ情報に基づいて任意の適切な場所またはオブジェクトのスコアを決定することを予期する。

0065

特定の実施形態において、検索エンジン・システム170は、識別された場所またはオブジェクトのスコアを、第1のユーザ(すなわち、クエリをするユーザ)に対して関連付けられた検索履歴に基づいて決定し得る。第1のユーザが過去にアクセスした特定のウェブページまたはソーシャル・グラフ・エンティティに対応する場所またはオブジェクトは、ユーザのクエリの対象となる可能性が高くなり得る。同様に、第1のユーザが過去に訪れたことがある位置を有する場所またはオブジェクトは、ユーザのクエリの対象となる可能性が高くなり得る。したがって、これらの場所またはオブジェクトは、より高いスコアを与えられる。限定としてではなく例として、第1のユーザが、「オールド・プロ」バーについての概念プロフィール・ページを過去に訪問したことがある場合において、「ビール」についてのクエリに応じて、場所またはオブジェクトのスコアを決定するとき、検索エンジン・システム170は、「オールド・プロ」というバーに対応するウェブページが相対的に高いスコアを有すると決定し得る。なぜなら、クエリをするユーザは、その会場についてのページに対して過去にアクセスしたことがあるためである。本開示は、特定の手法で特定の検索履歴情報に基づいて特定の場所またはオブジェクトのスコアを決定することを説明するが、本開示は、任意の適切な手法で任意の適切な検索履歴情報に基づいて任意の適切な場所またはオブジェクトのスコアを決定することを予期する。

0066

特定の実施形態において、検索エンジン・システム170は、識別された場所またはオブジェクトのうちの1つまたは複数への参照を含む検索結果を生成し得る。この参照は、例えば、場所もしくはオブジェクトの名前および/もしくは説明、場所もしくはオブジェクトの位置およびユーザからのその距離、場所もしくはオブジェクトに対して関連付けられたプロフィール・ページもしくは他のウェブページへのリンク(例えば、URL)、場所もしくはオブジェクトに関連するソーシャル・グラフ情報(例えば、分離度、他のソーシャル・グラフ要素との関連)、場所もしくはオブジェクトに対して関連付けられた他の情報、または、これらの任意の組み合わせを含んでもよい。特定の実施形態において、検索エンジン・システム170は、閾値ランクよりも高いランクを有する識別された場所またはオブジェクトへの参照を含む検索結果のみを生成し得る。閾値ランクは、特定の数の参照が検索結果に含まれるように設定される。限定としてではなく例として、検索エンジン・システム170は、上位R個にランク付けされる場所またはオブジェクトのみへの参照を含む検索結果を生成してもよい。Rの値は、ユーザによって手動で決定されても、または検索エンジン・システム170によって設定されてもよい。また、Rの値は、ユーザのクライアント・システム130上の利用可能なローカル記憶装置のサイズ、検索結果をクライアント・システム130へ送信するのに利用可能な帯域幅、クライアント・システム130の表示画面のサイズに基づいても、または、他の適切な要因に基づいてもよい。特定の実施形態において、検索エンジン・システム170は、場所またはオブジェクトについて決定されたスコアに基づいて、場所またはオブジェクトのランク付けされたリストを生成し得る。より良好な(例えば、より高い)スコアを有する場所またはオブジェクトは、より劣る(例えば、より低い)スコアを有する場所またはオブジェクトよりも、高くランク付けされる。特定の実施形態において、検索エンジン・システム170は、生成された検索結果の特定の割合がタイル地図上で第1のユーザに対して特定の地理的近接性を有する検索結果を生成し得る。限定ではなく例として、検索エンジン・システム170は、検索結果の60%が第1のタイル(すなわち、ユーザの現在のタイル)内に位置する場所もしくはオブジェクトまたは第1のタイルに対して関連付けられた場所もしくはオブジェクトへの参照を含む検索結果、検索結果の30%が第1のタイルの近隣のタイル内に位置する場所またはオブジェクトへの参照を含む検索結果、および、検索結果の10%が第1のタイルの親タイルに位置する場所またはオブジェクトへの参照を含む検索結果を生成してもよい。本開示は、特定の手法で特定の検索結果を生成することを説明するが、本開示は、任意の適切な手法で任意の適切な検索結果を生成することを予期する。

0067

特定の実施形態において、検索エンジン・システム170は、検索クエリが受信されたクライアント・システム130(例えば、クエリをするユーザのコンピューティング・デバイス)へ検索結果を送信し得る。検索結果は、構造化ドキュメント、例えば、ウェブページ、電子メール、または別の適切なドキュメントなどとして送信される。次いで、これらの送信された検索結果は、クライアント・システム130のユーザに対して表示される。限定としてではなく例として、検索エンジン・システム170は、ユーザの位置と、検索結果において参照される様々な場所またはオブジェクトの位置とを表示する地図を含むウェブページを、クライアント・システム130へ送信してもよい。限定としてではなく別の例として、検索エンジン・システム170は、識別された場所またはオブジェクトへの参照を列挙するドキュメントを、その場所またはオブジェクトについての他の関連情報と共に送信してもよい。特定の実施形態において、検索エンジン・システム170は、検索クエリに応じて、広告または他のスポンサー付きコンテンツもクライアント・システム130へ送信し得る。広告は、検索結果の一部として、または別個に、含まれ得る。広告は、検索結果において参照される場所またはオブジェクトのうちの1つまたは複数に対応し得る。本開示は、特定の手法で特定の検索結果を送信することを説明するが、本開示は、任意の適切な手法で任意の適切な検索結果を送信することを予期する。

0068

図9は、位置に対して関連付けられた1つまたは複数の場所を識別するための例示的な方法900を例示する。本方法は、コンピューティング・デバイスが位置の識別を受信する工程910において開始し得る。工程920において、コンピューティング・デバイスは、複数のレコードを含む逆索引にアクセスし得る。特定の実施形態において、逆索引の各レコードは、地図タイルに対応し、その地図タイルに対応する1つまたは複数の場所を識別し得る。特定の実施形態において、逆索引において識別される場所のうちの少なくとも1つは、複数の地図タイルに対応する複数のレコードにおいて識別される。ここで、複数の地図タイルは、場所を囲む領域を集合的に定義し得る。工程930において、コンピューティング・デバイスは、位置に対して関連付けられた1つまたは複数の場所を逆索引に基づいて識別し、この時点で、本方法は終了し得る。特定の実施形態は、必要に応じて、図9の方法の1つまたは複数の工程を繰り返し得る。本開示は、図9の方法の特定の工程を特定の順序で発生するものとして説明し、例示するが、本開示は、任意の適切な順序で発生する、図9の方法の任意の適切な工程を予期する。さらに、本開示は、図9の方法の特定の工程を含む、位置に対して関連付けられた1つまたは複数の場所を識別するための例示的な方法を説明し、例示するが、本開示は、必要に応じて、図9の方法の工程の全部を含み、一部を含み、または全く含まなくてもよい、任意の適切な工程を含む、位置に対して関連付けられた1つまたは複数の場所を識別するための任意の適切な方法を予期する。さらに、本開示は、図9の方法の特定の工程を実行する特定の構成要素、デバイス、またはシステムを説明し、例示するが、本開示は、図9の方法の任意の適切な工程を実行する任意の適切な構成要素、デバイス、またはシステムの任意の適切な組み合わせを予期する。

0069

図10は、例示的なコンピュータ・システム1000を示す。特定の実施形態では、1または複数のコンピュータ・システム1000は、本明細書に記載され、または示されている1または複数の方法の1または複数のステップを実施する。特定の実施形態では、1または複数のコンピュータ・システム1000は、本明細書に記載され、または示されている機能を提供する。特定の実施形態では、1または複数のコンピュータ・システム1000上で動作するソフトウェアは、本明細書に記載され、または示されている1または複数の方法の1または複数のステップを実施し、または本明細書に記載され、または示されている機能を提供する。特定の実施形態は、1または複数のコンピュータ・システム1000の1または複数の部分を含む。本明細書では、コンピュータ・システムに言及することは、適切な場合、コンピューティング・デバイスを包含してもよく、逆も同様である。さらに、コンピュータ・システムに言及することは、適切な場合、1または複数のコンピュータ・システムを包含してもよい。

0070

この開示は、任意の好適な数のコンピュータ・システム1000を企図する。この開示は、任意の好適な物理形態をとるコンピュータ・システム1000を企図する。限定するものとしてではなく一例として、コンピュータ・システム1000は、組込みコンピュータ・システム、システム・オンチップ(SOC)、シングルボード・コンピュータ・システム(SBC)(たとえば、コンピュータ・オン・モジュール(COM)またはシステム・オン・モジュール(SOM)など)、デスクトップ・コンピュータ・システム、ラップトップもしくはノートブック・コンピュータ・システム、対話キオスクメインフレーム、コンピュータ・システムのメッシュ移動体電話携帯情報端末(PDA)、サーバ、タブレット・コンピュータ・システム、またはこれらの2以上の組合せであってよい。適切な場合、コンピュータ・システム1000は、1または複数のコンピュータ・システム1000を含んでもよく、一元的なものであっても分散型であってもよく、複数のロケーションに跨ってもよく、複数のマシンに跨ってもよく、複数のデータ・センタに跨ってもよく、クラウド内にあってもよく、クラウドは、1または複数のネットワーク内で1または複数のクラウド・コンポーネントを含んでもよい。適切な場合、1または複数のコンピュータ・システム1000は、実質的な空間的または時間的制限なしに、本明細書に記載され、または示されている1または複数の方法の1または複数のステップを実施してもよい。限定するものとしてではなく一例として、1つまたは複数のコンピュータ・システム1000は、リアルタイムで、またはバッチ・モードで、本明細書に記載され、または示されている1または複数の方法の1または複数のステップを実施してもよい。1または複数のコンピュータ・システム1000は、適切な場合、異なる時に、または異なるロケーションで、本明細書に記載され、または示されている1または複数の方法の1または複数のステップを実施してもよい。

0071

特定の実施形態では、コンピュータ・システム1000は、プロセッサ1002、メモリ1004、ストレージ1006、入力/出力(I/O)インターフェース1008、通信インターフェース1010、およびバス1012を含む。この開示は、特定の数の特定の構成要素を特定の構成で有する特定のコンピュータ・システムについて記載し示しているが、この開示は、任意の好適な数の任意の好適な構成要素を任意の好適な構成で有する任意の好適なコンピュータ・システムを企図する。

0072

特定の実施形態では、プロセッサ1002は、コンピュータ・プログラムを構成するものなど命令を実行するためのハードウェアを含む。限定するものとしてではなく一例として、命令を実行するために、プロセッサ1002は、内部レジスタ内部キャッシュ、メモリ1004、またはストレージ1006から命令を取り出し(またはフェッチし)、それらを復号および実行し、次いで、1または複数の結果を内部レジスタ、内部キャッシュ、メモリ1004、またはストレージ1006に書き込む。特定の実施形態では、プロセッサ1002は、データ、命令、またはアドレス用に1または複数の内部キャッシュを含んでもよい。この開示は、適切な場合、任意の好適な数の任意の好適な内部キャッシュを含むプロセッサ1002を企図する。限定するものとしてではなく一例として、プロセッサ1002は、1または複数の命令キャッシュ、1または複数のデータ・キャッシュ、および1または複数の変換索引バッファTLB)を含んでもよい。命令キャッシュ内の命令は、メモリ1004またはストレージ1006内の命令のコピーであってもよく、命令キャッシュは、プロセッサ1002によるこれらの命令の取り出しを高速化する。データ・キャッシュ内のデータは、プロセッサ1002にて実行される命令が操作するための、メモリ1004またはストレージ1006内のデータのコピー、プロセッサ1002で実行される後続の命令によるアクセスための、またはメモリ1004もしくはストレージ1006に書き込むための、プロセッサ1002で実行された以前の命令の結果、あるいは他の好適なデータであってもよい。データ・キャッシュは、プロセッサ1002による読出しまたは書込み動作を高速化する。TLBは、プロセッサ1002のために仮想アドレス変換を高速化する。特定の実施形態では、プロセッサ1002は、データ、命令、またはアドレス用に1または複数の内部レジスタを含む。この開示は、適切な場合、任意の好適な数の任意の好適な内部レジスタを含むプロセッサ1002を企図する。適切な場合、プロセッサ1002は、1または複数の算術論理演算ユニットALU)を含むことができ、マルチコア・プロセッサであってもよく、1または複数のプロセッサ1002を含んでもよい。この開示は、特定のプロセッサについて記載し示しているが、この開示は、任意の好適なプロセッサを企図する。

0073

特定の実施形態では、メモリ1004は、プロセッサ1002が実行するための命令、またはプロセッサ1002が操作するためのデータを記憶するための主記憶装置を含む。限定するものとしてではなく一例として、コンピュータ・システム1000は、ストレージ1006または別のソース(たとえば、別のコンピュータ・システム1000など)からメモリ1004に命令をロードする。次いで、プロセッサ1002は、メモリ1004から内部レジスタまたは内部キャッシュに命令をロードする。命令を実行するために、プロセッサ1002は、内部レジスタまたは内部キャッシュから命令を取り出し、それらを復号する。命令の実行中、または実行後、プロセッサ1002は、1または複数の結果(中間結果であることも最終結果であることもある)を内部レジスタまたは内部キャッシュに書き込む。次いで、プロセッサ1002は、それらの結果の1または複数をメモリ1004に書き込む。特定の実施形態では、プロセッサ1002は、1もしくは複数の内部レジスタもしくは内部キャッシュ内、または(ストレージ1006もしくは他の場所ではなく)メモリ1004内の命令だけを実行し、1もしくは複数の内部レジスタもしくは内部キャッシュ内、または(ストレージ806もしくは他の場所ではなく)メモリ1004内のデータだけを操作する。1または複数のメモリ・バス(それぞれがアドレス・バスとデータ・バスを含むことがある)がプロセッサ1002をメモリ1004に結合してもよい。バス1012は、下記に記載されているように、1または複数のメモリ・バスを含んでもよい。特定の実施形態では、1または複数のメモリ管理ユニット(MMU)が、プロセッサ1002とメモリ1004との間に存在し、プロセッサ1002によって要求されるメモリ1004へのアクセスを容易にする。特定の実施形態では、メモリ1004は、ランダム・アクセス・メモリ(RAM)を含む。このRAMは、適切な場合、揮発性メモリであり得る。適切な場合、このRAMは、ダイナミックRAMDRAM)またはスタティックRAM(SRAM)であってよい。さらに、適切な場合、このRAMは、シングルポート型またはマルチポート型RAMであってよい。この開示は、任意の好適なRAMを企図する。メモリ1004は、適切な場合、1または複数のメモリ1004を含んでもよい。この開示は、特定のメモリについて記載し示しているが、この開示は、任意の好適なメモリを企図する。

0074

特定の実施形態では、ストレージ1006は、データまたは命令用のマス・ストレージを含む。限定するものとしてではなく一例として、ストレージ1006は、ハードディスクドライブ(HDD)、フロッピー(登録商標)ディスク・ドライブ、フラッシュ・メモリ、光ディスク光磁気ディスク磁気テープ、もしくはユニバーサルシリアル・バス(USB)ドライブ、またはこれらの2以上の組合せを含んでもよい。ストレージ1006は、適切な場合、取外し式または非取外し式(または固定)媒体を含んでもよい。ストレージ1006は、適切な場合、コンピュータ・システム1000に対して内部であっても外部であってもよい。特定の実施形態では、ストレージ1006は、不揮発性ソリッドステート・メモリである。特定の実施形態では、ストレージ1006は、読出し専用メモリ(ROM)を含む。適切な場合、このROMは、マスクプログラムドROM、プログラマブルROMPROM)、消去可能PROM(EPROM)、電気的消去可能PROM(EEPROM)、電気的書き換え可能ROMEAROM)、もしくはフラッシュ・メモリ、またはこれらの2以上の組合せであってよい。この開示は、任意の好適な物理形態をとるマス・ストレージ1006を企図する。ストレージ1006は、適切な場合、プロセッサ1002とストレージ1006の間の通信を容易にする1または複数のストレージ制御ユニットを含んでもよい。適切な場合、ストレージ1006は、1または複数のストレージ1006を含んでもよい。この開示は、特定のストレージについて記載し示しているが、この開示は、任意の好適なストレージを企図する。

0075

特定の実施形態では、I/Oインターフェース1008は、コンピュータ・システム1000と1または複数のI/Oデバイスとの間の通信のために1または複数のインターフェースを提供するハードウェア、ソフトウェア、またはその両方を含む。コンピュータ・システム1000は、適切な場合、これらのI/Oデバイスの1または複数を含んでもよい。これらのI/Oデバイスの1または複数は、人とコンピュータ・システム1000の間の通信を可能にする。限定するものとしてではなく一例として、I/Oデバイスは、キーボードキーパッド、マイクロフォン、モニタマウスプリンタ、スキャナ、スピーカ、スチル・カメラ、スタイラス、タブレット、タッチスクリーントラックボールビデオ・カメラ、別の好適なI/Oデバイス、またはこれらの2以上の組合せを含んでもよい。I/Oデバイスは、1または複数のセンサを含んでもよい。この開示は、任意の好適なI/Oデバイス、およびそれらのための任意の好適なI/Oインターフェース1008を企図する。適切な場合、I/Oインターフェース1008は、プロセッサ1002がこれらのI/Oデバイスの1または複数を駆動することを可能にする1または複数のデバイスまたはソフトウェア・ドライバを含む。I/Oインターフェース1008は、適切な場合、1または複数のI/Oインターフェース1008を含んでもよい。この開示は、特定のI/Oインターフェースについて記載し示しているが、この開示は、任意の好適なI/Oインターフェースを企図する。

0076

特定の実施形態では、通信インターフェース1010は、コンピュータ・システム1000と1もしくは複数の他のコンピュータ・システム1000または1もしくは複数のネットワークとの間の通信(たとえば、パケットベースの通信など)のために1または複数のインターフェースを提供するハードウェア、ソフトウェア、またはその両方を含む。限定するものとしてではなく一例として、通信インターフェース1010は、ETHERNET(登録商標)もしくは他の有線ベースのネットワークとの通信のためのインターフェース・コントローラ(NIC)もしくはネットワーク・アダプタ、またはWI−FIネットワークなど無線ネットワークとの通信のための無線NIC(WNIC)もしくは無線アダプタを含んでもよい。この開示は、任意の好適なネットワーク、およびそのための任意の好適な通信インターフェース1010を企図する。限定するものとしてではなく一例として、コンピュータ・システム1000は、アドホック・ネットワーク、パーソナル・エリア・ネットワーク(PAN)、ローカル・エリア・ネットワーク(LAN)、ワイド・エリア・ネットワーク(WAN)、メトロポリタン・エリア・ネットワーク(MAN)、またはインターネットの1もしくは複数の部分、あるいはこれらの2以上の組合せと通信する。これらのネットワークの1または複数のうちの1または複数の部分は、有線であっても無線であってもよい。一例として、コンピュータ・システム1000は、無線PAN(WPAN)(たとえば、BLUETOOTH(登録商標)WPANなど)、WI−FIネットワーク、WI−MAXネットワーク、携帯電話ネットワーク(たとえば、グローバル移動体通信システム(GSM(登録商標))ネットワークなど)、もしくは他の好適な無線ネットワーク、またはこれらの2以上の組合せと通信する。コンピュータ・システム1000は、適切な場合、これらのネットワークのいずれかのための任意の好適な通信インターフェース1010を含んでもよい。通信インターフェース1010は、適切な場合、1または複数の通信インターフェース1010を含んでもよい。この開示は、特定の通信インターフェースについて記載し示しているが、この開示は、任意の好適な通信インターフェースを企図する。

0077

特定の実施形態では、バス1012は、コンピュータ・システム1000の構成要素を互いに結合するハードウェア、ソフトウェア、またはその両方を含む。限定するものとしてではなく一例として、バス1012は、アクセラレィティッド・グラフィックスポート(AGP)もしくは他のグラフィックス・バス、EISA(Enhanced Industry Standard Architecture)バス、フロントサイド・バス(FSB)、HT(HYPERTRANSPORT相互接続ISA(Industry Standard Architecture)バス、インフィニバンド相互接続、LPC(low−pin−count)バス、メモリ・バス、MCA(Micro Channel Architecture)バス、PCI(Peripheral Component Interconnect)バス、PCIエクスプレス(PCIe)バス、SATA(serial advanced technology attachment)バス、VLB(Video Electronics StandardsAssociation local)バス、もしくは別の好適なバス、またはこれらの2以上の組合せを含んでもよい。バス1012は、適切な場合、1または複数のバス1012を含んでもよい。この開示は、特定のバスについて記載し示しているが、この開示は、任意の好適なバスまたは相互接続を企図する。

0078

本明細書では、1または複数の非一時的コンピュータ可読記憶媒体は、適切な場合、1または複数の半導体ベースの、もしくは他の集積回路(IC)(たとえば、フィールドプログラマブル・ゲート・アレイFPGA)または特定用途向けICASIC))、ハード・ディスク・ドライブ(HDD)、ハイブリッド・ハード・ドライブ(HHD)、光ディスク、光ディスク・ドライブ(ODD)、光磁気ディスク、光磁気ドライブ、フロッピー(登録商標)・ディスケット、フロッピー(登録商標)・ディスク・ドライブ(FDD)、磁気テープ、ソリッドステート・ドライブ(SSD)、RAMドライブセキュア・デジタル・カードもしくはセキュア・デジタル・ドライブ、任意の他の好適な非一時的コンピュータ可読記憶媒体、またはこれらの2以上の組合せを含んでもよい。非一時的コンピュータ可読記憶媒体は、適切な場合、揮発性、不揮発性、または揮発性と不揮発性の組合せであってよい。

0079

本明細書では、「または(もしくは)」は、別段明確に示されていない限り、または別段文脈によって示されない限り、包括的(inclusive)であり、排他的なものではない。したがって、本明細書では、「AまたはB」は、別段明確に示されていない限り、または別段文脈によって示されない限り、「A、B、またはその両方」を意味する。さらに、「および」は、別段明確に示されていない限り、または別段文脈によって示されない限り、共同であり、個別的でもある。したがって、本明細書では、「AおよびB」は、別段明確に示されていない限り、または別段文脈によって示されない限り、「AおよびBを共同で、または個別的に」意味する。

0080

この開示の範囲は、当業者であれば理解するであろう、本明細書に記載され、または示されている例示的な実施形態に対する変更、置換変形、代替、および修正すべてを包含する。この開示の範囲は、本明細書に記載され、または示されている例示的な実施形態に限定されない。さらに、この開示は、それぞれの実施形態について、本明細書では、特定の構成要素、要素、機能、動作、またはステップを含むものとして記載し示しているが、これらの実施形態のいずれも、当業者であれば理解するであろう、本明細書のどこかに記載され、または示されている構成要素、要素、機能、動作、またはステップのいずれかの任意の組合せまたは並べ替えを含んでもよい。さらに、添付の特許請求の範囲において、特定の機能を実施するように適合された、するように配置された、することが可能な、するように構成された、することが可能である、するように動作可能である、またはするように動作する装置もしくはシステム、または装置もしくはシステムの構成要素に言及することは、その装置、システム、または構成要素がそのように適合され、配置され、動作可能であり、構成され、可能であり、動作可能であり、動作する限り、それ、またはその特定の機能が作動される、オンにされる、またはロック解除されるか否かにかかわらず、その装置、システム、構成要素を包含する。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する未来の課題

関連する公募課題

ページトップへ

おすすめの成長市場

関連メディア astavision

  • 人工知能

    米国Google社が2015年6月23日に発表した“A Neural Conversational …

  • 画像診断・生体イメージング

    医療の診断において、非侵襲的あるいは低侵襲的な検査方法として、生体組織を可視化するin vivoイメ…

  • CCS(CO2の分離・回収、地下・海底貯留)

    CCS(Carbon dioxide Capture and Storage:二酸化炭素回収・貯蔵技…

ページトップへ

新着 最近公開された関連が強い技術

この技術と関連性が強い人物

この技術と関連する未来の課題

関連する未来の課題一覧

この技術と関連する公募課題

公募課題一覧

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ