(57)【要約】      （修正有）【課題】ソーシャル・グラフおよびソーシャル・ネットワーキング環境における好適な検索を提供する。【解決手段】方法は、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取る工程と、モバイル・クライアント・システムのデータ・ストアからの、オンライン・ソーシャル・ネットワークのソーシャル・グラフにアクセスする工程とを含む。ソーシャル・グラフは、第１のユーザに対応する第１のノードと、オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザに対応するいくつかの第２のノードとを含む。方法はまた、モバイル・クライアント・システムのデータ・ストアからの、文法テンプレートのセットにアクセスする工程を含む。各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンとを含み、各文法テンプレートは、自然言語文字列に基づいている。【選択図】図１１
2018173979.tif 000002
【特許請求の範囲】
【請求項１】
モバイル・クライアント・システムに関連付けられた１つまたは複数のプロセッサによる方法であって、
該モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取る工程と、
該モバイル・クライアント・システムのデータ・ストアからの該オンライン・ソーシャル・ネットワークのソーシャル・グラフの一組のノードにアクセスする工程であって、該ソーシャル・グラフは、複数のノードと、該ノードを接続する複数のエッジと、を含み、該ノードは、
該第１のユーザに対応する第１のノードと、
該オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれ対応する複数の第２のノードと、を含む、前記一組のノードにアクセスする工程と、
該モバイル・クライアント・システムのデータ・ストアからの一組の文法テンプレートにアクセスする工程であって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンと、を含み、該クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含み、各文法テンプレートは、自然言語文字列に基づく、前記一組の文法テンプレートにアクセスする工程と、
該モバイル・クライアント・システムが、該非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する該文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成する工程であって、各構造化クエリは、該１つまたは複数の非終端トークンとマッチした該アクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される該第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照を含む、前記１つまたは複数の構造化クエリを生成する工程と、
該モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを該第１のユーザへ表示する工程と、を備える、方法。
【請求項２】
前記モバイル・クライアント・システムが、前記非構造化テキスト・クエリを構文解析して１つまたは複数のｎ−ｇｒａｍにする工程と、
前記モバイル・クライアント・システムが、前記非終端トークンまたはクエリ・トークンのうちの１つに対応していない該ｎ−ｇｒａｍのうちの１つまたは複数に少なくとも部分的に基づいて、各文法テンプレートに対するコストを計算する工程と、をさらに備える請求項１に記載の方法。
【請求項３】
各非終端トークンおよびクエリ・トークンは、関連付けられた挿入コストを有し、
前記コストを計算する工程は、
１つまたは複数のｎ−ｇｒａｍに対応していない前記非終端トークンまたはクエリ・トークンのそれぞれに関する挿入コストを発生する工程を含む、請求項２に記載の方法。
【請求項４】
前記コストを計算する工程は、
前記モバイル・クライアント・システムが、各非終端トークンの該挿入コストに少なくとも部分的に基づいて、特定のｎ−ｇｒａｍに対応する前記非終端トークンのうちの１つまたは複数から特定の非終端トークンを識別する工程を含む、請求項３に記載の方法。
【請求項５】
前記コストを計算する工程は、
前記モバイル・クライアント・システムが、アクセスされたノードのうちの１つを前記非終端トークンのうちの１つへ関連付ける工程と、
該ｎ−ｇｒａｍのうちの１つに対応していない関連付けられたアクセスされたノードに基づいて、前記非終端トークンおよび該関連付けられたアクセスされたノードに関する挿入コストを発生する工程と、を含む、請求項３に記載の方法。
【請求項６】
前記モバイル・クライアント・システムが、関連付けられた文法テンプレートの計算されたコストに少なくとも部分的に基づいて、前記構造化クエリのうちの１つまたは複数をランク付けする工程をさらに備える請求項３に記載の方法。
【請求項７】
前記コストを計算する工程は、
各文法テンプレートに関連付けられた基本コストを発生する工程を含み、
該基本コストは、各文法テンプレートの基礎である１つまたは複数の検索クエリに関連付けられた人気度測定値に対して反比例関係を有する、請求項３に記載の方法。
【請求項８】
前記人気度測定値は、前記第１のユーザの検索クエリ履歴に少なくとも部分的に基づく、請求項７に記載の方法。
【請求項９】
前記人気度測定値は、前記オンライン・ソーシャル・ネットワークのユーザの検索クエリ履歴に少なくとも部分的に基づく、請求項８に記載の方法。
【請求項１０】
表示された構造化クエリのそれぞれは、閾値コスト値より低い計算されたコストを有する、請求項１に記載の方法。
【請求項１１】
前記モバイル・クライアント・システムが、前記第１のユーザから入力を受け取る工程は、
ユーザが文字列をグラフィカル・ユーザ・インターフェース内に入力すると、該文字列の１つまたは複数の文字を受け取る工程を含む、請求項１に記載の方法。
【請求項１２】
前記モバイル・クライアント・システムが、ユーザが該グラフィカル・ユーザ・インターフェース内に１つまたは複数の後続の文字を入力したときに修正された非構造化テキスト・クエリをマッチングすることにより、前記構造化クエリのうちの１つまたは複数を更新する工程をさらに備える請求項１１に記載の方法。
【請求項１３】
前記一組のノードの各ノードは、閾値より大きい係数を有する、請求項１に記載の方法。
【請求項１４】
前記モバイル・コンピューティング・デバイスが、所定の間隔で、前記オンライン・ソーシャル・ネットワークから、更新された一組の文法テンプレートまたは更新された一組のノードを受け取る工程をさらに備える請求項１に記載の方法。
【請求項１５】
前記第１のユーザからの表示された構造化クエリのうちの１つの選択に応答して、前記モバイル・クライアント・システムが、選択された構造化クエリを前記オンライン・ソーシャル・ネットワークに送る工程をさらに備える請求項１に記載の方法。
【請求項１６】
前記モバイル・クライアント・システムが、選択された構造化クエリが前記オンライン・ソーシャル・ネットワークへ送られたことに応答して、１つまたは複数の検索結果を受け取る工程をさらに備える請求項１５に記載の方法。
【請求項１７】
前記検索結果のそれぞれは、前記複数の第２のノードのうちの特定の第２のノードに対応する、請求項１６に記載の方法。
【請求項１８】
前記一組のノードは、所定の数のノードからなり、
前記一組の文法テンプレートは、所定の数の文法テンプレートからなる、請求項１に記載の方法。
【請求項１９】
ソフトウェアを具現化する１つまたは複数のコンピュータ可読非一時的記憶媒体であって、前記ソフトウェアは、実行されたとき、
モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ること、
該モバイル・クライアント・システムのデータ・ストアからの、該オンライン・ソーシャル・ネットワークのソーシャル・グラフの一組のノードにアクセスすることであって、該ソーシャル・グラフは、複数のノードと、該ノードを接続する複数のエッジと、を含み、該ノードは、
該第１のユーザに対応する第１のノードと、
該オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれ対応する複数の第２のノードと、を含む、前記一組のノードにアクセスすること、
該モバイル・クライアント・システムのデータ・ストアからの、一組の文法テンプレートにアクセスすることであって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンと、を含み、該クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含み、各文法テンプレートは、自然言語文字列に基づく、前記一組の文法テンプレートにアクセスすること、
該モバイル・クライアント・システムによって、該非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する該文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成することであって、各構造化クエリは、該１つまたは複数の非終端トークンにマッチされた該アクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される該第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照を含む、前記１つまたは複数の構造化クエリを生成すること、
該モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを該第１のユーザへ表示すること、を行うように動作可能である、１つまたは複数のコンピュータ可読非一時的記憶媒体。
【請求項２０】
１つまたは複数のプロセッサと、該プロセッサによって実行可能な命令を備える該プロセッサに結合されたメモリと、を備えるモバイル・クライアント・システムであって、該プロセッサは、該命令を実行すると、
該モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ること、
該モバイル・クライアント・システムのデータ・ストアからの、該オンライン・ソーシャル・ネットワークのソーシャル・グラフの一組のノードにアクセスすることであって、該ソーシャル・グラフは、複数のノードと、該ノードを接続する複数のエッジと、を含み、該ノードは、
該第１のユーザに対応する第１のノードと、
該オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれ対応する複数の第２のノードと、を含む、前記一組のノードにアクセスすること、
該モバイル・クライアント・システムのデータ・ストアからの、一組の文法テンプレートにアクセスすることであって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンと、を含み、該クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含み、各文法テンプレートは、自然言語文字列に基づく、前記一組の文法テンプレートにアクセスすること、
該モバイル・クライアント・システムによって、該非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する該文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成することであって、各構造化クエリは、該１つまたは複数の非終端トークンにマッチされた該アクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される該第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照からなる、前記１つまたは複数の構造化クエリを生成すること、
該モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを該第１のユーザへ表示すること、を行うように動作可能である、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は一般に、ソーシャル・グラフ、およびソーシャル・ネットワーキング環境内でオブジェクトを探して検索を実行することに関する。
【背景技術】
【０００２】
ソーシャル・ネットワーキング・システム（ソーシャルネットワーキング・ウェブサイトを含むことができる）は、そのソーシャル・ネットワーキング・システムのユーザ（人または組織など）がそのソーシャル・ネットワーキング・システムと、およびそのソーシャル・ネットワーキング・システムを通じて互いに対話することを可能にすることができる。ソーシャル・ネットワーキング・システムは、ユーザからの入力を用いて、そのユーザに関連付けられているユーザ・プロフィールを作成して、ソーシャル・ネットワーキング・システム内に記憶することができる。ユーザ・プロフィールは、人口統計学的情報、通信チャネル情報、およびユーザの個人的な関心に関する情報を含むことができる。ソーシャル・ネットワーキング・システムは、ユーザからの入力を用いて、そのユーザと、ソーシャル・ネットワーキング・システムのその他のユーザとの関係のレコードを作成および記憶すること、ならびにサービス（たとえば、ウォール投稿、写真共有、イベント編成、メッセージング、ゲーム、または広告）を提供して、ユーザ同士の間における社会的な交流を容易にすることも可能である。
【０００３】
ソーシャル・ネットワーキング・システムは、そのサービスに関連したコンテンツまたはメッセージを、１つまたは複数のネットワークを通じて、ユーザのモバイルまたはその他のコンピューティング・デバイスへ送信することができる。ユーザは、自分のユーザ・プロフィールおよびソーシャル・ネットワーキング・システム内のその他のデータにアクセスするためにソフトウェア・アプリケーションを自分のモバイルまたはその他のコンピューティング・デバイス上にインストールすることもできる。ソーシャル・ネットワーキング・システムは、ユーザにつながっているその他のユーザの集約されたストーリのニュース・フィードなど、ユーザに表示するためのコンテンツ・オブジェクトのパーソナライズされたセットを生成することができる。
【０００４】
ソーシャル・グラフ分析は、ソーシャルな関係を、ノードおよびエッジから構成されているネットワーク理論の点から見る。ノードは、ネットワーク内の個々の行為主体を表し、エッジは、行為主体同士の間における関係を表す。結果として生じるグラフベースの構造は、しばしば非常に複雑である。多くのタイプのノード、およびノード同士をつなげるための多くのタイプのエッジが存在することが可能である。ソーシャル・グラフは、その最もシンプルな形態においては、調査されているすべてのノードの間における関連があるすべてのエッジのマップである。
【発明の概要】
【課題を解決するための手段】
【０００５】
特定の実施形態では、方法は、クライアント側に記憶された文法テンプレートおよびエンティティを使用して、非構造化テキスト・クエリを構文解析することができる。完全な文法モデルを使用して、提案されるクエリをクライアント側で生成する代わりに、提案されるクエリは、クライアント上に記憶されている予め定められたテンプレートおよびソーシャル・グラフ・エンティティのセットを使用して生成することができる。ユーザからのテキスト入力に応答して、提案されるクエリをクライアント側で迅速に生成できるように、所定の数の文法テンプレートおよび高係数エンティティがクライアント側に記憶されることが可能である。これらの記憶されたテンプレートおよびエンティティは、ユーザによって実行されるクエリの９０％以上をカバーし得る。記憶される文法テンプレートは、グローバルに人気のあるクエリに基づいて決定され、かつ／またはユーザに人気のあるクエリに基づいてテンプレートをパーソナライズして、テンプレートに変換され得る。人気のあるクエリ／テンプレートは、たとえば、「Ｆｒｉｅｎｄｓ  ｏｆ  ［ｕｓｅｒ］」（「［ユーザ］の友人」）、「Ｐｈｏｔｏｓ  ｏｆ  ［ｕｓｅｒ］」（「［ユーザ］のフォト」）、または「Ｆｒｉｅｎｄｓ  ｗｈｏ  ｌｉｖｅ  ｎｅａｒ  ［ｌｏｃａｔｉｏｎ］」（「［場所］の近くに住んでいる友人」）を含むことができる。記憶されるエンティティは、特定のエンティティ・タイプ（たとえば、すべてのユーザの友人、ユーザによって管理されるページ、ユーザが属するグループ、ユーザが登録したイベント、ユーザがロードしたａｐｐ）を予め選択することによって、かつ／または最も高いアフィニティを有するエンティティの閾値数を選択することによって決定され得る。
【０００６】
特定の実施形態では、ユーザがテキスト文字列をクエリ・フィールド内に入力すると、クライアント側ａｐｐが、記憶されたテンプレートに対してそのテキスト文字列を整合し、各テンプレートに対するコストを計算する。基本的には、コストは、テンプレートからのテキスト文字列が構成する各ずれ（たとえば、語の欠落、語の変化など）について各テンプレートをパーソナライズすることによって決定される。そして、最も低コストのテンプレートがベスト・マッチであると決定される。そして、最も高くランク付けされたテンプレートが、提案されるクエリとしてユーザへ表示され得る。同様に、テキスト文字列の部分にマッチするエンティティを識別するために、テキスト文字列が構文解析され得る。たとえば、ユーザがテキスト・クエリ「ｆｒｉｅｎｄｓ  ｏｆ  ｆ」（「ｆの友人」）をタイプ入力した場合、クライアント側ａｐｐは、「Ｆｒｉｅｎｄｓ  ｏｆ  ［ｕｓｅｒ］」（「［ユーザ］の友人」）についての記憶された文法テンプレートにアクセスし、それをユーザ「Ｆｒｅｄ」（「フレッド」）についての記憶されたエンティティに対してマッチさせて、構造化クエリ「ｆｒｉｅｎｄｓ  ｏｆ  Ｆｒｅｄ」（「フレッドの友人」）を提案する。代替的には、クライアント側ａｐｐは、テキスト・クエリを文法テンプレート「ｆｒｉｅｎｄｓ  ｏｆ  ｆｒｉｅｎｄｓ  ｏｆ  ［ｕｓｅｒ］」（「［ユーザ］の友人の友人」）に対してマッチさせ、部分的構造化クエリ「ｆｒｉｅｎｄｓ  ｏｆ  ｆｒｉｅｎｄｓ  ｏｆ．．．」（「友人の友人の…」）を提案することができ、ユーザは、それを選択してテキストを入力するのを継続することができる。
【０００７】
本発明による実施形態は、方法、記憶媒体、およびシステムに関する添付の特許請求の範囲に特定的に開示されており、あるクレーム・カテゴリ、たとえば、方法に記載された任意の特徴が、別のクレーム・カテゴリ、たとえば、システムにおいても特許請求され得る。
【０００８】
本発明による実施形態では、方法は、モバイル・クライアント・システムに関連付けられた１つまたは複数のプロセッサによって、
モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取る工程と、
モバイル・クライアント・システムのデータ・ストアからの、オンライン・ソーシャル・ネットワークのソーシャル・グラフのノードのセットにアクセスする工程であって、ソーシャル・グラフは、複数のノードと、ノードを接続する複数のエッジとからなり、ノードは、
第１のユーザに対応する第１のノードと、
オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれが対応する複数の第２のノードと
からなる、アクセスする工程と、
モバイル・クライアント・システムのデータ・ストアからの、文法テンプレートのセットにアクセスする工程であって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンとからなり、クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照からなり、各文法テンプレートは、自然言語文字列に基づく、アクセスする工程と、
モバイル・クライアント・システムによって、非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成する工程であって、各構造化クエリは、１つまたは複数の非終端トークンにマッチされたアクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照からなる、生成する工程と、
モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを第１のユーザへ表示する工程と、を備える。
【０００９】
実施形態において、方法は、
モバイル・クライアント・システムによって、非構造化テキスト・クエリを構文解析して１つまたは複数のｎ−ｇｒａｍにする工程と、
モバイル・クライアント・システムによって、非終端またはクエリ・トークンの１つに対応していないｎ−ｇｒａｍのうちの１つまたは複数に少なくとも部分的に基づいて、各文法テンプレートに対するコストを計算する工程と、をさらに備えることができる。
【００１０】
各非終端およびクエリ・トークンは、関連付けられた挿入コストを有することができ、コストを計算する工程は、１つまたは複数のｎ−ｇｒａｍに対応していない非終端またはクエリ・トークンのそれぞれに関する挿入コストを発生する工程を備えることができる。
【００１１】
コストを計算する工程は、モバイル・クライアント・システムによって、各非終端トークンの挿入コストに少なくとも部分的に基づいて、特定のｎ−ｇｒａｍに対応する非終端トークンのうちの１つまたは複数から、特定の非終端トークンを識別する工程を備えることができる。
【００１２】
コストを計算する工程は、
モバイル・クライアント・システムによって、アクセスされたノードのうちの１つを非終端トークンのうちの１つへ関連付ける工程と、
ｎ−ｇｒａｍのうちの１つに対応していない関連付けられたアクセスされたノードに基づいて、非終端トークンおよび関連付けられたアクセスされたノードに関する挿入コストを発生する工程と、を備えることができる。
【００１３】
実施形態において、方法は、モバイル・クライアント・システムによって、関連付けられた文法テンプレートの計算されたコストに少なくとも部分的に基づいて、構造化クエリのうちの１つまたは複数をランク付けする工程をさらに備えることができる。
【００１４】
コストを計算する工程は、各文法テンプレートに関連付けられた基本コスト（ｂａｓｅ  ｃｏｓｔ）を発生する工程を備えることができ、基本コストは、各文法テンプレートの基礎である１つまたは複数の検索クエリに関連付けられた人気度測定値に対して反比例関係（ｉｎｖｅｒｓｅ  ｒｅｌａｔｉｏｎｓｈｉｐ）を有する。
【００１５】
人気度測定値は、第１のユーザの検索クエリ履歴に少なくとも部分的に基づくことができる。
人気度測定値は、オンライン・ソーシャル・ネットワークのユーザの検索クエリ履歴に少なくとも部分的に基づくことができる。
【００１６】
表示された構造化クエリのそれぞれは、閾値コスト値より低い計算されたコストを有することができる。
モバイル・クライアント・システムによって、第１のユーザから入力を受け取る工程は、ユーザが文字列をグラフィカル・ユーザ・インターフェース内に入力すると、文字列の１つまたは複数の文字を受け取る工程を備えることができる。
【００１７】
実施形態において、方法は、モバイル・クライアント・システムによって、ユーザがグラフィカル・ユーザ・インターフェース内に１つまたは複数の後続の文字を入力したときに修正された非構造化テキスト・クエリをマッチングすることにより、構造化クエリのうちの１つまたは複数を更新する工程をさらに備えることができる。
【００１８】
ノードのセットの各ノードは、閾値より大きい係数を有することができる。
実施形態において、方法は、モバイル・コンピューティング・デバイスによって、所定の間隔で、オンライン・ソーシャル・ネットワークから、更新されたセットの文法テンプレートまたは更新されたセットのノードを受け取る工程をさらに備えることができる。
【００１９】
実施形態において、方法は、第１のユーザからの表示された構造化クエリのうちの１つの選択に応答して、モバイル・クライアント・システムによって、選択された構造化クエリをオンライン・ソーシャル・ネットワークに送る工程をさらに備えることができる。
【００２０】
実施形態において、方法は、モバイル・クライアント・システムによって、選択された構造化クエリがオンライン・ソーシャル・ネットワークへ送られたことに応答して、１つまたは複数の検索結果を受け取る工程をさらに備えることができる。
【００２１】
検索結果のそれぞれは、複数の第２のノードのうちの特定の第２のノードに対応することができる。
ノードのセットは、所定の数のノードからなることができ、文法テンプレートのセットは、所定の数の文法テンプレートからなることができる。
【００２２】
本発明のさらなる実施形態では、１つまたは複数のコンピュータ可読非一時的記憶媒体がソフトウェアを具現化し、ソフトウェアは、実行されたとき、
モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ること、
モバイル・クライアント・システムのデータ・ストアからの、オンライン・ソーシャル・ネットワークのソーシャル・グラフのノードのセットにアクセスすることであって、ソーシャル・グラフは、複数のノードと、ノードを接続する複数のエッジとからなり、ノードは、
第１のユーザに対応する第１のノードと、
オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれが対応する複数の第２のノードとからなる、アクセスすること、
モバイル・クライアント・システムのデータ・ストアからの、文法テンプレートのセットにアクセスすることであって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンとからなり、クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照からなり、各文法テンプレートは、自然言語文字列に基づく、アクセスすること、
モバイル・クライアント・システムによって、非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成することであって、各構造化クエリは、１つまたは複数の非終端トークンにマッチされたアクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照からなる、生成すること、
モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを第１のユーザへ表示すること、を行うように動作可能である。
【００２３】
本発明のさらなる実施形態では、システムが、１つまたは複数のプロセッサと、プロセッサによって実行可能な命令を備えるプロセッサに結合されたメモリとからなり、プロセッサは、命令を実行すると、
モバイル・クライアント・システムにおいて、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ること、
モバイル・クライアント・システムのデータ・ストアからの、オンライン・ソーシャル・ネットワークのソーシャル・グラフのノードのセットにアクセスすることであって、ソーシャル・グラフは、複数のノードと、ノードを接続する複数のエッジとからなり、ノードは、
第１のユーザに対応する第１のノードと、
オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれが対応する複数の第２のノードとからなる、アクセスすること、
モバイル・クライアント・システムのデータ・ストアからの、文法テンプレートのセットにアクセスすることであって、各文法テンプレートは、１つまたは複数の非終端トークンと、１つまたは複数のクエリ・トークンとからなり、クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照からなり、各文法テンプレートは、自然言語文字列に基づく、アクセスすること、
モバイル・クライアント・システムによって、非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の構造化クエリを生成することであって、各構造化クエリは、１つまたは複数の非終端トークンにマッチされたアクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される第２のノードのうちの０個以上および１つまたは複数のエッジに対する参照からなる、生成すること、
モバイル・クライアント・システムにおいて、１つまたは複数の構造化クエリを第１のユーザへ表示することと、を行うように動作可能である。
【００２４】
同様に特許請求され得る本発明のさらなる実施形態では、１つまたは複数のコンピュータ可読非一時的記憶媒体がソフトウェアを具現化し、ソフトウェアは、実行されたとき、本発明または上記実施形態のいずれかによる方法を実施するように動作可能である。
【００２５】
同様に特許請求され得る本発明のさらなる実施形態では、システムが、１つまたは複数のプロセッサと、プロセッサによって実行可能な命令を備えるプロセッサに結合されたメモリとからなり、プロセッサは、命令を実行すると、本発明または上記実施形態のいずれかによる方法を実施するように動作可能である。
【図面の簡単な説明】
【００２６】
【図１】ソーシャル・ネットワーキング・システムに関連付けられた例示的ネットワーク環境を示す図。
【図２】例示的ソーシャル・グラフを示す図。
【図３】オンライン・ソーシャル・ネットワークの例示的ウェブページを示す図。
【図４】例示的モバイル・クライアント・システムを示す図。
【図５】例示的モバイル・クライアント・システム上の例示的ユーザ・インターフェース（ＵＩ）を示す図。
【図６】テキスト入力を文法テンプレートおよびソーシャル・グラフ・エンティティに対してマッチングするための例示的コスト計算のグラフ表現を示す図。
【図７】テキスト入力を文法テンプレートおよびソーシャル・グラフ・エンティティに対してマッチングするための例示的コスト計算のグラフ表現を示す図。
【図８】テキスト入力を文法テンプレートおよびソーシャル・グラフ・エンティティに対してマッチングするための例示的コスト計算のグラフ表現を示す図。
【図９】例示的構造化検索クエリを有する例示的モバイル・クライアント・システム上の例示的ＵＩを示す図。
【図１０】例示的構造化検索クエリを有する例示的モバイル・クライアント・システム上の例示的ＵＩを示す図。
【図１１】クライアント側構造化検索クエリを生成するための例示的方法を示す図。
【図１２】例示的コンピュータ・システムを示す図。
【発明を実施するための形態】
【００２７】
システムの概要
図１は、ソーシャル・ネットワーキング・システムに関連付けられている例示的なネットワーク環境１００を示している。ネットワーク環境１００は、ネットワーク１１０によって互いにつながっているクライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０を含む。図１は、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０の特定の構成を示しているが、本開示は、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０の任意の適切な構成を想定している。限定ではなく、例として、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０のうちの複数は、ネットワーク１１０を迂回して、互いに直接つながることが可能である。別の例として、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０のうちの複数は、物理的にまたは論理的に、全体としてまたは部分的に互いに同一場所に配置されることが可能である。その上、図１は、特定の数のクライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０を示しているが、本開示は、任意の適切な数のクライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０を想定している。限定ではなく、例として、ネットワーク環境１００は、複数のクライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０を含むことができる。
【００２８】
本開示は、任意の適切なネットワーク１１０を想定している。限定ではなく、例として、ネットワーク１１０の１つまたは複数の部分は、アド・ホック・ネットワーク、イントラネット、エクストラネット、仮想プライベート・ネットワーク（ＶＰＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、無線ＬＡＮ（ＷＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、無線ＷＡＮ（ＷＷＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、インターネットの一部分、公衆交換電話網（ＰＳＴＮ）の一部分、セルラー電話ネットワーク、またはこれらのうちの複数の組合せを含むことができる。ネットワーク１１０は、１つまたは複数のネットワーク１１０を含むことができる。
【００２９】
リンク１５０は、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０を通信ネットワーク１１０に、または互いに接続することができる。本開示は、任意の適切なリンク１５０を想定している。特定の実施形態においては、１つまたは複数のリンク１５０は、１つもしくは複数の有線リンク（たとえば、デジタル・サブスクライバ・ライン（ＤＳＬ）もしくはデータ・オーバ・ケーブル・サービス・インタフェース仕様（ＤＯＣＳＩＳ）など）、無線リンク（たとえば、Ｗｉ−Ｆｉもしくはワールドワイド・インターオペラビリティー・フォー・マイクロウェーブ・アクセス（ＷｉＭＡＸ）など）、または光リンク（たとえば、同期光ネットワーク（ＳＯＮＥＴ）もしくは同期デジタル階層（ＳＤＨ）など）を含む。特定の実施形態においては、１つまたは複数のリンク１５０はそれぞれ、アド・ホック・ネットワーク、イントラネット、エクストラネット、ＶＰＮ、ＬＡＮ、ＷＬＡＮ、ＷＡＮ、ＷＷＡＮ、ＭＡＮ、インターネットの一部分、ＰＳＴＮの一部分、セルラー・テクノロジーベースのネットワーク、衛星通信テクノロジーベースのネットワーク、別のリンク１５０、または複数のそのようなリンク１５０の組合せを含む。リンク１５０は、ネットワーク環境１００の全体を通じて必ずしも同じである必要はない。１つまたは複数の第１のリンク１５０は、１つまたは複数の点において１つまたは複数の第２のリンク１５０とは異なることが可能である。
【００３０】
特定の実施形態においては、クライアント・システム１３０は、クライアント・システム１３０によって実装またはサポートされる適切な機能を実行することができる、ハードウェア、ソフトウェア、もしくは組み込みロジック・コンポーネント、または複数のそのようなコンポーネントの組合せを含む電子デバイスであることが可能である。限定ではなく、例として、クライアント・システム１３０は、デスクトップ・コンピュータ、ノートブック・コンピュータもしくはラップトップ・コンピュータ、ネットブック、タブレット・コンピュータなどのコンピュータ・システム、ｅブック・リーダ、ＧＰＳデバイス、カメラ、携帯情報端末（ＰＤＡ）、ハンドヘルド電子デバイス、セルラー電話、スマートフォン、その他の適切な電子デバイス、またはそれらの任意の適切な組合せを含むことができる。本開示は、任意の適切なクライアント・システム１３０を想定している。クライアント・システム１３０は、クライアント・システム１３０のネットワーク・ユーザがネットワーク１１０にアクセスすることを可能にすることができる。クライアント・システム１３０は、自分のユーザがその他のクライアント・システム１３０のその他のユーザと通信することを可能にすることができる。
【００３１】
特定の実施形態においては、クライアント１３０は、ＭＩＣＲＯＳＯＦＴ  ＩＮＴＥＲＮＥＴ  ＥＸＰＬＯＲＥＲ、ＧＯＯＧＬＥ  ＣＨＲＯＭＥ、またはＭＯＺＩＬＬＡ  ＦＩＲＥＦＯＸなどのウェブ・ブラウザ１３２を含むことができ、１つまたは複数のアドオン、プラグイン、またはＴＯＯＬＢＡＲもしくはＹＡＨＯＯ  ＴＯＯＬＢＡＲなどのその他の拡張を有することができる。クライアント・システム１３０のユーザは、ウェブ・ブラウザ１３２を特定のサーバ（サーバ１６２、またはサードパーティ・システム１７０に関連付けられているサーバなど）へ導くユニフォーム・リソース・ロケータ（ＵＲＬ）またはその他のアドレスを入力することができ、ウェブ・ブラウザ１３２は、ハイパー・テキスト転送プロトコル（ＨＴＴＰ）要求を生成して、そのＨＴＴＰ要求をサーバに通信することができる。サーバは、そのＨＴＴＰ要求を受け入れて、そのＨＴＴＰ要求に応答して１つまたは複数のハイパー・テキスト・マークアップ言語（ＨＴＭＬ）ファイルをクライアント・システム１３０に通信することができる。クライアント・システム１３０は、ユーザに提示するためにサーバからのＨＴＭＬファイルに基づいてウェブページをレンダリングすることができる。本開示は、任意の適切なウェブページ・ファイルを想定している。限定ではなく、例として、ウェブページは、特定のニーズに従って、ＨＴＭＬファイル、拡張可能ハイパー・テキスト・マークアップ言語（ＸＨＴＭＬ）ファイル、または拡張可能マークアップ言語（ＸＭＬ）ファイルからレンダリングすることができる。そのようなページは、限定ではなく、例として、ＪＡＶＡＳＣＲＩＰＴ（登録商標）、ＪＡＶＡ（登録商標）、ＭＩＣＲＯＳＯＦＴ  ＳＩＬＶＥＲＬＩＧＨＴで書かれたスクリプトなどのスクリプト、ＡＪＡＸ（Ａｓｙｎｃｈｒｏｎｏｕｓ  ＪＡＶＡＳＣＲＩＰＴ（登録商標）ａｎｄ  ＸＭＬ）などのマークアップ言語とスクリプトの組合せなどを実行することもできる。本明細書においては、ウェブページへの参照は、適切な場合には、（そのウェブページをレンダリングするためにブラウザが使用することができる）１つまたは複数の対応するウェブページ・ファイルを含み、その逆もまた同様である。
【００３２】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、オンライン・ソーシャル・ネットワークをホストすることができるネットワークアドレス可能なコンピューティング・システムであることが可能である。ソーシャル・ネットワーキング・システム１６０は、たとえば、ユーザ・プロフィール・データ、コンセプト・プロフィール・データ、ソーシャル・グラフ情報、またはオンライン・ソーシャル・ネットワークに関連したその他の適切なデータなどのソーシャルネットワーキング・データを生成すること、記憶すること、受け取ること、および送信することが可能である。ソーシャル・ネットワーキング・システム１６０は、ネットワーク環境１００のその他のコンポーネントによって直接、またはネットワーク１１０を通じてアクセスされることが可能である。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、１つまたは複数のサーバ１６２を含むことができる。それぞれのサーバ１６２は、単一のサーバ、または複数のコンピュータもしくは複数のデータセンターにわたる分散サーバであることが可能である。サーバ１６２は、限定ではなく、例として、ウェブ・サーバ、ニュース・サーバ、メール・サーバ、メッセージ・サーバ、広告サーバ、ファイル・サーバ、アプリケーション・サーバ、Ｅｘｃｈａｎｇｅサーバ、データベース・サーバ、プロキシ・サーバ、本明細書において記述されている機能もしくはプロセスを実行するのに適している別のサーバ、またはそれらの任意の組合せなど、さまざまなタイプのものであることが可能である。特定の実施形態においては、それぞれのサーバ１６２は、サーバ１６２によって実装またはサポートされる適切な機能を実行するためのハードウェア、ソフトウェア、もしくは組み込みロジック・コンポーネント、または複数のそのようなコンポーネントの組合せを含むことができる。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６４は、１つまたは複数のデータ・ストア１６４を含むことができる。データ・ストア１６４は、さまざまなタイプの情報を記憶するために使用されることが可能である。特定の実施形態においては、データ・ストア１６４内に記憶されている情報は、特定のデータ構造に従って編成されることが可能である。特定の実施形態においては、それぞれのデータ・ストア１６４は、リレーショナル・データベースであることが可能である。特定の実施形態は、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、またはサードパーティ・システム１７０が、データ・ストア１６４内に記憶されている情報を管理すること、取り出すこと、修正すること、追加すること、または削除することを可能にするインタフェースを提供することができる。
【００３３】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、１つまたは複数のソーシャル・グラフを１つまたは複数のデータ・ストア１６４内に記憶することができる。特定の実施形態においては、ソーシャル・グラフは、複数のノード（複数のユーザ・ノード（それぞれが、特定のユーザに対応している）、または複数のコンセプト・ノード（それぞれが、特定のコンセプトに対応している）を含むことができる）と、ノード同士をつなげる複数のエッジとを含むことができる。ソーシャル・ネットワーキング・システム１６０は、オンライン・ソーシャル・ネットワークのユーザに、その他のユーザと通信および対話する能力を提供することができる。特定の実施形態においては、ユーザたちは、ソーシャル・ネットワーキング・システム１６０を通じてオンライン・ソーシャル・ネットワークに参加し、次いで、自分たちがつながりたいと望むソーシャル・ネットワーキング・システム１６０のその他の複数のユーザにつながり（すなわち、関係）を付加することができる。本明細書においては、「友達」という用語は、ユーザがソーシャル・ネットワーキング・システム１６０を通じて、つながり、関連付け、または関係を形成しているソーシャル・ネットワーキング・システム１６０のその他の任意のユーザを示すことができる。
【００３４】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、ソーシャル・ネットワーキング・システム１６０によってサポートされるさまざまなタイプのアイテムまたはオブジェクトに関してアクションを取る能力をユーザに提供することができる。限定ではなく、例として、それらのアイテムおよびオブジェクトは、ソーシャル・ネットワーキング・システム１６０のユーザが属することが可能であるグループもしくはソーシャル・ネットワーク、ユーザが関心を抱く可能性があるイベントもしくはカレンダー・エントリー、ユーザが使用することができるコンピュータベースのアプリケーション、ユーザがサービスを通じてアイテムを購入もしくは販売することを可能にするトランザクション、ユーザが実行することができる広告との対話、またはその他の適切なアイテムもしくはオブジェクトを含むことができる。ユーザは、ソーシャル・ネットワーキング・システム１６０において、またはサードパーティ・システム１７０の外部システム（ソーシャル・ネットワーキング・システム１６０とは別個のものであって、ネットワーク１１０を通じてソーシャル・ネットワーキング・システム１６０に結合されている）によって表されることが可能である任意のものと対話することができる。
【００３５】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、さまざまなエンティティ同士をリンクできることが可能である。限定ではなく、例として、ソーシャル・ネットワーキング・システム１６０は、ユーザたちが互いに対話すること、ならびにサードパーティ・システム１７０もしくはその他のエンティティからのコンテンツを受け取ることを可能にすることができ、またはユーザたちがアプリケーション・プログラミング・インタフェース（ＡＰＩ）もしくはその他の通信チャネルを通じてこれらのエンティティと対話することを可能にすることができる。
【００３６】
特定の実施形態においては、サードパーティ・システム１７０は、１つもしくは複数のタイプのサーバ、１つもしくは複数のデータ・ストア、１つもしくは複数のインタフェース（ＡＰＩを含むが、それには限定されない）、１つもしくは複数のウェブ・サービス、１つもしくは複数のコンテンツ・ソース、１つもしくは複数のネットワーク、または（たとえば、サーバが通信することができる）その他の任意の適切なコンポーネントを含むことができる。サードパーティ・システム１７０は、ソーシャル・ネットワーキング・システム１６０を運営しているエンティティとは異なるエンティティによって運営されることが可能である。しかしながら、特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０およびサードパーティ・システム１７０は、ソーシャル・ネットワーキング・システム１６０またはサードパーティ・システム１７０のユーザにソーシャルネットワーキング・サービスを提供するために互いに連携して機能することができる。この意味において、ソーシャル・ネットワーキング・システム１６０は、サードパーティ・システム１７０などのその他のシステムがインターネットを通じてソーシャルネットワーキング・サービスおよび機能をユーザに提供するために使用することができるプラットフォーム、またはバックボーンを提供することができる。
【００３７】
特定の実施形態においては、サードパーティ・システム１７０は、サードパーティ・コンテンツ・オブジェクト・プロバイダを含むことができる。サードパーティ・コンテンツ・オブジェクト・プロバイダは、コンテンツ・オブジェクトの１つまたは複数のソースを含むことができ、それらのソースは、クライアント・システム１３０に通信されることが可能である。限定ではなく、例として、コンテンツ・オブジェクトは、ユーザにとって関心がある物またはアクティビティに関する情報、たとえば、映画の開始時刻、映画のレビュー、レストランのレビュー、レストランのメニュー、製品の情報およびレビュー、またはその他の適切な情報などを含むことができる。限定ではなく、別の例として、コンテンツ・オブジェクトは、インセンティブ・コンテンツ・オブジェクト、たとえば、クーポン、ディスカウント・チケット、ギフト券、またはその他の適切なインセンティブ・オブジェクトを含むことができる。
【００３８】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０はまた、ユーザによって生成されたコンテンツ・オブジェクトを含み、それらのコンテンツ・オブジェクトは、ソーシャル・ネットワーキング・システム１６０とのユーザの対話を高めることができる。ユーザによって生成されたコンテンツは、ユーザがソーシャル・ネットワーキング・システム１６０に付加、アップロード、送信、または「投稿（ポスト）」することができる任意のものを含むことができる。限定ではなく、例として、ユーザは、クライアント・システム１３０からソーシャル・ネットワーキング・システム１６０へ投稿を通信する。投稿は、ステータス更新もしくはその他のテキスト・データ、ロケーション情報、写真、映像、リンク、音楽、またはその他の類似したデータもしくはメディアなどのデータを含むことができる。コンテンツは、ニュース・フィードまたはストリームなどの「通信チャネル」を通じてサードパーティによってソーシャル・ネットワーキング・システム１６０に付加されることも可能である。
【００３９】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、さまざまなサーバ、サブシステム、プログラム、モジュール、ログ、およびデータ・ストアを含むことができる。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、ウェブ・サーバ、アクション・ロガー、ＡＰＩ要求サーバ、関連性およびランク付け・エンジン、コンテンツ・オブジェクト分類子、通知コントローラ、アクション・ログ、サードパーティ・コンテンツ・オブジェクト露出ログ、推測モジュール、認可／プライバシ・サーバ、検索モジュール、広告ターゲティング・モジュール、ユーザインタフェース・モジュール、ユーザ・プロフィール・ストア、つながりストア、サードパーティ・コンテンツ・ストア、またはロケーション・ストアのうちの１つまたは複数を含むことができる。ソーシャル・ネットワーキング・システム１６０は、適切なコンポーネント、たとえば、ネットワーク・インタフェース、セキュリティー・メカニズム、ロード・バランサ、フェイルオーバ・サーバ、管理およびネットワークオペレーション・コンソール、その他の適切なコンポーネント、またはそれらの任意の適切な組合せを含むこともできる。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、ユーザ・プロフィールを記憶するための１つまたは複数のユーザ・プロフィール・ストアを含むことができる。ユーザ・プロフィールは、たとえば、経歴情報、人口統計学的情報、挙動情報、ソーシャルな情報、またはその他のタイプの記述的情報、たとえば、職業経験、学歴、趣味もしくは好み、関心、親近感、またはロケーションを含むことができる。関心情報は、１つまたは複数のカテゴリに関連した関心を含むことができる。カテゴリは、一般的または具体的であることが可能である。限定ではなく、例として、ユーザが、あるブランドの靴に関する記事に対して「いいね！」の表明をした場合には、カテゴリは、そのブランド、または「靴」もしくは「衣類」という一般的なカテゴリであることが可能である。ユーザに関するつながり情報を記憶するために、つながりストアが使用されることが可能である。つながり情報は、類似のもしくは共通の職業経験、グループ・メンバーシップ、趣味、学歴を有しているか、または何らかの形で関連しているか、もしくは共通の属性を共有しているユーザ同士を示すことができる。つながり情報は、さまざまなユーザおよびコンテンツ（内部および外部の両方）の間におけるユーザ定義のつながりを含むこともできる。ネットワーク１１０を通じてソーシャル・ネットワーキング・システム１６０を１つもしくは複数のクライアント・システム１３０または１つもしくは複数のサードパーティ・システム１７０にリンクさせるために、ウェブ・サーバが使用されることが可能である。ウェブ・サーバは、ソーシャル・ネットワーキング・システム１６０と、１つまたは複数のクライアント・システム１３０との間においてメッセージを受け取って回送するためにメール・サーバまたはその他のメッセージング機能を含むことができる。ＡＰＩ要求サーバは、サードパーティ・システム１７０が、１つまたは複数のＡＰＩを呼び出すことによってソーシャル・ネットワーキング・システム１６０からの情報にアクセスすることを可能にすることができる。ソーシャル・ネットワーキング・システム１６０の上のまたは外のユーザのアクションに関してウェブ・サーバから通信を受け取るために、アクション・ロガーが使用されることが可能である。アクション・ログとともに、サードパーティコンテンツ・オブジェクトへのユーザの露出についてのサードパーティコンテンツオブジェクト・ログが保持されることが可能である。通知コントローラは、コンテンツ・オブジェクトに関する情報をクライアント・システム１３０に提供することができる。情報は、通知としてクライアント・システム１３０へプッシュされることが可能であり、または情報は、クライアント・システム１３０から受け取られた要求に応答してクライアント・システム１３０からプルされることが可能である。ソーシャル・ネットワーキング・システム１６０のユーザの１つまたは複数のプライバシ設定を実施するために、認可サーバが使用されることが可能である。ユーザのプライバシ設定は、ユーザに関連付けられている特定の情報がどのように共有されることが可能であるかを特定する。認可サーバは、ユーザが、たとえば、適切なプライバシ設定を設定することなどによって、自分のアクションをソーシャル・ネットワーキング・システム１６０によって記録されること、またはその他のシステム（たとえば、サードパーティ・システム１７０）と共有されることのオプト・インまたはオプト・アウトを行うことを可能にすることができる。サードパーティ・システム１７０などのサードパーティから受け取られたコンテンツ・オブジェクトを記憶するために、サードパーティコンテンツオブジェクト・ストアが使用されることが可能である。ユーザに関連付けられているクライアント・システム１３０から受け取られたロケーション情報を記憶するために、ロケーション・ストアが使用されることが可能である。広告価格設定モジュールが、ソーシャルな情報、現在時刻、ロケーション情報、またはその他の適切な情報を組み合わせて、関連がある広告を、通知の形式でユーザに提供することができる。
【００４０】
ソーシャル・グラフ
図２は、例示的なソーシャル・グラフ２００を示している。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、１つまたは複数のソーシャル・グラフ２００を１つまたは複数のデータ・ストア内に記憶することができる。特定の実施形態においては、ソーシャル・グラフ２００は、複数のノード（複数のユーザ・ノード２０２、または複数のコンセプト・ノード２０４を含むことができる）と、ノード同士をつなげる複数のエッジ２０６とを含むことができる。図２において示されている例示的なソーシャル・グラフ２００は、教示上の目的から、２次元の視覚的マップ表示で示されている。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０、クライアント・システム１３０、またはサードパーティ・システム１７０は、適切なアプリケーションに関してソーシャル・グラフ２００および関連したソーシャル・グラフ情報にアクセスすることができる。ソーシャル・グラフ２００のノードおよびエッジは、データ・オブジェクトとして、たとえば（ソーシャル・グラフ・データベースなどの）データ・ストア内に記憶されることが可能である。そのようなデータ・ストアは、ソーシャル・グラフ２００のノードまたはエッジの１つまたは複数の検索可能なまたはクエリ可能なインデックスを含むことができる。
【００４１】
特定の実施形態においては、ユーザ・ノード２０２は、ソーシャル・ネットワーキング・システム１６０の第１のユーザに対応することができる。限定ではなく、例として、ユーザは、ソーシャル・ネットワーキング・システム１６０と、またはソーシャル・ネットワーキング・システム１６０を通じて対話または通信する個人（人間のユーザ）、エンティティ（たとえば、企業、ビジネス、もしくはサードパーティ・アプリケーション）、または（たとえば、個人もしくはエンティティの）グループであることが可能である。特定の実施形態においては、第１のユーザがソーシャル・ネットワーキング・システム１６０とのアカウントに登録した場合には、ソーシャル・ネットワーキング・システム１６０は、そのユーザに対応する第１のユーザ・ノード２０２を作成し、そのユーザ・ノード２０２を１つまたは複数のデータ・ストア内に記憶することができる。本明細書において記述されているユーザおよびユーザ・ノード２０２は、適切な場合には、登録されているユーザ、および登録されているユーザに関連付けられているユーザ・ノード２０２を示すことができる。追加として、または代替として、本明細書において記述されているユーザおよびユーザ・ノード２０２は、適切な場合には、ソーシャル・ネットワーキング・システム１６０に登録されていないユーザを示すことができる。特定の実施形態においては、ユーザ・ノード２０２は、ユーザによって提供された情報、またはソーシャル・ネットワーキング・システム１６０を含むさまざまなシステムによって収集された情報に関連付けられることが可能である。限定ではなく、例として、ユーザは、自分の名前、プロフィール画像、連絡先情報、生年月日、性別、婚姻状況、家族状況、勤務先、学歴、好み、関心、またはその他の人口統計学的情報を提供することができる。特定の実施形態においては、ユーザ・ノード２０２は、ユーザに関連付けられている情報に対応する１つまたは複数のデータ・オブジェクトに関連付けられることが可能である。特定の実施形態においては、ユーザ・ノード２０２は、１つまたは複数のウェブページに対応することができる。
【００４２】
特定の実施形態においては、コンセプト・ノード２０４は、コンセプトに対応することができる。限定ではなく、例として、コンセプトは、場所（たとえば、映画館、レストラン、ランドマーク、もしくは都市など）、ウェブサイト（たとえば、ソーシャルネットワーク・システム１６０に関連付けられているウェブサイト、もしくはウェブアプリケーション・サーバに関連付けられているサードパーティ・ウェブサイトなど）、エンティティ（たとえば、人、企業、グループ、スポーツ・チーム、もしくは有名人など）、ソーシャル・ネットワーキング・システム１６０内に、もしくはウェブアプリケーション・サーバなどの外部サーバ上に配置されることが可能であるリソース（たとえば、オーディオ・ファイル、営業ファイル、デジタル写真、テキスト・ファイル、構造化文書、もしくはアプリケーションなど）、物的もしくは知的財産（たとえば、彫塑、絵画、映画、ゲーム、曲、着想、写真、もしくは執筆作品など）、ゲーム、アクティビティ、着想もしくは理論、別の適切なコンセプト、または複数のそのようなコンセプトに対応することができる。コンセプト・ノード２０４は、ユーザによって提供されたコンセプトの情報、またはソーシャル・ネットワーキング・システム１６０を含むさまざまなシステムによって収集された情報に関連付けられることが可能である。限定ではなく、例として、コンセプトの情報は、名前もしくはタイトル、１つもしくは複数のイメージ（たとえば、本の表紙のイメージ）、ロケーション（たとえば、住所もしくは地理的ロケーション）、（ＵＲＬに関連付けられることが可能である）ウェブサイト、連絡先情報（たとえば、電話番号もしくはＥメール・アドレス）、その他の適切なコンセプト情報、またはそのような情報の任意の適切な組合せを含むことができる。特定の実施形態においては、コンセプト・ノード２０４は、コンセプト・ノード２０４に関連付けられている情報に対応する１つまたは複数のデータ・オブジェクトに関連付けられることが可能である。特定の実施形態においては、コンセプト・ノード２０４は、１つまたは複数のウェブページに対応することができる。
【００４３】
特定の実施形態においては、ソーシャル・グラフ２００内のノードは、ウェブページ（「プロフィール・ページ」と呼ばれる場合もある）を表すこと、またはウェブページによって表されることが可能である。プロフィール・ページは、ソーシャル・ネットワーキング・システム１６０によってホストされること、またはソーシャル・ネットワーキング・システム１６０にとってアクセス可能であることが可能である。プロフィール・ページは、サードパーティ・サーバ１７０に関連付けられているサードパーティ・ウェブサイト上にホストされることも可能である。限定ではなく、例として、特定の外部ウェブページに対応するプロフィール・ページは、その特定の外部ウェブページであることが可能であり、そのプロフィール・ページは、特定のコンセプト・ノード２０４に対応することができる。プロフィール・ページは、その他のユーザのうちのすべてまたは選択されたサブセットによって閲覧できることが可能である。限定ではなく、例として、ユーザ・ノード２０２は、対応するユーザ・プロフィール・ページを有することができ、そのユーザ・プロフィール・ページにおいては、対応するユーザが、コンテンツを付加すること、言明を行うこと、またはその他の形で自分自身を表現することが可能である。限定ではなく、別の例として、コンセプト・ノード２０４は、対応するコンセプト・プロフィール・ページを有することができ、そのコンセプト・プロフィール・ページにおいては、１人または複数のユーザが、特にコンセプト・ノード２０４に対応するコンセプトに関連して、コンテンツを付加すること、言明を行うこと、または自分自身を表現することが可能である。
【００４４】
特定の実施形態においては、コンセプト・ノード２０４は、サードパーティ・システム１７０によってホストされているサードパーティ・ウェブページまたはリソースを表すことができる。サードパーティ・ウェブページまたはリソースは、数ある要素の中でも、コンテンツ、選択可能なもしくはその他のアイコン、または、アクションもしくはアクティビティを表す（たとえば、ＪＡＶＡＳＣＲＩＰＴ（登録商標）、ＡＪＡＸ、もしくはＰＨＰコードで実装されることが可能である）その他の対話可能なオブジェクトを含むことができる。限定ではなく、例として、サードパーティ・ウェブページは、「いいね！」、「チェックイン」、「食べる」、「推奨する」、または別の適切なアクションもしくはアクティビティなどの選択可能なアイコンを含むことができる。サードパーティ・ウェブページを閲覧しているユーザは、それらのアイコンのうちの１つ（たとえば、「食べる」）を選択することによってアクションを実行して、クライアント・システム１３０に、そのユーザのアクションを示すメッセージをソーシャル・ネットワーキング・システム１６０へ送信させることができる。そのメッセージに応答して、ソーシャル・ネットワーキング・システム１６０は、ユーザに対応するユーザ・ノード２０２と、サードパーティ・ウェブページまたはリソースに対応するコンセプト・ノード２０４との間においてエッジ（たとえば、「食べる」エッジ）を作成して、エッジ２０６を１つまたは複数のデータ・ストア内に記憶することができる。
【００４５】
特定の実施形態においては、ソーシャル・グラフ２００内の１対のノードが、１つまたは複数のエッジ２０６によって互いにつながることが可能である。１対のノードをつなげるエッジ２０６は、それらの１対のノードの間における関係を表すことができる。特定の実施形態においては、エッジ２０６は、１対のノードの間における関係に対応する１つまたは複数のデータ・オブジェクトまたは属性を含むことまたは表すことが可能である。限定ではなく、例として、第１のユーザは、第２のユーザが第１のユーザの「友達」であるということを示すことができる。この表示に応答して、ソーシャル・ネットワーキング・システム１６０は、「友達要求」を第２のユーザに送信することができる。第２のユーザがその「友達要求」を承認した場合には、ソーシャル・ネットワーキング・システム１６０は、ソーシャル・グラフ２００内で第１のユーザのユーザ・ノード２０２を第２のユーザのユーザ・ノード２０２につなげるエッジ２０６を作成して、エッジ２０６をソーシャル・グラフ情報としてデータ・ストア２４のうちの１つまたは複数の中に記憶することができる。図２の例においては、ソーシャル・グラフ２００は、ユーザ「Ａ」のユーザ・ノード２０２と、ユーザ「Ｂ」のユーザ・ノード２０２との間における友達関係を示すエッジ２０６と、ユーザ「Ｃ」のユーザ・ノード２０２と、ユーザ「Ｂ」のユーザ・ノード２０２との間における友達関係を示すエッジとを含む。本開示は、特定のユーザ・ノード２０２同士をつなげる特定の属性を伴う特定のエッジ２０６を記述している、または示しているが、本開示は、ユーザ・ノード２０２同士をつなげる任意の適切な属性を伴う任意の適切なエッジ２０６を想定している。限定ではなく、例として、エッジ２０６は、友達関係、家族関係、ビジネスもしくは雇用関係、ファン関係、フォロワー関係、ビジター関係、サブスクライバ関係、上下関係、互恵的関係、非互恵的関係、別の適切なタイプの関係、または複数のそのような関係を表すことができる。その上、本開示は一般に、ノード同士をつながっているものとして記述しているが、本開示はまた、ユーザ同士またはコンセプト同士をつながっているものとして記述している。本明細書においては、つながっているユーザ同士またはコンセプト同士への言及は、適切な場合には、１つまたは複数のエッジ２０６によってソーシャル・グラフ２００内でつながっているそれらのユーザ同士またはコンセプト同士に対応するノード同士を示すことができる。
【００４６】
特定の実施形態においては、ユーザ・ノード２０２とコンセプト・ノード２０４との間におけるエッジ２０６は、ユーザ・ノード２０２に関連付けられているユーザによって、コンセプト・ノード２０４に関連付けられているコンセプトに対して実行された特定のアクションまたはアクティビティを表すことができる。限定ではなく、例として、図２において示されているように、ユーザは、コンセプトに対して「いいね！を表明すること」、「通うこと」、「プレイすること」、「聴くこと」、「料理すること」、「勤務すること」、または「観ること」を行った可能性があり、それらの各々は、エッジ・タイプまたはサブタイプに対応することができる。コンセプト・ノード２０４に対応するコンセプト・プロフィール・ページは、たとえば、選択可能な「チェックイン」アイコン（たとえば、クリック可能な「チェックイン」アイコンなど）、または選択可能な「お気に入りに追加」アイコンを含むことができる。同様に、ユーザがこれらのアイコンをクリックした後に、ソーシャル・ネットワーキング・システム１６０は、それぞれのアクションに対応するユーザのアクションに応答して「お気に入り」エッジまたは「チェックイン」エッジを作成することができる。限定ではなく、別の例として、あるユーザ（ユーザ「Ｃ」）が、特定のアプリケーション（オンライン音楽アプリケーションであるＳＰＯＴＩＦＹ）を使用して特定の曲（「イマジン」）を聴く場合がある。このケースにおいては、ソーシャル・ネットワーキング・システム１６０は、そのユーザに対応するユーザ・ノード２０２と、その曲およびアプリケーションに対応するコンセプト・ノード２０４との間において、（図２に示されているような）「聴いた」エッジ２０６および「使用した」エッジを作成して、そのユーザがその曲を聴いてそのアプリケーションを使用したということを示すことができる。その上、ソーシャル・ネットワーキング・システム１６０は、その曲に対応するコンセプト・ノード２０４と、そのアプリケーションに対応するコンセプト・ノード２０４との間において、（図２に示されているような）「再生した」エッジ２０６を作成して、その特定の曲がその特定のアプリケーションによって再生されたということを示すことができる。このケースにおいては、「再生した」エッジ２０６は、外部アプリケーション（ＳＰＯＴＩＦＹ）によって外部オーディオ・ファイル（「イマジン」という曲）に関して実行されたアクションに対応する。本開示は、ユーザ・ノード２０２とコンセプト・ノード２０４とをつなげる特定の属性を伴う特定のエッジ２０６について記述しているが、本開示は、ユーザ・ノード２０２とコンセプト・ノード２０４とをつなげる任意の適切な属性を伴う任意の適切なエッジ２０６を想定している。その上、本開示は、単一の関係を表すユーザ・ノード２０２とコンセプト・ノード２０４との間におけるエッジについて記述しているが、本開示は、１つまたは複数の関係を表すユーザ・ノード２０２とコンセプト・ノード２０４との間におけるエッジを想定している。限定ではなく、例として、エッジ２０６は、ユーザが特定のコンセプトに対して「いいね！」の表明をしているということ、およびその特定のコンセプトを使用したということの両方を表すことができる。あるいは、別のエッジ２０６は、（図２において、ユーザ「Ｅ」を表すユーザ・ノード２０２と、「ＳＰＯＴＩＦＹ」を表すコンセプト・ノード２０４との間において示されているような）ユーザ・ノード２０２とコンセプト・ノード２０４との間におけるそれぞれのタイプの関係（または、単一の関係が複数集まったもの）を表すことができる。
【００４７】
特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、ソーシャル・グラフ２００内でユーザ・ノード２０２とコンセプト・ノード２０４との間においてエッジ２０６を作成することができる。限定ではなく、例として、（たとえば、ユーザのクライアント・システム１３０によってホストされているウェブ・ブラウザまたは専用のアプリケーションを使用することなどによって）コンセプト・プロフィール・ページを閲覧しているユーザは、「いいね！」アイコンをクリックまたは選択することにより、コンセプト・ノード２０４によって表されているコンセプトを自分が気に入っているということを示すことができ、その「いいね！」アイコンをクリックまたは選択することは、ユーザのクライアント・システム１３０に、そのコンセプト・プロフィール・ページに関連付けられているそのコンセプトをそのユーザが気に入っているということを示すメッセージをソーシャル・ネットワーキング・システム１６０へ送信させることができる。そのメッセージに応答して、ソーシャル・ネットワーキング・システム１６０は、そのユーザとコンセプト・ノード２０４との間における「いいね！」エッジ２０６によって示されているように、そのユーザに関連付けられているユーザ・ノード２０２とコンセプト・ノード２０４との間においてエッジ２０６を作成することができる。特定の実施形態においては、ソーシャル・ネットワーキング・システム１６０は、エッジ２０６を１つまたは複数のデータ・ストア内に記憶することができる。特定の実施形態においては、エッジ２０６は、特定のユーザ・アクションに応答してソーシャル・ネットワーキング・システム１６０によって自動的に形成されることが可能である。限定ではなく、例として、第１のユーザが、画像をアップロードすること、映画を観ること、または曲を聴くことを行った場合には、エッジ２０６は、第１のユーザに対応するユーザ・ノード２０２と、それらのコンセプトに対応するコンセプト・ノード２０４との間において形成されることが可能である。本開示は、特定の様式で特定のエッジ２０６を形成することについて記述しているが、本開示は、任意の適切な様式で任意の適切なエッジ２０６を形成することを想定している。
【００４８】
先行入力工程
特定の実施形態では、１または複数のクライアント側および／またはバックエンド（サーバ側）工程は、ソーシャル・ネットワーキング・システム１６０によってホストされるまたはアクセス可能であり得る要求されたウェブページ（たとえば、ユーザ・プロフィール・ページ、コンセプト・プロフィール・ページ、検索結果ウェブページ、またはオンライン・ソーシャル・ネットワークの他の適切なページなど）と併せてレンダリングされる入力形式でユーザによって現在入力されている情報に対して、ソーシャル・グラフ要素（たとえば、ユーザ・ノード２０２、コンセプト・ノード２０４、またはエッジ２０６）をマッチさせることを自動的に試みることができる「先行入力」機能を実装し利用することができる。特定の実施形態では、ユーザが宣言を行うためにテキストを入力しているときに、先行入力機能は、宣言で入力されているテキスト文字列を、ユーザ、コンセプト、またはエッジおよびソーシャル・グラフ２００内のそれらの対応する要素に対応する文字の列（たとえば、名前、説明）に対してマッチさせることを試みることができる。特定の実施形態では、マッチングが見つかったときに、先行入力機能は、既存のソーシャル・グラフ要素のソーシャル・グラフ要素（たとえば、ノード名／タイプ、ノードＩＤ、エッジ名／タイプ、エッジＩＤ、または別の適切な参照もしくは識別子など）を参照して、フォームに自動的に投入をすることができる。
【００４９】
特定の実施形態では、ユーザが、ユーザのプロフィール・ページ、ホーム・ページ、または他のページの様々なセクションにおいてコンテンツを付加するまたは宣言を行うために使用されるフォーム内にテキストをタイプするまたは他の形式で入力する際に、先行入力工程は、ソーシャル・ネットワーキング・システム１６０において（またはその中で）（たとえば、サーバ１６２内で）実行している１つまたは複数のフロントエンド（クライアント側）および／またはバックエンド（サーバ側）先行入力工程（以下では、単に「先行入力工程」と呼ぶ）と連携して機能して、そのユーザがテキストの文字を入力する際にそのユーザによって入力されたそれらのテキストの文字に対して最も関連するまたはベスト・マッチであると決定された、既存のソーシャル・グラフ要素の名前に対応する１つもしくは複数の用語、または既存のソーシャル・グラフ要素に関連付けられた用語をフォームに自動投入することを対話形式にかつ（ユーザにとってそう見えるように）実質的に瞬時に試みることができる。ノードおよびエッジに関連付けられた情報を含めて、ソーシャル・グラフ・データベース内のソーシャル・グラフ情報、またはソーシャル・グラフ・データベースから抽出およびインデックス付けされた情報を利用して、先行入力工程は、ソーシャル・グラフ・データベースからの情報と連携して、また場合によっては、ソーシャル・ネットワーキング・システム１６０内において配置または実行されている他の様々な工程、アプリケーション、またはデータベースと連携して、ユーザの意図されている宣言を高い精度で予測することができる。しかしながら、ソーシャル・ネットワーキング・システム１６０はまた、ユーザに、自分が望む任意の宣言を実質的に入力するための自由を提供することもでき、したがって、ユーザが自分自身を自由に表現することを可能にする。
【００５０】
特定の実施形態では、ユーザがテキスト文字をフォーム・ボックスまたは他のフィールド内に入力する際に、先行入力工程は、ユーザが文字を入力している際にユーザの宣言において入力された文字の列にマッチする既存のソーシャル・グラフ要素（たとえば、ユーザ・ノード２０２、コンセプト・ノード２０４、またはエッジ２０６）を識別することを試みることができる。特定の実施形態では、ユーザが文字をフォーム・ボックス内に入力する際に、先行入力工程は、入力されたテキスト文字の列を読み取ることができる。各キーストロークが行われた際に、フロントエンド先行入力工程は、入力された文字列を、要求（またはコール）として、ソーシャル・ネットワーキング・システム１６０内で実行するバックエンド先行入力工程に送信することができる。特定の実施形態では、先行入力工程は、ＡＪＡＸ（非同期ＪａｖａＳｃｒｉｐｔおよびＸＭＬ）または他の適切な技法、特に非同期技法を介して通信を行うことができる。特定の実施形態では、要求は、結果の迅速かつ動的な送信およびフェッチを可能にする、ＸＭＬＨＴＴＰＲｅｑｕｅｓｔ（ＸＨＲ）であるか、またはＸＨＲを含むことができる。特定の実施形態では、先行入力工程は、要求の前に、要求の後に、または要求と共に、ユーザが宣言を行っている特定のページの特定のセクションを識別するセクション識別子（セクションＩＤ）を送信することもできる。特定の実施形態では、ユーザＩＤパラメータが送信されることもあるが、これは、いくつかの実施形態では、ユーザがソーシャル・ネットワーキング・システム１６０にログインしている（または他の形式で認証されている）ことに基づいてユーザが既に「知られている」ので、不要なことがある。
【００５１】
特定の実施形態では、先行入力工程は、マッチしているソーシャル・グラフ要素を識別することを試みるために１つまたは複数のマッチング・アルゴリズムを使用することができる。特定の実施形態では、１つまたは複数のマッチが見つかったとき、先行入力工程は、たとえば、マッチしているソーシャル・グラフ要素の名前（名前文字列）または説明、ならびに場合によっては、マッチしているソーシャル・グラフ要素に関連付けられた他のメタデータを含むことができる（ＡＪＡＸまたは他の適切な技法を利用することができる）応答を、ユーザのクライアント・システム１３０に送信することができる。限定ではなく例として、ユーザが文字「ｐｏｋ」（「ポｋ」）をクエリ・フィールド内に入力している場合、先行入力工程は、ドロップダウン・メニューを表示することができ、そのドロップダウン・メニューは、マッチしている既存のプロフィール・ページ、たとえば、「ｐｏｋｅｒ」（「ポーカー」）もしくは「ｐｏｋｅｍｏｎ」（「ポケモン」）という名前もしくはその専用のプロフィール・ページ、およびそれぞれのユーザ・ノード２０２またはコンセプト・ノード２０４の名前を表示し、次いで、ユーザが、それをクリックまたは他の形式で選択し、それにより、選択されたノードに対応するマッチされたユーザまたはコンセプトの名前を宣言したいという要望を確定する。限定ではなく別の例として、「ｐｏｋｅｒ」（「ポーカー」）をクリックすると、先行入力工程は、宣言「ｐｏｋｅｒ」（「ポーカー」）をクエリ・フィールドに自動投入すること、またはその自動投入をウェブ・ブラウザ１３２に行わせることが可能である。特定の実施形態では、先行入力工程は、ドロップダウン・メニューを表示するのではなく、最上位にランク付けされたマッチの名前または他の識別子をフィールドに単に自動投入することができる。次いで、ユーザは、単に自分のキーボードで「Ｅｎｔｅｒ」キーを打つことによって、またはその自動投入された宣言をクリックすることによって、その自動投入された宣言を確定することができる。
【００５２】
先行入力工程に関するさらなる情報は、２０１０年４月１９日に出願された米国特許出願第１２／７６３１６２号、および２０１２年７月２３日に出願された米国特許出願第１３／５５６０７２号に見ることができ、それらを本願明細書に援用する。
【００５３】
構造化検索クエリ（Structured Search Queries）
図３は、オンライン・ソーシャル・ネットワークの例示的ウェブページを示す。特定の実施形態では、第１のユーザ（特定のユーザ・ノード２０４に対応する「ユーザ」または「問合せユーザ（ｑｕｅｒｙｉｎｇ  ｕｓｅｒ）」とも呼ばれる）は、テキスト・クエリをクエリ・フィールド３５０内に入力することによって、ソーシャル・ネットワーク・システム１６０にクエリをサブミットすることができる。オンライン・ソーシャル・ネットワークの第１ユーザは、特定の主題（たとえば、ユーザ、コンセプト、外部コンテンツ、またはリソース）を記述する短い語句（しばしば「検索クエリ」と呼ばれる）を、検索エンジンに提供することによって、その主題に関連する情報を求めて検索することができる。そのクエリは、非構造化テキスト・クエリとすることができ、（１つまたは複数のｎ−ｇｒａｍを含むことができる）１つまたは複数のテキスト文字列を含むことができる。一般に、第１のユーザは、任意の文字列をクエリ・フィールド３５０内に入力して、テキスト・クエリにマッチするソーシャル・ネットワーキング・システム１６０上のコンテンツを求めて検索することができる。次いで、ソーシャル・ネットワーキング・システム１６０は、クエリにマッチするコンテンツを識別するために、データ・ストア１６４（または、特にソーシャル・グラフ・データベース）を検索することができる。検索エンジンは、様々な検索アルゴリズムを使用してクエリ語句に基づく検索を行って、検索クエリに関連している可能性が最も高いリソースまたはコンテンツ（たとえば、ユーザ・プロフィール・ページ、コンテンツ・プロフィール・ページ、または外部リソース）を識別する検索結果を生成することができる。検索を行うために、第１のユーザは、検索クエリを検索エンジンに入力または送信することができる。それに応答して、検索エンジンは、その検索クエリに関連している可能性が高い１つまたは複数のリソースを識別することができ、それらの各リソースは、個々に「検索結果」と呼ばれることがあり、あるいは集合的に検索クエリに対応する「（複数の）検索結果」と呼ばれることがある。識別されたコンテンツは、たとえば、ソーシャル・グラフ要素（すなわち、ユーザ・ノード２０２、コンセプト・ノード２０４、エッジ２０６）、プロフィール・ページ、外部ウェブページ、またはそれらの任意の組合せを含む場合がある。次いで、ソーシャル・ネットワーキング・システム１６０は、識別されたコンテンツに対応する検索結果を伴う検索結果ウェブページを生成し、検索結果ウェブページを第１のユーザに送信することができる。検索結果は、しばしば検索結果ウェブページ上のリンクのリストという形式で、ユーザに提示されることが可能であり、各リンクは、識別されたリソースまたはコンテンツのうちのいくつかを含む異なるウェブページに関連付けられている。特定の実施形態では、検索結果内の各リンクは、対応するウェブページが配置されている場所と、それを取り出すためのメカニズムとを指定するユニフォーム・リソース・ロケータ（ＵＲＬ）の形式であってよい。次いで、ソーシャル・ネットワーキング・システム１６０は、検索結果ウェブページを第１のユーザのクライアン���・システム１３０上のウェブ・ブラウザ１３２へ送信することができる。次いで、第１のユーザは、ＵＲＬリンクをクリックして、または検索結果ウェブページからのコンテンツを他の形式で選択して、ソーシャル・ネットワーキング・システム１６０からの、または必要に応じて外部システム（たとえば、サードパーティ・システム１７０など）からのコンテンツにアクセスすることができる。リソースは、検索クエリに対するそれらの相対的な関連度に従ってランク付けされてユーザに提示されることが可能である。また、検索結果が、第１のユーザに対するそれらの相対的な関連度に従ってランク付けされてユーザに提示されることも可能である。言い換えれば、検索結果は、問合せユーザのために、たとえば、そのユーザのソーシャル・グラフ情報、ユーザ情報、検索もしくはブラウジング履歴、またはそのユーザに関連した他の適切な情報に基づいてパーソナライズされることが可能である。特定の実施形態では、リソースのランキングは、検索エンジンによって実装されるランキング・アルゴリズムによって決定され得る。限定ではなく例として、検索クエリまたはユーザに対する関連性がより高いリソースは、検索クエリまたはユーザに対する関連性がより低いリソースよりも高くランク付けされ得る。特定の実施形態では、検索エンジンは、その検索を、オンライン・ソーシャル・ネットワーク上のリソースおよびコンテンツに限定することができる。しかしながら、特定の実施形態では、検索エンジンは、他のソース、たとえば、サードパーティ・システム１７０、インターネットもしくはワールド・ワイド・ウェブ、または他の適切なソース上のリソースまたはコンテンツを検索することもできる。本開示では特定の様式でオンライン・ソーシャル・ネットワーク１６０に問い合わせることを説明しているが、本開示は任意の適切な様式でソーシャル・ネットワーキング・システム１６０に問い合わせることを企図する。
【００５４】
特定の実施形態では、本明細書で説明されている先行入力工程は、ユーザによって入力された検索クエリに適用され得る。限定ではなく例として、ユーザがテキスト文字を検索フィールド内に入力する際に、先行入力工程は、ユーザが文字を入力している際に検索フィールドに入力された文字の列にマッチする１つまたは複数のユーザ・ノード２０２、コンセプト・ノード２０４、またはエッジ２０６を識別することを試みることができる。先行入力工程がテキスト・クエリからの文字列またはｎ−ｇｒａｍを含む要求またはコールを受け取った際、先行入力工程は、入力されたテキストにマッチしているそれぞれの名前、タイプ、カテゴリ、または他の識別子を有する既存のソーシャル・グラフ要素（すなわち、ユーザ・ノード２０２、コンセプト・ノード２０４、エッジ２０６）を識別するための検索を実行すること、またはそうした検索が実行されるようにすることが可能である。先行入力工程は、マッチしているノードまたはエッジを識別することを試みるために１つまたは複数のマッチング・アルゴリズムを使用することができる。１つまたは複数のマッチが見つかったとき、先行入力工程は、たとえば、マッチしているノードの名前（名前文字列）、ならびに場合によってはマッチしているノードに関連付けられた他のメタデータを含むことができる応答を、ユーザのクライアント・システム１３０へ送信することができる。次いで、先行入力工程は、ドロップダウン・メニュー３００を表示することができ、ドロップダウン・メニュー３００は、マッチしている既存のプロフィール・ページおよびそれぞれのユーザ・ノード２０２またはコンセプト・ノード２０４の名前を表示し、マッチしているユーザ・ノード２０２またはコンセプト・ノード２０４に接続することが可能であるマッチしているエッジ２０６の名前を表示し、次いで、ユーザが、それをクリックまたは他の形式で選択し、それにより、選択されたノードに対応するマッチされたユーザもしくはコンセプトの名前を検索したい、またはマッチしているエッジによってマッチされたユーザもしくはコンセプトに接続されたユーザもしくはコンセプトを検索したいという要望を確定することができる。代替的には、先行入力工程は、ドロップダウン・メニュー３００を表示するのではなく、最上位にランク付けされたマッチングの名前または他の識別子をフォームに単に自動投入することができる。次いで、ユーザは、単にキーボードで「Ｅｎｔｅｒ」キーを打つことによって、またはその自動投入された宣言をクリックすることによって、その自動投入された宣言を確定することができる。マッチしているノードおよびエッジをユーザが確定すると、先行入力工程は、マッチしているソーシャル・グラフ要素を含むクエリをユーザが確定したことをソーシャル・ネットワーキング・システム１６０に通知する要求を送信することができる。送信された要求に応答して、ソーシャル・ネットワーキング・システム１６０は、マッチしているソーシャル・グラフ要素を求めて、または必要に応じて、マッチしているソーシャル・グラフ要素に接続されたソーシャル・グラフ要素を求めて、ソーシャル・グラフ・データベースを自動的に（または代替的には、要求内の命令に基づいて）コールまたは他の形式で検索することができる。本開示では特定の様式で先行入力工程を検索クエリに適用することを説明しているが、本開示は任意の適切な様式で先行入力工程を検索クエリに適用することを企図する。
【００５５】
検索クエリおよび検索結果に関連して、特定の実施形態は、本願明細書に援用する２００６年８月１１日に出願された米国特許出願第１１／５０３０９３号、２０１０年１２月２２日に出願された米国特許出願第１２／９７７０２７号、および２０１０年１２月２３日に出願された米国特許出願第１２／９７８２６５号に開示された１つまたは複数のシステム、コンポーネント、要素、機能、方法、動作、または工程を利用してもよい。
【００５６】
特定の実施形態では、問合せユーザから受け取られた構造化検索クエリに応答して、ソーシャル・ネットワーキング・システム１６０が１つまたは複数の検索結果を生成することができ、各検索結果は、構造化クエリの用語にマッチしている（または実質的にマッチしている）。ソーシャル・ネットワーキング・システム１６０は、問合せユーザから構造化クエリを受け取ることができる。構造化クエリに応答して、ソーシャル・ネットワーキング・システム１６０は、構造化クエリに対応する１つまたは複数の検索結果を生成することができる。各検索結果は、プロフィール・ページへのリンク、およびプロフィール・ページ（またはそのページに対応するノード）の説明または要約を含むことができる。検索結果は、検索結果ページとして問合せユーザへ提示および送信され得る。特定の検索結果ページを生成するために使用される構造化クエリが、クエリ・フィールド３５０内に示され、構造化クエリに応答して生成される様々な検索結果が、提示される検索結果のためのフィールドに例示される。特定の実施形態では、クエリ・フィールド３５０は、ページに対するタイトル・バーの役割もすることができる。言い換えれば、タイトル・バーおよびクエリ・フィールド３５０は、実質的に検索結果ページ上の統合されたフィールドであってもよい。検索結果ページはまた、検索結果を修正するためのフィールド、および提案された検索を提供するためのフィールドを含んでもよい。検索結果を生成するとき、ソーシャル・ネットワーキング・システム１６０は、各検索結果に対する１つまたは複数のスニペット（snippet）を生成することができ、ここで、スニペットは、検索結果の対象に関するコンテキスト情報（すなわち、特定の検索結果に対応するソーシャル・グラフ・エンティティ、プロフィール・ページ、または他のコンテンツに関するコンテキスト情報）である。本開示では特定の検索結果ページを説明し示しているが、本開示は任意の適切な検索結果ページを企図する。
【００５７】
検索結果の生成に関するさらなる情報は、本願明細書に援用する２０１２年１２月３１日に出願された米国特許出願第１３／７３１９３９号に見出すことができる。
クライアント側検索テンプレート
図４は、例示的モバイル・クライアント・システム１３０を示す。本開示は、任意の適切な物理的形態を取るモバイル・クライアント・システム１３０を企図する。特定の実施形態では、モバイル・クライアント・システム１３０は、以下に説明されるようなコンピューティング・システムであり得る。限定ではなく例として、モバイル・クライアント・システム１３０は、シングルボード・コンピュータ・システム（ＳＢＣ）（たとえば、コンピュータオンモジュール（ＣＯＭ）もしくはシステムオンモジュール（ＳＯＭ）など）、ラップトップもしくはノートブック・コンピュータ・システム、携帯電話、スマートフォン、携帯情報端末（ＰＤＡ）、タブレット・コンピュータ・システム、またはこれらの複数の組合せであり得る。特定の実施形態では、モバイル・クライアント・システム１３０は、入力コンポーネントとしてタッチ・センサ１３２を有することができる。図４の例では、タッチ・センサ１３２は、モバイル・クライアント・システム１３０の前面に組み込まれている。容量性タッチ・センサの場合、送信と受信の２つのタイプの電極があり得る。これらの電極は、電気パルスを用いて送信電極を駆動し、タッチまたは近接入力によって引き起こされる受信電極からの静電容量の変化を測定するように構成されたコントローラに接続され得る。図１の例では、モバイル・クライアント・システム１３０の１つまたは複数の側面に１つまたは複数のアンテナ１３４Ａ〜Ｂを組み込むことができる。アンテナ１３４Ａ〜Ｂは、電流を電波に変換し、またその逆を行うコンポーネントである。信号の送信の際、送信機は、発振無線周波数（ＲＦ）電流をアンテナ１３４Ａ〜Ｂの端子に印加し、アンテナ１３４Ａ〜Ｂは、印加された電流のエネルギーを電磁（ＥＭ）波として放射する。信号の受信の際、アンテナ１３４Ａ〜Ｂはアンテナ１３４Ａ〜Ｂの端子で入力ＥＭ波の電力を電圧に変換する。電圧は増幅用の受信機に送信され得る。
【００５８】
特定の実施形態では、多くのモバイル・クライアント・システム１３０は、イーサネットもしくは他の有線ベースのネットワークと通信するためのアンテナ１３４Ａ〜Ｂに結合される通信コンポーネント、または、ワイヤレス・ネットワークと通信するためのワイヤレスＮＩＣ（ＷＮＩＣ）、ワイヤレス・アダプタ、たとえば、第三世代移動体通信（３Ｇ）もしくはロング・ターム・エボリューション（ＬＴＥ）ネットワークなどのセルラー・ネットワークと通信するためのＷｉ−Ｆｉネットワークもしくはモデムを含むことができる。本開示では、そのための任意の適切なネットワークおよび任意の適切な通信コンポーネント２０を企図している。限定ではなく例として、モバイル・クライアント・システム１３０は、アド・ホック・ネットワーク、パーソナル・エリア・ネットワーク（ＰＡＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、もしくはインターネットの１つまたは複数の部分、またはこれらの複数の組合せと通信することができる。これらのネットワークのうちの１つまたは複数の１つまたは複数の部分は、有線または無線であることが可能である。別の例として、モバイル・クライアント・システム１３０は、ワイヤレスＰＡＮ（ＷＰＡＮ）（たとえば、ブルートゥースＷＰＡＮなど）、Ｗｉ−Ｆｉネットワーク、ＷＩ−ＭＡＸネットワーク、セルラー電話ネットワーク（たとえば、移動通信用グローバルシステム（ＧＳＭ）ネットワーク、３Ｇ、もしくはＬＴＥネットワークなど）、または他の適切なワイヤレス・ネットワーク、あるいはこれらの複数の組合せと通信することができる。モバイル・クライアント・システム１３０は、必要に応じて、任意のこれらのネットワークに対応する任意の適切な通信コンポーネントを含むことができる。
【００５９】
図５は、例示的モバイル・クライアント・システムの例示的ＵＩを示す。特定の実施形態では、ユーザは、モバイル・クライアント・システム１３０のＵＩの検索クエリ・フィールド３５０にテキストを入力することによって、ソーシャル・ネットワーキング・システム１６０にクエリをサブミットすることができる。上述のように、オンライン・ソーシャル・ネットワークのユーザは、「検索クエリ」としばしば呼ばれる主題を記述する短い語句を検索エンジンに提供することにより、情報を求めて検索することができる。さらに、ユーザは任意の文字列を検索クエリ・フィールド３５０に入力して、テキスト・クエリとマッチするソーシャル・ネットワーキング・システム１６０上のソーシャル・グラフ・エンティティを求めて検索することができる。次いで、ソーシャル・ネットワーキング・システム１６０は、データ・ストア１６４（または特に、ソーシャル・グラフ・データベース）を検索して、クエリとマッチするソーシャル・グラフ・エンティティを識別することができる。後述するように、モバイル・クライアント・システム１３０は、ユーザによって検索クエリ・フィールド３５０内に入力されたテキスト入力に基づいて、１つまたは複数の構造化クエリを識別することができる。特定の実施形態では、識別された構造化クエリは、ドロップダウン・メニュー３００内に表示され得る。特定の実施形態では、テキスト・クエリがモバイル・クライアント・システム１３０上に記憶された文法テンプレートを使用して、所定の数の構造化クエリにマッチされない場合、テキスト・クエリは、ソーシャル・ネットワーキング・システム１６０に送ることができ、そこでは、文脈自由文法モデルを使用して、文法モデルによって生成された自然言語文字列に基づいて、提案されるクエリを生成することができる。
【００６０】
特定の実施形態では、第１のユーザ（すなわち問合せユーザ）から受け取られたテキスト・クエリに応答して、モバイル・クライアント・システム１３０は、自然言語シンタックスで与えられる１つまたは複数の構造化クエリを生成することができ、各構造化クエリは、１つまたは複数の識別されたソーシャル・グラフ要素に対応するクエリ・トークンを含む。構造化クエリは、問合せユーザが、特定のエッジ・タイプによってソーシャル・グラフ２００内で特定のユーザまたはコンセプトに接続されたコンテンツを求めて検索をすることを可能にすることができる。限定ではなく例として、モバイル・クライアント・システム１３０は、第１のユーザから非構造化テキスト・クエリを受け取ることができる。それに応答して、モバイル・クライアント・システム１３０は（たとえば、サーバ側要素検知工程を介して）、ソーシャル・グラフ２００にアクセスし、次いで、テキスト・クエリを構文解析して、テキスト・クエリからｎ−ｇｒａｍに対応するソーシャル・グラフ要素を識別することができる。次いで、モバイル・クライアント・システム１３０は、後述される、複数の文法テンプレートを含む文脈自由文法モデルなどの文法モデルにアクセスすることができる。識別されたソーシャル・グラフ要素は、文法テンプレートにおいて終端トークン（「クエリ・トークン」）として使用され得る。選択された文法テンプレートを使用して、識別されたソーシャル・グラフ要素を参照するクエリ・トークンを含む１つまたは複数の構造化されたクエリを生成することができる。これらの構造化クエリは、文法テンプレートによって生成される文字列に基づくことができ、それらが、自然言語シンタックスを使用して適切なソーシャル・グラフ要素を参照してレンダリングされるようにする。構造化クエリは、（たとえば、クライアント側先行入力工程を介して）ドロップダウン・メニュー３００に表示されることが可能であり、そこで、第１のユーザは、所望のコンテンツを求めて検索するために適切なクエリを選択することができる。本明細書で説明されている構造化クエリを使用する利点のいくつかは、限られた情報に基づいてオンライン・ソーシャル・ネットワーキングのユーザを見つけ出すこと、様々なソーシャル・グラフ要素に対するそのコンテンツの関係に基づいてオンライン・ソーシャル・ネットワークからのコンテンツの仮想インデックスを一緒にすること、または自分および／もしくは自分の友人に関連したコンテンツを見つけ出すことを含む。この工程を使用して、自然言語レンダリング工程の出力が効率的に構文解析されて、たとえば、修正されたまたは代替的な構造化されたクエリを生成することができる。さらに、この工程によって使用される規則は文法モデルから導出されるので、文法モデルの規則に対するどんな修正も即座にレンダリング工程に反映され得る。本開示では特定の様式で特定の構造化クエリを生成することを説明し示しているが、本開示は任意の適切な様式で任意の適切な構造化クエリを生成することを企図する。
【００６１】
特定の実施形態では、モバイル・クライアント・システム１３０は、（第１のユーザ・ノード２０２に対応する）問合せ／第１のユーザから、非構造化テキスト・クエリを受け取ることができる。限定ではなく例として、第１のユーザは、（１）第１のユーザの１次の友人であって、（２）スタンフォード大学（Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ）に関連付けられた（すなわち、ユーザ・ノード２０２は、エッジ２０６によって学校「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）に対応するコンセプト・ノード２０４に接続されている）他のユーザを検索したいと望むことがある。次いで、第１のユーザは、テキスト・クエリ「ｆｒｉｅｎｄｓ  Ｓｔａｎｆｏｒｄ」（「友人  スタンフォード」）を検索クエリ・フィールド３５０内に入力する。本明細書で使用される場合、非構造化テキスト・クエリへの参照とは、ユーザによって入力されたシンプルなテキスト文字列を指すことができる。テキスト・クエリは、もちろん、標準的な言語／文法規則（たとえば、英語文法）に関して構造化され得る。しかしながら、テキスト・クエリは通常、ソーシャル・グラフ要素に関しては構造化されていない。言い換えれば、単なるテキスト・クエリは通常、特定のソーシャル・グラフ要素へ埋め込まれた参照を含んでいないことになる。したがって、本明細書で使用される場合、構造化クエリとは、特定のソーシャル・グラフ要素への参照を含み、識別された要素に基づいて検索エンジンが検索を行うことを可能にするクエリを指す。さらに、テキスト・クエリは、形式的クエリ・シンタックスに関して構造化されていないことがある。言い換えれば、単純なテキスト・クエリは、必ずしも、検索エンジンによって直接実行可能なクエリ・コマンドのフォーマットではない。本開示では特定の様式で特定のクエリを受け取ることを説明しているが、本開示は任意の適切な様式で任意の適切なクエリを受け取ることを企図する。
【００６２】
特定の実施形態では、モバイル・クライアント・システム１３０は、第１のユーザ（すなわち、問合せユーザ）から受け取られた非構造化テキスト・クエリ（単に検索クエリとも呼ばれる）を構文解析して、１つまたは複数のｎ−ｇｒａｍを識別することができる。一般に、ｎ−ｇｒａｍは、テキストまたは音声の所与のシーケンスからのｎ個のアイテムの連続したシーケンスである。これらのアイテムは、テキストまたは音声のシーケンスからの文字（ｃｈａｒａｃｔｅｒｓ）、音素、音節、英字（ｌｅｔｔｅｒｓ）、単語、基底対（ｂａｓｅ  ｐａｉｒ）、プレフィックス、または他の識別可能なアイテムであってよい。ｎ−ｇｒａｍは、問合せユーザによって入力されたテキストの１つまたは複数の文字（英字、数字、句読点など）を含むことができる。サイズ１のｎ−ｇｒａｍは「ユニグラム」と呼ばれることがあり、サイズ２のｎ−ｇｒａｍは「バイグラム」または「ダイグラム」と呼ばれることがあり、サイズ３のｎ−ｇｒａｍは「トライグラム」と呼ばれることがあり、以下同様である。各ｎ−ｇｒａｍは、問合せユーザから受け取られたテキスト・クエリからの１つまたは複数の部分を含むことができる。特定の実施形態では、各ｎ−ｇｒａｍは、第１のユーザによって入力された文字列（たとえば、テキストの１つまたは複数の文字）を含むことができる。限定としてではなく例として、モバイル・クライアント・システム１３０は、テキスト・クエリ「ｆｒｉｅｎｄｓ  Ｓｔａｎｆｏｒｄ」（「友人  スタンフォード」）を構文解析して、以下のｎ−ｇｒａｍ、すなわち、ｆｒｉｅｎｄｓ（友人）；Ｓｔａｎｆｏｒｄ（スタンフォード）；ｆｒｉｅｎｄｓ  Ｓｔａｎｆｏｒｄ（友人  スタンフォード）を識別することができる。限定としてではなく別の例として、モバイル・クライアント・システム１３０は、テキスト・クエリ「ｆｒｉｅｎｄｓ  ｉｎ  ｐａｌｏ  ａｌｔｏ」（「パロアルトの友人」）を構文解析して、以下のｎ−ｇｒａｍ、すなわち、ｆｒｉｅｎｄｓ（友人）；ｉｎ（の）；ｐａｌｏ（パロ）；ａｌｔｏ（アルト）；ｆｒｉｅｎｄｓ  ｉｎ（の友人）；ｉｎ  ｐａｌｏ（パロの）；ｐａｌｏ  ａｌｔｏ（パロアルト）；ｆｒｉｅｎｄ  ｉｎ  ｐａｌｏ（パロの友人）；ｉｎ  ｐａｌｏ  ａｌｓｏ（パロアルトの）；ｆｒｉｅｎｄｓ  ｉｎ  ｐａｌｏ  ａｌｔｏ（パロアルトの友人）を識別することができる。特定の実施形態では、各ｎ−ｇｒａｍは、テキスト・クエリからのｎ個のアイテムの連続したシーケンスを含むことができる。本開示では特定の様式で特定のクエリを構文解析することを説明しているが、本開示は任意の適切な様式で任意の適切なクエリを構文解析することを企図する。
【００６３】
特定の実施形態では、モバイル・クライアント・システム１３０は、テキスト・クエリで識別された各ｎ−ｇｒａｍについて、ｎ−ｇｒａｍがソーシャル・グラフ要素に対応するかを決定するためにスコアを決定または計算することができる。スコアは、たとえば、信頼スコア、確率、質、ランキング、他の適切なタイプのスコア、またはこれらの任意の組合せであってよい。限定ではなく例として、モバイル・クライアント・システム１３０は、ｎ−ｇｒａｍがソーシャル・グラフ２００のユーザ・ノード２０２、コンセプト・ノード２０４、またはエッジ２０６などのソーシャル・グラフ要素に対応する、確率スコア（単に「確率」とも呼ばれる）を決定することができる。確率スコアは、ｎ−ｇｒａｍと特定のソーシャル・グラフ要素との間の類似度または関連性のレベルを示すことができる。確率を計算するための多くの異なる方法が存在し得る。本開示は、検索クエリ内で識別されたｎ−ｇｒａｍに対する確率スコアを計算するための任意の適切な方法を企図する。特定の実施形態では、モバイル・クライアント・システム１３０は、ｎ−ｇｒａｍが特定のソーシャル・グラフ要素に対応する確率ｐを決定することができる。確率ｐは、特定の検索クエリＸを与えられた場合に特定のソーシャル・グラフ要素ｋに対応する確率として計算され得る。言い換えれば、確率は、ｐ＝（ｋ｜Ｘ）として計算され得る。限定ではなく例として、ｎ−ｇｒａｍがソーシャル・グラフ要素に対応する確率は、ｐｉ，ｊ，ｋとして示される確率スコアとして計算され得る。入力は、テキスト・クエリＸ＝（ｘ１，ｘ２，…，ｘＮ）およびクラス（ｃｌａｓｓ）の集合であることが可能である。各（ｉ：ｊ）およびクラスｋに関して、モバイル・クライアント・システム１３０は、ｐｉ，ｊ，ｋ＝ｐ（ｃｌａｓｓ（ｘｉ，ｊ）＝ｋ｜Ｘ）を算出することができる。限定ではなく例として、ｎ−ｇｒａｍ「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）は、学校「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）＝０．７、場所「Ｓｔａｎｆｏｒｄ，  Ｃａｌｉｆｏｒｎｉａ」（「カリフォルニア州スタンフォード」）＝０．２、ユーザ「Ａｌｌｅｎ  Ｓｔａｎｆｏｒｄ」（「アレン・スタンフォード」）＝０．１のように、ソーシャル・グラフ要素に関してスコア付けされ得る。限定ではなく別の例として、ｎ−ｇｒａｍ「ｆｒｉｅｎｄｓ」（「友人」）は、ユーザ「ｆｒｉｅｎｄｓ」（「友人」）＝０．９、テレビ番組「Ｆｒｉｅｎｄｓ」（「友人」）＝０．１のように、ソーシャル・グラフ要素に関してスコア付けされ得る。特定の実施形態では、モバイル・クライアント・システム１３０は、特定のｎ−ｇｒａｍが特定のソーシャル・グラフ要素に対応する確率を決定するために、前向き後ろ向きアルゴリズムを使用することができる。テキスト・クエリ内の所与のｎ−ｇｒａｍに関して、モバイル・クライアント・システム１３０は、どの特定のソーシャル・グラフ要素が所与のｎ−ｇｒａｍに対応するかを決定するために、先行と後続の両方のｎ−ｇｒａｍを使用することができる。特定の実施形態では、識別されたソーシャル・グラフ要素は、検索エンジンによって実行可能なクエリ・コマンドを生成するために使用され得る。クエリ・コマンドは、特定の引数を受け入れる定義された関数を有する構造化されたセマンティック・クエリ（semantic query）であってよい。限定ではなく例として、テキスト・クエリ「ｆｒｉｅｎｄ  ｍｅ  ｍａｒｋ」（「友人  私  マーク」）が構文解析されて、クエリ・コマンド：ｉｎｔｅｒｓｅｃｔ（ｆｒｉｅｎｄ（ｍｅ），  ｆｒｉｅｎｄ（Ｍａｒｋ））（共通（友人（私），友人（マーク）））が形成され得る。言い換えれば、クエリは、問合せユーザ（「ｍｅ」（「私」））およびユーザ「Ｍａｒｋ」（「マーク」）に共通するソーシャル・グラフ内のノード（すなわち、友人タイプ・エッジ２０６によって問合せユーザのユーザ・ノード２０２と、友人タイプ・エッジ２０６によってユーザ「Ｍａｒｋ」（「マーク」）のユーザ・ノード２０２とに接続されたユーザ・ノード２０２）を探している。本開示ではｎ−ｇｒａｍがソーシャル・グラフ要素に対応するかどうかを特定の様式で決定することを説明しているが、本開示はｎ−ｇｒａｍがソーシャル・グラフ要素に対応するかどうかを任意の適切な様式で決定することを企図する。さらに、本開示ではｎ−ｇｒａｍがソーシャル・グラフ要素に対応するかどうかを特定のタイプのスコアを使用して決定することを説明しているが、本開示は、ｎ−ｇｒａｍがソーシャル・グラフ要素に対応するかどうかを任意の適切なタイプのスコアを使用して決定することを企図する。
【００６４】
特定の実施形態では、モバイル・クライアント・システム１３０は、エッジ閾値（ｅｄｇｅ−ｔｈｒｅｓｈｏｌｄ）確率よりも高い確率を有する１つまたは複数のエッジ２０６を識別することができる。識別されたエッジ２０６のそれぞれは、ｎ−ｇｒａｍのうちの少なくとも１つに対応することが可能である。限定ではなく例として、ｎ−ｇｒａｍは、ｐｉ，ｊ，ｋ＞ｐｅｄｇｅ−ｔｈｒｅｓｈｏｌｄである場合に、エッジｋに対応するものとして識別されるだけであり得る。さらに、識別されたエッジ２０６のそれぞれは、識別されたノードのうちの少なくとも１つに接続され得る。言い換えれば、モバイル・クライアント・システム１３０は、特定のｎ−ｇｒａｍに対応するものとして以前に識別されたユーザ・ノード２０２またはコンセプト・ノード２０４に接続されているエッジ２０６またはエッジ・タイプを識別するだけであり得る。いずれの以前に識別されたノードにも接続されていないエッジ２０６またはエッジ・タイプは、典型的には、検索クエリ内の特定のｎ−ｇｒａｍに対応する可能性が低い。これらのエッジ２０６およびエッジ・タイプをフィルタ除去または無視することによって、モバイル・クライアント・システム１３０は、関連があるソーシャル・グラフ要素を求めてソーシャル・グラフ２００をさらに効率よく検索することができる。限定ではなく例として、図２を参照すると、「ｗｅｎｔ  ｔｏ  Ｓｔａｎｆｏｒｄ」（「スタンフォードに行った」）を含むテキスト・クエリに関して、識別されたコンセプト・ノード２０４が学校「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）である場合、モバイル・クライアント・システム１３０は、「ｗｏｒｋｅｄ  ａｔ」（「勤務した」）に対応するエッジ２０６、および「ａｔｔｅｎｄｅｄ」（「通っていた」）に対応するエッジ２０６を識別することができ、それらは両方とも「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）を表すコンセプト・ノード２０４に接続されている。したがって、「ｗｅｎｔ  ｔｏ」（「行った」）というｎ−ｇｒａｍは、これらのエッジ２０６に対応するものとして識別され得る。しかしながら、同じテキスト・クエリに関して、モバイル・クライアント・システム１３０は、ソーシャル・グラフ２００内の「ｌｉｋｅ」（「「いいね」を表明する」）または「ｆａｎ」（「ファン」）に対応するエッジ２０６を識別することはできない。なぜならば、ノード「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）は、自身に接続されたそのようなエッジをまったく有していないからである。本開示ではｎ−ｇｒａｍに対応するエッジ２０６を特定の様式で識別することを説明しているが、本開示はｎ−ｇｒａｍに対応するエッジ２０６を任意の適切な様式で識別することを企図する。
【００６５】
特定の実施形態では、モバイル・クライアント・システム１３０は、ノード閾値（ｎｏｄｅ−ｔｈｒｅｓｈｏｌｄ）確率よりも高い確率を有する１つまたは複数のユーザ・ノード２０２またはコンセプト・ノード２０４を識別することができる。識別されたノードのそれぞれは、ｎ−ｇｒａｍのうちの少なくとも１つに対応することが可能である。限定ではなく例として、ｎ−ｇｒａｍは、ｐｉ，ｊ，ｋ＞ｐｎｏｄｅ−ｔｈｒｅｓｈｏｌｄである場合に、ノードｋに対応するものとして識別されるだけであり得る。さらに、識別されたユーザ・ノード２０２またはコンセプト・ノード２０４のそれぞれは、識別されたエッジ２０６のうちの少なくとも１つに接続され得る。言い換えれば、モバイル・クライアント・システム１３０は、特定のｎ−ｇｒａｍに対応するものとして以前に識別されたエッジ２０６に接続されているノードまたはノード・タイプを識別するだけであり得る。いずれの以前に識別されたエッジ２０６にも接続されていないノードまたはノード・タイプは、典型的には、検索クエリ内の特定のｎ−ｇｒａｍに対応する可能性が低い。これらのノードおよびノード・タイプをフィルタ除去または無視することによって、モバイル・クライアント・システム１３０は、関連があるソーシャル・グラフ要素を求めてソーシャル・グラフ２００をさらに効率よく検索することができる。限定ではなく例として、「ｗｏｒｋｅｄ  ａｔ  Ａｐｐｌｅ」（「アップルに勤務した」）を含むテキスト・クエリに関して、識別されたエッジ２０６が「ｗｏｒｋｅｄ  ａｔ」（「勤務した」）である場合、モバイル・クライアント・システム１３０は、ＡＰＰＬＥ，ＩＮＣ．（アップル社）という会社に対応するコンセプト・ノード２０４を識別することができ、それは、自身に接続された「ｗｏｒｋｅｄ  ａｔ」（「勤務した」）という複数のエッジ２０６を有することができる。しかしながら、同じテキスト・クエリに関して、モバイル・クライアント・システム１３０は、フルーツ・タイプ「ａｐｐｌｅ」（「アップル」）に対応するコンセプト・ノード２０４を識別することがなく、それは、自身に接続された複数の「ｌｉｋｅ」（「「いいね」を表明する」）または「ｆａｎ」（「ファン」）エッジを有することができるが、「ｗｏｒｋｅｄ  ａｔ」（「勤務した」）というエッジ接続を有することがない。特定の実施形態では、ノード閾値確率は、ユーザ・ノード２０２とコンセプト・ノード２０４に対して異なることが可能であり、これらのノード間でも異なることが可能である（たとえば、いくつかのコンセプト・ノード２０４は、他のコンセプト・ノード２０４と異なるノード閾値確率を有することがある）。限定ではなく例として、ｎ−ｇｒａｍは、ｐｉ，ｊ，ｋ＞ｐｕｓｅｒ−ｎｏｄｅ−ｔｈｒｅｓｈｏｌｄである場合、ユーザ・ノード（user-node）３０２ｋｕｓｅｒに対応するものとして識別されることが可能であり、また、ｎ−ｇｒａｍは、ｐｉ，ｊ，ｋ＞ｐｃｏｎｃｅｐｔ−ｎｏｄｅ−ｔｈｒｅｓｈｏｌｄである場合、コンセプト・ノード（concept-node）３０４ｋｃｏｎｃｅｐｔに対応するものとして識別されることが可能である。特定の実施形態では、モバイル・クライアント・システム１３０は、第１の��ーザ（すなわち、問合せユーザ）に対応するユーザ・ノード２０２の閾値分離度（threshold degree of separation）以内にあるノードだけを識別することができる。閾値分離度は、たとえば、１、２、３、またはすべてであってよい。本開示ではｎ−ｇｒａｍに対応するノードを特定の様式で識別することを説明しているが、本開示はｎ−ｇｒａｍに対応するノードを任意の適切な様式で識別することを企図している。
【００６６】
特定の実施形態では、モバイル・クライアント・システム１３０は、複数の文法テンプレートにアクセスすることができる。各文法テンプレートは、１つもしくは複数の非終端トークン（non-terminal token）（または「非終端シンボル」）、および１つもしくは複数の終端トークン（または「終端シンボル」／「クエリ・トークン」）を含むことができ、特定の非終端トークンは、終端トークンと置換されることが可能である。文法モデルは、形式言語における文字列に関する形成規則のセットである。本開示では特定の文法テンプレートにアクセスすることを説明しているが、本開示は任意の適切な文法を企図する。
【００６７】
特定の実施形態では、モバイル・クライアント・システム１３０は、１つまたは複数の文法テンプレートを使用して１つまたは複数の文字列を生成することができる。非終端シンボルは、終端シンボル（すなわち、終端トークンまたはクエリ・トークン）と置換されることが可能である。クエリ・トークンのうちのいくつかは、前述のように、識別されたノードまたは識別されたエッジに対応することが可能である。そして、文法テンプレートによって生成された文字列は、識別されたノードまたは識別されたエッジに対する参照を含む構造化クエリのための基礎として使用されることが可能である。文法によって生成された文字列は、自然言語シンタックスでレンダリングされ、したがって、その文字列に基づく構造化クエリも自然言語でレンダリングされ得る。文脈自由文法は、各生成規則の左側が単一の非終端シンボルのみから構成されている文法である。確率的文脈自由文法は、タプル〈Σ，Ｎ，Ｓ，Ｐ〉であり、ここで、互いに素な集合ΣおよびＮは、それぞれ終端シンボルおよび非終端シンボルを指定し、Ｓ∈Ｎは、開始シンボルである。Ｐは、生成の集合であり、それらは、Ｅ→ξ（ｐ）という形式を取り、Ｅ∈Ｎ、ξ∈（Σ∪Ｎ）＋、およびｐ＝Ｐｒ（Ｅ→ξ）であり、ｐは、Ｅが文字列ξへ展開される確率である。所与の非終端Ｅのすべての展開にわたる確率ｐの合計は、１でなければならない。本開示では特定の様式で文字列を生成することを説明しているが、本開示は任意の適切な様式で文字列を生成することを企図する。
【００６８】
特定の実施形態では、モバイル・クライアント・システム１３０は、以前に識別されたノードおよびエッジに対応する１つまたは複数のクエリ・トークンを識別することができる。言い換えれば、識別されたノードまたは識別されたエッジが特定の文法テンプレートにおいてクエリ・トークンとして使用されることが可能である場合、クエリ・トークンがモバイル・クライアント・システム１３０によって識別されることが可能である。限定ではなく例として、例示的な文法テンプレートは、［ｕｓｅｒ］［ｕｓｅｒ−ｆｉｌｔｅｒ］［ｓｃｈｏｏｌ］（［ユーザ］［ユーザ・フィルタ］［学校］）であってよい。次いで、受け取られたテキスト・クエリ内のｎ−ｇｒａｍに基づいて、非終端トークン［ｕｓｅｒ］（［ユーザ］）、［ｕｓｅｒ−ｆｉｌｔｅｒ］（［ユーザ・フィルタ］）、および［ｓｃｈｏｏｌ］（［学校］）が決定され得る。テキスト・クエリ「ｆｒｉｅｎｄｓ  Ｓｔａｎｆｏｒｄ」（「友人  スタンフォード」）に関して、このクエリは、文法テンプレートを使用することによって、たとえば、「［ｆｒｉｅｎｄｓ］［ｗｈｏ  ｇｏ  ｔｏ］［Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ］」（「［スタンフォード大学］［に通っている］［友人］」）、または「［ｆｒｉｅｎｄｓ］［ｗｈｏ  ｗｏｒｋ  ａｔ］［Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ］」（「［スタンフォード大学］［に勤務している］［友人］」）として構文解析され得る。限定ではなく別の例として、例示的文法テンプレートは、［ｕｓｅｒ］［ｕｓｅｒ−ｆｉｌｔｅｒ］［ｌｏｃａｔｉｏｎ］（［ユーザ］［ユーザ・フィルタ］［場所］）であってよい。テキスト・クエリ「ｆｒｉｅｎｄｓ  Ｓｔａｎｆｏｒｄ」（「友人  スタンフォード」）に関して、このクエリは、文法テンプレートを使用することによって、たとえば、「［ｆｒｉｅｎｄｓ］［ｗｈｏ  ｌｉｖｅ  ｉｎ］［Ｓｔａｎｆｏｒｄ，  Ｃａｌｉｆｏｒｎｉａ］」（「［カリフォルニア州スタンフォード］［に住んでいる］［友人］」）として構文解析され得る。上述の例示的なケースの両方において、受け取られたテキスト・クエリのｎ−ｇｒａｍがクエリ・トークンとして使用されることが可能である場合、これらのクエリ・トークンはモバイル・クライアント・システム１３０によって識別され得る。本開示では特定の様式で特定のクエリ・トークンを識別することを説明しているが、本開示は任意の適切な様式で任意の適切なクエリ・トークンを識別することを企図する。
【００６９】
特定の実施形態では、ユーザが検索クエリ・フィールド３５０内に１つまたは複数のテキスト文字を入力したとき、モバイル・クライアント・システム１３０上で実行されるプログラムまたはアプリケーションが、テキスト文字を、モバイル・クライアント・システム１３０上に予めロードされた文法テンプレートに対してマッチングすることができる。後述するように、次いで、モバイル・クライアント・システム１３０は、モバイル・クライアント・システム１３０のデータ・ストアを検索して、１つまたは複数のクエリのマッチングを決定するために、文法テンプレートにアクセスすることができる。限定ではなく例として、モバイル・クライアント・システム１３０上で実行されるアプリケーションは、各キーストロークの後に、入力されたテキスト文字の文法テンプレートに対するマッチングを行うことができる。別の例として、入力されたテキストは、上述の１つまたは複数のｎ−ｇｒａｍになるように構文解析され得る。特定の実施形態では、マッチングは、クライアント側先行入力工程の一部であってよい。特定の実施形態では、モバイル・クライアント・システム１３０は、入力テキストを、１つまたは複数の文法テンプレート、またはモバイル・クライアント・システム１３０上に記憶されたソーシャル・グラフ・エンティティを識別するデータに対してマッチさせることに少なくとも部分的に基づいて、１つまたは複数の構造化クエリを識別することができる。
【００７０】
特定の実施形態では、モバイル・クライアント・システム１３０は、以前に識別されたノードおよびエッジのそれぞれに対応する少なくとも１つのクエリ・トークンを有する１つまたは複数の文法テンプレートを選択することができる。テキスト・クエリにおいて識別されたｎ−ｇｒａｍに応じて、特定の文法テンプレートのみが使用され得る。したがって、すべての使用可能な文法テンプレートの終端トークンが、テキスト・クエリから、識別されたｎ−ｇｒａｍにマッチするものを見つけるために検査されるべきである。言い換えれば、特定の文法テンプレートが、識別されたノードおよびエッジのすべてをクエリ・トークンとして使用できる場合、その文法テンプレートは、モバイル・クライアント・システム１３０によって、構造化クエリを生成するために使用することが可能な文法テンプレートとして選択され得る。これは、実質的にボトムアップ構文解析の一種であり、クエリに適用するための適用可能な文法テンプレートを決定するために、可能なクエリ・トークンが使用される。限定ではなく例として、テキスト・クエリ「ｆｒｉｅｎｄｓ  Ｓｔａｎｆｏｒｄ」（「友人  スタンフォード」）に関して、モバイル・クライアント・システム１３０は、［ｆｒｉｅｎｄｓ］（［友人］）および［Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ］（［スタンフォード大学］）のクエリ・トークンを識別することができる。文法テンプレートの終端トークンは、前に論じたように識別され得る。次いで、［ｆｒｉｅｎｄｓ］（［友人］）および［Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ］（［スタンフォード大学］）トークンの両方を使用できる任意の文法テンプレートが選択され得る。たとえば、文法テンプレート［ｕｓｅｒ］［ｕｓｅｒ−ｆｉｌｔｅｒ］［ｓｃｈｏｏｌ］（［ユーザ］［ユーザ・フィルタ］［学校］）が選択され得る。なぜならば、この文法テンプレートは、文字列「ｆｒｉｅｎｄｓ  ｗｈｏ  ｇｏ  ｔｏ  Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学に通っている友人」）または「ｆｒｉｅｎｄｓ
ｗｈｏ  ｗｏｒｋ  ａｔ  Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学に勤務している友人」）を形成することなどによって、［ｆｒｉｅｎｄｓ］（［友人］）および［Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ］（［スタンフォード大学］）トークンをクエリ・トークンとして使用し得るからである。したがって、受け取られたテキスト・クエリのｎ−ｇｒａｍが文法テンプレートにおけるクエリ・トークンとして使用できる場合、これらの文法テンプレートはモバイル・クライアント・システム１３０によって選択され得る。同様に、受け取られたテキスト・クエリが文法内のクエリ・トークンとして使用できないｎ−ｇｒａｍを含む場合、その文法は選択されることがない。本開示では特定の様式で特定の文法テンプレートを選択することを説明しているが、本開示は任意の適切な様式で任意の適切な文法テンプレートを選択することを企図する。
【００７１】
特定の実施形態では、モバイル・クライアント・システム１３０は、各選択された文法テンプレートに対するスコアを決定することができる。スコアは、たとえば、信頼スコア、確率、質、ランキング、他の適切なタイプのスコア、またはこれらの任意の組合せであってよい。スコアは、選択された文法に関連付けられた個々のスコアまたは確率に基づいてよい。文法は、それが相対的に高い個々のスコアを有するクエリ・トークンを使用している場合、より高い相対的スコアを有することができる。限定ではなく例として、先の例を続けると、ｎ−ｇｒａｍ「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）は、学校「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）＝０．７、場所「Ｓｔａｎｆｏｒｄ，  Ｃａｌｉｆｏｒｎｉａ」（「カリフォルニア州スタンフォード」）＝０．２、ユーザ「Ａｌｌｅｎ  Ｓｔａｎｆｏｒｄ」（「アレン・スタンフォード」）＝０．１のように、ソーシャル・グラフ要素に関してスコア付けされ得る。ｎ−ｇｒａｍ「ｆｒｉｅｎｄｓ」（「友人」）は、ユーザ「ｆｒｉｅｎｄｓ」（「友人」）＝０．９、テレビ番組「Ｆｒｉｅｎｄｓ」（「友人」）＝０．１のように、ソーシャル・グラフ要素に関してスコア付けされ得る。したがって、文法テンプレート［ｕｓｅｒ］［ｕｓｅｒ−ｆｉｌｔｅｒ］［ｓｃｈｏｏｌ］（［ユーザ］［ユーザ・フィルタ］［学校］）は、相対的に高い個々のスコアを両方が有しているユーザ「ｆｒｉｅｎｄｓ」（「友人」）および学校「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）についてクエリ・トークンを使用する（たとえば、文字列「ｆｒｉｅｎｄｓ  ｗｈｏ  ｇｏ  ｔｏ  Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学に通っている友人」）を生成する）場合には、相対的に高いスコアを有することができる。対照的に、文法［ｕｓｅｒ］［ｕｓｅｒ−ｆｉｌｔｅｒ］［ｕｓｅｒ］（［ユーザ］［ユーザ・フィルタ］［ユーザ］）は、ユーザ「ｆｒｉｅｎｄｓ」（「友人」）およびユーザ「Ａｌｌｅｎ  Ｓｔａｎｆｏｒｄ」（「アレン・スタンフォード」）を表すクエリ・トークンを使用する（たとえば、文字列「ｆｒｉｅｎｄｓ  ｏｆ  Ａｌｌｅｎ  Ｓｔａｎｆｏｒｄ」（「アレン・スタンフォードの友人」）を生成する）場合には、後者のクエリ・トークンは相対的に低い個々のスコアを有するので、相対的に低いスコアを有することができる。本開示では特定の様式で特定の文法に関する特定のスコアを決定することを説明しているが、本開示は任意の適切な様式で任意の適切な文法に関する任意の適切なスコアを決定することを企図する。
【００７２】
特定の実施形態では、モバイル・クライアント・システム１３０は、問合せユーザ（すなわち、第１のユーザ・ノード２０２に対応する第１のユーザ）に対する、文法テンプレートのクエリ・トークンに対応するソーシャル・グラフ要素の関連性に基づいて、選択された文法テンプレートに関するスコアを決定することができる。エッジ２０６によって直接的に第１のユーザ・ノード２０２に接続されたユーザ・ノード２０２およびコンセプト・ノード２０４は、第１のユーザに関連があるとみなされることが可能である。したがって、これらの関連があるノードおよびエッジに対応するクエリ・トークンを含む文法テンプレートは、問合せユーザとより関連があるとみなされることが可能である。限定ではなく例として、エッジ２０６によって第１のユーザ・ノード２０２に接続されたコンセプト・ノード２０４は、第１のユーザ・ノード２０２に関連があるとみなされることが可能である。本明細書で使用される場合、ソーシャル・グラフ２００を参照するときに、用語「接続された」は、２つのノードの間のソーシャル・グラフ２００内に経路が存在することを意味し、この経路は、１または複数のエッジ２０６ならびに０個以上の中間ノードを含むことができる。特定の実施形態では、１または複数の介在ノード（および、したがって２以上のエッジ２０６）を通じて第１のユーザ・ノード２０２に接続されたノードも、第１のユーザに関連があるとみなされることが可能である。さらに、特定の実施形態では、第２のノードが第１のユーザ・ノードに近いほど、第２のノードは第１のユーザ・ノードと関連性が高いとみなされることが可能である。すなわち、第１のユーザ・ノード２０２を特定のユーザ・ノード２０２またはコンセプト・ノード２０４から隔てるエッジ２０６が少ないほど（すなわち、分離度が小さいほど）、ユーザ・ノード２０２またはコンセプト・ノード２０４と第１のユーザとの関連性は高いとみなされることが可能である。限定ではなく例として、図２に示すように、学校「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）に対応するコンセプト・ノード２０４は、ユーザ「Ｃ」に対応するユーザ・ノード２０２に接続されており、したがって、コンセプト「Ｓｔａｎｆｏｒｄ」（「スタンフォード」）は、ユーザ「Ｃ」に関連があるとみなされることが可能である。限定ではなく別の例として、ユーザ「Ａ」に対応するユーザ・ノード２０２は、１つの中間ノードおよび２つのエッジ２０６（すなわち、ユーザ「Ｂ」に対応する中間ユーザ・ノード２０２）を介して、ユーザ「Ｃ」に対応するユーザ・ノード２０２に接続されており、したがって、ユーザ「Ａ」はユーザ「Ｃ」に関連があるとみなされることが可能であるが、ユーザ「Ａ」のユーザ・ノード２０２はユーザ「Ｃ」に関して２次接続であるため、その特定のコンセプト・ノード２０４は、単一のエッジ２０６によって、ユーザ「Ｃ」のユーザ・ノードに接続されたユーザ・ノード２０２、たとえば、ユーザ「Ｂ」に対応するユーザ・ノード２０２などよりも関連性が低いとみなされることが可能である。限定ではなくさらに別の例として、（オンライン・マルチプレーヤ・ゲームに対応し得る）「Ｏｎｌｉｎｅ  Ｐｏｋｅｒ」（「オン���イン・ポーカー」）のコンセプト・ノードは、ソーシャル・グラフ２００内のいずれの経路によっても、ユーザ「Ｃ」のユーザ・ノードに接続されておらず、したがって、コンセプト「Ｏｎｌｉｎｅ  Ｐｏｋｅｒ」（「オンライン・ポーカー」）はユーザ「Ｃ」に関連があるとみなされないことが可能である。特定の実施形態では、第２のノードは、第１のユーザ・ノード２０２の閾値分離度以内にある場合に、第１のユーザに関連があるとみなされることのみが可能である。限定ではなく例として、閾値分離度が３である場合、ユーザ「Ｄ」に対応するユーザ・ノード２０２は、レシピ「Ｃｈｉｃｋｅｎ  Ｐａｒｍｅｓａｎ」（「チキン・パルメザン」）に対応するコンセプト・ノード２０４に関連があるとみなされることが可能であり、それらは、図２に示されているソーシャル・グラフ２００上で互いから３次以内にある。しかしながら、この例を続けると、アプリケーション「Ａｌｌ  Ａｂｏｕｔ  Ｒｅｃｉｐｅｓ」（「レシピのすべて」）に対応するコンセプト・ノード２０４は、これらのノードがソーシャル・グラフ２００内で４次離れているため、ユーザ「Ｄ」に対応するユーザ・ノード２０２に関連があるとみなされない。本開示では特定のソーシャル・グラフ要素同士（ひいては、それらの対応するクエリ・トークン同士）が互いに関連があるかどうかを特定の様式で決定することを説明しているが、本開示は、任意の適切なソーシャル・グラフ要素同士が互いに関連があるかどうかを任意の適切な様式で決定することを企図する。さらに、本開示ではユーザ・ノード２０２およびコンセプト・ノード２０４に対応する特定のクエリ・トークンが問合せユーザに関連があるかどうかを決定することを説明しているが、本開示は、任意の適切なクエリ・トークン（ひいては、任意の適切なノード）が他の任意の適切なユーザに関連があるかどうかも同様に決定することを企図する。
【００７３】
特定の実施形態では、モバイル・クライアント・システム１３０は、選択された文法テンプレートに関するスコアを、その文法のクエリ・トークンに対応するソーシャル・グラフ情報に基づいて決定することができる。限定ではなく例として、ｎ−ｇｒａｍが特定のソーシャル・グラフ要素に対応する確率ｐを決定するとき、その確率の計算はソーシャル・グラフ情報を考慮に入れることもできる。したがって、特定の検索クエリＸおよびソーシャル・グラフ情報Ｇが与えられると、特定のソーシャル・グラフ要素ｋに対応する確率がｐ＝（ｋ｜Ｘ，Ｇ）として計算されてもよい。次いで、それらのソーシャル・グラフ要素をクエリ・トークンとして使用して文法テンプレートに関するスコアを決定するために、識別されたノードおよびエッジに関する個々の確率が使用されてよい。特定の実施形態では、選択された文法に対するスコアは、第１のユーザ・ノード２０２と、文法テンプレートにおいてクエリ・トークンとして使用される特定のソーシャル・グラフ要素との間の分離度に基づくことができる。ソーシャル・グラフ２００内で問合せユーザにより近い（すなわち、要素と第１のユーザ・ノード２０２との間の分離度がより小さい）ソーシャル・グラフ要素に対応するクエリ・トークンを有する文法テンプレートは、ユーザからより遠いソーシャル・グラフ要素に対応するクエリ・トークンを使用する文法よりも高くスコア付けされ得る（すなわち、分離度がより大きい）。限定ではなく例として、図２を参照すると、ユーザ「Ｂ」がテキスト・クエリ「ｃｈｉｃｋｅｎ」（「チキン」）を入力した場合、エッジ２０６によってユーザ「Ｂ」に接続されたレシピ「Ｃｈｉｃｋｅｎ  Ｐａｒｍｅｓａｎ」（「チキン・パルメザン」）のコンセプト・ノード２０４に対応するクエリ・トークンを有する文法は、ソーシャル・グラフ２００内でユーザ「Ｂ」に接続されていないチキンというｎ−ｇｒａｍに関連付けられた他のノード（たとえば、「ｃｈｉｃｋｅｎ  ｎｕｇｇｅｔｓ」（「チキン・ナゲット」）または「ｆｕｎｋｙ  ｃｈｉｃｋｅｎ  ｄａｎｃｅ」（「ファンキー・チキン・ダンス」）に対応するコンセプト・ノード２０４）に対応するクエリ・トークンを有する文法テンプレートよりも相対的に高いスコアを有することができる。特定の実施形態では、選択された文法テンプレート対するスコアは、文法テンプレートのクエリ・トークンに対応する識別されたエッジ２０６に基づくことができる。モバイル・クライアント・システム１３０が、受け取られたテキスト・クエリ内のｎ−ｇｒａｍに対応する１つまたは複数のエッジを既に識別している場合、それらの識別されたエッジは、文法テンプレートによるテキスト・クエリの特定の構文解析に関するスコアを決定する際に考慮され得る。特定の文法テンプレートが、識別されたノードと識別されたエッジの両方に対応するクエリ・トークンを含む場合に、識別されたノードが、識別されたエッジのうちのいずれにも実際に接続されていないならば、その特定の文法テンプレートは、ゼロまたはヌル・スコアを割り当てられることが可能である。特定の実施形態では、選択された文法テンプレートに対するスコアは、文法テンプレートのクエリ・トークンに対応���るノードに接続されたエッジ２０６の数に基づくことができる。より多くの接続しているエッジ２０６を伴うノードに対応するクエリ・トークンを含む文法テンプレートは、より人気があり、検索クエリのターゲットである可能性が高いことがある。限定ではなく例として、「Ｓｔａｎｆｏｒｄ，  Ｃａｌｉｆｏｒｎｉａ」（「カリフォルニア州スタンフォード」）のコンセプト・ノード２０４が、５個のエッジによって接続されているだけであり、その一方で「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）のコンセプト・ノード２０４が、５０００個のエッジによって接続されている場合には、これらのノードのいずれかに対応するクエリ・トークンを含む文法に関するスコアを決定するときに、モバイル・クライアント・システム１３０は、「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）のコンセプト・ノード２０４に対応するクエリ・トークンを有する文法テンプレートが、「Ｓｔａｎｆｏｒｄ，  Ｃａｌｉｆｏｒｎｉａ」（「カリフォルニア州スタンフォード」）のコンセプト・ノード２０４を参照する文法テンプレートよりも相対的に高いスコアを有するということを決定することができ、その理由は、前者のコンセプト・ノード２０４に接続されたエッジの数の方が多いからである。特定の実施形態では、選択された文法に対するスコアは、第１のユーザ（すなわち、問合せユーザ）に関連付けられた検索履歴に基づくことができる。第１のユーザが以前にアクセスしたノード、または第１のユーザが以前にアクセスしたノードに関連があるノードに対応するクエリ・トークンを有する文法テンプレートは、第１のユーザの検索クエリのターゲットである可能性が高いことがある。したがって、これらの文法テンプレートは、より高いスコアを与えられてよい。限定ではなく例として、第１のユーザが以前に「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）のプロフィール・ページを訪れたことがあるが、「Ｓｔａｎｆｏｒｄ，  Ｃａｌｉｆｏｒｎｉａ」（「カリフォルニア州スタンフォード」）のプロフィール・ページを訪れたことがまったくない場合、これらのコンセプトに対応するクエリ・トークンを有する文法テンプレートに対するスコアを決定するとき、モバイル・クライアント・システム１３０は、「Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ」（「スタンフォード大学」）のコンセプト・ノード２０４が、ひいては、対応するクエリ・トークンを使用する文法テンプレートが、相対的に高いスコアを有するということを決定することができる。なぜならば、問合せユーザが、その学校を表すコンセプト・ノード２０４に以前にアクセスしたことがあるからである。限定ではなく別の例として、第１のユーザが以前にテレビ番組「Ｆｒｉｅｎｄｓ」（「友人」）に関するコンセプト・プロフィール・ページを訪れたことがある場合、そのコンセプトに対応するクエリ・トークンを有する文法テンプレートに対するスコアを決定するとき、モバイル・クライアント・システム１３０は、テレビ番組「Ｆｒｉｅｎｄｓ」（「友人」）に対応するコンセプト・ノード２０４が、ひいては、対応するクエリ・トークンを使用する文法テ��プレートが、相対的に高いスコアを有するということを決定することができる。なぜならば、問合せユーザが、そのテレビ番組のコンセプト・ノード２０４に以前にアクセスしたことがあるからである。本開示では特定の様式で特定のソーシャル・グラフ情報に基づいて特定の文法テンプレートに関するスコアを決定することを説明しているが、本開示は、任意の適切な様式で任意の適切なソーシャル・グラフ情報に基づいて任意の適切な文法テンプレートに関するスコアを決定することを企図する。
【００７４】
図６〜８は、テキスト入力を文法テンプレートおよびソーシャル・グラフ・エンティティに対してマッチングするための例示的コスト計算のグラフ表現を示す。特定の実施形態では、モバイル・クライアント・システム１３０は、１つまたは複数の文法テンプレートまたは記憶されたソーシャル・グラフ要素を選択することに基づいて、１つまたは複数の構造化クエリを生成することができる。本明細書では、クエリまたは終端トークンに対する参照は、１つまたは複数の識別されたソーシャル・グラフ要素を指すことができる。本明細書では、非終端トークンに対する参照は、１つまたは複数のソーシャル・グラフ要素に対してマッチされ得る構造化クエリのトークンを指すことができる。特定の実施形態では、１つまたは複数の文法テンプレートが、自然言語文字列に基づくことができ、モバイル・クライアント・システム１３０のデータ・ストアに記憶され得る。各記憶されたソーシャル・グラフ・エンティティのタイプが、１つまたは複数の文法テンプレートの特定の非終端トークンに対する記憶されたソーシャル・グラフ・エンティティの関連性を決定するために使用され得る。特定の実施形態では、モバイル・クライアント・システム１３０は、テキスト・クエリ内で識別されたｎ−ｇｒａｍに関係して各文法テンプレートに対するコストを計算することに少なくとも部分的に基づいて、１つまたは複数の文法テンプレートを選択することができる。上述のように、文法テンプレートは、１つまたは複数の非終端トークン、および１つまたは複数の（クエリ・トークンとも呼ばれる）終端トークンを含むことができる。たとえば、文法テンプレート「Ｐｈｏｔｏｓ  ｏｆ  ［ｕｓｅｒ］  ｉｎ  ［ｃｉｔｙ］」（「［都市］における［ユーザ］のフォト」）に関して、非終端トークンは、［ｕｓｅｒ］（［ユーザ］）および［ｃｉｔｙ］（［都市］）であり、クエリ・トークンは、「Ｐｈｏｔｏｓ  ｏｆ」（［のフォト］）および「ｉｎ」（［における］）である。非終端トークンは、ソーシャル・グラフ・エンティティにマッチされることがあり、それらのマッチしているエンティティに対する参照は、完成された構造化クエリ（たとえば、「Ｐｈｏｔｏｓ  ｏｆ  Ｊｕｓｔｉｎ  ｉｎ  Ｓａｎ  Ｆｒａｎｃｉｓｃｏ」（「サンフランシスコにおけるジャスティンのフォト」））を形成するために、文法テンプレートに挿入され得る。特定の実施形態では、非終端トークンに対してクエリ・トークンとしてマッチされたｎ−ｇｒａｍは、コスト計算において関連付けられた挿入コストを発生することがない。限定ではなく例として、ｎ−ｇｒａｍ「ｍ」は、クエリ・トークン［ｍｙ］（［私の］）に対するｎ−ｇｒａｍ「ｍ」内の文字「ｍ」の部分的文字マッチングに少なくとも部分的に基づいて、クエリ・トークン［ｍｙ］（［私の］）にマッチされ得る。そうではなく、文法テンプレートの特定の非終端トークンがテキスト文字のいずれにもマッチしないとき、コスト計算における特定の非終端トークンに関連付けられた挿入コストが発生する。特定の実施形態では、所定の数のソーシャル・グラフ・エンティティがモバイル・クライアント・システム１３０上に記憶されてよく、各記憶されたソーシャル・グラフ・エン���ィティは、文法テンプレートのうちの１つまたは複数のクエリ・トークンに対応し得る。さらに、モバイル・クライアント・システム１３０上にソーシャル・グラフ・エンティティを記憶することは、ソーシャル・グラフを識別するデータ（たとえば、ソーシャル・グラフ・エンティティを記述するテキスト文字列またはタイトル）、特定のシステムに対してソーシャル・グラフ・エンティティを一意に識別するデータ（たとえば、識別番号または文字列）、ソーシャル・グラフ・エンティティに関連付けられたタイプ（たとえば、ユーザまたはイベント）、あるいはこれらの任意の組合せを含むことができる。たとえば、特定のシステムに対してソーシャル・グラフ・エンティティを一意に識別するデータは、ソーシャル・グラフ・エンティティを参照する識別文字列またはリンクを含むことができる。本開示では特定の様式で構造化クエリを生成することを説明しているが、本開示は任意の適切な様式で構造化クエリを生成することを企図する。
【００７５】
特定の実施形態では、モバイル・クライアント・システム１３０上に記憶されたソーシャル・グラフ・エンティティは、ソーシャル・グラフ・エンティティの特定のタイプ（たとえば、人気のあるエンティティ）を予め選択することによって決定され得る。例として、モバイル・クライアント・システム１３０上に記憶された各ユーザのソーシャル・グラフ・エンティティは、ユーザの友人、ユーザのページ、ユーザのグループ、ユーザのイベント、モバイル・クライアント・システム１３０上でユーザによってインストールされたアプリケーション、またはこれらの任意の組合せに対応することができる。たとえば、ユーザのページは、ユーザに関連付けられたエンティティ、たとえば、ユーザの出身地、出身校、雇用主などを含むことができる。特定の実施形態では、所定の数のソーシャル・グラフ・エンティティは、１次のソーシャル・グラフ・エンティティ（たとえば、エッジ２０６によってユーザのユーザ・ノード２０２に接続されたコンセプト・ノード２０４もしくはユーザ・ノード２０２）、または各ユーザの高係数エンティティであってよい。
【００７６】
特定の実施形態では、文法テンプレートは、自然言語文字列、たとえば、「ｆｒｉｅｎｄｓ  ｏｆ  ［ｕｓｅｒ］」（「［ユーザ］の友人」）または「ｆｒｉｅｎｄｓ  ｗｈｏ  ｌｉｖｅ  ｎｅａｒ  ［ｃｉｔｙ］」（「［都市］の近くに住んでいる友人」）などに基づくことができる。モバイル・クライアント・システム１３０のデータ・ストアに記憶された１つまたは複数の文法テンプレートは、（たとえば、人気のあるグラフ検索クエリのデコンストラクションを介して）ソーシャル・ネットワーキング・システム１６０上で実行される検索クエリの分析に少なくとも部分的に基づいて識別／構築されてもよい。限定ではなく例として、所定数の最も人気のある検索クエリを識別するために、ソーシャル・ネットワーキング・システム１６０上の検索クエリのログが分析されてもよい。別の例として、識別された検索クエリのランキングが、各ユーザの検索クエリ履歴に少なくとも部分的に基づいて、ユーザごとにパーソナライズされてもよい。特定の実施形態では、識別された検索クエリは、検索クエリに関連付けられる１つまたは複数のソーシャル・グラフ・エンティティなしに、自然言語文字列として文法テンプレートに変換されてよく、それは、代わりに文法テンプレートにおける非終端トークンと置換され得る。
【００７７】
特定の実施形態では、各記憶されたソーシャル・グラフ・エンティティのタイプが、１つまたは複数の文法テンプレートの特定の非終端トークンに対する記憶されたソーシャル・グラフ・エンティティの関連性を決定するために使用され得る。限定ではなく例として、文法テンプレート「Ｐｈｏｔｏｓ  ｏｆ  ［ｕｓｅｒ］」（「［ユーザ］のフォト」）に関連する記憶されたソーシャル・グラフ・エンティティのタイプは、ユーザの友人に対応するタイプであってよい。別の例として、非終端トークン［ｌｏｃａｔｉｏｎ］（［場所］）に関連するソーシャル・グラフ・エンティティのタイプは、ユーザのページ（たとえば出身地）に対応するタイプであってよい。さらに、ソーシャル・グラフ・エンティティに関連付けられた文法テンプレートおよびデータは、ユーザが検索クエリ・フィールド３５０内にテキストを入力する前に、モバイル・クライアント・システム１３０に送られて予めロードされることが可能である。特定の実施形態では、各ユーザについての予め定められた文法テンプレートおよびソーシャル・グラフ・エンティティが、所定の間隔（たとえば１週間に１回）でソーシャル・ネットワーキング・システム１６０によって再評価および更新され得る。限定ではなく例として、ソーシャル・ネットワーキング・システム１６０は、所定の間隔で、ソーシャル・グラフ・エンティティを識別する更新された文法テンプレートまたはデータを、モバイル・クライアント・システム１３０に送ることができる。
【００７８】
特定の実施形態では、モバイル・クライアント・システム１３０のクライアント側先行入力工程は、各記憶された文法テンプレートに関連付けられたコストを計算することに少なくとも部分的に基づいて、テキスト入力にマッチしている１つまたは複数の構造化クエリを識別することができる。限定ではなく例として、各記憶された文法テンプレートは、基本コストを有してもよい。さらに、各記憶された文法テンプレートの基礎となるコストは、各予め定められた文法テンプレートの基礎である検索クエリの人気度（popularity）に反比例してもよい。言い換えれば、より人気のある検索クエリから導出された文法テンプレートは、関連付けられた基本コストがより低いことが可能である。特定の実施形態では、各文法テンプレートの各非終端トークンは、関連付けられた挿入コストを有することがある。限定ではなく例として、各非終端トークンの挿入コストは、関連付けられた予め定められた文法テンプレートに対する特定の非終端トークンによって提供される差別化の量に関係付けられ得る。たとえば、文法テンプレート「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）の場合、「ｆｒｉｅｎｄｓ」（「友人」）に対応する終端トークンは、より高い挿入コストを有することがあるのに対し、「ｏｆ」（「の」）または「ｍｙ」（「私の」）に対応するトークンは、より一般的とみなされ、特定の文法テンプレートを識別することへの寄与がより少ないことがある。特定の実施形態では、非終端トークンに対してクエリ・トークンとしてマッチされたｎ−ｇｒａｍは、コスト計算において関連付けられた挿入コストを発生することがない。しかしながら、文法テンプレートの特定の非終端トークンがテキスト文字のいずれにもマッチしないとき、コスト計算においてその特定の非終端トークンに関連付けられた挿入コストが発生する。特定の実施形態では、特定の非終端トークンに関連付けられた１つまたは複数のソーシャル・グラフ・エンティティのそれぞれが、関連付けられた挿入コストを有してよい。
【００７９】
限定ではなく例として、検索クエリ・フィールド３５０内のテキスト入力「ｐｈｏｔｏ  ｍ」（「フォトｍ」）は、ｎ−ｇｒａｍ「ｐｈｏｔｏ」（「フォト」）および「ｍ」に区切られ、文法テンプレート「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）および「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  ［ｅｍｐｌｏｙｅｒ］」（「［雇用主］に勤務している私の友人のフォト」）にマッチされることが可能であり、ここで、［ｅｍｐｌｏｙｅｒ］（［雇用主］）は、後述されるように、記憶されたソーシャル・グラフ・エンティティのうちの１つまたは複数に関連付けられ得る非終端トークンである。さらに、１つまたは複数のソーシャル・グラフ・エンティティが、ソーシャル・グラフ・エンティティのタイプに基づいて、非終端トークンに関連があると識別され得る。上述のように、クライアント側先行入力工程は、テキスト入力「ｐｈｏｔｏ  ｍ」（「フォトｍ」）を構文解析してｎ−ｇｒａｍ「ｐｈｏｔｏ」（「フォト」）および「ｍ」にすることができる。図６の例で示されるように、文法テンプレート６１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）は、ｎ−ｇｒａｍ「ｐｈｏｔｏ」（「フォト」）および「ｍ」に関して評価され得る。限定ではなく例として、完全にマッチされたときの予め定められた文法テンプレート６１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）は、クエリ・トークン「ｐｈｏｔｏ」（「フォト」）、［ｏｆ］（［の］）、［ｍｙ］（［私の］）、および［ｆｒｉｅｎｄｓ］（［友人］）を有することができ、そうでなければ、上述のように、挿入コストを発生し得る。最初に、６２０で示されるように、ｎ−ｇｒａｍ「ｐｈｏｔｏ」（「フォト」）は、記憶されたソーシャル・グラフ・エンティティに対応する文法テンプレート６１０のクエリ・トークン「ｐｈｏｔｏ」（「フォト」）とマッチされることができ、コスト計算においてコストを発生しない。モバイル・クライアント・システム１３０上の修正された先行入力工程が、入力されたテキスト文字の残りの部分に対して文法テンプレート６１０の残りの非終端トークンを評価することができる。６３０で示されるように、ｎ−ｇｒａｍ「ｍ」は、クエリ・トークン［ｏｆ］（［の］）とマッチしない。結果として、コスト計算は、クエリ・トークン［ｏｆ］（［の］）とマッチしないことに関連付けられた挿入コストを発生する。６４０で示されるように、ｎ−ｇｒａｍ「ｍ」は、クエリ・トークン［ｍｙ］（［私の］）とマッチされることができ、結果として、まったく挿入コストを発生しない。限定ではなく例として、ｎ−ｇｒａｍ「ｍ」は、クエリ・トークン［ｍｙ］（［私の］）に対するｎ−ｇｒａｍ「ｍ」内の文字「ｍ」の部分的文字マッチングに少なくとも部分的に基づいて、クエリ・トークン［ｍｙ］（［私の］）にマッチされ得る。本開示では特定の基準に基づいて特定のｎ−ｇｒａｍと特定のクエリ・トークンとの間のマッチを決定することを説明しているが、本開示は、任意の適切な基準、たとえば、信頼スコア、確率、質、ランキング、またはこれらの任意の組合せなどに基づいて、任意の適切なｎ−ｇｒａｍと任意の適切なクエリ・トークンとの間のマッチを決定することを企図する。６５０で示されるように、残りのテキスト文字が存在しないので、マッチされないクエリ・トークン［ｆｒｉｅｎｄｓ］（［友人］）に関連付けられた挿入コストが発生する。文法テンプレート６１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）の基本コストは、１．１であり、マッチされないクエリ・トークン「ｐｈｏｔｏ」（「フォト」）、［ｏｆ］（［の］）、［ｍｙ］（［私の］）、および［ｆｒｉｅｎｄｓ］（［友人］）の挿入コストはそれぞれ、２．２、０．５、０、および１．５であると仮定すると、構造化検索クエリ「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）に対する計算されたコストは、３．１である。
【００８０】
図７の例で示されるように、文法テンプレート７１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  ［ｅｍｐｌｏｙｅｒ］」（「［雇用主］に勤務している私の友人のフォト」）は、入力されたテキスト「ｐｈｏｔｏ  ｍ」（「フォトｍ」）に関して評価され得る。限定ではなく例として、完全にマッチされたときの文法テンプレート７１０は、クエリ・トークン「ｐｈｏｔｏ」（「フォト」）、［ｏｆ］（［の］）、［ｍｙ］（［私の］）、および［ｆｒｉｅｎｄｓ］（［友人］）、「ｗｈｏ」（「している」）、［ｗｏｒｋ］（［勤務］）、「ａｔ」（「に」）、ならびに非終端トークン［ｅｍｐｌｏｙｅｒ］（［雇用主］）を有することができ、［ｅｍｐｌｏｙｅｒ］（［雇用主］）は、タイプ「ｅｍｐｌｏｙｅｒ」（「雇用主」）の最も低いコストの記憶されたソーシャル・グラフ・エンティティに対応するソーシャル・グラフ・エンティティ「Ｆａｃｅｂｏｏｋ」（［フェイスブック］）を用いて評価される。最初に、７２０で示されるように、ｎ−ｇｒａｍ「ｐｈｏｔｏ」（「フォト」）は、文法テンプレート７１０のクエリ・トークン「ｐｈｏｔｏ」（「フォト」）とマッチされることができ、コスト計算においてコストを発生しない。予め定められた文法テンプレートの残りの非終端トークンは、残りのｎ−ｇｒａｍに対して評価され得る。７３０で示されるように、ｎ−ｇｒａｍ「ｍ」はクエリ・トークン［ｏｆ］（［の］）とマッチしない。結果として、コスト計算は、クエリ・トークン［ｏｆ］（［の］）とマッチしないｎ−ｇｒａｍに関連付けられた挿入コストを発生する。７４０で示されるように、ｎ−ｇｒａｍ「ｍ」は、クエリ・トークン［ｍｙ］（［私の］）とマッチし、結果として、まったく挿入コストを発生しない。上述のように、ｎ−ｇｒａｍ「ｍ」は、クエリ・トークン［ｍｙ］（［私の］）に対するｎ−ｇｒａｍ「ｍ」内の文字「ｍ」の部分的文字マッチングに少なくとも部分的に基づいて、クエリ・トークン［ｍｙ］（［私の］）にマッチされ得る。７５０〜７９０で示されるように、残りのテキスト文字が存在しないので、マッチされないクエリ・トークン［ｆｒｉｅｎｄｓ］（［友人］）、「ｗｈｏ」（「している」）、［ｗｏｒｋ］（［勤務］）、および「ａｔ」（「に」）に関連付けられた挿入コストが発生する。文法テンプレート７１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  ［ｅｍｐｌｏｙｅｒ］」（「［雇用主］に勤務している私の友人のフォト」）の基本コストは、２．１であり、クエリ・トークン「ｐｈｏｔｏ」（「フォト」）、［ｏｆ］（［の］）、［ｍｙ］（［私の］）、［ｆｒｉｅｎｄｓ］（［友人］）、「ｗｈｏ」（「している」）、［ｗｏｒｋ］（［勤務］）、「ａｔ」（「に」）、および［ｅｍｐｌｏｙｅｒ］（［雇用主］）と一致しないときの非終端トークンの挿入コストはそれぞれ、２．２、０．５、０、１．５、０．１、０．３、０．５、および１．０であると仮定し、ソーシャル・グラフ・エンティティ「Ｆａｃｅｂｏｏｋ」（［フェイスブック］）の挿入コストは、０．０３であると仮定すると、構造化検索クエリ「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  Ｆａ���ｅｂｏｏｋ」（「フェイスブックに勤務している私の友人のフォト」）に対する結果の計算されたコストは、６．０３である。
【００８１】
図８の例に示されるように、ソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）を有する文法テンプレート８１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  ［ｅｍｐｌｏｙｅｒ］」（「［雇用主］に勤務している私の友人のフォト」）は、入力されたテキスト「ｐｈｏｔｏ  ｍ」（「フォトｍ」）に関して評価され得る。上述のように、８２０で示されるように、ｎ−ｇｒａｍ「ｐｈｏｔｏ」（「フォト」）は、文法テンプレート８１０のクエリ・トークン「ｐｈｏｔｏ」（「フォト」）とマッチされることができ、コスト計算においてコストを発生しない。予め定められた文法テンプレートの残りの非終端トークンは、残りのｎ−ｇｒａｍに対して評価され得る。８３０で示されるように、ｎ−ｇｒａｍ「ｍ」はクエリ・トークン［ｏｆ］（［の］）とマッチしない。結果として、コスト計算は、クエリ・トークン［ｏｆ］（［の］）とマッチしないことに関連付けられた挿入コストを発生する。特定の実施形態では、クライアント側先行入力工程が複数のクエリ・トークンにマッチするとき、クライアント側先行入力工程は、より高い挿入コストのクエリ・トークンにｎ−ｇｒａｍをマッチさせることができる。限定ではなく例として、一致されないときの非終端トークン［ｅｍｐｌｏｙｅｒ］（［雇用主］）、ソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）、およびクエリ・トークン［ｍｙ］（［私の］）はそれぞれ、１．０、０．０４、および０の挿入コストを有すると仮定すると、クライアント側先行入力工程は、８４０および８９０で示されるように、ｎ−ｇｒａｍ「ｍ」を非終端トークン［ｅｍｐｌｏｙｅｒ］（［雇用主］）およびソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）にマッチすることができるが、クエリ・トークン［ｍｙ］（［私の］）とマッチしない。限定ではなく例として、ｎ−ｇｒａｍ「ｍ」は、ソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）に対するｎ−ｇｒａｍ「ｍ」内の文字「ｍ」の部分的文字マッチングに少なくとも部分的に基づいて、ソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）を用いて評価される非終端トークン［ｅｍｐｌｏｙｅｒ］（［雇用主］）にマッチされ得る。さらに、ソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）を用いて評価される非終端トークン［ｅｍｐｌｏｙｅｒ］（［雇用主］）は、マッチされたソーシャル・グラフ・エンティティ（たとえば「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」））に対応する非終端トークンである。結果として、コスト計算は、非終端トークン［ｅｍｐｌｏｙｅｒ］（［雇用主］）またはソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフト」）に関連付けられた挿入コストをまったく発生せず、クエリ・トークン［ｍｙ］（［私の］）にマッチしないことに関連付けられた挿入コストを発生する。８５０〜８８０で示されるように、残りのｎ−ｇｒａｍが存在しないので、マッチされないクエリ・トークン［ｆｒｉｅｎｄｓ］（［友人］）、「ｗｈｏ」��「している」）、［ｗｏｒｋ］（［勤務］）、および「ａｔ」（「に」）に関連付けられた挿入コストが発生する。文法テンプレート８１０「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  ［ｅｍｐｌｏｙｅｒ］」（「［雇用主］に勤務している私の友人のフォト」）の基本コストは、２．１であり、クエリ・トークン「ｐｈｏｔｏ」（「フォト」）、［ｏｆ］（［の］）、［ｍｙ］（［私の］）、［ｆｒｉｅｎｄｓ］（［友人］）、「ｗｈｏ」（「している」）、［ｗｏｒｋ］（［勤務］）、「ａｔ」（「に」）、および［ｅｍｐｌｏｙｅｒ］（［雇用主］）と一致しない挿入コストはそれぞれ、２．２、０．５、０、１．５、０．１、０．３、０．５、および１．０であると仮定し、ソーシャル・グラフ・エンティティ「Ｍｉｃｒｏｓｏｆｔ」（［マイクロソフト］）の挿入コストは、０．０４であると仮定すると、構造化検索クエリ「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフトに勤務している私の友人のフォト」）に対する結果の計算されたコストは、５．０４である。
【００８２】
特定の実施形態では、モバイル・クライアント・システム１３０は、選択された文法テンプレート（たとえば、文法閾値スコアよりも大きいスコアを有する文法テンプレート）に対応する１つまたは複数の構造化クエリを生成することができる。各構造化クエリは、対応する選択された文法テンプレートによって生成される文字列に基づくことができる。限定ではなく例として、テキスト・クエリ「ｐｈｏｔｏ  ｍ」（「フォトｍ」）に応答して、文法［ｏｂｊｅｃｔｓ］［ｕｓｅｒ−ｆｉｌｔｅｒ］［ｕｓｅｒ］［ｕｓｅｒ］（［オブジェクト］［ユーザ・フィルタ］［ユーザ］［ユーザ］）が、文字列「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）を生成することができ、文法の非終端トークン［ｏｂｊｅｃｔｓ］（［オブジェクト］）、［ｕｓｅｒ−ｆｉｌｔｅｒ］（［ユーザ・フィルタ］）、［ｕｓｅｒ］（［ユーザ］）はそれぞれ、クエリ・トークン「ｐｈｏｔｏ」（「フォト」）、［ｏｆ］（［の］）、［ｍｙ］（［私の］）、および［ｆｒｉｅｎｄｓ］（［友人］）によって置換されていて、文字列を生成している。特定の実施形態では、自然言語シンタックスを使用して文法によって生成された文字列は、自然言語における構造化クエリとしてレンダリングされ得る。限定ではなく例として、前述の例の構造化クエリは、クエリ・トークン［ｏｆ］（［の］）を使用し、これは、自然言語シンタックスを使用して、文法によってレンダリングされた文字列が自然言語であるようにする。次いで、文法によって生成された自然言語文字列は、ソーシャル・グラフ要素に対応するクエリ・トークンを修正して、それらのソーシャル・グラフ要素に対する参照を含むことによって、構造化クエリを形成するようにレンダリングされ得る。限定ではなく例として、文字列「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）は、ユーザの友人に対応する１つまたは複数の第２のユーザ・ノード２０２に対する参照として「友人」に関するクエリ・トークンが構造化クエリ内に出現するようにレンダリングされてよく、この参照は、強調表示、インライン・リンク、スニペット、別の適切な参照、またはこれらの任意の組合せを含むことができる。各構造化クエリは、対応する選択された文法に対応するクエリ・トークンを含むことができ、これらのクエリ・トークンは、識別されたエッジ２０６のうちの１つまたは複数、および識別されたノードのうちの１つまたは複数に対応する。
【００８３】
後述するように、クライアント側先行入力工程は、検索クエリ・フィールド３５０内のテキスト入力にマッチしている１つまたは複数の構造化クエリを識別することができる。特定の実施形態では、識別された構造化クエリは、上述された計算されたコストに少なくとも部分的に基づいてランク付けされ得る。限定ではなく例として、識別された構造化クエリは、最も低い計算されたコストに少なくとも部分的に基づいてランク付けされ得る。たとえば、上述されたコスト計算に基づいて、テキスト入力「ｐｈｏｔｏ  ｍ」（「フォトｍ」）について識別された構造化クエリが、「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ」（「私の友人のフォト」）、「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  Ｍｉｃｒｏｓｏｆｔ」（「マイクロソフトに勤務している私の友人のフォト」）、および「ｐｈｏｔｏｓ  ｏｆ  ｍｙ  ｆｒｉｅｎｄｓ  ｗｈｏ  ｗｏｒｋ  ａｔ  ［Ｆａｃｅｂｏｏｋ］」（「フェイスブックに勤務している私の友人のフォト」）の最も高いランク付けから最低までの例示的ランキングを有することができる。本開示では特定の様式で特定の構造化クエリに対して特定のテキスト入力をマッチさせランク付けすることを説明しているが、本開示は、任意の適切な様式で任意の適切な構造化クエリに対して任意の適切なテキスト入力をマッチさせランク付けすることを企図する。検索クエリを伴う文法モデルを使用することに関するさらなる情報は、本願明細書に援用する２０１２年１１月１２日に出願された米国特許出願第１３／６７４６９５号に見ることができる。
【００８４】
図９〜１０は、例示的構造化検索クエリを有する例示的モバイル・クライアント・システム上の例示的ＵＩを示す。特定の実施形態では、構造化クエリが識別された後、モバイル・クライアント・システム１３０は、識別された文法テンプレートまたは記憶されたソーシャル・グラフ・エンティティに基づいて、構造化クエリのうちの１つまたは複数を表示することができる。構造クエリは、たとえば、ユーザのモバイル・クライアント・システム１３０のモバイル・ウェブ・ブラウザまたはＵＩ上に表示されてよく、たとえば、それは、参照されたソーシャル・グラフ要素の名前（名前文字列）、他のクエリ制限（たとえば、ブール演算子など）、ならびに場合によっては、参照されたソーシャル・グラフ要素に関連付けられた他のメタデータを含むことができる。限定ではなく例として、問合せユーザのモバイル・クライアント・システム１３０上のモバイル・ウェブ・ブラウザまたはＵＩは、図９〜１０に示されるように、識別された構造化クエリをドロップダウン・メニュー３００内に表示することができる。クライアント側先行入力工程は、各キーストロークの後に、予め定められた文法テンプレートに対して検索クエリ・フィールド３５０内のテキスト入力をマッチングすることができる。特定の実施形態では、ユーザが検索クエリ・フィールド３５０内に追加の文字を提供すると、クライアント側先行入力工程は、追加のテキストを評価して、ドロップダウン・メニュー３００内でユーザに提示される構造化クエリを更新することができる。さらに、次いでユーザは、ユーザがソーシャル・ネットワーキング・システム１６０に実行させたい特定の構造化クエリを示すために、クリックまた他の形式で選択をする（たとえば、モバイル・クライアント・システム１３０のディスプレイ上で選択される構造化クエリをタップする）ことができる。特定の実施形態では、構造化クエリは、たとえば、上述されたように、前もって決定されたコスト計算に基づいて、ランク付けされた順序で問合せユーザへ提示され得る。より高いランキングを有する構造化クエリは、より目立つ位置に提示され得る。さらに、特定の実施形態では、閾値コスト値より低いコスト計算を有する構造化クエリのみが、問合せユーザへ表示され得る。限定ではなく例として、図９〜１０に示されるように、構造化クエリは、ドロップダウン・メニュー３００内で問合せユーザに提示されることが可能であり、そこでは、より高くランク付けされた構造化されたクエリがメニューのトップに提示され、より低くランク付けされた構造化クエリはドロップダウン・メニュー３００内に降順で提示され得る。特定の実施形態では、構造化クエリ内の１つまたは複数の参照は、特定のソーシャル・グラフ要素に対するその対応を示すために強調表示される（たとえば、外形を囲まれる、下線を付けられる、丸を付けられる、太字にされる、斜体にされる、色を付けられる、明るくされる、ずらされる、大文字にされる）ことが可能である。さらに、検索結果のタイプに対応するグラフィカル・インジケータが、ドロップダウン・メニュー３００内に構造化クエリと共に表示されてもよい。本開示では特定の様式で特定の構造化クエリを表示することを説明しているが、本開示は任意の適切な様式で任意の適切な構造化クエリを表示することを企図する。
【００８５】
上述のように、クライアント側先行入力工程は、各キーストロークの後に、予め定められた文法テンプレートに対して検索クエリ・フィールド３５０内のテキスト入力をマッチングすることができる。結果として、ドロップダウン・メニュー３００内に表示された識別された構造化クエリは、各キーストロークの後に更新され得る。図９に示される例では、ドロップダウン・メニュー３００は、テキスト入力「ｐｈｏｔｏｓ」（「フォト」）にマッチする上位６つの高くランク付けされた構造化クエリを表示することができる。ユーザが検索クエリ・フィールド３５０内に追加の文字を提供すると、クライアント側先行入力工程は、追加のテキストを評価して、ドロップダウン・メニュー３００内でユーザに提示される構造化クエリを更新することができる。図１０に示される例では、ドロップダウン・メニュー３００は、テキスト入力「ｐｈｏｔｏｓ  ｏｆ  ｍｙ」（「私の…のフォト」）にマッチする上位６つの高くランク付けされた構造化クエリを表示することができる。
【００８６】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、モバイル・クライアント・システム１３０からのドロップダウン・メニュー３００内の構造化クエリのうちの１つの選択を問合せユーザから受け取ることができる。受け取られた構造化クエリにおいて参照されるノードおよびエッジはそれぞれ、選択されたノードおよび選択されたエッジと呼ばれることがある。限定ではなく例として、問合せユーザのモバイル・クライアント・システム１３０上のウェブ・ブラウザまたはＵＩは、上述のように、ドロップダウン・メニュー３００内に識別された構造化クエリを表示することができ、次いで、ユーザは、ユーザがソーシャル・ネットワーキング・システム１６０に実行させたい特定の構造化クエリを示すために、クリックまた他の形式で選択をする（たとえば、モバイル・クライアント・システム１３０のディスプレイ上で選択される構造化クエリをタップする）ことができる。限定ではなく例として、図１０を参照すると、問合せユーザは、検索クエリ・フィールド３５０内への非構造化テキスト・クエリ「ｐｈｏｔｏｓ  ｏｆ  ｍｙ」（「私の…のフォト」）に続く入力を修正することができる。モバイル・クライアント・システム１３０は、更新されたｎ−ｇｒａｍ、および更新ｎ−ｇｒａｍに基づく各記憶された文法テンプレートに関する再計算されたコストに基づいて、表示された構造化クエリを修正することができる。特定の識別された構造化クエリを選択すると、ユーザのモバイル・クライアント・システム１３０は、ソーシャル・ネットワーキング・システム１６０にコールまたは他の形式で指示して、選択された構造化クエリを実行させることができる。本開示では特定の様式で特定の構造化クエリの選択を受け取ることを説明しているが、本開示は任意の適切な様式で任意の適切な構造化クエリの選択を受け取ることを企図する。
【００８７】
図１１は、クライアント側構造化検索クエリを生成するための例示的方法を示す。方法は、工程１１１０から開始することができ、この工程では、モバイル・クライアント・システムが、オンライン・ソーシャル・ネットワークの第１のユーザから非構造化テキスト・クエリを受け取ることができる。工程１１２０で、モバイル・クライアント・システムのデータ・ストアからの、オンライン・ソーシャル・ネットワークのソーシャル・グラフのいくつかの第１のノードのうちの１つまたは複数のノードがアクセスされ得る。特定の実施形態では、ソーシャル・グラフは、いくつかのノード、およびこれらのノードを接続するいくつかのエッジを含む。さらに、ノードのうちの２つの間のエッジのそれぞれは、それらの間の単一分離度を表すことができる。特定の実施形態では、ノードは、オンライン・ソーシャル・ネットワークに関連付けられたコンセプトまたは第２のユーザにそれぞれが対応する複数の第１のノードと、第１のユーザに対応する第２のノードとを含むことができる。工程１１３０で、モバイル・クライアント・システムのデータ・ストアからの文法テンプレートのセットがアクセスされ得る。特定の実施形態では、各文法テンプレートは、１つまたは複数の非終端トークンおよび１つまたは複数のクエリ・トークンを含む。上述のように、クエリまたは終端トークンは、１つまたは複数の識別されたソーシャル・グラフ要素に対応することができる。さらに、特定の非終端トークンは、文法テンプレートにおいて１つまたは複数の識別されたソーシャル・グラフ要素（たとえばクエリ・トークン）で置換され得る。特定の実施形態では、クエリ・トークンは、０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含む。限定ではなく例として、各文法テンプレートは自然言語文字列に基づく。工程１１４０で、モバイル・クライアント・システムは、非構造化テキスト・クエリを、アクセスされたノードのうちの１つまたは複数に対してマッチさせること、およびマッチされたノードに対応する非終端トークンを有する文法テンプレートのうちの１つまたは複数に対してマッチさせることによって、１つまたは複数の完成された構造化クエリを生成することができる。限定ではなく例として、非構造化テキスト・クエリを文法テンプレートのうちの１つまたは複数に対してマッチさせることは、１つまたは複数のｎ−ｇｒａｍと文法テンプレートの１つまたは複数のクエリ・トークンとの間の部分的文字マッチに少なくとも部分的に基づくことができる。特定の実施形態では、各構造化クエリは、１つまたは複数の非終端トークンにマッチされたアクセスされたノードのうちの１つまたは複数ならびに対応する文法テンプレートにおいて参照される０個以上の第２のノードおよび１つまたは複数のエッジに対する参照を含むことができる。工程１１５０で、モバイル・クライアント・システムは、１つまたは複数の完成された構造化クエリを第１のユーザへ表示することができる。特定の実施形態では、必要に応じて、図１１の方法の１つまたは複数の工程を繰り返すことができる。本開示では図１１の特定の工程が特定の順序で行われるように説明し示しているが、本開示は図１１の方法の任意の適切な工程が任意の適切な順序で行われることを企図する。さらに、本開示では特定のコンポーネント、デバイス、またはシステムが図１１の方法の特定の工程を実行することを説明し示しているが、本開示は、任意の適切なコンポーネント、デバイス、またはシステムの任意の適切な組合せが図１１の方法の任意の適切な工程を実行することを企図する。
【００８８】
ソーシャル・グラフ・アフィニティおよび係数
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、様々なソーシャル・グラフ・エンティティの互いのソーシャル・グラフ・アフィニティ（本明細書では「アフィニティ」と呼ばれることがある）を決定することができる。アフィニティは、オンライン・ソーシャル・ネットワークに関連付けられた特定のオブジェクトの間、たとえば、ユーザ、コンセプト、コンテンツ、アクション、広告、オンライン・ソーシャル・ネットワークに関連付けられた他のオブジェクト、またはこれらの任意の適切な組合せなどの間の、関係または関心レベルの強度を表すことができる。また、アフィニティは、サードパーティ・システム１７０または他の適切なシステムに関連付けられたオブジェクトに対して決定されてもよい。ユーザ、主題、またはコンテンツのタイプごとのソーシャル・グラフ・エンティティに対する全体的アフィニティが設定されてもよい。全体的アフィニティは、ソーシャル・グラフ・エンティティに関連付けられたアクションまたは関係の継続的監視に基づいて変化してもよい。本開示では特定の様式で特定のアフィニティを決定することを説明しているが、本開示は任意の適切な様式で任意の適切なアフィニティを決定することを企図する。
【００８９】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、アフィニティ係数（本明細書では「係数」と呼ばれることがある）を使用して、ソーシャル・グラフ・アフィニティを測定または定量化することができる。係数は、オンライン・ソーシャル・ネットワークに関連付けられた特定のオブジェクトの間の関係の強度を表すまたは定量化することができる。係数は、特定のアクションに対するユーザの関心に基づいて、そのアクションをユーザが行う予測確率を測定する確率または関数を表してもよい。このようにして、ユーザの将来のアクションは、ユーザの以前のアクションに基づいて予測されてよく、この場合、係数はユーザのアクションの履歴に少なくとも部分的に基づいて計算されてよい。係数は、オンライン・ソーシャル・ネットワークの内部または外部であり得る任意の数のアクションを予測するために使用され得る。限定ではなく例として、これらのアクションは、様々なタイプの通信、たとえば、メッセージを送る、コンテンツを投稿する、またはコンテンツにコメントすることなど、様々なタイプの観察アクション、たとえば、プロフィール・ページ、メディア、または他の適切なコンテンツにアクセスする、またはそれらを閲覧することなど、２つ以上のソーシャル・グラフ・エンティティに関する様々なタイプの一致情報、たとえば、同じグループにある、同じ写真にタグ付けされた、同じ場所でチェックインした、または同じイベントに出席することなど、あるいは他の適切なアクションを含むことができる。本開示では特定の様式でアフィニティを測定することを説明しているが、本開示は任意の適切な様式でアフィニティを測定することを企図する。
【００９０】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数を計算するために多種多様なファクタを使用することができる。これらのファクタは、たとえばユーザ・アクション、オブジェクト間の関係のタイプ、場所情報、他の適切なファクタ、またはこれらの任意の組合せを含むことができる。特定の実施形態では、係数を計算するときに、異なるファクタは各様に重み付けされ得る。各ファクタに対する重みは静的であってよく、あるいは重みは、たとえば、ユーザ、関係のタイプ、アクションのタイプ、およびユーザの場所などに応じて変化してもよい。ファクタに対するレーティング（rating）がそれらの重みに応じて組み合わせて、ユーザに対する全体的係数を決定してもよい。限定ではなく例として、特定のユーザ・アクションにはレーティングと重みの両方が割り当てられ得る一方、特定のユーザ・アクションに関連付けられた関係には、レーティングと相関重み（たとえば、重みの合計は１００％）が割り当てられる。特定のオブジェクトに対するユーザの係数を計算するために、ユーザのアクションに割り当てられるレーティングは、たとえば、全体的係数の６０％を構成する一方、ユーザとオブジェクトとの関係は、全体的係数の４０％を構成することができる。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数を計算するために使用される様々なファクタに対する重みを決定するときに、多種多様な変数、たとえば、情報がアクセスされてからの時間、減衰係数、アクセス頻度、情報に対する関係もしくはアクセスされた情報に関わるオブジェクトに対する関係、オブジェクトに接続されたソーシャル・グラフ・エンティティに対する関係、ユーザ・アクションの短期または長期的平均、ユーザ・フィードバック、他の適切な変数、またはこれらの任意の組合せを考慮に入れることができる。限定ではなく例として、係数は、係数を計算するときに、特定のアクションによって提供された信号の強度を時間と共に減衰させて、より最近のアクションがより関連があるようにする減衰係数を含むことができる。レーティングおよび重みは、係数が基づくアクションの継続的追跡に基づいて継続的に更新されてよい。各ファクタに対するレーティングおよびファクタに割り当てられる重みの割当て、組合せ、および平均化などをするために、任意のタイプの工程またはアルゴリズムが採用され得る。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、アクションの履歴および過去のユーザ応答で訓練された機械学習アルゴリズム、またはそれらを様々なオプションにさらし、応答を測定することによってユーザから調達されたデータを使用して、係数を決定することができる。本開示では特定の様式で係数を計算することを説明しているが、本開示は任意の適切な様式で係数を計算することを企図する。
【００９１】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、ユーザのアクションに基づいて係数を計算することができる。ソーシャル・ネットワーキング・システム１６０は、オンライン・ソーシャル・ネットワーク、サードパーティ・システム１７０、他の適切なシステム、またはこれらの任意の組合せにおける、そのようなアクションを監視することができる。任意の適切なタイプのユーザのアクションが追跡または監視され得る。典型的なユーザ・アクションは、プロフィール・ページを閲覧すること、コンテンツを作成または投稿すること、コンテンツと対話すること、画像においてタグ付けするまたはタグ付けされること、グループに参加すること、イベントへの出席をリストおよび確認すること、場所でチェックインすること、特定のページに「いいね」を表明すること、ページを作成すること、およびソーシャル・アクションを促進する他のタスクを行うことを含む。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のタイプのコンテンツを有するユーザのアクションに基づいて係数を計算することができる。コンテンツは、オンライン・ソーシャル・ネットワーク、サードパーティ・システム１７０、または別の適切なシステムに関連付けられてよい。コンテンツは、ユーザ、プロフィール・ページ、投稿、ニュース記事、ヘッドライン、インスタント・メッセージ、チャットルームの会話、電子メール、広告、写真、映像、音楽、他の適切なオブジェクト、またはこれらの任意の組合せを含むことができる。ソーシャル・ネットワーキング・システム１６０は、ユーザのアクションを分析して、アクションのうちの１つまたは複数が主題、コンテンツ、および他のユーザなどに対するアフィニティを示すかどうかを決定することができる。限定ではなく例として、ユーザが「ｃｏｆｅｅ」（「コーヒー」）またはその変形に関係したコンテンツを頻繁に投稿できる場合、ソーシャル・ネットワーキング・システム１６０は、ユーザがコンセプト「ｃｏｆｅｅ」（「コーヒー」）に対して高い係数を有すると決定することができる。特定のアクションまたは特定のタイプのアクションには、全体的な計算された係数に影響し得る他のアクションよりも大きな重みおよび／またはレーティングが割り当てられてよい。限定ではなく例として、第１のユーザが第２のユーザに電子メールを送る場合、第１のユーザが第２のユーザのユーザ・プロフィール・ページを単に見る場合よりも、アクションの重みまたはレーティングが高いことが可能である。
【００９２】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のオブジェクトの間の関係のタイプに基づいて係数を計算することができる。ソーシャル・グラフ２００を参照して、ソーシャル・ネットワーキング・システム１６０は、係数を計算するときに、特定のユーザ・ノード２０２およびコンセプト・ノード２０４を接続するエッジ２０６の数および／またはタイプを分析することができる。限定ではなく例として、（２人のユーザが結婚していることを表す）配偶者タイプのエッジによって接続されたユーザ・ノード２０２は、友人タイプのエッジによって接続されたユーザ・ノード２０２よりも高い係数を割り当てられることが可能である。言い換えれば、特定のユーザに関するアクションおよび関係に割り当てられる重みに応じて、全体的アフィニティは、ユーザの友人に関するコンテンツよりもユーザの配偶者に関するコンテンツに対して、より高く決定され得る。特定の実施形態では、ユーザが別のオブジェクトと有する関係は、そのオブジェクトに対する係数を計算することに関して、ユーザのアクションに関する重みおよび／またはレーティングに影響することがある。限定ではなく例として、ユーザは第１のフォトにタグ付けされるが、単に第２のフォトに「いいね」を表明する場合、ソーシャル・ネットワーキング・システム１６０は、第２のフォトに対してよりも第１のフォトに対して高い係数を有すると決定することができ、なぜならば、コンテンツとのタグ付けタイプ（ｔａｇｇｅｄ−ｉｎ−ｔｙｐｅ）関係を有することは、コンテンツとの「いいね」タイプ関係を有する場合よりも大きな重みおよび／またはレーティングを割り当てられ得るからである。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、１つまたは複数の第２のユーザが特定のオブジェクトと有する関係に基づいて、第１のユーザに対する係数を計算することができる。言い換えれば、他のユーザがオブジェクトと有する接続および係数は、そのオブジェクトに対する第１のユーザの係数に影響を与え得る。限定ではなく例として、第１のユーザが１または複数の第２のユーザに対して接続されている、またはそうした第２のユーザに対して高い係数を有し、そうした第２のユーザが特定のオブジェクトに接続されている、またはその特定のオブジェクトに対して高い係数を有している場合、ソーシャル・ネットワーキング・システム１６０は、第１のユーザもその特定のオブジェクトに対して相対的に高い係数を有するはずであると決定することができる。特定の実施形態では、係数は、特定のオブジェクトの間の分離度に基づくことができる。より低い係数は、ソーシャル・グラフ２００において第１のユーザに間接的に接続されているユーザのコンテンツ・オブジェクトへの関心を第１のユーザが共有する可能性が低くなっていることを表すことができる。限定ではなく例として、ソーシャル・グラフ・エンティティは、ソーシャル・グラフ２００においてより近い（すなわち、分離度が小さい）ソーシャル・グラフ・エンティティ同士は、ソーシャル・グラフ２００においてより離れているエンティティよりも高い係数を有することができる。
【００９３】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、場所情報に基づいて係数を計算することができる。地理的に互いにより近いオブジェクトは、より遠いオブジェクトよりも互いに関係している、または関心があるとみなされることが可能である。特定の実施形態では、特定のオブジェクトに対するユーザの係数は、ユーザに関連付けられた現在の場所（またはユーザのクライアント・システム１３０の場所）に対するオブジェクトの場所の近接性に基づくことができる。第１のユーザは、第１のユーザにより近い他のユーザまたはコンセプトに対して関心がより大きいことがある。限定ではなく例として、ユーザが空港から１．６ｋｍ（１マイル）でありガソリン・スタンドから３．２ｋｍ（２マイル）である場合、ソーシャル・ネットワーキング・システム１６０は、空港のユーザに対する近接性に基づいて、ユーザがガソリン・スタンドよりも空港に対してより高い係数を有すると決定することができる。
【００９４】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数情報に基づいて、ユーザに対して特定のアクションを行うことができる。係数は、特定のアクションに対するユーザの関心に基づいて、ユーザがそのアクションを行うかどうかを予測するために使用され得る。係数は、ユーザに対して任意のタイプのオブジェクト、たとえば、広告、検索結果、ニュース記事、メディア、メッセージ、通知、または他の適切なオブジェクトなどを、生成または提示するときに使用され得る。係数はまた、必要に応じて、そのようなオブジェクトをランク付けおよび順序付けするために利用されてもよい。このようにして、ソーシャル・ネットワーキング・システム１６０は、ユーザの関心および現在の状況に関連がある情報を提供し、それらが関心のあるそのような情報を見つける可能性を大きくすることができる。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数情報に基づいてコンテンツを生成することができる。コンテンツ・オブジェクトは、ユーザに特有の係数に基づいて提供または選択されてよい。限定ではなく例として、係数は、ユーザのためのメディアを生成するために使用されることがあり、この場合、ユーザは、メディア・オブジェクトに対してユーザが高い全体的係数を有するメディアを提示され得る。限定ではなく別の例として、係数は、ユーザに対する広告を生成するために使用されることがあり、この場合、ユーザは、広告されるオブジェクトに対してユーザが高い全体的係数を有する広告を提示され得る。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数情報に基づいて検索結果を生成することができる。特定のユーザのための検索結果は、問合せユーザに対する検索結果に関連付けられた係数に基づいてスコア付けまたはランク付けされ得る。限定ではなく例として、より高い係数を有するオブジェクトに対応する検索結果は、より低い係数を有するオブジェクトに対応する検索結果よりも、検索結果ページ上で高くランク付けされ得る。
【００９５】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のシステムまたは工程からの係数を求める要求に応答して、係数を計算することができる。所与の状況でユーザが取り得る（または主題となり得る）可能性が高いアクションを予測するために、任意の工程が、ユーザに対する計算された係数を要求することができる。要求はまた、係数を計算するために使用される様々なファクタに対して使用する重みのセットを含んでもよい。この要求は、オンライン・ソーシャル・ネットワーク上で実行されている工程から、（たとえば、ＡＰＩまたは他の通信チャネルを介して）サードパーティ・システム１７０から、または他の適切なシステムから来ることが可能である。要求に応答して、ソーシャル・ネットワーキング・システム１６０は、係数を計算する（または、係数情報が前もって計算され記憶されている場合はそれにアクセスする）ことができる。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定の工程に対するアフィニティを測定することができる。（オンライン・ソーシャル・ネットワークの内部および外部の両方の）様々な工程が、特定のオブジェクトまたはセットのオブジェクトに対する係数を要求することができる。ソーシャル・ネットワーキング・システム１６０は、アフィニティの測定値を要求した特定の工程に関連があるアフィニティの測定値を提供することができる。このようにして、各工程は、異なるコンテキストに対して調整されたアフィニティの測定値を受け取り、工程はアフィニティの測定値を使用することになる。
【００９６】
ソーシャル・グラフ・アフィニティおよびアフィニティ係数に関連して、特定の実施形態は、本願明細書に援用する２００６年８月１１日に出願された米国特許出願第１１／５０３０９３号、２０１２年１２月２２日に出願された米国特許出願第１２／９７７０２７号、２０１０年１２月２３日に出願された米国特許出願第１２／９７８２６５号、および２０１２年１０月１日に出願された米国特許出願第１３／６３２８６９号に開示された１つまたは複数のシステム、コンポーネント、要素、機能、方法、動作、または工程を利用してもよい。
【００９７】
システムおよび方法
図１２は、例示的なコンピュータ・システム１２００を示している。特定の実施形態においては、１つまたは複数のコンピュータ・システム１２００が、本明細書において記述されているまたは示されている１つまたは複数の方法の１つまたは複数の工程を実行する。特定の実施形態においては、１つまたは複数のコンピュータ・システム１２００が、本明細書において記述されているまたは示されている機能を提供する。特定の実施形態においては、１つまたは複数のコンピュータ・システム１２００上で稼働するソフトウェアが、本明細書において記述されているもしくは示されている１つもしくは複数の方法の１つもしくは複数の工程を実行し、または本明細書において記述されているもしくは示されている機能を提供する。特定の実施形態は、１つまたは複数のコンピュータ・システム１２００の１つまたは複数の部分を含む。本明細書においては、コンピュータ・システムへの言及は、適切な場合には、コンピューティング・デバイスを包含することができる。その上、コンピュータ・システムへの言及は、適切な場合には、１つまたは複数のコンピュータ・システムを包含することができる。
【００９８】
本開示は、任意の適切な数のコンピュータ・システム１２００を想定している。本開示は、任意の適切な物理的な形態を取るコンピュータ・システム１２００を想定している。限定ではなく、例として、コンピュータ・システム１２００は、組み込みコンピュータ・システム、システムオンチップ（ＳＯＣ）、シングルボード・コンピュータ・システム（ＳＢＣ）（たとえば、コンピュータオンモジュール（ＣＯＭ）もしくはシステムオンモジュール（ＳＯＭ）など）、デスクトップ・コンピュータ・システム、ラップトップもしくはノートブック・コンピュータ・システム、対話キオスク、メインフレーム、コンピュータ・システムのメッシュ、モバイル電話、携帯情報端末（ＰＤＡ）、サーバ、タブレット・コンピュータ・システム、またはこれらのうちの複数の組合せであることが可能である。適切な場合には、コンピュータ・システム１２００は、１つもしくは複数のコンピュータ・システム１２００を含むこと、単一型もしくは分散型であること、複数のロケーションにわたること、複数のマシンにわたること、複数のデータセンターにわたること、または、クラウド（１つもしくは複数のネットワーク内の１つもしくは複数のクラウド・コンポーネントを含むことができる）内に常駐することが可能である。適切な場合には、１つまたは複数のコンピュータ・システム１２００は、本明細書において記述されているまたは示されている１つまたは複数の方法の１つまたは複数の工程を、実質的な空間上のまたは時間上の制限を伴わずに実行することができる。限定ではなく、例として、１つまたは複数のコンピュータ・システム１２００は、本明細書において記述されているまたは示されている１つまたは複数の方法の１つまたは複数の工程をリアルタイムで、またはバッチ・モードで実行することができる。１つまたは複数のコンピュータ・システム１２００は、適切な場合には、本明細書において記述されているまたは示されている１つまたは複数の方法の１つまたは複数の工程を別々の時点で、または別々のロケーションで実行することができる。
【００９９】
特定の実施形態においては、コンピュータ・システム１２００は、プロセッサ１２０２、メモリ１２０４、ストレージ１２０６、入力／出力（Ｉ／Ｏ）インタフェース１２０８、通信インタフェース１２１０、およびバス１２１２を含む。本開示は、特定の数の特定のコンポーネントを特定の構成で有する特定のコンピュータ・システムについて記述し、示しているが、本開示は、任意の適切な数の任意の適切なコンポーネントを任意の適切な構成で有する任意の適切なコンピュータ・システムを想定している。
【０１００】
特定の実施形態においては、プロセッサ１２０２は、コンピュータ・プログラムを構成している命令などの命令を実行するためのハードウェアを含む。限定ではなく、例として、命令を実行するために、プロセッサ１２０２は、内部レジスタ、内部キャッシュ、メモリ１２０４、またはストレージ１２０６から命令を取り出し（またはフェッチし）、それらの命令をデコードして実行し、次いで、１つまたは複数の結果を内部レジスタ、内部キャッシュ、メモリ１２０４、またはストレージ１２０６に書き込むことができる。特定の実施形態においては、プロセッサ１２０２は、データ、命令、またはアドレスのための１つまたは複数の内部キャッシュを含むことができる。本開示は、適切な場合には、任意の適切な数の任意の適切な内部キャッシュを含むプロセッサ１２０２を想定している。限定ではなく、例として、プロセッサ１２０２は、１つまたは複数の命令キャッシュ、１つまたは複数のデータ・キャッシュ、および１つまたは複数の変換ルックアサイド・バッファ（ＴＬＢ）を含むことができる。命令キャッシュ内の命令は、メモリ１２０４またはストレージ１２０６内の命令のコピーであることが可能であり、命令キャッシュは、プロセッサ１２０２によるそれらの命令の取り出しをスピードアップすることができる。データ・キャッシュ内のデータは、プロセッサ１２０２において実行される命令が機能する際に基づくメモリ１２０４もしくはストレージ１２０６内のデータのコピー、プロセッサ１２０２において実行される後続の命令によるアクセスのための、もしくはメモリ１２０４もしくはストレージ１２０６への書き込みのためのプロセッサ１２０２において実行された以前の命令の結果、またはその他の適切なデータであることが可能である。データ・キャッシュは、プロセッサ１２０２による読み取りオペレーションまたは書き込みオペレーションをスピードアップすることができる。ＴＬＢは、プロセッサ１２０２のための仮想アドレス変換をスピードアップすることができる。特定の実施形態においては、プロセッサ１２０２は、データ、命令、またはアドレスのための１つまたは複数の内部レジスタを含むことができる。本開示は、適切な場合には、任意の適切な数の任意の適切な内部レジスタを含むプロセッサ１２０２を想定している。適切な場合には、プロセッサ１２０２は、１つまたは複数の演算ロジック・ユニット（ＡＬＵ）を含むこと、マルチコア・プロセッサであること、または１つもしくは複数のプロセッサ１２０２を含むことが可能である。本開示は、特定のプロセッサについて記述し、示しているが、本開示は、任意の適切なプロセッサを想定している。
【０１０１】
特定の実施形態においては、メモリ１２０４は、プロセッサ１２０２が実行するための命令、またはプロセッサ１２０２が機能する際に基づくデータを記憶するためのメイン・メモリを含む。限定ではなく、例として、コンピュータ・システム１２００は、命令をストレージ１２０６または別のソース（たとえば、別のコンピュータ・システム１２００など）からメモリ１２０４にロードすることができる。次いでプロセッサ１２０２は、命令をメモリ１２０４から内部レジスタまたは内部キャッシュにロードすることができる。命令を実行するために、プロセッサ１２０２は、命令を内部レジスタまたは内部キャッシュから取り出し、それらの命令をデコードすることができる。命令の実行中または実行後に、プロセッサ１２０２は、１つまたは複数の結果（それらは、中間の結果または最終的な結果である場合がある）を内部レジスタまたは内部キャッシュに書き込むことができる。次いでプロセッサ１２０２は、それらの結果のうちの１つまたは複数をメモリ１２０４に書き込むことができる。特定の実施形態においては、プロセッサ１２０２は、（ストレージ１２０６またはその他の場所ではなく）１つもしくは複数の内部レジスタもしくは内部キャッシュ内の、またはメモリ１２０４内の命令のみを実行し、（ストレージ１２０６またはその他の場所ではなく）１つもしくは複数の内部レジスタもしくは内部キャッシュ内の、またはメモリ１２０４内のデータ上でのみ機能する。１つまたは複数のメモリ・バス（それらは各々、アドレス・バスおよびデータ・バスを含むことができる）は、プロセッサ１２０２をメモリ１２０４に結合することができる。バス１２１２は、以降で記述されているような１つまたは複数のメモリ・バスを含むことができる。特定の実施形態においては、１つまたは複数のメモリ管理ユニット（ＭＭＵ）が、プロセッサ１２０２とメモリ１２０４との間に常駐し、プロセッサ１２０２によって要求されるメモリ１２０４へのアクセスを容易にする。特定の実施形態においては、メモリ１２０４は、ランダム・アクセス・メモリ（ＲＡＭ）を含む。このＲＡＭは、適切な場合には、揮発性メモリであることが可能である。適切な場合には、このＲＡＭは、ダイナミックＲＡＭ（ＤＲＡＭ）またはスタティックＲＡＭ（ＳＲＡＭ）であることが可能である。その上、適切な場合には、このＲＡＭは、シングルポートＲＡＭまたはマルチポートＲＡＭであることが可能である。本開示は、任意の適切なＲＡＭを想定している。メモリ１２０４は、適切な場合には、１つまたは複数のメモリ１２０４を含むことができる。本開示は、特定のメモリについて記述し、示しているが、本開示は、任意の適切なメモリを想定している。
【０１０２】
特定の実施形態においては、ストレージ１２０６は、データまたは命令のためのマス・ストレージを含む。限定ではなく、例として、ストレージ１２０６は、ハード・ディスク・ドライブ（ＨＤＤ）、フロッピー（登録商標）ディスク・ドライブ、フラッシュ・メモリ、光ディスク、光磁気ディスク、磁気テープ、またはユニバーサル・シリアル・バス（ＵＳＢ）ドライブ、またはこれらのうちの複数の組合せを含むことができる。ストレージ１２０６は、適切な場合には、取り外し可能なまたは取り外し不能な（すなわち、固定された）媒体を含むことができる。ストレージ１２０６は、適切な場合には、コンピュータ・システム１２００の内部または外部に存在することが可能である。特定の実施形態においては、ストレージ１２０６は、不揮発性のソリッドステート・メモリである。特定の実施形態においては、ストレージ１２０６は、読み取り専用メモリ（ＲＯＭ）を含む。適切な場合には、このＲＯＭは、マスクプログラムＲＯＭ、プログラマブルＲＯＭ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、電気的消去可能ＰＲＯＭ（ＥＥＰＲＯＭ）、電気的書替え可能ＲＯＭ（ＥＡＲＯＭ）、またはフラッシュ・メモリ、またはこれらのうちの複数の組合せであることが可能である。本開示は、任意の適切な物理的な形態を取るマス・ストレージ１２０６を想定している。ストレージ１２０６は、適切な場合には、プロセッサ１２０２とストレージ１２０６との間における通信を容易にする１つまたは複数のストレージ・コントロール・ユニットを含むことができる。適切な場合には、ストレージ１２０６は、１つまたは複数のストレージ１２０６を含むことができる。本開示は、特定のストレージについて記述し、示しているが、本開示は、任意の適切なストレージを想定している。
【０１０３】
特定の実施形態においては、Ｉ／Ｏインタフェース１２０８は、コンピュータ・システム１２００と１つまたは複数のＩ／Ｏデバイスとの間における通信のための１つまたは複数のインタフェースを提供するハードウェア、ソフトウェア、またはその両方を含む。コンピュータ・システム１２００は、適切な場合には、これらのＩ／Ｏデバイスのうちの１つまたは複数を含むことができる。これらのＩ／Ｏデバイスのうちの１つまたは複数は、人とコンピュータ・システム１２００との間における通信を可能にすることができる。限定ではなく、例として、Ｉ／Ｏデバイスは、キーボード、キーパッド、マイクロフォン、モニタ、マウス、プリンタ、スキャナ、スピーカ、スチル・カメラ、スタイラス、タブレット、タッチ・スクリーン、トラックボール、映像カメラ、別の適切なＩ／Ｏデバイス、またはこれらのうちの複数の組合せを含むことができる。Ｉ／Ｏデバイスは、１つまたは複数のセンサを含むことができる。本開示は、任意の適切なＩ／Ｏデバイス、およびそれらのＩ／Ｏデバイスのための任意の適切なＩ／Ｏインタフェース１２０８を想定している。適切な場合には、Ｉ／Ｏインタフェース１２０８は、プロセッサ１２０２がこれらのＩ／Ｏデバイスのうちの１つまたは複数を駆動することを可能にする１つまたは複数のデバイス・ドライバまたはソフトウェア・ドライバを含むことができる。Ｉ／Ｏインタフェース１２０８は、適切な場合には、１つまたは複数のＩ／Ｏインタフェース１２０８を含むことができる。本開示は、特定のＩ／Ｏインタフェースについて記述し、示しているが、本開示は、任意の適切なＩ／Ｏインタフェースを想定している。
【０１０４】
特定の実施形態においては、通信インタフェース１２１０は、コンピュータ・システム１２００と、１つもしくは複数のその他のコンピュータ・システム１２００または１つもしくは複数のネットワークとの間における通信（たとえば、パケットベースの通信など）のための１つまたは複数のインタフェースを提供するハードウェア、ソフトウェア、またはその両方を含む。限定ではなく、例として、通信インタフェース１２１０は、イーサネット（登録商標）もしくはその他の有線ベースのネットワークと通信するためのネットワーク・インタフェース・コントローラ（ＮＩＣ）もしくはネットワーク・アダプタ、またはＷＩ−ＦＩネットワークなどの無線ネットワークと通信するための無線ＮＩＣ（ＷＮＩＣ）もしくは無線アダプタを含むことができる。本開示は、任意の適切なネットワーク、およびそのネットワークのための任意の適切な通信インタフェース１２１０を想定している。限定ではなく、例として、コンピュータ・システム１２００は、アド・ホック・ネットワーク、パーソナル・エリア・ネットワーク（ＰＡＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、またはインターネットの１つまたは複数の部分、またはこれらのうちの複数の組合せと通信することができる。これらのネットワークのうちの１つまたは複数の１つまたは複数の部分は、有線または無線であることが可能である。例として、コンピュータ・システム１２００は、無線ＰＡＮ（ＷＰＡＮ）（たとえば、ブルートゥースＷＰＡＮなど）、ＷＩ−ＦＩネットワーク、ＷＩ−ＭＡＸネットワーク、セルラー電話ネットワーク（たとえば、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ（登録商標））ネットワークなど）、またはその他の適切な無線ネットワーク、またはこれらのうちの複数の組合せと通信することができる。コンピュータ・システム１２００は、適切な場合には、これらのネットワークのうちの任意のネットワークのための任意の適切な通信インタフェース１２１０を含むことができる。通信インタフェース１２１０は、適切な場合には、１つまたは複数の通信インタフェース１２１０を含むことができる。本開示は、特定の通信インタフェースについて記述し、示しているが、本開示は、任意の適切な通信インタフェースを想定している。
【０１０５】
特定の実施形態においては、バス１２１２は、コンピュータ・システム１２００のコンポーネント同士を互いに結合するハードウェア、ソフトウェア、またはその両方を含む。限定ではなく、例として、バス１２１２は、アクセラレイティッド・グラフィックス・ポート（ＡＧＰ）もしくはその他のグラフィックス・バス、エンハンスト・インダストリー・スタンダード・アーキテクチャ（ＥＩＳＡ）バス、フロントサイド・バス（ＦＳＢ）、ハイパートランスポート（ＨＴ）インターコネクト、インダストリー・スタンダード・アーキテクチャ（ＩＳＡ）バス、インフィニバンド・インターコネクト、ローピンカウント（ＬＰＣ）バス、メモリ・バス、マイクロ・チャネル・アーキテクチャ（ＭＣＡ）バス、ペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バス、ＰＣＩエクスプレス（ＰＣＩｅ）バス、シリアル・アドバンスト・テクノロジー・アタッチメント（ＳＡＴＡ）バス、ビデオ・エレクトロニクス・スタンダーズ・アソシエーション・ローカル（ＶＬＢ）バス、または別の適切なバス、またはこれらのうちの複数の組合せを含むことができる。バス１２１２は、適切な場合には、１つまたは複数のバス１２１２を含むことができる。本開示は、特定のバスについて記述し、示しているが、本開示は、任意の適切なバスまたはインターコネクトを想定している。
【０１０６】
本明細書においては、１つまたは複数の非一時的なコンピュータ可読記憶媒体は、適切な場合には、１つもしくは複数の半導体ベースのもしくはその他の集積回路（ＩＣ）（たとえば、フィールドプログラマブル・ゲート・アレイ（ＦＰＧＡ）もしくは特定用途向け集積回路（ＡＳＩＣ）など）、ハード・ディスク・ドライブ（ＨＤＤ）、ハイブリッド・ハード・ドライブ（ＨＨＤ）、光ディスク、光ディスク・ドライブ（ＯＤＤ）、光磁気ディスク、光磁気ドライブ、フロッピー（登録商標）・ディスケット、フロッピー（登録商標）・ディスク・ドライブ（ＦＤＤ）、磁気テープ、ソリッドステート・ドライブ（ＳＳＤ）、ＲＡＭドライブ、セキュア・デジタル・カードもしくはドライブ、その他の任意の適切な非一時的なコンピュータ可読記憶媒体、またはこれらのうちの複数の組合せを含むことができる。非一時的なコンピュータ可読記憶媒体は、適切な場合には、揮発性、不揮発性、または揮発性と不揮発性の組合せであることが可能である。
【０１０７】
その他
本明細書においては、「または（もしくは）」は、包含的であり、排他的ではない（ただし、そうではないことが明示されている場合、または、そうではないことが文脈によって示されている場合は除く）。したがって、本明細書においては、「ＡまたはＢ」は、「Ａ、Ｂ、またはその両方」を意味する（ただし、そうではないことが明示されている場合、または、そうではないことが文脈によって示されている場合は除く）。その上、「および（ならびに）」は、包括的および個別的の両方である（ただし、そうではないことが明示されている場合、または、そうではないことが文脈によって示されている場合は除く）。したがって、本明細書においては、「ＡおよびＢ」は、「まとめて、または個別に、ＡおよびＢ」を意味する（ただし、そうではないことが明示されている場合、または、そうではないことが文脈によって示されている場合は除く）。
【０１０８】
本開示の範囲は、当技術分野における標準的な技術者が理解するであろう、本明細書において記述されているまたは示されている例示的な実施形態に対するすべての変更、置換、変形、改変、および修正を包含する。本開示の範囲は、本明細書において記述されているまたは示されている例示的な実施形態に限定されない。その上、本開示は、本明細書における各々の実施形態を、特定のコンポーネント、要素、機能、オペレーション、または工程を含むものとして記述し、示しているが、これらの実施形態のいずれも、当技術分野における標準的な技術者が理解するであろう、本明細書の任意の箇所において記述されているまたは示されているコンポーネント、要素、機能、オペレーション、または工程のうちの任意のものの任意の組合せまたは順列を含むことができる。さらに、特定の機能を実行するように適合されている、実行するようにアレンジされている、実行することができる、実行するように構成されている、実行することを可能にされている、実行するように機能できる、または実行するように機能する装置もしくはシステム、または装置もしくはシステムのコンポーネントへの添付の特許請求の範囲における言及は、その装置、システム、コンポーネント、またはその特定の機能が、アクティブ化されているか否か、オンにされているか否か、またはロック解除されているか否かを問わず、その装置、システム、またはコンポーネントが、そうするように適合されている、そうするようにアレンジされている、そうすることができる、そうするように構成されている、そうすることを可能にされている、そうするように機能できる、またはそうするように機能する限り、その装置、システム、コンポーネントを包含する。
【図１】
2018173979.tif 000003
【図２】
2018173979.tif 000004
【図３】
2018173979.tif 000005
【図４】
2018173979.tif 000006
【図５】
2018173979.tif 000007
【図６】
2018173979.tif 000008
【図７】
2018173979.tif 000009
【図８】
2018173979.tif 000010
【図９】
2018173979.tif 000011
【図１０】
2018173979.tif 000012
【図１１】
2018173979.tif 000013
【図１２】
2018173979.tif 000014