(57)【特許請求の範囲】
【請求項１】
トラベルクエリの曖昧性を解消するためのコンピュータ実施方法であって、前記コンピュータ実施方法は、
特定の実行可能命令によって構成される１つまたは複数のコンピューティングデバイスによって実施されるとき、
トラベルアイテム・クエリをユーザに関連付けられたユーザコンピューティングデバイスから受信するステップと、
前記トラベルアイテム・クエリに応答して、複数のトラベルアイテムを識別するステップと、
前記複数のトラベルアイテムの各々のための地理的位置を決定するステップと、
前記複数のトラベルアイテムのそれぞれの地理的位置に従って、前記複数のトラベルアイテムをクラスタ化し、少なくとも２つのトラベルアイテム・クラスタを識別するステップであって、前記少なくとも２つのトラベルアイテム・クラスタの各トラベルアイテム・クラスタは、前記複数のトラベルアイテムからの一組のトラベルアイテムを含むステップと、
前記少なくとも２つのトラベルアイテム・クラスタの第１のトラベルアイテム・クラスタのための予想される関連が、前記第１のトラベルアイテム・クラスタに対応する地理的領域に少なくとも部分的に基づくことを決定するステップであって、前記第１のトラベルアイテム・クラスタのための前記予想される関連は、前記ユーザによって提出された前記トラベルアイテム・クエリ内の用語と、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の地理的識別子と、の間の類似性に基づき決定されるステップと、
前記少なくとも２つのトラベルアイテム・クラスタの第２のトラベルアイテム・クラスタのための予想される関連が、前記第２のトラベルアイテム・クラスタ内のトラベルアイテムの識別子に少なくとも部分的に基づくことを決定するステップであって、前記第２のトラベルアイテム・クラスタのための前記予想される関連は、前記ユーザによって提出された前記トラベルアイテム・クエリ内の前記用語と、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子と、の間の類似性に基づき決定されるステップと、
前記少なくとも２つのトラベルアイテム・クラスタの各トラベルアイテム・クラスタのための識別子を、前記ユーザコンピューティングデバイスに、前記ユーザに提示するために送信するステップであって、前記第１のトラベルアイテム・クラスタのための前記識別子は、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の前記地理的識別子であり、前記第２のトラベルアイテム・クラスタのための前記識別子は、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子であるステップと、
前記ユーザコンピューティングデバイスから、前記少なくとも２つのトラベルアイテム・クラスタからのトラベルアイテム・クラスタの選択を受信するステップと、
前記ユーザコンピューティングデバイスに、前記選択されたトラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムに関する情報を、前記ユーザに提示するために送信するステップと、
を含むコンピュータ実施方法。
【請求項２】
トラベルアイテムは、宿泊設備、地上輸送機関、アクティビティ、ツアー、日帰り旅行または目的地サービスの少なくとも１つを備える、
請求項１に記載のコンピュータ実施方法。
【請求項３】
前記トラベルアイテム・クエリは、自由形式のテキスト・クエリである、
請求項１に記載のコンピュータ実施方法。
【請求項４】
前記トラベルアイテム・クエリ内の、所定の品詞に対応する１つまたは複数の用語を識別するステップと、
前記１つまたは複数の用語を前記トラベルアイテム・クエリから取り除くステップと、
をさらに含む、
請求項１に記載のコンピュータ実施方法。
【請求項５】
複数のトラベルアイテムのための位置情報を含むデータストアと、
前記データストアと通信するコンピューティングデバイスと、
を備えるシステムであって、
前記コンピューティングデバイスは、コンピュータ実行可能命令によって実行されるとき、前記コンピューティングデバイスに、少なくとも、
トラベルアイテム・クエリを他のコンピューティングデバイスから受信することと、
前記トラベルアイテム・クエリに応答して、前記複数のトラベルアイテムを前記データストアから識別することと、
前記複数のトラベルアイテムの各トラベルアイテムのためのそれぞれの前記位置情報に従って、前記複数のトラベルアイテムをクラスタ化し、少なくとも２つのトラベルアイテム・クラスタを識別することであって、前記少なくとも２つのトラベルアイテム・クラスタの各トラベルアイテム・クラスタは、前記複数のトラベルアイテムからの一組のトラベルアイテムを含むことと、
前記少なくとも２つのトラベルアイテム・クラスタの第１のトラベルアイテム・クラスタのための予想される関連が、前記第１のトラベルアイテム・クラスタに対応する地理的領域に少なくとも部分的に基づくことを決定することであって、前記第１のトラベルアイテム・クラスタのための前記予想される関連は、ユーザによって提出された前記トラベルアイテム・クエリ内の用語と、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の地理的識別子と、の間の類似性に基づき決定されることと、
前記少なくとも２つのトラベルアイテム・クラスタの第２のトラベルアイテム・クラスタのための予想される関連が、前記第２のトラベルアイテム・クラスタ内のトラベルアイテムの識別子に少なくとも部分的に基づくことを決定することであって、前記第２のトラベルアイテム・クラスタのための前記予想される関連は、前記ユーザによって提出された前記トラベルアイテム・クエリ内の前記用語と、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子と、の間の類似性に基づき決定されることと、
前記少なくとも２つのトラベルアイテム・クラスタの各トラベルアイテム・クラスタのための識別子を前記他のコンピューティングデバイスに送信することであって、前記第１のトラベルアイテム・クラスタのための前記識別子は、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の前記地理的識別子であり、前記第２のトラベルアイテム・クラスタのための前記識別子は、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子であることと、
前記他のコンピューティングデバイスから、前記少なくとも２つのトラベルアイテム・クラスタからのトラベルアイテム・クラスタの選択を受信することと、
前記他のコンピューティングデバイスに、前記選択されたトラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムに関する情報を送信することと、
をさせるように構成される、
システム。
【請求項６】
前記コンピュータ実行可能命令は、前記コンピューティングデバイスに、さらに少なくとも、
前記第１のトラベルアイテム・クラスタ内の各トラベルアイテムの前記位置情報に少なくとも部分的に基づいて、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域を識別させる、
請求項５に記載のシステム。
【請求項７】
前記コンピュータ実行可能命令は、前記コンピューティングデバイスに、さらに少なくとも、
前記第１のトラベルアイテム・クラスタに対応する前記地理的領域を、前記データストア内で識別される複数の所定の地理的領域から識別させる、
請求項５に記載のシステム。
【請求項８】
前記コンピュータ実行可能命令は、前記コンピューティングデバイスに、少なくとも、
単純ベイズ分類器に従って、前記クエリの１つまたは複数の用語を処理することに少なくとも部分的に基づいて、前記複数のトラベルアイテムを前記データストアから前記クエリに応答するものとして識別させる、
請求項５に記載のシステム。
【請求項９】
前記単純ベイズ分類器は、前記クエリの前記１つまたは複数の用語を前記複数のトラベルアイテムに関連付けるクリックストリーム・データに少なくとも部分的に基づく、
請求項８に記載のシステム。
【請求項１０】
コンピュータ実行可能命令を含む非一時的コンピュータ可読媒体であって、
前記コンピュータ実行可能命令は、プロセッサを備えるコンピューティングシステムによって実行されるとき、前記コンピューティングシステムに、少なくとも、
トラベルアイテム・クエリをコンピューティングデバイスから受信することと、
前記トラベルアイテム・クエリに応答して、複数のトラベルアイテムを識別することであって、前記複数のトラベルアイテムの各々は、位置情報に関連付けられていることと、
前記複数のトラベルアイテムのそれぞれの位置情報に従って、前記複数のトラベルアイテムをクラスタ化し、少なくとも２つのトラベルアイテム・クラスタを識別することであって、前記少なくとも２つのトラベルアイテム・クラスタの各々は、前記複数のトラベルアイテムからの一組のトラベルアイテムを含むことと、
前記少なくとも２つのトラベルアイテム・クラスタの第１のトラベルアイテム・クラスタのための予想される関連が、前記第１のトラベルアイテム・クラスタに対応する地理的領域に少なくとも部分的に基づくことを決定することであって、前記第１のトラベルアイテム・クラスタのための前記予想される関連は、ユーザによって提出された前記トラベルアイテム・クエリ内の用語と、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の地理的識別子と、の間の類似性に基づき決定されることと、
前記少なくとも２つのトラベルアイテム・クラスタの第２のトラベルアイテム・クラスタのための予想される関連が、前記第２のトラベルアイテム・クラスタ内のトラベルアイテムの識別子に少なくとも部分的に基づくことを決定することであって、前記第２のトラベルアイテム・クラスタのための前記予想される関連は、前記ユーザによって提出された前記トラベルアイテム・クエリ内の前記用語と、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子と、の間の類似性に基づき決定されることと、
前記少なくとも２つのトラベルアイテム・クラスタの各々のための識別子を前記コンピューティングデバイスに送信することであって、前記第１のトラベルアイテム・クラスタのための前記識別子は、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の前記地理的識別子であり、前記第２のトラベルアイテム・クラスタのための前記識別子は、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子であることと、
前記コンピューティングデバイスから、前記少なくとも２つのトラベルアイテム・クラスタからのトラベルアイテム・クラスタの選択を受信することと、
前記コンピューティングデバイスに、前記トラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムに関する情報を送信することと、
をさせる、
非一時的コンピュータ可読媒体。
【請求項１１】
前記位置情報は、トラベルアイテムに対応する地理座標またはトラベルアイテムの住所情報の少なくとも１つを含む、
請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１２】
前記コンピュータ実行可能命令が、前記コンピューティングデバイスに、前記複数のトラベルアイテムのそれぞれの位置情報に従って、前記複数のトラベルアイテムをクラスタ化し、少なくとも２つのトラベルアイテム・クラスタを識別させることは、少なくとも部分的に、
前記複数のトラベルアイテム内の各トラベルアイテムのために、
前記トラベルアイテムの位置が任意の以前に確立したクラスタから閾値距離内にあるかを決定し、
前記トラベルアイテムが以前に確立したクラスタから前記閾値距離内にあることが決定される場合、前記トラベルアイテムを前記以前に確立したクラスタ内に含み、
前記トラベルアイテムが任意の以前に確立したクラスタから前記閾値距離内にないことが決定される場合、前記トラベルアイテムを含む新しいクラスタを確立する、
ことによって行われる、
請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１３】
前記コンピュータ実行可能命令は、前記コンピューティングデバイスに、さらに少なくとも、
前記選択されたトラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムをランク付けさせ、
前記選択されたトラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムの表現は、前記トラベルアイテムのそれぞれのランキングに従って、前記一組のトラベルアイテムを表す、
請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１４】
前記コンピュータ実行可能命令は、前記コンピューティングデバイスに、さらに少なくとも、
前記トラベルアイテム・クエリ内の、所望のアメニティに対応する１つまたは複数の用語を識別させ、
前記所望のアメニティに少なくとも部分的に基づいて、前記選択されたトラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムをランク付けさせる、
請求項１３に記載の非一時的コンピュータ可読媒体。
【請求項１５】
コンピュータ実施方法であって、
特定のコンピュータ実行可能命令を実行するプロセッサの制御下で、
トラベルアイテム・クエリをコンピューティングデバイスから受信するステップと、
前記トラベルアイテム・クエリに応答して、複数のトラベルアイテムを識別するステップであって、前記複数のトラベルアイテムの各々は、位置情報に関連付けられているステップと、
前記複数のトラベルアイテムのそれぞれの位置情報に従って、前記複数のトラベルアイテムをクラスタ化し、少なくとも２つのトラベルアイテム・クラスタを識別するステップであって、前記少なくとも２つのトラベルアイテム・クラスタの各々は、前記複数のトラベルアイテムからの一組のトラベルアイテムを含むステップと、
前記少なくとも２つのトラベルアイテム・クラスタの第１のトラベルアイテム・クラスタのための予想される関連が、前記第１のトラベルアイテム・クラスタに対応する地理的領域に少なくとも部分的に基づくことを決定するステップであって、前記第１のトラベルアイテム・クラスタのための前記予想される関連は、ユーザによって提出された前記トラベルアイテム・クエリ内の用語と、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の地理的識別子と、の間の類似性に基づき決定されるステップと、
前記少なくとも２つのトラベルアイテム・クラスタの第２のトラベルアイテム・クラスタのための予想される関連が、前記第２のトラベルアイテム・クラスタ内のトラベルアイテムの識別子に少なくとも部分的に基づくことを決定するステップであって、前記第２のトラベルアイテム・クラスタのための前記予想される関連は、前記ユーザによって提出された前記トラベルアイテム・クエリ内の前記用語と、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子と、の間の類似性に基づき決定されるステップと、
前記少なくとも２つのトラベルアイテム・クラスタの各トラベルアイテム・クラスタのための識別子を、前記コンピューティングデバイスに、前記ユーザに提示するために送信するステップであって、前記第１のトラベルアイテム・クラスタのための前記識別子は、前記第１のトラベルアイテム・クラスタに対応する前記地理的領域の前記地理的識別子であり、前記第２のトラベルアイテム・クラスタのための前記識別子は、前記第２のトラベルアイテム・クラスタ内の前記トラベルアイテムの前記識別子であるステップと、
前記コンピューティングデバイスに、選択されたトラベルアイテム・クラスタ内に含まれる前記一組のトラベルアイテムに関する情報を送信するステップと、
を含むコンピュータ実施方法。
【請求項１６】
前記トラベルアイテム・クエリ内の、地理的位置に対応する１つまたは複数の用語を識別するステップをさらに含み、
前記トラベルアイテム・クエリに応答して、複数のトラベルアイテムを識別するステップは、前記地理的位置に対応する複数のトラベルアイテムを識別するステップを含む、
請求項１５に記載のコンピュータ実施方法。
【請求項１７】
前記トラベルアイテム・クエリ内の、所望のアメニティに対応する１つまたは複数の用語を識別するステップをさらに含み、
前記トラベルアイテム・クエリに応答して、複数のトラベルアイテムを識別するステップは、前記トラベルアイテム・クエリ内の、所望のアメニティに対応する前記１つまたは複数の用語を無視するステップを含む、
請求項１５に記載のコンピュータ実施方法。
【請求項１８】
前記トラベルアイテム・クエリ内の、前記所望のアメニティに対応する１つまたは複数の用語を識別するステップは、自然言語処理を前記トラベルアイテム・クエリに適用するステップを含む、
請求項１７に記載のコンピュータ実施方法。
【請求項１９】
前記少なくとも２つのトラベルアイテム・クラスタの各々のための前記決定された識別子に少なくとも部分的に基づいて、トラベルアイテム・クラスタを前記少なくとも２つのトラベルアイテム・クラスタから識別するステップは、
前記コンピューティングデバイスに、前記少なくとも２つのトラベルアイテム・クラスタの各々の前記識別子を送信するステップと、
前記コンピューティングデバイスから、前記トラベルアイテム・クラスタの選択を受信するステップと、
を含む、
請求項１５に記載のコンピュータ実施方法。
【請求項２０】
前記少なくとも２つのトラベルアイテム・クラスタの各々のための前記決定された識別子に少なくとも部分的に基づいて、トラベルアイテム・クラスタを前記少なくとも２つのトラベルアイテム・クラスタから識別するステップは、
前記コンピューティングデバイスに関連付けられたユーザによって獲得されるトラベルアイテムの履歴に少なくとも部分的に基づいて、前記ユーザの少なくとも１つの好適な地理的領域を決定するステップと、
前記トラベルアイテム・クラスタの位置が前記好適な地理的領域に対応することを決定するステップと、
を含む、
請求項１５に記載のコンピュータ実施方法。
【発明の詳細な説明】
【背景技術】
【０００１】
[0001]コンピューティングデバイスおよびコンピューティングネットワークは、ユーザによってしばしば使用され、さまざまな主題に関する情報を取得する。提供される情報の幅のため、多くのネットワークベースのシステムは、ユーザがこのシステム上で情報を検索することを可能にする。一般に、ユーザは、はっきりしている（構造化されている）クエリまたははっきりしていない（構造化されていない）クエリをネットワークベースのシステムに提出することができ、次に、システムは、クエリを一組の潜在的検索結果に整合することを試みる。はっきりしていないクエリ、例えば自由形式のテキスト文字列は、使いやすいため、ユーザによってしばしば好まれる。しかしながら、これらのクエリは、部分的にはそのはっきりしていない性質のため、しばしば曖昧であり、それゆえ結果として、少なくとも部分的に無関係な検索結果がユーザに提供されてしまう。
【発明の概要】
【発明が解決しようとする課題】
【０００２】
[0002]例えば、ミズーリ州スプリングフィールドの市内のホテル宿泊設備に関する情報を見つけることに関心を持つユーザは、ネットワークベースのサービスで、クエリ文字列「スプリングフィールド内のホテル」を用いて検索してもよい。しかしながら、ネットワークベースのサービスは、クエリのテキストから、ユーザが「スプリングフィールド」のどの特定の市（例えば、ミズーリ州スプリングフィールド、マサチューセッツ州スプリングフィールド、オレゴン州スプリングフィールドなど）に関心を持つかを決定することができないかもしれないし、または、実際、「スプリングフィールド」がそもそも米国の市を意味するかを決定することができないかもしれない。このように、単にクエリを実行し、一組の結果を提供するだけでは、無関係な情報をユーザに提示する可能性が非常に高く、結果として、システムに対するユーザの満足感を減少させ、サービスをユーザに提供するのに必要な計算資源の使用が増加する。
【図面の簡単な説明】
【０００３】
【図１】例示的ネットワーク環境の概略ブロック図であり、トラベルサービスは、ユーザがトラベルアイテムのためのクエリを提出するのを可能にし、結果の地理的クラスタ化に基づいて、ユーザクエリの曖昧性を解消するように動作してもよい。
【図２】図１のトラベルサービス内に含まれるクエリ処理システムの例示的ブロック図であり、結果の地理的クラスタ化に基づいて、ユーザクエリを処理し、潜在的曖昧性を検出してもよい。
【図３】例示的ユーザインタフェースであり、このユーザインタフェースは、ユーザコンピューティングデバイス上に表示され、ユーザに潜在的に曖昧なクエリを通知し、検出される曖昧性に基づいて、クエリの結果を提供してもよい。
【図４】検索結果の地理的クラスタ化の例示的視覚化であり、例示的視覚化は、対応するクエリ内の曖昧性を示してもよい。
【図５Ａ】曖昧性を含んでもよいユーザが提出したクエリを処理するため、結果の地理的クラスタ化に基づいてこの種の曖昧性を検出するため、および、クエリの結果をユーザに提供するためのフロー図である。
【図５Ｂ】曖昧性を含んでもよいユーザが提出したクエリを処理するため、結果の地理的クラスタ化に基づいてこの種の曖昧性を検出するため、および、クエリの結果をユーザに提供するためのフロー図である。
【発明を実施するための形態】
【０００４】
[0008]一般的に記載すると、本発明の態様は、曖昧な用語または検索基準を含んでもよいユーザが提出したクエリを処理することに関するものであり、曖昧性を解消し、意味がありかつ正確な検索結果をユーザに提供するためのものである。より具体的には、本発明の態様は、検索結果の地理的クラスタ化を、位置ベースの商品またはサービス（例えばホテル宿泊設備）のために利用し、有効な結果が位置しうる一組の潜在的エリアまたは領域を決定して、顧客にさまざまなエリアまたは領域を通知する。例示的には、米国ベースのネットワーク・トラベルサービスのユーザは、「スプリングフィールド内のホテル」のためのクエリを提出してもよい。トラベルサービスは、クエリのための有効な結果が、ミズーリ州スプリングフィールド、オレゴン州スプリングフィールドまたはマサチューセッツ州スプリングフィールド内のホテルを含んでもよいことを決定してもよい。したがって、ユーザは、ホテル宿泊設備が所望される正しい位置を選択するように促されてもよい。後述するように、トラベルサービスは、クエリの用語を特定領域に文字通りにマッピングする必要なく（例えば、「スプリングフィールド」という名前の市が複数の州内に存在する場合、「スプリングフィールド」が参照する１つの市を検出する必要なく）、潜在的に有効な結果を含む一組の領域を決定してもよい。このように、トラベルサービスは、任意の自由形式のクエリの曖昧性を解消することができてもよい。例えば、「浜辺のホテル」のためのクエリは、結果として、浜辺を有するさまざまな位置（例えば、ハワイ、カリフォルニア、フロリダなど）の潜在的結果を検出してもよい。同様に、「エッジウォーター・ホテル」のためのクエリは、結果として、（「エッジウォーター・ホテル」という名前のホテルが位置する）ワシントン州シアトルと、ニュージャージー州エッジウォーターの市内と、の両方内の潜在的なホテル宿泊設備を検出してもよい。後述するように、それゆえ、トラベルサービスは、より高速かつ正確にユーザクエリを処理することができてもよく、その結果、ユーザ体験が改善され、ネットワーク・トラベルサービスを利用するのに必要な計算資源が減少する。
【０００５】
[0009]クエリに対する潜在的に有効な結果が位置する一組のエリアまたは領域を決定するために、トラベルサービスは、結果のクラスタ化を利用してもよい。具体的には、トラベルサービスは、クエリを最初に実行し、一組の結果を決定してもよい（例えば、後述するアルゴリズム、技術分野で周知の従来の検索アルゴリズムまたは任意の他の検索アルゴリズムに従って）。その後、トラベルサービスは、各検索結果の地理的位置を決定してもよい。例えば、トラベルサービスは、周知の住所データまたは緯度および経度データを、一組の結果の各々のために利用し、位置を結果に割り当ててもよい。次に、トラベルサービスは、それらの割り当てられた位置に従って、結果をクラスタ化してもよい。一実施形態では、結果は、単純な距離計算に基づいてクラスタ化されてもよく、（トラベルサービスによって予め定義されてもよい）互いの閾値距離内の２つの結果は、同じ「クラスタ」内に配置され、一方、任意の既存のクラスタからの閾値距離超の結果は、新しいクラスタ内に配置される。他のクラスタリング・アルゴリズム、例えば「ｋ平均」クラスタリングは、技術分野で周知であり、結果クラスタを決定するために利用されてもよい。
【０００６】
[0010]一組の結果クラスタが決定された後、トラベルサービスは、識別子をクラスタに割り当ててもよい。一実施形態では、識別子は、クラスタ内の各結果に関する既存のメタデータに基づいてもよい。例えば、トラベルサービスは、各結果のための多数の地理的識別子を維持してもよく、地理的識別子は、各結果の市、郡、領域、州、国などを示す。このように、各クラスタは、クラスタ内のすべての結果によって共有される最も特徴的な地理的識別子に基づいて識別されてもよい。したがって、ワシントン州シアトルのダウンタウン内の結果クラスタは、「ワシントン州シアトルのダウンタウン内のホテル」として識別されてもよく、一方、ロードアイランド州全体に広がる結果クラスタは、「ロードアイランド内のホテル」として識別されてもよい。
【０００７】
[0011]その後、決定された一組のクラスタに関する情報は、ユーザのクエリに応答してユーザに提示されてもよい。例えば、「スプリングフィールド内のホテル」のためのクエリによって、トラベルサービスは、潜在的結果が、ミズーリ州スプリングフィールド、オレゴン州スプリングフィールドまたはマサチューセッツ州スプリングフィールド内に見つけられたという印を返答（リターン）し、ユーザがこれらの領域の１つを選択するように要求し、選択領域内のホテル宿泊設備を表示してもよい。このように、最初にオレゴン州スプリングフィールド内のホテル宿泊設備を検索することを意図したユーザには、ミズーリ州スプリングフィールド内のホテル宿泊設備のための結果が提示されない（さもなければ一組の検索結果内でより顕著に表示されるかもしれない）。さらに、結果のクラスタ化に基づいて、クエリの曖昧性を解消したので、トラベルサービスは、検索を実行する前に、検索基準内の曖昧性を検出する別々のシステムを実施することを試みる必要がない。このようにクラスタ化に基づく曖昧性解消は、他の曖昧性解消技術、例えば潜在的に曖昧な用語またはフレーズの所定のリストを検出するために各クエリをスキャンすることに対して明らかな改善を表す。
【０００８】
[0012]いくつかの実施形態では、トラベルサービスは、ユーザが関心を持つエリアを表す可能性が高いクラスタと、ユーザが関心を持つ特定のアイテムを含む可能性が高いクラスタと、を区別するように構成されてもよい。例えば、「エッジウォーター・ホテル」のためのクエリは、結果として、２つのクラスタになってもよい。第１のクラスタは、ワシントン州シアトル内のジ・エッジウォーター・ホテルおよびシアトル内の他の近くのホテルを含み、第２のクラスタは、ニュージャージー州エッジウォーター地区内のさまざまなホテルを含む。第１のクラスタ内のホテルの各々が「ワシントン州シアトル内のホテル」として正確に記述されてもよいが、この種の記述は、特定の「エッジウォーター・ホテル」を検索するユーザには役に立たないと見えるかもしれない（なぜなら、この種の結果は、最初の検索より漠然としているように見えるかもしれないからである）。したがって、第１のクラスタに対応する領域をユーザに提示するよりはむしろ、トラベルサービスは、そのクラスタ内に含まれるジ・エッジウォーター・ホテルが、ユーザが関心を持つ特定のアイテムであると検出してもよい。このように、トラベルサービスは、結果の第１のクラスタをユーザにシアトル内のジ・エッジウォーター・ホテルに対応するものとして表してもよく、ユーザが、第１のクラスタを選択し、ジ・エッジウォーター・ホテルでのホテル宿泊設備を見ることを可能にしてもよい。
【０００９】
[0013]いくつかの例では、クラスタの明確なユーザ選択に追加的または代替的に、ユーザのユーザ履歴または他のユーザプロファイルデータを用いて、クラスタ間を区別してもよい。例えば、トラベルサービスが、特定の地理的領域内の特定の日付のユーザの以前の購入記録を有する場合、トラベルサービスは、その地理的領域に対応するクラスタを選択することによって、その特定の日付のユーザの追加のクエリの曖昧性を自動的に解消することができる。さらなる例として、トラベルサービスが、（例えば、反復された過去の購入、領域のための選好の明確な印などによって示されるような）特定領域のためのユーザ選好の記録を有する場合、トラベルサービスは、特定領域に対応するクラスタを選択することによって、ユーザのクエリの曖昧性を自動的に解消することができる。いくつかの例では、好適領域に対応するクラスタを自動的に選択するよりはむしろ、トラベルサービスは、領域のためのユーザ選好を利用し、クラスタを優先してもよい（例えば、好適領域に対応するクラスタが代替のクラスタより上に表示される）。
【００１０】
[0014]当業者によって認識されるように、検索クエリの曖昧性を解消するために地理的クラスタ化を用いることは、従来の実施態様に勝る重要な利点を表す。具体的には、地理的クラスタ化を用いることにより、ユーザに提示される無関係な結果の数が減少し、それゆえ、ユーザは、関心を持つアイテムを、より高速かつ効率的に検索および見つけることができる。このように、クエリの曖昧性を解消するために地理的クラスタ化を用いることにより、トラベルサービスは、より効率的に動作することができてもよく、トラベルサービスは、より高速にかつより少ない計算資源を利用して、関連するクエリ結果を返答することができる。さらに、検索クエリの曖昧性を解消するために地理的クラスタ化を用いることは、（例えば、クエリ用語を潜在的に曖昧な用語の周知のリストに整合することを試みることによって）クエリ自体の独立分析を必要とせず、むしろ、クエリに整合するさまざまな検索結果を利用し、曖昧性を検出する。このように、本願明細書に記載されている実施形態は、既存のシステムに対する大きな進歩を表す。
【００１１】
[0015]本願明細書では、トラベルサービスの特定のタイプ、例えばホテル宿泊設備に関する例が提供されるが、本発明の実施形態は、任意の地理的ベースのアイテムまたはサービスに適用されてもよく、アイテムまたはサービスは、飛行機、宿泊設備、他の輸送機関、アクティビティ、ツアー、旅行保険、日帰り旅行、目的地サービスまたはそれらの組み合わせを含むが、これらに限定されるものではない。
【００１２】
[0016]図１は、例示的動作環境を表すブロック図であり、ネットワークベースのトラベルサービス１５０により、顧客は、第三者提供者またはトラベルサービス１５０のオペレータによって利用できるようにしたトラベルアイテムを閲覧、検索および獲得することができる。図１に例示するように、動作環境は、１つまたは複数の予約システム１２０および１つまたは複数のユーザコンピューティングデバイス１１０を含み、これらは、ネットワーク１３０を介してネットワークベースのトラベルサービス１５０に接続されている。第三者提供者は、予約システム１２０を用いて、トラベルアイテムまたはトラベルアイテムに関する情報を、ネットワーク１３０を介してトラベルサービス１５０が利用できるようにしてもよい。次に、トラベルサービス１５０は、トラベルアイテムおよび他のトラベルアイテムを旅行者コンピューティングデバイス１１０が利用できるようにしてもよい。したがって、予想される旅行者は、ユーザコンピューティングデバイス１１０を用いて、トラベルサービス１５０から利用できるトラベルアイテムを閲覧し、トラベルアイテムを検索し、１つまたは複数の所望のトラベルアイテムを獲得または予約することができる。
【００１３】
[0017]ユーザコンピューティングデバイス１１０は、任意のコンピューティングデバイス、例えばラップトップまたはタブレットコンピュータ、パーソナルコンピュータ、サーバ、携帯情報端末（ＰＤＡ）、ハイブリッドＰＤＡ／携帯電話、携帯電話、電子ブックリーダ、セットトップボックス、カメラ、デジタルメディアプレーヤなどでもよい。予約システム１２０およびユーザコンピューティングデバイス１１０は、ネットワーク１３０を介してトラベルサービス１５０と通信してもよい。当業者は、ネットワーク１３０が任意の有線ネットワーク、無線ネットワークまたはそれらの組み合わせでもよいことを認識するであろう。さらに、ネットワーク１３０は、パーソナル・エリア・ネットワーク、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、ケーブル・ネットワーク、衛星ネットワーク、携帯電話ネットワークまたはそれらの組み合わせでもよい。例示的実施形態では、ネットワーク１３０は、インターネットである。インターネットまたは他の上述したタイプの通信ネットワークのいずれかを介して通信するためのプロトコルおよび構成要素は、コンピュータ通信の当業者に周知であるので、本願明細書においてさらに詳細に記載される必要はない。
【００１４】
[0018]予約システム１２０は、トラベルアイテムの予約または獲得を可能にするように構成される任意のシステムまたはデバイスに対応してもよい。例えば、予約システム１２０は、集中型予約システム（ＣＲＳ）、グローバル分散システム（ＧＤＳ）または任意の他のシステムに対応してもよく、ここでは、複数のトラベルアイテムの提供者、例えば航空会社、ホテル、レンタカー会社、船旅会社、バスサービスなどは、トラベルアイテムを予約および／または購入に利用できるようにする。他の実施形態では、予約システム１２０は、個々のトラベルアイテムの提供者（例えば、特定の航空会社、ホテルまたはホテルチェーン、レンタカー会社、船旅会社、バスサービスなど）により提供されるシステムに対応してもよい。一般的に、各予約システムにより、他のネットワークベースのデバイス、例えばトラベルサービス１５０のデバイスは、トラベルアイテムに関する情報（例えば、利用可能性、価格、トラベル計画など）を要求し、トラベルアイテムを検索し、トラベルアイテムを予約または獲得することができてもよい。予約システムの動作は、技術分野で周知であるので、本願明細書ではさらに詳細に記載されない。
【００１５】
[0019]例示的実施形態では、トラベルサービス１５０は、いくつかのコンピュータシステムを含むコンピュータ環境として例示され、いくつかのコンピュータシステムは、１つまたは複数のネットワークを用いて相互接続される。より具体的には、トラベルサービス１５０は、ユーザインタフェースシステム１５６、予約システム・インタフェース１５２、クエリ処理システム１５４、旅行者プロファイル・データストア１５８およびトラベルアイテム・データストア１６０を含んでもよい。図１では別個のシステムとして示されるが、いくつかの実施形態では、ユーザインタフェースシステム１５６、予約システム・インタフェース１５２、クエリ処理システム１５４、旅行者プロファイル・データストア１５８およびトラベルアイテム・データストア１６０の１つまたは複数は、１つまたは複数の集約システムに組み合わせられてもよい。さらに、トラベルサービス１５０が図１に例示されるより少ないまたは多い構成要素を有することができ、さまざまなウェブサービスおよび／またはピアツーピア・ネットワーク構成を含むことができることを当業者は認識されたい。いくつかの実施形態では、トラベルサービス１５０の１つまたは複数の構成要素は、ホストコンピューティング環境において実施される仮想機械によって実施されてもよい。ホストコンピューティング環境は、１つまたは複数の高速に設定および解放された計算資源を含んでもよく、計算資源は、コンピューティングデバイス、ネットワークデバイスおよび／またはストレージデバイスを含んでもよい。ホストコンピューティング環境は、クラウドコンピューティング環境と称されてもよい。このように、図１のトラベルサービス１５０の表現は、例示的であり、本発明を限定しないものと認識されたい。
【００１６】
[0020]ユーザインタフェースシステム１５６、予約システム・インタフェース１５２、クエリ処理システム１５４、旅行者プロファイル・データストア１５８およびトラベルアイテム・データストア１６０の任意の１つまたは複数は、複数の構成要素内で実施されてもよく、各構成要素は、ユーザインタフェースシステム１５６、予約システム・インタフェース１５２、クエリ処理システム１５４、旅行者プロファイル・データストア１５８およびトラベルアイテム・データストア１６０のそれぞれのインスタンスを実行する。ユーザインタフェースシステム１５６、予約システム・インタフェース１５２、クエリ処理システム１５４、旅行者プロファイル・データストア１５８およびトラベルアイテム・データストア１６０の任意の１つを実施するサーバまたは他のコンピューティング構成要素は、ネットワーク・インタフェース、メモリ、処理ユニットおよびコンピュータ可読媒体ドライブを含んでもよく、これらのすべては、互いに通信バスを介して通信してもよい。ネットワーク・インタフェースは、ネットワーク１３０および／または他のネットワークまたはコンピュータシステムを介した接続を提供してもよい。処理ユニットは、プログラム命令を含むメモリと通信してもよく、処理ユニットは、命令を実行し、ユーザインタフェースシステム１５６、予約システム・インタフェース１５２、クエリ処理システム１５４、旅行者プロファイル・データストア１５８およびトラベルアイテム・データストア１６０のそれぞれを動作する。メモリは、一般的に、ＲＡＭ、ＲＯＭ、他の持続的な補助メモリおよび／または任意の非一時的コンピュータ可読媒体を含んでもよい。
【００１７】
[0021]本発明の実施形態に従って、クエリ処理システム１５４は、クエリを処理し、一組のクエリ結果を決定するように構成されてもよい（例えば、ユーザコンピューティングデバイス１１０にユーザインタフェースシステム１５６を介して提示するために）。より具体的には、クエリ処理システム１５４は、地理的ベースのクラスタ化を利用し、曖昧なクエリを検出し、ユーザコンピューティングデバイス１１０に、各結果クラスタの印（インジケータ）を提示してもよい（例えば、クラスタが位置する地理的領域の識別子として、または、ユーザが関心を持つ可能性が高いクラスタ内の特定のアイテムの識別子として）。後述するように、クエリ処理システム１５４は、クエリ上の追加の前処理または後処理を実行し、結果の精度を増加させてもよい。
【００１８】
[0022]いくつかの実施形態では、クエリ処理システム１５４は、予約システム１２０から取得されるトラベルアイテムに関する情報を利用してもよい。予約システム１２０との相互作用は、予約システム・インタフェース１５２によって容易にされてもよく、予約システム・インタフェース１５２は、予約システム１２０上の関連するトラベルアイテムに関する情報を問い合わせ、トラベルアイテムに関する情報を予約システム１２０から検索し、トラベルアイテムをユーザのために予約することを可能にしてもよい。いくつかの実施形態では、複数の予約システム・インタフェース１５２が提供され、各々が１つまたは複数の特定の予約システム１２０と相互作用するように構成されてもよい。例えば、第１の予約システム・インタフェース１５２は、航空会社ベースの予約システム１２０と相互作用してもよく、一方、第２の予約システム・インタフェース１５２は、ホテルベースの予約システム１２０と相互作用してもよい。予約システム１２０との相互作用のためのシステムおよび方法の実施形態は、２００９年５月２１日に出願された、「ＯＰＴＩＭＩＺＥＤ  ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＦＩＮＤＩＮＧ  ＢＥＳＴ  ＦＡＲＥ」という名称の米国特許出願第１２／４７０４４２号明細書（ＵＳ２００９２３４６８１Ａ１）に記載され、その全体が本願明細書に引用されるものである。
【００１９】
[0023]クエリ処理システム１５４は、トラベルアイテム・データストア１６０からの情報をさらに利用してもよく、トラベルアイテム・データストア１６０は、関連するトラベルアイテムに関するさまざまなデータを含んでもよい。トラベルアイテム・データストア１６０は、任意の物理的なデータストア、物理的なデータストアの集合、または、１つまたは複数の物理的なデータストアによって実施される仮想データストアに対応することができ、例えば、ハードディスクドライブ（ＨＤＤ）、ソリッドステートドライブ（ＳＳＤ）、テープドライブ、ネットワーク接続ストレージ（ＮＡＳ）または任意の他の持続的または実質的に持続的なストレージ構成要素である。いくつかの例では、トラベルアイテム・データストア１６０内のデータ（例えば、名前、住所、利用できる予約タイプなど）は、予約システム１２０から予約システム・インタフェース１５２を介して取得されてもよい。トラベルアイテム・データストア１６０は、トラベルサービス１５０自体によって生成される情報、または、ユーザコンピューティングデバイス１１０によってトラベルサービス１５０に提出された情報をさらに含んでもよく、情報は、例えば、レビュー、評価、画像またはさまざまなトラベルアイテムについてのコメントである。トラベルアイテム・データストア１６０は、第三者サービス、例えば、独立したトラベルアイテム評価サービスまたは旅行代理店（図１に図示せず）によって検索または提出される情報を含んでもよい。いくつかの例では、クエリ処理システム１５４は、予約システム１２０との通信の遅延により、予約システム１２０から直接検索される情報より排他的または優先的に、トラベルアイテム・データストア１６０からの情報を利用してもよい。それゆえ、いくつかの例では、トラベルアイテム・データストア１６０は、予約システム１２０または他の別個のシステム（図１に図示せず）からの情報を、クエリ処理システム１５４が使用するためにキャッシュするように機能してもよい。
【００２０】
[0024]クエリ処理システム１５４への提出は、ユーザコンピューティングデバイス１１０によってユーザインタフェースシステム１５６を介して提出されてもよく、ユーザインタフェースシステム１５６は、また、クエリ結果をユーザコンピューティングデバイス１１０に送信してもよい。したがって、ユーザインタフェースシステム１５６は、ユーザがユーザコンピューティングデバイス１１０を介してトラベルアイテムを検索、閲覧および獲得（例えば、予約などによって）するのを容易にしてもよい。いくつかの実施形態では、ユーザインタフェースシステム１５６は、ネットワークサーバ、例えばウェブサーバを、ネットワークページ（例えば、ウェブページ）の受信デバイスによる提示のための命令を生成するために含んでもよく、ネットワークページは、この種の検索、閲覧および獲得を容易にする。命令がユーザインタフェースシステム１５６によって生成されてもよいユーザインタフェースの一例が、以下、図３においてさらに詳細に記載されている。
【００２１】
[0025]ユーザインタフェースシステム１５６は、旅行者プロファイル・データストア１５８からの情報を格納、維持および獲得するようにさらに構成されてもよい。旅行者プロファイル・データストア１５８は、任意の持続的または実質的に持続的なデータストアに対応してもよく、例えば１つまたは複数のハードディスクドライブ（ＨＤＤ）、ソリッドステートドライブ（ＳＳＤ）またはネットワーク接続ストレージデバイス（ＮＡＳ）である。旅行者プロファイル・データストア１５８は、ユーザに関する情報、例えば、ユーザの名前、年齢、住所、生年月日、クレジットカード情報、購入履歴および旅行予約、常連旅客または報酬プログラム情報などを、トラベルサービス１５０による使用のために格納してもよい。後述するように、旅行者プロファイル・データストア１５８からの情報を利用して、１つまたは複数の好適領域を、クエリを提出するユーザのために決定してもよく、このことが、クエリの曖昧性解消を支援してもよい。
【００２２】
[0026]図２には、クエリ処理システム１５４に関するさらなる詳細が示され、図２は、クエリ処理システム１５４の例示的構成要素を表すブロック図である。構成要素２０２〜２１０の各々は、クエリ処理システム１５４内の別個のコンピューティングデバイス（コンピュータ実行可能命令を実行するように構成される少なくとも１つの物理的なプロセッサを含む）を表してもよいし、または、クエリ処理システム１５４内の１つまたは複数のコンピューティングデバイス内に含まれる少なくとも１つのプロセッサによって実行されるプログラム、機能、コードモジュールまたは他のコードを表してもよい。例示目的のために、これらの構成要素２０２〜２１０は、（例えばユーザコンピューティングデバイス１１０によって）クエリ処理システム１５４に入力される一例のクエリの処理に関して議論される。
【００２３】
[0027]クエリ処理システム１５４によって受信されるクエリは、最初にクエリ注釈部２０２に渡されてもよく、クエリ注釈部２０２において、クエリのさまざまな用語は、クエリ処理システム内の後の使用のために検査され、注釈が付けられてもよい。いくつかの実施形態では、クエリ注釈部２０２は、技術分野で周知であるような自然言語処理技術を利用して、任意の用語または用語の連続（時々「ｎグラム」と称される）が所定の用語タイプに分類可能かを決定してもよい。例示的に、用語タイプは、探されるトラベルアイテムのタイプ（例えば、ホテル、車、飛行機、アクティビティなど）、探される特定のアイテムの名前（例えば、特定のホテル名、ホテルのブランドなど）、アイテムが探される地理的位置（例えば、市、郡など）、地理的位置のための地理的記述子（例えば、浜辺、山など）、所望のトラベルアイテムにより提供されるアメニティ（例えば、プール、温水浴槽、食事、フィットネスセンター、温泉など）、サービスレベル記述子（例えば、ラグジュアリ、ビジネス、エコノミーなど）、または、特定の品詞（例えば、名詞、動詞、分詞、代名詞、前置詞、副詞、接続詞など）を含んでもよい（しかし、これらに限定されるものではない）。後述するように、クエリ処理システム１５４は、用語注釈を利用して、クエリのどの用語がクエリ処理システム１５４内の所定のステージで処理されるべきかを決定してもよい。例えば、検索されたトラベルアイテムを含んでもよい地理的領域を見つけることを試みるとき、クエリ処理システム１５４は、所望のアメニティ（例えば、プール、温泉、提供される食事）を無視してもよい。なぜなら、これらの用語は、地理的に意味がある可能性が低いからである。さらなる例として、クエリ処理システム１５４は、クエリの処理の間、意味がある可能性が低い特定の品詞、例えば前置詞を無視してもよい。
【００２４】
[0028]その後、クエリ処理システム１５４は、注釈が付けられたクエリを検索エンジン２０４に渡してもよく、検索エンジン２０４は、クエリに潜在的に関連するトラベルアイテムを見つけるように機能する。一実施形態では、検索エンジン２０４は、単純な用語整合を利用して、クエリに応答して潜在的トラベルアイテムをランク付けおよびソートしてもよく、その結果、記述がクエリの用語により密接に整合するトラベルアイテムが、クエリに応答して返答され、トラベルアイテムの関連する記述と用語との間の対応のレベルに基づいてランク付けされる。他の実施形態では、検索エンジン２０４は、履歴的なユーザアクティビティデータ、例えば「クリックストリーム」データを利用して、所定のクエリに応答するトラベルアイテムを決定してもよい。例えば、検索エンジン２０４は、所定のホテルクエリのために、同じクエリまたは同じクエリ内の用語を利用するとき、以前のユーザが選択した一組のホテルを決定してもよい。検索エンジン２０４は、以前のユーザ選択の頻度に基づいて、一組のホテルをさらにランク付けすることができる。一実施形態では、検索エンジン２０４は、単純ベイズ分類器を用いて、検索語を特定のトラベルアイテムに関連させてもよい。クリックストリーム・データを用いて関連するクエリを決定することにより、検索クエリおよび結果として生じるトラベルアイテムが用語を共有しないときでさえ、検索エンジン２０４が、関連する結果を識別することができてもよい。例えば、クリックストリーム・データは、「ビッグアップル内のホテル」を検索した後、「ビッグアップル」という用語は、実際には特定のホテルの記述内で発生していないにもかかわらず、ニューヨーク州ニューヨーク市内の特定のホテルがユーザによって選択されることを示してもよい。いくつかの実施形態では、クリックストリーム・データは、ユーザコンピューティングデバイス１１０とトラベルサービス１５０との間の相互作用によって生成されてもよい（例えば、ユーザによってトラベルサービス１５０上でなされる検索の結果として）。他の実施形態では、クリックストリーム・データは、トラベルサービス１５０への照会の間、第三者検索エンジン（図示せず）によって推定または収集されてもよく、第三者検索エンジンは、トラベルサービス１５０に、第三者検索エンジンによって利用される特定のユーザクエリを通知し、ユーザをトラベルサービス１５０に向けてもよい。追加的または代替的に、検索エンジン２０４は、技術分野で周知の検索アルゴリズムの任意数を利用し、ユーザのクエリに潜在的に関連するトラベルアイテムを見つけてもよい。
【００２５】
[0029]いくつかの例では、検索エンジン２０４は、潜在的結果の地理的クラスタ化に関連すると予想される用語のサブセットのみをクエリから利用してもよい。例えば、検索エンジン２０４は、最初の結果を識別するために、所望のアメニティを特定するクエリ内の用語を無視してもよい。後述するように、これらの用語は、クエリ処理システム１５４によって後で利用され、個々のトラベルアイテムがユーザに提示される前に、この種のトラベルアイテムをランク付けしてもよい。いくつかの実施形態では、検索エンジン２０４は、検索結果をさらに処理してもよいし、または、検索結果を修正してもよい。例えば、検索エンジン２０４は、検索結果の一部を除去（ｐｒｕｎｅ）してもよいので、結果は、ユーザのクエリに潜在的に関連する上位ｎ個のトラベルアイテムのみを含む。
【００２６】
[0030]一組の最初の検索結果を決定した後、クエリ処理システム１５４は、最初の検索結果を領域識別子２０６に渡してもよく、領域識別子２０６は、結果を一組の領域にクラスタ化してもよい。一実施形態では、クラスタ化は、シングルパス・アルゴリズムに基づいて発生してもよいので、トラベルアイテムに関連付けられた位置が以前に識別されたクラスタの閾値距離（例えば、５０マイル）内にある場合、トラベルアイテムが以前に識別されたクラスタに該当し、さもなければ、新しいクラスタを構成すると決定される。トラベルアイテムが単一の地理的位置（例えば、宿泊設備を提供するホテルの位置、目的地サービスが提供される位置、レンタカー会社の位置）に関連付けられる例では、領域識別子２０６は、その単一の地理的位置をトラベルサービスの位置として利用してもよい。トラベルアイテムが複数の地理的位置に関連付けられる例では（例えば、出発位置および戻り位置を有する飛行機）、複数の地理的位置のいずれかが、クラスタから閾値距離内にある場合、トラベルアイテムは、クラスタの閾値距離内で考慮されてもよい。クラスタからの距離は、クラスタ内の任意の位置に基づいて決定されてもよい。いくつかの実施形態では、トラベルアイテムは、そのトラベルアイテムの位置が、以前から存在していたクラスタ内にすでに存在している任意の他のトラベルアイテムの位置から閾値距離内にある場合、以前から存在していたクラスタの閾値距離内で考慮されてもよい。他の実施形態では、トラベルアイテムは、そのトラベルアイテムの位置が、以前から存在していたクラスタの重心の閾値距離内にある場合、以前から存在していたクラスタの閾値距離内で考慮されてもよい（例えば、クラスタ内にすでに存在している各トラベルアイテムの平均位置から決定されるように）。この種のシングルパス・クラスタリング・アルゴリズムは、クエリ処理システム１５４によって高速に利用され、地理的に分散したアイテムに関連するクラスタを決定してもよいという点で有利になりうる。しかしながら、より複雑なクラスタリング・アルゴリズム、例えば（技術分野で周知の）ｋ−平均クラスタリングもまた、領域識別子２０６によって利用され、トラベルアイテムのクラスタを決定してもよい。
【００２７】
[0031]多数のクラスタを識別した後、領域識別子２０６は、地理的識別子を各クラスタにさらに割り当ててもよい。一実施形態では、領域識別子２０６は、クエリ処理システム１５４が利用できる地理的メタデータを（例えば、図１のトラベルアイテム・データストア１６０から）利用し、クラスタ内のすべての（または閾値パーセンテージの）ホテルに適用できるほとんどの特定の地理的識別子を識別してもよい。この種のメタデータは、一組のゾーンを識別することを含んでもよく、各ゾーンは、特定の領域識別子に関連付けられた地理的領域を識別する。一実施形態では、メタデータは、既存の地理的境界、例えば、地区、市、郡または州の境界線に基づいて生成されてもよい。他の実施形態では、メタデータは、トラベルサービス１５０によって手動で生成されてもよい。さらなる実施形態では、トラベルサービス１５０は、地理的識別子および対応する地理的ゾーンまたは位置を識別するメタデータを第三者サービスから、例えば、技術分野で周知のような地理的情報サービス（ＧＩＳ）から取得してもよい。この種の地理的メタデータを用いて、領域識別子２０６は、任意の所定のクラスタ内のトラベルアイテムの位置を比較し、クラスタ内のすべてのまたは閾値パーセンテージのトラベルアイテムの位置を含む１つまたは複数の地理的領域の識別子を決定してもよい。したがって、ワシントン州シアトルのフレモント地区内に位置するホテルのための宿泊設備のクラスタは、「ワシントン州シアトル、フレモント」クラスタとして識別されてもよく、一方、ワシントン州スポーケン内に位置するホテルのための宿泊設備のクラスタは、「ワシントン州スポーケン」クラスタとして識別されてもよい。いくつかの実施形態では、トラベルサービス１５０は、トラベルアイテムのメタデータ内の関連する地理的識別子を含むこともできる。例えば、１つまたは複数のトラベルアイテムは、「スペースニードルの近く」（ワシントン州シアトルの展望塔）と分類されてもよい。クラスタのトラベルアイテムが複数の領域（例えば、関連する識別子、地区および市）内に含まれる場合、トラベルサービス１５０は、各領域の優先レベルに基づいて、複数の領域から選択してもよい。例示的には、領域は、領域内に含まれる全エリアに基づいて、トラベルサービス１５０上の領域の人気に基づいて（例えば、どれだけしばしばユーザがその領域に対応するトラベルアイテムを検索するかに基づいて）、またはその両方に基づいて、トラベルサービス１５０を優先してもよい。例えば、クラスタのトラベルアイテムが、領域「ワシントン州シアトルのダウンタウン」および「ワシントン州シアトル」の両方内に位置する場合、トラベルサービス１５０は、その領域がより小さいサイズを有し、かつ、トラベルサービス１５０のユーザの間で人気が高いため、そのクラスタのための識別子「ワシントン州シアトルのダウンタウン」を使用することができる。追加的または代替的に、トラベルサービス１５０は、ユーザのクエリ内で用いられる用語と各領域の識別子との間の相関関係に基づいて、複数の領域から選択してもよい。例えば、「スペースニードルの近くのホテル」のための検索は、結果として、「ワシントン州シアトル内」としてよりはむしろ、「スペースニードルの近く」として識別されるホテルのクラスタになってもよい。検索クエリと領域識別子との間の用語の重なりに少なくとも部分的に起因する。
【００２８】
[0032]追加的に、領域識別子２０６は、決定されたクラスタをソートし、各クラスタの検索クエリに対する予測された関連性を定めてもよい。一実施形態では、クラスタは、クラスタに該当するように決定されるトラベルアイテムに基づいてソートされてもよい。例えば、（例えば、検索エンジン２０４によって決定されるような）各トラベルアイテムの最初のランキングを利用して、各クラスタ内のトラベルアイテムの集積または平均ランキングを決定してもよい（その結果、検索エンジン２０４によって高くランク付けされるトラベルアイテムを含むクラスタは、検索エンジン２０４によって高くランク付けされないトラベルアイテムを含むクラスタより上にランク付けされる）。他の実施形態では、クラスタは、クラスタに割り当てられる地理的識別子とクエリとの間の相関関係に少なくとも部分的に基づいてソートされてもよく、その結果、地理的に「スペースニードルの近く」として識別されるホテルのクラスタは、「スペースニードル」という用語を含むクエリのために高くランク付けされる。さらに他の実施形態では、クラスタは、クラスタ自体の地理的識別子に基づいてソートされてもよいし（例えば、トラベルサービス１５０のユーザに人気が高い地理的識別子が、人気が低い地理的識別子より高くランク付けされる、または、より特定の地理的識別子がより特定でない地理的識別子より高く評価される）、または、（例えば、ユーザのプロファイル・データによって決定されるような）少なくとも１つのクラスタに対応する地理的識別子のためのユーザの選好に基づいてソートされてもよい。
【００２９】
[0033]その後、クエリ処理システム１５４は、識別されたクラスタを領域分類器２０８に渡してもよく、領域分類器２０８は、クラスタ内に含まれるトラベルアイテムに基づいて、関連するクラスタから、クラスタの地理的位置によって関連するクラスタを区別することを試みることができる。例えば、「エッジウォーター・ホテル」のためのクエリは、結果として、２つのクラスタになってもよい。第１のクラスタは、ジ・エッジウォーター・ホテルおよびワシントン州シアトル内の他の近くのホテルを含み、第２のクラスタは、ニュージャージー州エッジウォーター地区内および地区周辺のホテルを含む。これらの中で、クラスタ内に含まれる特定のトラベルアイテム（ジ・エッジウォーター・ホテル）に基づいて、第１のクラスタが関連すると予想される。したがって、地理的識別子（例えば、「ワシントン州シアトル内のホテル」）をユーザに提示するよりはむしろ、クラスタは、ユーザに、関心を持つと予想されるクラスタ内の特定のトラベルアイテム（例えば、「ワシントン州シアトルのジ・エッジウォーター・ホテル」）として表すことができる。次に、クラスタのユーザ選択は、結果として、特定のトラベルアイテムに関する詳細な情報になる。反対に、（ニュージャージー州エッジウォーター地区内および地区周辺のホテルの）第２のクラスタは、ユーザに、選択可能な領域（例えば、「ニュージャージー州エッジウォーター」）として、その領域内のホテル宿泊設備のリストを見るために選択可能に表すことができる。
【００３０】
[0034]特定のトラベルアイテムのために関連する領域とそれ自身関連する領域とを区別するために、領域分類器２０８は、検索エンジン２０４によって割り当てられるようなクラスタ内の個々のトラベルアイテムの関連するランキングを利用してもよい（例えば、クリックストリーム・データ、用語分析または任意の他の検索およびランキング基準に基づく）。所定のクラスタ内で最高にランク付けされたトラベルアイテムが次に高くランク付けされたトラベルアイテムよりはるかに関連するように見える例では、クラスタが、その最高にランク付けされたトラベルアイテムによって関連する可能性が高い。このように、そのクラスタは、ユーザに、単にトラベルアイテム自体として（例えば、特定のトラベルアイテムに関する追加情報を見るためのリンクとして）表すことができる。反対に、クラスタ内のすべてのトラベルアイテムが同じようにランク付けされる場合、そのクラスタは、ユーザに、地理的識別子（例えば、特定の市）として、その市内のトラベルアイテムを見るために選択可能に提示されてもよい。領域分類器２０８は、所定のクラスタのアイテム間の任意数の比較を利用して、クラスタ内の個々のトラベルアイテムが、顧客が特定の関心を持つアイテムを表すかを区別してもよい。クラスタ内の個々のトラベルアイテムが、（例えば、検索エンジン２０４によって）スコアを割り当てられた例では、クラスタのアイテム間の比較の例は、
・（例えば、絶対差、対数領域の差などとして測定されるような）クラスタ内で第１にランク付けされたトラベルアイテムと最後にランク付けされたトラベルアイテムとの間のスコアの差、
・クラスタ内で第１にランク付けされたトラベルアイテムと第２にランク付けされたトラベルアイテムとの間のスコアの差、
・クラスタ内で第１にランク付けされたアイテムと第２にランク付けされたアイテムとの間のスコアの差と、クラスタ内で第２にランク付けされたアイテムと第３にランク付けされたアイテムとの間のスコアの差と、の比、
・クラスタ内で第１にランク付けされたアイテムと第２にランク付けされたアイテムとの間のスコアの差と、クラスタ内で第２にランク付けされたアイテムと最後にランク付けされたアイテムとの間のスコアの差と、の比、
を含むが、これらに限定されるものではない。クラスタ（例えば、領域的に関連するクラスタまたは特定のトラベルアイテムによって関連するクラスタ）のタイプ間で区別するために領域分類器２０８が用いてもよい他のファクタは、クエリに対する検索結果の上位ｎ個に基づいて生成されるクラスタの数、（例えば、クラスタの中心、クラスタの端などに基づいて決定されるような）抽出されたクラスタ間の平均距離、すべての抽出されたクラスタ間の最大距離、および、すべての抽出されたクラスタ間の最小距離を含んでもよい。
【００３１】
[0035]追加的または代替的にクラスタのタイプ（例えば、領域的に関連するクラスタまたは特定のトラベルアイテムによって関連するクラスタ）は、ユーザにより入力されるクエリ用語と、クラスタ内で最高にランク付けされたトラベルアイテムに関連付けられた用語と、の比較に基づいて区別されてもよい。例えば、検索クエリおよび上位ランクのトラベルアイテムが類似の用語を共有する場合（例えば、「エッジウォーター・ホテル」のためのクエリおよび「ジ・エッジウォーター・ホテル」という名称のトラベルアイテム）、クラスタの関連は、その上位ランクのトラベルアイテムにリンクされる可能性が高い。反対に、検索クエリおよび上位ランクのトラベルアイテムが類似の用語を共有しない場合（例えば、「ワシントン州シアトル内のホテル」のためのクエリおよび「ジ・エッジウォーター・ホテル」の上位ランクのトラベルアイテム）、クラスタは、一般的に関連する可能性が高く、ユーザは、クラスタに関連付けられた地理的識別子内のホテルを見ることから利益を得てもよい。いくつかの例では、クエリとトラベルアイテムとの間の用語の類似性は、クエリとトラベルアイテム識別子（例えば名前）との間の整合する用語（または「ｎグラム」）と、クエリ内の全用語（または「ｎグラム」）と、の比率として量子化されてもよい。一実施形態では、特定のトラベルアイテムおよびユーザのクエリが閾値量より上の整合する用語の比率を有する場合、領域分類器２０８は、クラスタがその特定のトラベルアイテムによって関連すると決定してもよい。いくつかの実施形態では、クラスタタイプは、クエリ用語と、クラスタのための領域識別子と、の比較に基づいて区別されてもよい。例えば、領域の名前がクエリ内の１つまたは複数の用語に密接に整合するとき、クラスタは、その対応する領域によって関連すると決定されてもよい。またさらに、クラスタタイプは、クエリ内の特定の用語または用語タイプの使用に基づいて区別されてもよい。例示的には、クラスタのための領域識別子は、特定のトラベルアイテム識別子より、複数の用語（例えば、「１つのホテル」に対して「複数のホテル」）を含むクエリに関連する可能性が高くてもよい。いくつかの実施形態では、上述した測定基準の各々は量子化されてもよく、追加の測定基準は、この種の量子化の比較から導出されてもよい。例えば、クエリ処理システム１５４は、スコアをクラスタの領域識別子とクエリ内で用いられる用語との類似性に割り当ててもよいし、スコアを当該用語に対するクラスタ内の上位の検索結果の類似性に割り当ててもよい。次に、追加の測定基準は、これらの２つのスコアを比較することによって作成されてもよい。追加の測定基準が可能であり、本発明の範囲内で考察される。いくつかの例では、クラスタタイプ間で区別するために用いられる特定の測定基準（またはそれらの組み合わせ）は、クエリおよび周知の関連タイプを有する対応する結果クラスタを含むトレーニング・データセットを処理するための機械学習アルゴリズムの使用に基づいて決定されてもよい（例えば、地理的識別子に基づいて、または、クラスタ内の上位のトラベルアイテムに基づいて関連する）。
【００３２】
[0036]その後、クエリ処理システム１５４は、識別および分類されたクラスタを結果コーディネータ２１０に渡してもよい。複数のクラスタが識別された場合、結果コーディネータ２１０は、地理的識別子またはクラスタ内の上位ランクのトラベルアイテムのいずれかによって識別されるように、（例えば、ユーザインタフェースシステム１５６を介して）クラスタの１つを選択するための要求をユーザに送信してもよい。ユーザが上位ランクのトラベルアイテム、例えばホテルによって識別されるクラスタを選択する場合、ユーザを、ホテルの予約が可能な詳細ページにすぐに向けることができる。ユーザが地理的識別子によって識別されるクラスタを選択する場合、結果コーディネータ２１０は、クラスタ内で利用できるトラベルアイテムのリストを提示してもよい。いくつかの例では、結果コーディネータ２１０は、クラスタ内のトラベルアイテムを再ソートまたは再ランク付けしてもよい。例えば、アメニティ（例えば、温泉、フィットネスセンターなど）としてタグ付けされるクエリ用語が検索エンジン２０４によって以前無視された場合、結果コーディネータは、各トラベルアイテムのための当該アメニティの入手可能性に基づいて、クラスタ内のトラベルアイテムを再評価してもよい。いくつかの例では、結果コーディネータは、クラスタによって識別される地理的領域に限られている新しい検索を実行し、一組のトラベルアイテムを決定し、顧客に提示してもよい。
【００３３】
[0037]単一のクラスタのみがクエリ処理システム１５４によって以前に識別された例では、結果コーディネータ２１０は、あたかもユーザがその１つのクラスタを選択したかのように進めてもよい。このように、単一のクラスタが上位にランク付けされたトラベルアイテムに基づいて、クエリに関連すると決定される場合、ユーザは、そのトラベルアイテムの詳細ページに向けられてもよい。単一のクラスタが地理的領域に基づいて関連すると決定される場合、結果コーディネータ２１０は、（最初のクエリに基づいて潜在的に再ソートまたは再ランク付けされるように）クラスタ内のトラベルアイテムのリストを提示してもよいし、または、地理的領域内のトラベルアイテムのための新しい検索の結果を提示してもよい。
【００３４】
[0038]上述した方法では、クエリ処理システム１５４は、はっきりしていないクエリを処理し、クエリ内の潜在的地理的曖昧性を決定し、ユーザが、意図されたトラベルアイテムまたは地理的領域を選択することを可能にしてもよい。このように、クエリ処理システム１５４によって、従来の検索アルゴリズムと比較して、トラベルアイテムに関連する情報を検索するための速度、効率および精度の改善が可能になる。
【００３５】
[0039]図３には、地理的クラスタを利用する検索クエリの曖昧性解消を可能にするためのユーザインタフェース３００の一例が例示される。この例では、ユーザインタフェース３００は、ユーザコンピューティングデバイス１１０上で実行するブラウザ・アプリケーション（例えば、「ウェブブラウザ」）によって、トラベルサービス１５０から受信される命令（および、例えばハイパーテキスト・マークアップ言語（ＨＴＭＬ）文書）に基づいて生成される。ユーザインタフェース３００によって、ユーザコンピューティングデバイス１１０は、クエリをトラベルサービスに提出し、この種のクエリが曖昧であると決定される例では、結果の適切なクラスタを選択し、提出されたトラベルクエリに応答して、利用できるトラベルアイテムを見て、獲得し、提出されたトラベルクエリに少なくとも部分的に基づいて生成されるトラベルパッケージ推奨を見ることができる。図３の例では、「旅行者トム」として識別されたユーザは、トラベルサービス１５０にアクセスしている。ユーザがトラベルサービス１５０のさまざまなインタフェース間でナビゲートできるために、ユーザインタフェース３００は、ナビゲーションパネル３０２を含み、ナビゲーションパネル３０２は、その旅行者を、トラベルサービス１５０によって提供されるさまざまな他の特徴に向ける。例示的には、ナビゲーションパネル３０２内のテキストの部分は、インタラクティブ・リンクに対応してもよく、インタラクティブ・リンクは、選択されるとき、ユーザインタフェース３００を修正または変更する。現在の例では、旅行者トムは、リンク３０４「ホテル」を選択している。この選択に基づいて、ユーザインタフェースシステム１５６は、ユーザインタフェース３００のための内容を返答する。ユーザは、ナビゲーションパネル３０２内の代替のリンクの選択によって代替のユーザインタフェースを見ることができてもよい。例えば、ユーザは、「パッケージ」「車」「飛行機」などというタイトルのナビゲーションパネルの部分を選択することによって、他のタイプのトラベルアイテムに関連する代替のインタフェースを見てもよい。
【００３６】
[0040]ユーザインタフェース３００の検索ボックス３０６を用いて、旅行者コンピューティングデバイス１１０は、クエリをトラベルサービス１５０に提出してもよい。現在の例では、ユーザは、はっきりしていないクエリテキスト「ワシントン州内のホテル」を提出している。このクエリを受信すると、トラベルサービス１５０は、クエリテキストを（任意の他の追加情報、例えばユーザのプロファイル情報とともに）クエリ処理システム１５４に渡してもよい。上述したように、クエリ処理システム１５４は、クエリのための一組の結果を（例えば、用語整合、クリックストリーム分類または他の検索アルゴリズムを用いて）見つけ、結果を処理し、結果内に含まれるトラベルアイテムを地理的にクラスタ化してもよい。
【００３７】
[0041]図４には、クエリ「ワシントン州内のホテル」のための潜在的地理的クラスタの一例が示される。図４に示すように、クエリ「ワシントン州内のホテル」に関連する潜在的トラベルアイテムは、ワシントン州領域４００全体に広がってもよい。図４に示される特定のクラスタは、例示的な性質のみを有し、クエリ「ワシントン州内のホテル」に関連する潜在的トラベルアイテムは、ワシントン州領域４００外に位置するトラベルアイテム（例えばワシントンＤ．Ｃ．内）を含んでもよいことに留意されたい。クエリの曖昧性を解消するために、クエリ処理システム１５４は、クラスタリング・アルゴリズム（例えば上述したアルゴリズム）を利用し、結果を３つのクラスタ４０２Ａ、４０２Ｂおよび４０２Ｃにクラスタ化することができる。図４には３つのクラスタのみが示されるが、任意数のクラスタは、クエリ処理システム１５４によって識別されてもよい。いくつかの例では、クエリ処理システム１５４は、クラスタの「一部を除去」してもよく、その結果、（例えば、クラスタ内のトラベルアイテムの集約または平均スコアによって決定されるような）低い潜在的関連性を有するクラスタは、さらなる処理のために選択されず、これにより、ユーザに表されるクラスタの数は減少する。図４の例では、各クラスタは、ワシントン州内の予め決定された地理的領域に関連付けられ、その結果、クラスタ内の各トラベルアイテムは、その地理的領域に関連付けられている。具体的には、クラスタ４０２Ａ内のトラベルアイテムは、「グレーターシアトルエリア（Ｇｒｅａｔｅｒ  Ｓｅａｔｔｌｅ  Ａｒｅａ）」領域に例示的に関連付けられ、クラスタ４０２Ｂ内のトラベルアイテムは、「スポーケン」領域に例示的に関連付けられ、クラスタ４０２Ｃ内のトラベルアイテムは、「ヤキモー・バレー」領域に例示的に関連付けられている。
【００３８】
[0042]大部分の旅行者が比較的特定のトラベル位置を考えるので、ユーザは、クラスタ４０２Ａ〜Ｃの各々からのホテルが同時に提示されることから利益を得る可能性が低い。さらに、ユーザが、人気が低いまたはさもなければより低くランク付けされた領域への旅行に実際に関心を持っていた場合、クラスタ４０２Ａ〜Ｃの各々から選択される結果の最初の一組がユーザの所望の領域からのいかなるトラベルアイテムも含まないということがありうるので、ユーザに、（例えば、結果の次の「ネットワークページ」に移動することによって）追加の検索結果を要求し、（例えば、検索用語が関心を持たれる領域を手動で特定することによって）検索用語を「狭くする」ことを要求し、または、異なる検索クエリを再提出するように要求する。これらの代替のオプションの各々は、ともに、ユーザの経験に有害であり、トラベルサービス１５０が動作しうる速度、精度および効率を減少させる。
【００３９】
[0043]これらの問題に対処するために、本発明の態様によって、３つのクラスタ４０２Ａ〜Ｃの各々は、ユーザに、クラスタ内の個々のトラベルアイテムとしてよりはむしろ、グループとして表されることができる。上述したように、クエリ処理システム１５４は、各クラスタ４０２Ａ〜Ｃの予想される関連性を、その地理的位置によって関連するとして、または、クラスタ４０２Ａ〜Ｃ内の上位ランクのトラベルアイテムによって関連するとして識別するように構成されてもよい。図４の例では、クラスタ４０２Ａ〜Ｃの各々は、クエリ処理システム１５４によって、その地理的位置によって関連すると決定されると仮定される。このように、クエリ「ワシントン州内のホテル」の曖昧性を解消するために、トラベルサービス１５０は、ユーザに、クラスタ４０２Ａ〜Ｃによって表される地理的領域の１つを選択するように要求してもよい。
【００４０】
[0044]図３には、多数の識別されたクラスタから選択するための要求の一例が示される。具体的には、図３は、トラベルサービス１５０によって生成されるプロンプト３０８を含み、ユーザは、複数の領域を識別する３つの地理的識別子３１０〜３１４から選択するように要求され、当該複数の領域内にクエリ「ワシントン州内のホテル」から生じるトラベルアイテムが位置する。地理的識別子３１０〜３１４の各々は、図４に示されるクラスタ４０２Ａ〜Ｃの１つに対応する（識別子３１０「ワシントン州シアトル内のホテル」は、クラスタ４０２Ａに対応し、識別子３１２「ワシントン州スポーケン内のホテル」は、クラスタ４０２Ｂに対応し、識別子３１４「ワシントン州ヤキモー内のホテル」は、クラスタ４０２Ｃに対応する）。ユーザインタフェース３００を介して、ユーザは、地理的識別子３１０〜３１４のうちの１つを選択し、選択された識別子に関する追加情報を受信してもよい。一実施形態では、識別子の選択の結果、識別子によって表される、クラスタ内に含まれる一組のトラベルアイテムが表示されてもよい。他の実施形態では、識別子の選択の結果、新しいクエリがユーザのために生成されてもよい（例えば、以前に提出されたはっきりしていないクエリ用語を共有するが、選択された地理的識別子によって識別される領域に限定されている）。トラベルアイテム・クエリに対する結果を表示するためのさまざまなシステムおよび方法は、技術分野で周知であり、本願明細書では詳述されない。
【００４１】
[0045]図３では、各クラスタ４０２Ａ〜Ｃが地理的識別子によって表されるが、いくつかの実施形態では、クラスタは、クラスタ内に位置する上位ランクのトラベルアイテムによって、代替的に表されてもよい（例えば、そのトラベルアイテムの名前として）。さらに、異なるタイプの識別されたクラスタのための識別子は、同じプロンプト内で混在してもよい。例えば、「エッジウォーター・ホテル」のためのクエリは、結果として、「ワシントン州シアトルのジ・エッジウォーター・ホテル」（そのクラスタ内の上位ランクのトラベルアイテムに基づいて関連するクラスタを表す）と、「ニュージャージー州エッジウォーター地区内のホテル」（クラスタ内のトラベルアイテムが位置する地理的領域に基づいて関連するクラスタを表す）と、の間のプロンプト要求選択になってもよい。顧客が特定のトラベルアイテム（例えば、「ワシントン州シアトルのジ・エッジウォーター・ホテル」）に対応する識別子を選択する例では、ユーザは、特定のトラベルアイテムに関する情報ページに自動的に向けられてもよい（情報ページは、ユーザが、トラベルアイテムを予約する、または、さもなければ獲得するのを可能にしてもよい）。
【００４２】
[0046]図５Ａおよび図５Ｂには、潜在的結果の地理的クラスタ化に基づいて、検索クエリの曖昧性を解消するための例示的ルーチン５００が記載されている。例示するルーチン５００は、例えば、クエリ処理システム１５４およびトラベルサービス１５０の追加の構成要素によって実行されてもよい。ルーチン５００は、ブロック５０２から開始し、ブロック５０２において、クエリ処理システム１５４は、トラベルアイテム・クエリを受信する。例示的には、クエリは、ユーザから、図１のユーザコンピューティングデバイス１１０を利用して、図３のユーザインタフェース３００への提出を介して受信されてもよい。ルーチン５００は、ブロック５０４に続き、ブロック５０４において、クエリ処理システム１５４は、クエリを前処理、フィルタ処理および／または正規化し、さらなる処理を容易にする。例示的には、ブロック５０４は、大文字化、過剰なスペースまたは他の無視された書式設定または文字を取り除くことによりクエリを正規化することと、所定の正規表現をクエリ上で実行することと、複数の単語を単一の用語にグループ化すること（例えば、「ニュー」および「ヨーク」という単語を単一の用語「ニューヨーク」にグループ化すること）と、またはさもなければ、周知のプロセスをクエリ上で実行し、クエリ処理システム１５４によるさらなる使用のためにクエリを準備することと、を含んでもよい。
【００４３】
[0047]その後、ルーチン５００は、ブロック５０６に続き、ブロック５０６において、クエリの用語は、注釈が付けられ、用語のための「タイプ」を識別することができ、タイプとは、探されるトラベルアイテムのタイプ（例えば、ホテル、車、飛行機、アクティビティなど）、探される特定のアイテムの名前または記述子（例えば、特定のホテル名、ホテルのブランドなど）、探されるアイテムの地理的位置（例えば、市、郡など）、地理的位置のための地理的記述子（例えば、浜辺、山など）、所望のトラベルアイテムにより提供されるアメニティ（例えば、プール、温水浴槽、食事、フィットネスセンター、温泉など）、サービスレベル記述子（例えば、ラグジュアリ、ビジネス、エコノミーなど）、または、特定の品詞（例えば、名詞、動詞、分詞、代名詞、前置詞、副詞、接続詞など）である。一実施形態では、ブロック５０６は、クエリ処理システム１５４による自然言語処理アルゴリズムの実行を含んでもよく、クエリ処理システム１５４は、クエリを処理し、クエリ内の個々の用語に決定された用語タイプで注釈を付ける。いくつかの実施形態では、ルーチン５００が続く前に、１つまたは複数の所定のタイプ、例えば前置詞で注釈が付けられたクエリの用語は、クエリから取り除かれてもよい。他の実施形態では、１つまたは複数の所定のタイプで注釈が付けられたクエリの用語は、クエリ内で維持されてもよいが、ルーチン５００の特定部分において無視されてもよい。例えば、地理的ベースのクラスタを導出するための潜在的結果の最初の一組を決定するとき、クエリ処理システム１５４は、「アメニティ」として注釈が付けられた用語を無視してもよい。
【００４４】
[0048]ブロック５０８において、クエリ処理システム１５４は、クエリに対する一組の潜在的結果のための検索を実施する。一実施形態では、クエリ処理システム１５４は、用語整合を利用して、トラベルアイテムの記述が、クエリ内においてもまた用語を含むトラベルアイテムを決定してもよい。他の実施形態では、クエリ処理システム１５４は、トラベルサービス１５０のユーザの履歴的な使用データを利用してもよい（例えば、トラベルサービス１５０によって取得された「クリックストリーム」データによって表されるように）。一実施形態では、クエリ処理システム１５４は、単純ベイズ分類器を利用して、クエリに従って、トラベルアイテムをランク付けまたはスコア付けしてもよい。例えば、クエリ処理システム１５４は、任意の所定のトラベルアイテムのために、そのトラベルアイテムがクエリに応答してユーザによって選択される確率を決定することを試みてもよい。この確率は、Ｐ（Ｔ｜Ｑ）の形で表されてもよく、「Ｔ」はトラベルアイテムを表し、「Ｑ」はクエリを表す。この確率は、以下の式によって表されてもよい。
【００４５】
[0049]Ｐ（Ｔ｜Ｑ）＝Ｐ（Ｑ｜Ｔ）×Ｐ（Ｔ）
Ｐ（Ｔ）は、所定のトラベルアイテムが選択される確率を表し、関連するデータ内のトラベルアイテムのユーザ選択の発生の全数を、関連するデータ内のクエリの全数によって除算することによって計算されてもよい。次に、関数Ｐ（Ｑ｜Ｔ）は、以下の式に従って計算されてもよい。
【００４６】
[0050]Ｐ（Ｑ｜Ｔ）＝Ｐ（Ｗ１｜Ｔ）×Ｐ（Ｗ２｜Ｔ）…×Ｐ（Ｗｎ｜Ｔ）
Ｗ１…ｎは、クエリ内の用語の連続（または「ｎグラム」）を表し、Ｐ（Ｗｎ｜Ｔ）は、所定の単語Ｗｎが、トラベルアイテムＴの選択に結果としてなるすべてのクエリ内の個々のクエリ内で発生する回数のパーセンテージを表す。このように、クリックストリーム・データを分析し、過去のクエリと個々のトラベルアイテムとの間の相関関係を決定することにより、クエリ処理システム１５４は、新しく提出されたクエリに応答して、個々のトラベルアイテムをスコア付けまたはランク付けしてもよい。
【００４７】
[0051]クエリに応答してトラベルアイテムを見つけるためのさまざまな追加のメカニズムおよびアルゴリズムは、技術分野で周知であり、上述したものに対して追加的または代替的に利用されてもよい。いくつかの例では、クエリ処理システム１５４は、別個のシステムと通信し、クエリの検索結果を決定してもよい。例えば、クエリ処理システム１５４は、第三者検索エンジン、例えば、予約システム１２０または図示されない他のシステムによって提供される検索エンジンと通信し、ルーチン５００とともに用いるための検索結果を決定してもよい。このように、上述した検索メカニズムおよびアルゴリズムは、例示的であり包括的性質ではないことを意図する。
【００４８】
[0052]その後、ルーチン５００は、図５Ｂのブロック５１２に続く。具体的には、ブロック５１２において、クエリ処理システム１５４は、以前に確立した一組の検索結果を利用して、各トラベルアイテムの地理的位置に基づいて、クエリに応答するトラベルアイテムの１つまたは複数のクラスタを決定する。例示的には、地理的位置は、トラベルアイテムの緯度および経度の座標、トラベルアイテムの住所またはトラベルアイテムを地理的に位置決めするための他の印（インジケータ）に基づいて確立されてもよい。トラベルアイテムの地理的位置は、トラベルサービス１５０によって予め決定されてもよいし、または、ルーチン５００の実施の間、クエリ処理システム１５４によって（例えば、トラベルアイテム・データストア１６０、予約システム１２０または他のシステムから導出される情報を利用して）決定されてもよい。クエリ処理システム１５４は、任意の種類のクラスタリング・アルゴリズムに基づいて、トラベルアイテムをクラスタ化してもよい。一実施形態では、クエリ処理システム１５４は、シングルパス・クラスタリング・アルゴリズムを利用するので、トラベルアイテムが既存のクラスタから閾値距離（例えば、１００キロメートル）以内に位置する場合（例えばクラスタの中央点、クラスタの境界、クラスタ内の１つまたは複数のトラベルアイテムなどによって表される）、所定のトラベルアイテムは、既存のクラスタに関連付けられると識別され、さもなければ、新しいクラスタを構成するように決定される。他の実施形態では、クエリ処理システム１５４は、ｋ平均クラスタリング・アルゴリズムを利用する。さまざまな追加のクラスタリング・アルゴリズムは、技術分野で周知であり、それゆえ、本願明細書では詳述されない。
【００４９】
[0053]いくつかの実施形態では、クエリ処理システム１５４は、ユーザ検索に関連する可能性が低いクラスタを取り除くことによって、クラスタの一部をさらに除去してもよい。一実施形態では、クラスタは、クラスタ内に含まれるトラベルアイテムの平均スコアまたは全スコアの少なくとも１つによって決定されるように、クラスタのスコアに基づいて一部が除去される。例示的には、個々のトラベルアイテムのためのスコアは、ブロック５０８に関して上述した最初の検索の間に決定されてもよい。例えば、クエリ処理システム１５４は、スコアがすべての決定されたクラスタの全スコアの閾値パーセンテージ未満を表すクラスタを除去（例えば、無視）してもよい。他の例として、クエリ処理システム１５４は、クラスタをスコアによりランク付けしてもよいし、所定のランク未満の任意のクラスタを除去してもよい。
【００５０】
[0054]その後、ルーチンは、ブロック５１４に続き、ブロック５１４において、クエリ処理システム１５４は、クラスタを分類し、クラスタの予想される関連を決定する。一実施形態では、クエリ処理システム１５４は、所定のクラスタが、クエリに起因している地理的識別子（例えば、特定の地区、市など）に基づいて、関連する可能性が高いかを決定することを試みてもよいし、または、クラスタが、クラスタ内に含まれる特定のトラベルアイテムのために、関連する可能性が高いかを決定することを試みてもよい。上述したように、クエリ処理システム１５４は、多数の基準に基づいて、クラスタのタイプ間で区別してもよく、基準は、
・クエリの用語とクラスタ内の上位にランク付けされたトラベルアイテムの用語との類似性、
・クエリ内に含まれる検索結果全体の上位ｎ個内のトラベルアイテムの数、
・クラスタ内で第１にランク付けされたトラベルアイテムと最後にランク付けされたトラベルアイテムとの間のスコアの差、
・クラスタ内で第１にランク付けされたトラベルアイテムと第２にランク付けされたトラベルアイテムとの間のスコアの差、
・クラスタ内で第１にランク付けされたアイテムと第２にランク付けされたアイテムとの間のスコアの差と、クラスタ内で第２にランク付けされたアイテムと第３にランク付けされたアイテムとの間のスコアの差と、の比、
・クラスタ内で第１にランク付けされたアイテムと第２にランク付けされたアイテムとの間のスコアの差と、クラスタ内で第２にランク付けされたアイテムと最後にランク付けされたアイテムとの間のスコアの差と、の比、
を含むが、これらに限定されるものではない。一実施形態では、機械学習技術を利用して、クラスタのタイプ間で区別するために利用される特定の基準を決定してもよい。
【００５１】
[0055]その後、ルーチン５００は、ブロック５１６に続き、ブロック５１６において、クエリ処理システム１５４は、ユーザに、各識別されたクラスタの表現を提示することができる。クラスタの表現を提示するユーザインタフェースの一例は、図３に関して上述している。例示的には、クラスタが、クラスタに対応する地理的領域に基づいて関連すると決定される場合、クラスタは、クラスタに関連付けられた地理的識別子（例えば、地区、市、または、クラスタ内のトラベルアイテムのすべてまたは閾値パーセンテージが位置する領域）によって顧客に提示可能である。クラスタが、クラスタ内の上位ランクのトラベルアイテムに基づいて関連すると決定される場合、クラスタは、その上位にランク付けされたトラベルアイテムの名前または他の識別子としてユーザに提示可能である。
【００５２】
[0056]ブロック５１８において、クエリ処理システム１５４は、提示されたクラスタのユーザ選択を、（例えば、ユーザコンピューティングデバイス１１０上で実行されるブラウザ・アプリケーションを介した入力として）受信する。例示的には、提示されたクラスタの選択は、提示されたクラスタに対応するハイパーリンク（例えば、ＨＴＭＬ文書内のリンク）の選択を含んでもよい。その後、ブロック５２０において、クエリ処理システム１５４は、選択されたクラスタの結果を、（例えば、ＨＴＭＬ文書または選択されたリンクに対応するＨＴＭＬ文書の部分を返答することによって）表示する。例示的には、地理的識別子（例えば、地区、市または領域識別子）によって表されるクラスタの選択の結果、ユーザが提出したクエリに整合し、かつ、地理的識別子内に位置するトラベルアイテムを表示してもよい。同様に、個々のトラベルアイテムの識別子（例えば、クラスタ内の上位ランクのトラベルアイテムの名前）によって表されるクラスタの選択の結果、個々のトラベルアイテムに関する情報を表示し、ユーザがトラベルアイテムを予約するのを可能にするインタフェースを表示してもよい。このように、識別されるクラスタをクエリ処理システム１５４によって選択することによって、ユーザには、彼らの潜在的に曖昧なクエリに応答して最初に識別される、結果の特定の曖昧性が解消された部分に関する情報が提示されてもよい。次に、ルーチン５００は、ブロック５２２において終了してもよい。
【００５３】
[0057]本願明細書に開示される実施形態に関連して記載されているさまざまな例示的な論理ブロック、ルーチンおよびアルゴリズムは、電子ハードウェアまたは電子ハードウェア上で実行するコンピュータ・ソフトウェアとして実施可能である。これを例示するために、さまざまな例示的構成要素、ブロック、モジュールおよびステップは、それらの機能に関して一般的に上述されてきた。この種の機能がハードウェアとしてまたはハードウェアを介して実行されるソフトウェアとして実施されるかは、特定のアプリケーションおよびシステム全体に課される設計制約に依存する。記載されている機能は、特定のアプリケーションごとに異なる方法で実施可能であるが、この種の実施決定が、本発明の範囲から逸脱させるものと解釈されるべきではない。
【００５４】
[0058]本願明細書において開示される実施形態に関連して記載されている方法のステップ、プロセス、ルーチンまたはアルゴリズムは、直接ハードウェアにおいて、プロセッサによって実行されるソフトウェア・モジュールにおいて、または、２つの組み合わせにおいて実施可能である。ソフトウェア・モジュールは、一般的に、コンピューティングデバイスが所望の機能を実施するのを可能にするコンピュータ実行可能命令の集合に対応することができる。ソフトウェア・モジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭまたは任意の他の形の非一時的コンピュータ可読記憶媒体内に存在することができる。記憶媒体の一例は、プロセッサに結合可能であり、プロセッサは、情報を記憶媒体から読み出すことができるとともに、情報を記憶媒体に書き込むことができる。代替例では、記憶媒体は、プロセッサに組み込み可能である。プロセッサおよび記憶媒体は、ＡＳＩＣ内に存在することができる。ＡＳＩＣは、ユーザ端末内に存在することができる。代替例では、プロセッサおよび記憶媒体は、別々の構成要素としてユーザ端末内に存在することができる。
【００５５】
[0059]本願明細書で用いられる条件付きの用語、例えば中でも「できる」「可能である」「かもしれない」「してもよい」「例えば」などは、特に明記されない限り、または、前後関係で他のように理解されない限り、一般的に、特定の実施形態が特定の特徴、要素および／またはステップを含み、一方、他の実施形態がこれらを含まないことを意図するものである。このように、この種の条件付きの用語は、一般的に、特徴、要素および／またはステップが、１つまたは複数の実施形態のためにいかなる形であれ必要とされることを示唆することを意図しないし、または、１つまたは複数の実施形態は、著者の入力または促進の有無にかかわらず、これらの特徴、要素および／またはステップが、任意の特定の実施形態に含まれる、または、実施されるべきであるかを決定するための論理を必ず含むことを示唆することを意図しない。「備えている」「含んでいる」「有している」などの用語は、同義であり、包括的に無制限の方式で用いられ、追加の要素、特徴、ステップ、動作などを除外しない。また、「または」という用語は、包括的な意味で用いられる（排他的な意味では用いられない）ので、例えば、要素のリストを接続するために用いられるとき、「または」という用語は、リスト内の１つ、いくつかまたはすべてを意味する。
【００５６】
[0060]離接的用語、例えば、「Ｘ、ＹまたはＺのうちの少なくとも１つ」というフレーズは、特に明記されない限り、アイテム、用語などが、Ｘ、ＹまたはＺのいずれかでもよいし、または、これらの任意の組み合わせ（例えば、Ｘ、Ｙおよび／またはＺ）でもよいことを一般的に提示するように用いられる文脈でさもなければ理解されるものである。このように、この種の離接的用語は、一般的に、特定の実施形態が、少なくとも１つのＸ、少なくとも１つのＹまたは少なくとも１つのＺが各々存在することを必要とすることを示唆することを意図しないし、示唆すべきではない。
【００５７】
[0061]上述した説明は、各種実施形態に適用される新しい特徴を示し、記載し、指摘してきたが、本発明の精神を逸脱することなく、例示されるデバイスまたはアルゴリズムの形および詳細においてさまざまな省略、置換および変更が可能であることを理解されたい。認識可能なように、本願明細書に記載されている本発明の特定の実施形態は、本願明細書に記載される特徴および利点のすべてを提供するわけではない形で実施可能であり、いくつかの特徴は、他の特徴とは別に使用または実行可能である。本願明細書に開示される特定の発明の範囲は、上述した説明よりもむしろ添付の特許請求の範囲によって示される。特許請求の範囲と均等の意味および範囲内のすべての変更は、本発明の範囲内に包含されるものである。
【図１】
0006790067.tif 000002
【図２】
0006790067.tif 000003
【図３】
0006790067.tif 000004
【図４】
0006790067.tif 000005
【図５Ａ】
0006790067.tif 000006
【図５Ｂ】
0006790067.tif 000007