(57)【特許請求の範囲】
【請求項１】
格納された命令を有するメモリと該メモリに結合されたプロセッサとを備えたコンピューターシステム上で実行される、エリアをカバーするマップを提供する方法であって、
前記プロセッサが、前記命令を実行して、クエリを受信するステップであって、該クエリは検索語及び検索エリアを有する、受信するステップと、
前記プロセッサが、前記命令を実行して、適合するリストを求めるステップであって、該適合するリストは、前記検索語に対応する情報を有する、前記検索エリア内の地理的ロケーションに関連付けられたリストを含む、求めるステップと、
前記プロセッサが、前記命令を実行して、前記検索エリアを複数の領域に分割し、該領域毎に適合するリストの数を選択するステップであって、各前記領域について、前記適合するリストの前記選択された数は、該領域内の前記適合するリストの密度に比例する、分割し選択するステップと、
前記プロセッサが、前記命令を実行して、所与の領域内の前記適合するリスト毎にスコアを求めるステップと、
前記プロセッサが、前記命令を実行して、前記適合するリストに関連付けられた地理的ロケーションと、前記所与の領域内のロケーションとの間の距離に基づいて、前記所与の領域内の前記適合するリスト毎に前記スコアを平滑化するステップと、
前記プロセッサが、前記命令を実行して、前記所与の領域内の前記適合するリスト毎に前記平滑化されたスコアを用いるステップであって、前記所与の領域について前記適合するリストの数を選択する、用いるステップと、
前記プロセッサが、前記命令を実行して、前記検索エリアのマップ、及び前記検索エリア内の前記領域毎の前記選択された数の適合するリストに関する情報を提供するステップと
を含んでなる、エリアをカバーするマップを提供する方法。
【請求項２】
前記リストは、該リストが前記検索語を含む情報を有するときに該検索語に対応する情報を有する、請求項１に記載の方法。
【請求項３】
前記適合するリストは、所在地住所に関連付けられたビジネスリストを含む、請求項２に記載の方法。
【請求項４】
前記検索エリアは、前記ユーザーに表示されるマップの座標から求められる、請求項１に記載の方法。
【請求項５】
前記複数の領域は実質的に面積が等しい、請求項１に記載の方法。
【請求項６】
前記領域毎の前記選択された数の適合するリストに関する前記情報は、該選択された数の適合するリストのうちの少なくとも１つにおける前記ロケーションを示す第２のマップを含む、請求項１に記載の方法。
【請求項７】
前記プロセッサが、前記命令を実行して、前記第２のマップを前記検索エリアの前記マップと合成するステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記領域毎の前記選択された数の適合するリストに関する前記情報は、該選択された数の適合するリストのうちの少なくとも１つに関するテキストデータを含む、請求項１に記載の方法。
【請求項９】
エリアをカバーするマップを提供するシステムであって、
格納された命令を有するメモリと、
前記メモリに結合され、該メモリに格納された前記命令を実行するように構成されたプロセッサであって、それによって、
クエリを受信し、ここで、該クエリは検索語及び検索エリアを含み、
適合するリストを求め、ここで、該適合するリストは前記検索語に対応する情報を有する前記検索エリア内の地理的ロケーションに関連付けられたリストを含み、
前記検索エリアを複数の領域に分割し、該領域毎に前記リストの数を選択し、ここで、各該領域について、前記適合するリストの前記選択された数は該領域内の前記適合するリストの密度に比例しており、
所与の領域内の前記適合するリスト毎にスコアを求め、
前記適合するリストに関連付けられた前記地理的ロケーションと前記所与の領域内のロケーションとの間の距離に基づいて前記所与の領域内の前記適合するリスト毎に前記スコアを平滑化し、
前記所与の領域内の前記適合するリスト毎の前記平滑化されたスコアを用いて該所与の領域の前記適合するリストの数を選択し、
前記検索エリアのマップ及び該検索エリア内の前記領域毎の前記選択された数の適合するリストに関する情報を提供するものである、プロセッサと
を備えてなる、エリアをカバーするマップを提供するシステム。
【請求項１０】
前記リストは、該リストが前記検索語を含む情報を有するときに該検索語に対応する情報を有する、請求項９に記載のシステム。
【請求項１１】
前記適合するリストは、所在地住所に関連付けられたビジネスリストを含む、請求項９に記載のシステム。
【請求項１２】
前記検索エリアは、前記ユーザーに表示されるマップの座標から求められる、請求項９に記載のシステム。
【請求項１３】
前記複数の領域は実質的に面積が等しい、請求項９に記載のシステム。
【請求項１４】
前記領域毎の前記選択された数の適合するリストに関する前記情報は、該選択された数の適合するリストのうちの少なくとも１つの前記ロケーションを示す第２のマップを含む、請求項９に記載のシステム。
【請求項１５】
前記プロセッサは、前記検索エリアの前記マップを用いて前記第２のマップを合成するための命令を実行するようにさらに構成される、請求項１４に記載のシステム。
【請求項１６】
前記領域毎の前記選択された数の適合するリストの数に関する前記情報は、該選択された数の適合するリストのうちの少なくとも１つに関するテキストデータを含む、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本願は、２００９年１月２６日に出願された米国特許出願第１２／３５９，７１５号、代理人整理番号第ＧＯＯＧＬＥ３．０−０３８号の優先権を主張し、該特許出願の開示内容全体を引用することにより、本明細書の一部を成すものとする。本願はまた、２００９年１月２６日に出願された米国特許出願第１２／３５９，７３４号の優先権も主張し、該特許出願の開示内容全体を引用することにより、本明細書の一部を成すものとする。
【背景技術】
【０００２】
Ｇｏｏｇｌｅ  Ｍａｐｓ（maps.google.com）等のサービスは、ユーザーが、特定の地理的エリアに限定された検索を実行するのを可能にする。たとえば、ユーザーは、Ｇｏｏｇｌｅ  Ｃｈｒｏｍｅ等のウェブブラウザーでニューヨーク市の市街マップ又は衛星マップを閲覧しながら、単語「pizza」を検索する場合がある。それに応じて、サーバーはユーザーのコンピューターに、名前に「pizza」を含むレストラン等の、クエリに適合するリストの位置を示すアイコンを表示させる。
【０００３】
クエリの結果は、多大なインタラクティブ性を可能にする方法で送信することができる。たとえば、マップは、画像のタイルとして送信され、結果の記述及びそれらの位置がテキスト（ＪＳＯＮ（Javascript Object Notation：Ｊａｖａｓｃｒｉｐｔオブジェクト表記法）又はＨＴＭＬとしてフォーマット設定されたデータ等）として送信される。これによって、ユーザーのコンピューターがマップ上にアイコンを表示し、マップの隣りに結果のテキストリストを表示することが可能になる。クライアントコンピューターは、サーバーによって提供されるＪａｖａｓｃｒｉｐｔを用いて、ユーザーが、インタラクティブなアイコンによって占有されるマップのエリアをクリックしたか否かを判断し、それに応じて、リストに関するさらに多くの情報を含むバルーンを表示する等の複数の動作を実行することができる。
【０００４】
Ｇｏｏｇｌｅ  Ｍａｐｓはレイヤーも可能にする。たとえば、現在閲覧されている地理的エリアに合致する緯度／経度に関連付けられたWikipedia.orgにおけるエントリのアイコンを示すことが可能である（たとえば、http://en.wikipedia.org/wiki/Wikipedia:WikiProject_Geographical_coordinates）。エントリのアイコンは画像として送信され、該エントリに関する情報と共にマップ上にオーバーレイされる。情報はマップ上のエントリの位置を特定する情報及びエントリの識別情報と共にＪＳＯＮで送信される。位置情報はユーザーのコンピューターによって、ユーザーが（アイコンをクリックするか又はアイコンの上でマウスカーソルをホバリングさせる等によって）アイコンを起動したか否かを判断するのに用いることができ、識別情報は、アイコンが起動された場合にサーバーからより多くの情報を取得するのに用いることができる。ＹｏｕＴｕｂｅの結果もレイヤーとして示すことができる。これらの結果はクエリに基づいてフィルタリングされるのではなく、マップによってカバーされるエリア内の全てのエントリを示す。
【０００５】
Ｇｏｏｇｌｅ  Ｍａｐｓは、ユーザーが、サーバーによって送信された、「Italian」及び「Pizza」レストラン、銀行、ガソリンスタンド等の或る特定の予め選択されたカテゴリ内に入る全てのビジネスに関連付けられたアイコンを表示することを可能とする、「名所」レイヤーも特徴とする。ユーザーは予め選択されたカテゴリ、及び予め選択されていないカスタム検索語に基づく検索から検索結果を集合的に表示することができるが、結果は別個であり、すなわち予め選択されたカテゴリのアイコンはユーザー定義語に基づいて変化せず、逆もまた同様である。たとえば、ユーザーは「pizza」の隣りのボックスをチェックし、語「vegetarian」をタイプ入力する場合があり、この場合、Ｇｏｏｇｌｅ  Ｍａｐｓは検索結果を合成して一緒に表示するが、「pizza」に関連付けられた結果が「vegetarian」クエリに基づいて選択されるわけではなく、「vegetarian」クエリに関連付けられた結果がリストからの「pizza」の選択に基づいて選択されるわけでもない。www.tavernoxoros.gr（予め選択されたカテゴリのユーザーの選択に応じてマップ上に多くのロケーションを示す）及びwww.smalltownbrooklyn.com（マップ上に全てのビジネスを示すことを可能とすることができる）等のサイトは同様に、予め選択されたカテゴリに関連付けられた全ての結果を示すことが可能である。
【発明の概要】
【０００６】
１つの態様では、クエリを受信するステップと、適合するリストを求めるステップと、複数の適合するリストを選択するステップと、マップを提供するステップとを含む方法が提供される。前記リストは、地理的ロケーションに関連付けられたオブジェクト及び該オブジェクトに関連する情報を特定するデータを含み、前記リストは、該リストの情報が前記クエリに合致し、かつ該リストの前記地理的ロケーションがマップエリアに合致するときに適合する。前記マップエリアの第２の部分に関連付けられた地理的ロケーションを有する適合するリストの数に対する、前記マップエリアの第１の部分に関連付けられた地理的ロケーションを有する適合するリストの数に基づいて複数の適合するリストが選択される。前記マップは前記適合するリストのインジケーションと共に提供される。
【０００７】
別の態様は、マップを表示するシステムを提供する。
このシステムは、
ユーザー入力デバイスと、
命令、及び異なる地理的ロケーションにおける異なるオブジェクトを表すデータを格納するメモリと、
前記命令に従って前記ユーザー入力デバイスから受信した情報を処理するように該ユーザー入力デバイスと通信するプロセッサと、
前記プロセッサと通信して該プロセッサから受信した情報を表示するディスプレイと
を備えてなる。
前記命令は、
前記ユーザー入力デバイスを介して入力されたロケーション情報に基づいてマップを読み出すことと、
前記ユーザー入力デバイスを介して入力された情報に合致するオブジェクトの識別情報を読み出すことであって、該読み出される識別情報は、前記ユーザー入力を介して入力された前記情報に合致する前記オブジェクトの全てよりも少なく、前記マップの部分内の合致するオブジェクトの密度に基づいて選択される、読み出すことと、
前記ディスプレイにおいて前記マップ上に前記識別情報を表示することと
を含む。
【０００８】
さらに別の態様は、マップエリアをカバーするマップを表示する方法を提供する。  この方法は、
ネットワークの第１のノードの第１のコンピューターから該ネットワークの第２のノードの第２のコンピューターにロケーション及び単語を送信するステップであって、該単語はユーザーによって任意に選択される、送信するステップと、
マップ及びリストを表すデータを受信するステップであって、該マップはエリアをカバーする、受信するステップと、
前記データに基づいてマップ及び該マップ上のリストを表示するステップと
を含んでなる。
前記マップデータは、前記ロケーションに基づいて前記第２のコンピューターによって選択される。前記リストは、密度判断基準及び該リストが適合するか否かに基づいて前記第２のコンピューターによって選択され、ここで、（ａ）前記リストは、前記送信された単語のうちの１つ以上が該リストに関連付けられた情報内に存在する場合に適合し、（ｂ）前記密度判断基準は、前記マップエリアの別の領域に対する前記マップエリアの１つの領域における適合するリストの量に依拠したものである。本発明のいくつかの態様では、単語のすべてが適合しなければならない。
【０００９】
さらなる態様は、マップを表示する方法を提供する。
この方法は、
ネットワークの第１のノードの第１のコンピューターから該ネットワークの第２のノードの第２のコンピューターに、ユーザーによって任意に選択されたロケーション及び単語を送信するステップと、
エリアをカバーするマップを表す画像データを受信するステップと、
リストの第１のセットを表す画像データを受信するステップと、
リストの第２のセットを表すテキストデータを受信するステップと、
前記データに基づいて、マップ及び該マップ上のリストを表示するステップと
を含んでなる。
この方法は、前記マップデータが前記ロケーションに基づいて前記第２のコンピューターによって選択されたものであるようになっている。さらに、該方法は、前記リストデータによって表される前記リストが、密度判断基準及び該リストが適合したか否かに基づいて前記第２のコンピューターによって選択されたものであるようになっており、ここで、（ａ）前記リストは、該リストに関連付けられた単語と前記送信された単語との間に合致があったか否か、及び該リストに関連付けられたロケーションと前記エリアとの間に合致があったか否かに依拠して適合し、（ｂ）前記密度判断基準は、前記エリアの別の領域に対する前記エリアの１つの領域における適合するリストの量に依拠したものである。
【００１０】
さらに別の態様は、クエリを受信する手段及び適合するリストを求める手段を有するシステムに関し、ここで、リストは、地理的ロケーションに関連付けられたオブジェクトを識別するデータ及び該オブジェクトに関連する情報を含み、適合の判断は、前記リスト情報が前記クエリに合致するか否か及び前記地理的ロケーションが前記マップエリアに合致するか否かを判断することを含む。このシステムは、前記エリアの第２の部分に関連付けられた地理的ロケーションを有する適合するリストの数に対する、前記エリアの第１の部分に関連付けられた地理的ロケーションを有する適合するリストの数に基づいて複数の前記適合するリストを選択する手段をさらに備える。さらに、該システムは、前記マップエリアのマップ及び前記適合するリストのインジケーションを提供する手段であって、各該インジケーションは、その地理的ロケーションに対して前記マップに配置される、提供する手段を備える。
【００１１】
さらに別の態様では、マップを表示する方法が提供される。
この方法は、
ネットワークの第１のノードの第１のコンピューターから該ネットワークの第２のノードの第２のコンピューターに、ユーザーによって任意に選択されたロケーション及び単語を送信するステップと、
エリアをカバーするマップを表す画像データを受信するステップと、
リストの第１のセットを表す画像データを受信するステップと、
リストの第２のセットを表すテキストデータを受信するステップであって、該第２のセット内のリストは前記第１のセット内のリストと異なる、受信するステップと、
前記リストの第１のセット及び前記リストの第２のセットを前記マップ上に表示するステップと
を含んでなる。
マップデータは、前記ロケーションに基づいて前記第２のコンピューターによって選択され、リストの双方のセットは、前記第２のコンピューターによって、リストが適合するか否かに基づいて選択されたものである。リストは、該リストに関連付けられた単語と前記送信された単語との間に合致が存在し、かつ前記リストに関連付けられたロケーションと前記マップエリアとの間に合致が存在するときに適合していると見なされる。
【００１２】
画像データの非限定的な例には、ベクトル又はビットマップ形式のデータが含まれる。テキストデータの非限定的な例には、ＪＳＯＮ、ＸＭＬ、又はＨＴＭＬとしてフォーマット設定されるデータが含まれる。
【００１３】
別の態様は、
データ及び命令を格納するメモリと、
前記命令に従って前記データを処理するプロセッサと、
前記プロセッサと通信して該プロセッサから受信した情報を表示するディスプレイと
を有するシステムに関する。前記命令は、ネットワークを介して、エリアをカバーするマップを表す画像データ、リストの第１のセットを表す画像データ、及びリストの第２のセットを表すテキストデータを受信することを含む。命令は、データに基づいてマップ及び該マップ上のリストを表示することも含み、マップデータは前記ロケーションに基づいてサーバーによって選択されたものである。さらに、前記サーバーによってリストが適合するか否かに基づいてリストが選択され、該リストは該リストに関連付けられた単語と前記送信された単語との間に合致が存在し、かつ前記リストに関連付けられたロケーションと前記マップエリアとの間に合致が存在するときに適合する。
【００１４】
またさらなる態様は、マップを送信する方法に関する。この態様は、ネットワークの第１のノードの第１のコンピューターにおいて、前記ネットワークの第２のノードの第２のコンピューターから、ユーザーによって選択されたロケーション及び任意の単語を受信するステップを含む。これは、第２のコンピューターにおけるプロセッサを用いて、前記ロケーション及び前記リストのマップを表すデータを選択するステップも含む。前記リストは、該リストに関連付けられた記述が前記受信した単語と合致するか否か、及び前記リストに関連付けられたロケーションが前記受信したロケーションと合致するか否かに基づいて選択される。この方法は、前記マップデータを画像データとして送信するステップと、前記選択されたリストに基づいて画像データを生成するステップとをさらに含み、ここで各選択された画像はアイコンに関連付けられ、該アイコンの位置は他のリストに対する前記リストの前記ロケーションに合致する。この方法は、前記選択されたリストに基づいて前記画像データも送信する。
【００１５】
本システムのさらに別の態様は、
ネットワークの第１のノードの第１のコンピューターから前記ネットワークの第２のノードの第２のコンピューターに、ユーザーによって任意に選択されたロケーション及び単語を送信する手段と、
エリアをカバーするマップを表す画像データを受信する手段と、
リストの第１のセットを表す画像データを受信する手段と、
リストの第２のセットを表すテキストデータを受信する手段と、
前記マップを表示する手段であって、前記マップ上の前記リストの第１のセット及び前記リストの第２のセットは前記データに基づく、表示する手段と
を備えてなる。
このシステムは、前記マップが前記ロケーションに基づいて前記第２のコンピューターによって選択されるようになっており、前記リストデータによって表されるリストは、前記第２のコンピューターによって、該リストが適合するか否かに基づいて選択され、ここで前記リストは、該リストに関連付けられた単語と前記送信された単語との間に合致があり、かつ該リストに関連付けられたロケーションと前記マップエリアとの間に合致がある場合に適合する。
【図面の簡単な説明】
【００１６】
【図１】本システム及び本方法の一態様によるシステムのブロック図である。
【図２】本システム及び本方法の一態様によるシステムの概略図である。
【図３】本システム及び本方法の一態様による、マップエリア、マップタイル、及び領域間の関係を表す図である。
【図４】本システム及び本方法の一態様による、マップ及びリストのセットのスクリーンショットである。
【図５】本システム及び本方法の一態様による、リストを示す前のマップ表示である。
【図６】全ての応答リストを示すマップ表示の例である。
【図７ａ】図７ｂに表示されるマップの一部分を示す図である。
【図７ｂ】表示されたマップエリアに基づいて選択された限られた数のリスト、及びユーザーのクエリに対する該リストの関連性を示すマップ表示の例である。
【図８ａ】図８ｂに表示されるマップの、図７ａに示す部分と異なる一部分を示す図である。
【図８ｂ】表示されたマップエリアに基づいて選択された限られた数のリスト、及び図７ｂと同じクエリに対する該リストの関連性を示すマップ表示の例である。
【図９】本システム及び本方法の一態様によるフローチャートである。
【図１０】本システム及び本方法の一態様による、マップの領域内の応答リストの数を示す図である。
【図１１】本システム及び本方法の一態様による、マップの領域内の応答リストの密度を示す図である。
【図１２】本システム及び本方法の一態様による、領域内の応答リストの位置を示す図である。
【図１３】本システム及び本方法の一態様によるマップ表示である。
【図１４】本システム及び本方法の一態様によるマップ表示である。
【図１５】本システム及び本方法の一態様による概略図である。
【図１６】本システム及び本方法の一態様によるリストの画像である。
【図１７】本システム及び本方法の一態様に従って表示されるマップ及びリストのセットのスクリーンショットである。
【図１８】本システム及び本方法の一態様によるフローチャートである。
【図１９】本システム及び本方法の一態様によるフローチャートである。
【図２０】本システム及び本方法の一態様によるフローチャートである。
【図２１】本システム及び本方法の一態様によるフローチャートである。
【発明を実施するための形態】
【００１７】
１つの態様では、本システム及び本方法は、いずれのエリアに応答リストがより密に存在しているかを示すように、マップ上にユーザーのクエリの結果を表示する。クライアントコンピューターの処理の必要性を低減するために、最も高スコアのリストのうちのいくつかをインタラクティブなアイコンとしてレンダリングするようにテキストとして送信することができるのに対し、残りのリストはマップにオーバーレイすることができる画像レイヤーとして送信される。
【００１８】
図１及び図２に示すように、１つの態様によるシステム１００は、プロセッサ２１０、メモリ２２０、及び汎用コンピューターに通常存在する他の構成要素を備えるコンピューター１１０を含む。
【００１９】
メモリ２２０は、プロセッサ２１０によって実行することができる命令２４０を含む、プロセッサ２１０によってアクセス可能な情報を格納する。メモリは、プロセッサによって読み出し（retrieve）、操作、又は格納することができるデータ２３０も含む。メモリは、ハードドライブ、メモリカード、ＲＯＭ、ＲＡＭ、ＤＶＤ、ＣＤ−ＲＯＭ、書き込み可能メモリ、及び読出し専用メモリ等、プロセッサによってアクセス可能な情報を格納することができる任意のタイプのものとすることができる。プロセッサ２１０は、Ｉｎｔｅｌ社のプロセッサ等の任意の既知のプロセッサとすることができる。代替的に、プロセッサはＡＳＩＣ等の専用コントローラーとすることもできる。
【００２０】
命令２４０は、プロセッサによって直接実行される命令（機械コード等）又は間接的に実行される命令（スクリプト等）の任意のセットとすることができる。これに関して、用語「命令」、「ステップ」、及び「プログラム」は本明細書において交換可能に用いることができる。命令は、プロセッサによる直接処理のためのオブジェクトコード形式で格納することもできるし、スクリプト又はオンデマンドで解釈実行されるか若しくは事前にコンパイルされる独立したソースコードモジュールの集合を含む任意の他のコンピューター言語で格納することもできる。命令の機能、方法、及びルーチンは以下でより詳細に説明する。
【００２１】
データ２３０は命令２４０に従ってプロセッサ２１０によって読み出し（retrieve）、格納、又は変更することができる。たとえば、本システム及び本方法はいかなる特定のデータ構造によっても制限されないが、データは、コンピューターレジスタにおいて、複数の異なるフィールド及びレコード、ＸＭＬ文書、又はフラットファイルを有するテーブルとして関係データベース内に格納することができる。データはまた、限定ではないが、バイナリ値、ＡＳＣＩＩ、又はＵｎｉｃｏｄｅ等の任意のコンピューター可読フォーマットでフォーマット設定することができる。さらに、データは、数字、説明文、所有権コード、ポインター、他のメモリ（他のネットワークロケーションを含む）に格納されたデータの参照子、又は関連データを計算する関数によって用いられる情報等の関連情報を特定するのに十分な任意の情報を含むことができる。
【００２２】
プロセッサ及びメモリは図１において同じブロック内に機能的に示されているが、当業者であれば、プロセッサ及びメモリが実際に複数のプロセッサ及びメモリを含むことができ、それらは同じ物理筐体内に格納することもしないこともできることが理解されよう。たとえば、命令及びデータによっては、取り外し可能なＣＤ−ＲＯＭに格納することができるものもあれば、読出し専用コンピューターチップ内に格納することができるものもある。命令及びデータのうちのいくつか又は全てを、プロセッサから物理的に離れているが依然としてアクセス可能なロケーションに格納することができる。同様に、プロセッサは実際に、並列に動作することもしないこともできるプロセッサの集合を含むこともできる。
【００２３】
１つの態様では、コンピューター１１０は、１つ以上のクライアントコンピューター１５０、１７０と通信するサーバーである。各クライアントコンピューターは、サーバー１１０と同様に、プロセッサ、メモリ、及び命令で構成することができる。各クライアントコンピューター１５０、１７０は人１９０及び１９１による使用を意図され、中央処理装置（ＣＰＵ）、ディスプレイ１６０（たとえばプロセッサによって処理される情報を表示するモニター）、ＣＤ−ＲＯＭ、ハードドライブ、ユーザー入力デバイス（たとえば、マウス、キーボード、タッチスクリーン、又はマイク）、スピーカー、モデム、及び／又はネットワークインターフェースデバイス（電話、ケーブル等）、並びにこれらの要素を互いに接続し、それらが（直接的に又は間接的に）互いに通信することを可能にするのに用いられる構成要素の全て等の、パーソナルコンピューターに通常見られる全ての内部構成要素を有するパーソナルコンピューターとすることができる。さらに、本明細書に記載されるシステム及び方法によるコンピューターは、命令を処理し、人間、及びローカルストレージ機能のないネットワークコンピューターを含む他のコンピューターに対し、それらからデータを送受信することが可能な任意のデバイスを含みうる。
【００２４】
クライアントコンピューター１５０及び１７０はフルサイズのパーソナルコンピューターを含むことができるが、本システム及び本方法の多くの態様は、インターネット等のネットワークを介してサーバーとデータを無線で交換することが可能な移動デバイスとの接続において用いられるときに特に有利である。たとえば、クライアントコンピューター１７０は、Ｂｌａｃｋｂｅｒｒｙ電話又はインターネット対応の携帯電話等の無線可能ＰＤＡとすることができる。それに関して、ユーザーは小さいキーボード（Ｂｌａｃｋｂｅｒｒｙ電話の場合）、キーパッド（通常の携帯電話の場合）、タッチスクリーン（ＰＤＡの場合）、又はユーザー入力の任意の他の手段を用いて情報を入力することができる。
【００２５】
クライアントコンピューター１５０及び１７０は、デバイスの地理的ロケーションを求める回路等の構成要素を含むことができる。たとえば、移動デバイス１７０はＧＰＳ受信機１５５を含むことができる。さらなる例として、構成要素は、移動デバイスが携帯電話である場合は１つ以上の携帯電話塔から携帯電話のアンテナにおいて受信した信号等、移動デバイス１５０において受信した他の信号に基づいてデバイスの位置を求めるためのソフトウェアを含むことができる。
【００２６】
サーバー１１０並びにクライアントコンピューター１５０及び１７０は、直接通信、及びネットワーク２９５等を介した間接通信が可能である。図１及び図２にはわずかな数のコンピューターのみが示されているが、通常のシステムは多数の接続されたコンピューターを含むことができ、各異なるコンピューターがネットワーク２９５の異なるノードにあることを理解すべきである。ネットワーク及び介在するノードは、インターネット、ワールドワイドウェブ、イントラネット、仮想プライベートネットワーク、広域ネットワーク、局所ネットワーク、携帯電話ネットワーク、１つ以上の会社の独自開発の通信プロトコルを用いるプライベートネットワーク、イーサネット（登録商標）、ＷｉＦｉ、及びＨＴＴＰを含む、デバイス及び通信プロトコルの様々な組み合わせを含むことができる。そのような通信は、他のコンピューターに対し他のコンピューターからデータを送信することが可能な、モデム（たとえばダイアルアップ又はケーブル）、ネットワーク及び無線インターフェース等の任意のデバイスによって容易にすることができる。サーバー１１０はウェブサーバーでありうる。
【００２７】
情報が上述したように送信又は受信されるとき、或る特定の利点が得られるが、本システム及び本方法の他の態様は、いかなる特定の情報送信方法にも限定されない。たとえば、いくつかの態様では、情報はディスク、テープ、又はＣＤ−ＲＯＭ等の媒体を介して送信することができる。他の態様では、情報は非電子フォーマットで送信することができ、システムに手作業で入力することもできる。またさらに、サーバー上で行われるものとして示される機能もあれば、クライアント上で行われるものとして示される機能もあるが、本システム及び本方法の様々な態様は、単一のプロセッサを有する単一のコンピューターによって実施することもできる。
【００２８】
サーバー１１０のマップデータベース２７０はマップに関連する情報を格納するが、そのうちの少なくとも一部分をクライアントデバイスに送信することができる。たとえば、マップデータベース２７０はマップタイル２７２を格納することができ、ここで各タイルは特定の地理的エリアのマップ画像である。解像度（たとえばマップがズームインされているか又はズームアウトされているか）に依拠して、単一のタイルによって、州等の全体領域を比較的大まかにカバーすることができる。他のタイルはいくつかの通りのみを高度に詳細にカバーすることもできる。本システム及び本方法のマップ情報は、いかなる特定の形式にも限定されない。たとえば、画像はストリートマップ、衛星画像、又はこれらの組合せを含むことができ、ベクトル（特に街路マップに関して）又はビットマップ（特に衛星画像に関して）としてフォーマット設定することができる。様々なマップタイルはそれぞれ地理的ロケーションに関連付けられ、それによって、サーバー１１０が地理的ロケーション又は地理的ロケーションの範囲の受信に基づいて１つ以上のタイルを選択、読み出し（retrieve）、及び送信することが可能になる。
【００２９】
マップデータベース２７０は、ビジネス若しくは他のオブジェクトを特定するリスト情報、又は特定の地理的ロケーションに関連付けられた地理的特徴も格納することができる。たとえば、各ローカルビジネス２７４は、名前、カテゴリ（「ピザ、イタリアンレストラン」、又は「球場」等）、他の情報（営業時間、メニューにある食べ物等）、及びロケーションに関連付けることができる。ロケーションは、テキストベースの所在地住所（「1600 Amphitheatre Parkway, Mountain View, CA」）、又は緯度／経度位置（緯度３７．４２３０２１、経度−１２２．０８３７３９等）等の異なる形式で表現することができる。また、ビジネスの住所について、所在地住所及び緯度／経度位置の双方を格納する等、複数の記述も同様に格納することができる。データベースは（ウェブサイト又は電話帳等から）自動的にビジネス情報を集めることによって編纂することもできるし、ユーザーがサーバー１１０によってサービス提供されているウェブページを介して自身でローカルビジネス記録を入力又は編集することもできる。
【００３０】
多くの場合に、異なるビジネス毎にマップデータベース２７０内に単一のリスト２７４が存在する。しかしながら、同じビジネスを多くの異なるリストに関連付けることができること、及び単一のリストを多くの異なるビジネスに関連付けることができることが理解されよう。
【００３１】
リストは、ビジネスに加えて又はビジネスの代わりに、他の地理的に配置されたオブジェクトを含むことができる。たとえば、それらは家、ランドマーク、道路、陸地、自動車の現在の位置、店に配置された商品等を特定することもできる。したがって、ビジネスリストへの言及は例示としてのみ理解され、本システム及び本方法の対象となることができるリストのタイプに対する制限としては理解されない。
【００３２】
本システム及び本方法の１つの態様において、各リストは「領域セル」と呼ばれる１つ以上の地理的領域にも配分される。たとえば、地球は様々なレベル及びサイズの個々の領域に分割されていると見なすことができる。最も高いレベルにおいて、地球は４つの領域セル、すなわち赤道より北の２つ及び下の２つに分割されていると見なすことができる。２番目に高いレベルにおいて、これらのセル（赤道の北で本初子午線の東のセル等）を別の４つのセルにさらに分割することができる。３番目に高いレベルにおいて、２番目に高いレベルのセルのそれぞれを、さらに別の４つのセルに分割することができる。これは、領域セルの所望の数のレベルが達成されるまで継続することができる（地球が始めに４つのセルに分割されることも、各レベルが４つのセルによって分割されることも必須ではない。）
【００３３】
このため、地球上の任意の特定の点が、各レベルにつき１つの、多くの異なる領域セル内に含まれることになる。同様に各領域セルが地理的エリアに関連付けられる。
【００３４】
マップデータベース２７０は、リスト２７４毎に、リストが存在する領域セルを格納することができる。たとえば、マンハッタンのピザ屋が多くのセルに関連付けられ、これらのセルは、（１）本初子午線の東の北半球の全てを含む大きな領域セル、及び（２）マンハッタンの近隣のみを含むはるかに小さな領域セル、の双方を含む。代替的に、リストの適用可能な領域セルは、クエリが受信された後等、必要な場合に要求に応じて確定することができる。
【００３５】
図３は、マップエリア、領域セル、及びタイルの境界が互いに関連することができる方法を示している。ブロック３１０（太い実線）は表示されるマップエリアを表す。ブロック３２０及び３２１、並びに細い実線によって画定される他のボックスは、マップを示すためにクライアントコンピューターに送信され、該クライアントコンピューターによって綴じ合わせられる個々のマップタイルを表す。ボックス３３０及び３３１、並びに破線によって画定される他のボックスは、マップエリアに関連付けられた領域セルの１つのレベルを表す。マップエリア、タイル、及び領域セルのエッジは互いに完全に整列されていない場合があるが、それぞれが特定の地理的位置に関連付けられており、このため互いに対するそれらの位置が知られている。
【００３６】
図１８に示す動作に加えて、本システム及び本方法の多岐にわたる態様による様々な動作を次に説明する。以下の動作は後述する厳密な順序で実行される必要はないことを理解すべきである。そうではなく、様々なステップを逆の順序で又は同時に処理することができる。
【００３７】
図４は、ユーザーが閲覧するマップのスクリーンショットを示している。たとえば、本システム及び本方法は、マップ及び他の情報を示すウェブページを表示するＧｏｏｇｌｅ  Ｃｈｒｏｍｅ等のインターネットブラウザーと関連して実施することができる。
【００３８】
ユーザーは、クエリを入力することによって特定のロケーションに関連付けられたリストの検索を実行することができる、たとえば、ユーザーは、テキストボックス４１０に「Pizza nyc」をタイプすることによって、サーバーに１つ以上の検索語（「pizza」等）及びロケーション（「nyc」等）を提供し、ニューヨーク市内のピザに関連するビジネスを検索することができる（図４では例として架空の町「Ａｎｙｔｏｗｎ」が用いられる）。
【００３９】
本発明の１つの態様において、クエリはユーザーに選択された任意の単語を含む。たとえば、ユーザーを検索語又は検索タイプの予め定義されたリストに制限するのではなく、ユーザーは自身のキーボードを用いて、自身の望む任意の１つ以上の単語を一度に１文字タイプすることができる。
【００４０】
ユーザーは、マウス、キーボード、又は他のユーザー入力デバイスを用いることによって特定の地理的エリアを選択し、所望に応じてパン及びズームすることもできる。音声及び画像を提供すること等によって他のフォーマットでも同様にクエリを提供することができる。
【００４１】
ユーザーのクエリに応答して、サーバーはマップ４４０の画像のみでなく、検索結果を送信することができる。サーバー１１０は、応答リストをマップ上に描画して、そのマップを送信するのではなく、リストの説明及びそのロケーションをクライアント１５０に送信する。これによって、ユーザーコンピューターは、クリックに応答するアイコン４２０を描画する等、リストとのインタラクションを容易に可能にすることができようになる。ユーザーコンピューターは、マップ４４０に隣接した別個のロケーションにテキスト４３０としてリストを示すこともできる。
【００４２】
多数のリストが返されるとき、本システム及び本方法はそれらを全て表示することができる。しかしながら、マップ上にリストを表示するのに用いられるアイコンがあまりに広範囲に重なるため、マップが許容できないほど見えにくくなる場合がある。たとえば、図５及び図６は、「pizza nyc」の（それぞれ）検索前及び検索後について、名前に「pizza」を有しかつニューヨーク市内にある全てのリストについてアイコン５２０が表示される場合にニューヨーク市のマップ５１０がどのように見える可能性があるかを示している。
【００４３】
さらに、多くのクライアントコンピューターは、数百個のリストを許容可能に処理及び表示することができない。たとえば、クライアントコンピューターが、携帯電話等の比較的低電力低メモリのデバイスであり、かつリストがＪＳＯＮ又はＸＭＬ等のテキストベースのファイルとして送信される場合において、クライアントコンピューターは、ユーザーがマップをパンする場合に、迅速にリストの全てを描画して迅速にリストを再配置するのが非常に困難な場合がある。ニューヨーク市内のピザを販売するレストランは数万店存在する場合がある。
【００４４】
背景技術のセクションにおいて上述したように、クライアントコンピューターにおける視覚クラッター又は処理要件を低減するために、或る特定の数の応答リストのみを送信することができる。図７ｂはスコア上位２５個のピザリスト（ピン７１０等の黒いピンで示される）が、非常に密度の高いマンハッタン７３０の全て及び密度がより低いブルックリン／クイーンズ７４０のうちのいくらかを含むマップ７２０に示される場合の１つの可能な結果を示している。図７ａのブロック７５０は、ニューヨーク市の残りの部分に対するマップ７２０の外形を示している。密度に差異があるため、マンハッタンに示されるリスト７６０の数（２２個のリスト）は、ブルックリン／クイーンズのリスト７７０の数（２個のリスト）をはるかに上回る。これによって、マンハッタンは極端にかつ密に高スコアのリストでいっぱいなのに対し、ブルックリン／クイーンズは高スコアのリストが比較的少ないという印象が伝わる。
【００４５】
ニューヨーク市のビューが、図８に示すように、ブルックリン／クイーンズをはるかに多く含みかつマンハッタンをはるかに少なく含むようにパンされ、マップ８２０内にスコア上位２５個のリストが示される場合、より多くのブルックリン／クイーンズのリストが示され、より少ないマンハッタンのリストが示されることが予期される。１つの可能な結果が図８ｂに示されている。しかしながら、クエリされるリストのセットが変化する（ここでマップ８２０ににはマンハッタンの一部のみが見られ、ブルックリン／クイーンズはより多く見られる）ので、上位スコアのリスト８６０は劇的に変化する場合がある。たとえば、マンハッタンのリスト８６０は図７ｂのマンハッタンのリスト７６０よりもはるかに密度が低く見える場合がある。さらに、マンハッタンのリスト８６０が依然としてブルックリン／クイーンズのリスト８７０よりも密度が高く見えるが、近隣間の差は図８ｂにおいて図７ｂよりはるかに際立っていない。ユーザービューマップ図８ｂは、リストがどれだけ近接して互いに詰まっているかに関して言えば、マンハッタンとブルックリン／クイーンズとの間の差異についてユーザービューマップ図７ｂとはるかに異なる印象を有する。
【００４６】
本システム及び本方法の１つの態様において、リストは、クエリに応答して、他のリストに対する該リストの地理的近接性に少なくとも部分的に基づいて選択される。たとえば、リストは、他のリストが密集した地理的エリアにある場合、表示される可能性がより高い。
【００４７】
これに関して、本システム及び本方法は、１つのエリア（マンハッタン等）内のリスト数を表示される別の地理的エリア（ブルックリン等）と比較し、差異に基づいてリストの一部分を選択する。換言すれば、マンハッタンがブルックリンの２倍のリストを有する場合、ブルックリンの２倍のリストがマンハッタンにおいて示されることになる。
【００４８】
さらに、リストは、該リストがクエリとどの程度合致するかに基づいて選択することができる。たとえば、システムがマンハッタン及びブルックリングの双方を含むマップにおいて３０個のリストを同時に示すとして、マンハッタンにおいてブルックリンの２倍の応答リストが存在する場合、マンハッタンの上位２０個の最も適合するリストがマンハッタンにおいて表示され、ブルックリンの上位１０個の最も適合するリストがブルックリンにおいて表示される。換言すれば、マップはマンハッタン及びブルックリンの双方を示しているが、上位１００個のリストの全てがマンハッタンにある場合であっても、依然としてブルックリンにおいて１０個の適合するものを示すことになる。同様に、マップは、上位１００個のリストの全てがブルックリンにある場合であっても、依然としてマンハッタンにおいて２０個の適合するものを示すことになる。
【００４９】
より多くのリストを示すことによって、リストの分布のより大きな意味を伝えるのに役立つことができる。しかしながら、図６に関連して上述したように、リストが密度に基づいて選択された場合であっても、クライアントコンピューターはマップ上に多数のリストを示すことが困難である場合がある。リストはマップに直接描画しクライアントに送信することができるが、クライアントコンピューターは、リストが図４に関連して説明したようなテキストで送信されたかのように、ユーザーに同じインタラクティブ性を提供することができない場合がある。
【００５０】
本システム及び本方法の１つの態様は、サーバーを用いてリストのうちのいくつかを画像上に位置決めし、クライアントコンピューターを用いて、様々な形式のリスト及びマップ情報を提供することによってリストのうちのいくつかを位置決めする。
【００５１】
図９に示すように、クライアントコンピューター９１０からのクエリに応答して、サーバー９２０はマップの画像９３０（ビットマップ又はベクトルベースのタイル）、上位リストを特定する情報のうちのいくつかを記述する情報９４０（テキストベースのＨＴＭＬ、ＪＳＯＮ、又はＸＭＬファイル等）、及びマップ画像９３０の上にオーバーレイする、クライアントコンピューター用の他のリストの画像９５０を送信する。クライアントコンピューター９１０のプロセッサは、この情報を受信及び処理して、単一画像９６０を作成及び表示する。
【００５２】
たとえば、クライアントコンピューターは、ウェブブラウザーにおいてマップ９６０を表示することができ、リスト情報９４０内に含まれる情報を用いてマップ９３０上のユーザーが起動可能な（user-actuable）アイコン９９０の位置を確定してレンダリングし、また、情報をマップの隣にテキスト９９１として表示する。１つの態様において、リストはユーザーの関心対象となる尤度に基づいてテキストとして送信される。
【００５３】
クライアントコンピューター９１０は、マップ上に他のリストの画像９５０もオーバーレイし、これによってユーザーが、リスト情報９４０内に含まれるリストを超える他のリストのインジケーション９８０を見ることを可能にする。リスト情報９４０に含まれるリストのように、これらのリストもユーザーのクエリに応答する。さらに、これらのリストは、上記で検討したように密度を反映するよう選択することができる。
【００５４】
他のリストの画像はサーバーによってレンダリングされるので、本システム及び本方法の１つの態様では、クライアントコンピューターはオーバーレイ上のリストのロケーションを計算する必要もないし、さらには認識する必要もない。そうではなく、それらのリストは既にサーバー９２０によってオーバーレイ上に位置決めされているので、クライアントコンピューター９１０はマップ９３０の上に他のリストを迅速に表示することができる。さらに、マップ上に示される数百個の他のリストが存在する場合であっても、クライアントコンピューターはそれらのロケーションを受信する必要も処理する必要もないし、それらの起動を個々に表示する必要も試験する必要もない。本システム及び本方法のこの態様は、制限されたユーザー入力又は処理力を有するデバイスに関連して特に有利とすることができる。
【００５５】
本システム及び本方法の態様は有利には、クライアントコンピューターのプロセッサに過度な負荷をかけることなく様々な特徴を同時に利用可能とする。例として、ユーザーがニューヨーク市等の高密度のエリアを閲覧しているときに「pizza」がクエリされた場合、画像オーバーレイ９５０は、ユーザーのクエリに応答した多くのリストが存在することをユーザーが見て取ることを可能にする。加えて、サーバーが上述した密度に基づいてオーバーレイ９５０内のリストを選択すると、ユーザーはどこにリストが最も集中しているかを見ることもできる。これは、ユーザーが訪ねることを望み得るエリアを求めるときに非常に価値があるものとすることができる。サーバーによって予め選択されたカテゴリ又は用語ではなく、ユーザーによって提供された任意の単語を含むクエリに少なくとも部分的に基づいてリストの双方のセットが選択される。
【００５６】
この態様は、ユーザーがリストと大きくインタラクトすることを可能にするという利点も有する。たとえば、クライアントコンピューターはリスト９９１に関連付けられたアイコン９９０をクリックすることによって該アイコンを起動することができる。アイコンを起動することによって、より多くの情報をもたらすことができる（住所及び写真のようなさらなる情報を含むバルーンを表示する等）。同様に、テキストリスト９９１をクリックすることによって、マップ上のリストの関連付けられたアイコン９９０を強調表示することができる。したがって、ユーザーの最も大きな関心対象である可能性が高いリストが高度にインタラクティブであり続ける。
【００５７】
次に、ユーザーの任意のクエリ、リストの密度に基づいてリストを選択し、リストの画像オーバーレイを処理するための１つの可能なシステム及び方法を、限定ではなく例として説明する。
【００５８】
図１及び図２に示すように、ユーザー１９０はクライアントコンピューター１５０上のウェブブラウザープログラムに、ネットワーク２９５を介してウェブサーバー１１０に接続させる。サーバー１１０は、Ｊａｖａｓｃｒｉｐｔを含むウェブページをブラウザーに送信する。クライアントコンピューターのプロセッサはＪａｖａｓｃｒｉｐｔ命令を実行する。該Ｊａｖａｓｃｒｉｐｔ命令はサーバーに特定のロケーションにおける初期マップを要求することを含む。初期ロケーションは、ユーザーが閲覧した最後のロケーションを用いること、サーバーにデフォルトロケーションを選択させること、サーバーにログインするのに用いられるＵＲＬにロケーションを付加すること、及び他の多くの方法を含む任意の数の方法で特定することができる。本システム及び本方法は、ロケーションを特定するいかなる特定の方法にも限定されない。
【００５９】
次に、ユーザーはウェブブラウザーにクエリを入力することができる。そのクエリはウェブサーバーに送信される。サーバー１１０は、クライアントコンピューター１５０からクエリを受信した後、クエリがロケーションに関連付けられているか否かを判断し、関連付けられている場合、そのロケーションがどこであるかを求める。たとえば、クエリが「pizza nyc」である場合、サーバーはクエリの「nyc」部分がロケーションに関連すると判断し、そのロケーションの緯度／経度位置を求めることに進むことができる。それに関して、ロケーションに関連付けられた部分は、ジオコーディングルーチンに渡すことができ、ジオコーディングルーチンは（「1600 Amphitheatre Parkway, Mountain View, CA」のような）アドレスを（緯度３９．４２３０２１及び経度−１２２．０８３９３９のような）地理的座標に変換する。同様に、ジオコーディングルーチンは、「nyc」をニューヨーク市の中心の緯度／経度に変換することもできる。
【００６０】
サーバー１１０は、緯度／経度又は同様の位置を求めることに加えて、どれだけの地理的エリアを表示するかも求める。たとえば、特定の所在地住所の要求によって、サーバー１１０に、その住所を中心とするほぼ１マイル四方のエリアを含むロケーション矩形を選択させることができる。同様に、ユーザーが「nyc」等の都市のみを特定する場合、サーバーは、ニューヨーク市の全体を画するロケーション矩形を選択することができる。ロケーション矩形のサイズは、ユーザーのマップの現在のズームレベルを用いる（ユーザーが現在マップを閲覧していると仮定する）等によって他の要因によっても同様に求めることができる。
【００６１】
クエリ内でロケーションが見つかると、サーバーはユーザーが最後に閲覧した地理的エリア内又は該地理的エリアの近くのリストを検索していると仮定することができる。この場合、サーバーはユーザーが現在閲覧している地理的エリアに相応のロケーション矩形を選択することができる。他の形状も用いることができる。たとえば、地球等の半球の表面は厳密に矩形ではなく、したがって、矩形が十分でないと考えられる場合、他の形状を選択することができる。たとえば、他の四頂点形状、多角形、及び曲線形状を同様に矩形の代わりに用いることができる。
【００６２】
ロケーション矩形は、所望のズームレベルによって作用を受けることもできる。たとえば、ユーザーが検索を実行した時点で該ユーザーがマップを閲覧している場合、サーバーはその現在選択されているズームレベルを用いてロケーションエリアを確定することができる。
【００６３】
サーバー１１０のプロセッサ２１０は、ユーザーのクエリ（たとえば「pizza」）及びロケーション矩形（たとえば異なる緯度／経度位置に４つの角を有し、ニューヨーク市の全体又はほとんどを画する矩形）を用いてリスト２９４をクエリする。次に、サーバーは、ロケーション矩形内又はロケーション矩形の比較的近くにあり、かつ要求された語（たとえば「pizza」）、その変形（たとえば「pizzeria」）、高度に関連していると知られる語（たとえば「parlor」）、又は本システム及び本方法によって適合を示すと定義される方法で他の形でユーザークエリに合致する語を含む任意のリスト等の適合を探すことに進む。適合と考えられるリストは以後、特に「応答リスト」と呼ばれる場合がある。
【００６４】
サーバー１１０は応答リストのスコアを求める。例として、スコアはリストがユーザーの関心対象である尤度に関連する値とすることができる。比較的高いスコアによって比較的高い関心の尤度を表すことができ、比較的低いスコアによって比較的低い関心の尤度を表すことができる。スコアは、任意の数の要因と、正値又は負値を様々な特性に割り当て、それらの値を合算すること等の任意の数の公式とに基づくことができる。以下ではいくつかの特性が説明されるが、以下の特性は本システム及び本方法のすべての態様において必要とされるわけではない。さらに、他の特性も同様に用いることができる。
【００６５】
スコアのいくつかの特性は、クエリのリストの比較に依拠することができる。たとえば、ユーザーのクエリ内の単語がリストの名前又はカテゴリ内の単語に完全に適合する場合（たとえば、ユーザーが「pizza」を検索しており、ビジネス名が「Joe's Pizza」である）、非常に高い値をスコアに付加することができる。ユーザーの語がリスト内の他の情報に部分的に適合する場合（たとえばユーザーが「pizza」を検索しており、ビジネスがそのウェブサイト上のどこかで「pizza burgers」をサービス提供していることにたまたま言及している球場である）、スコアにより低い値を付加することができる。
【００６６】
１つの態様において、スコアはユーザーが要求したロケーションに対するリストの近接性に依拠して変更することもできる。たとえば、ユーザーが所在地住所を提供し、リストの所在地が正確に適合する場合、非常に高い値をスコアに付加することができる。ユーザーが都市名を提供し、リストの住所が近隣の都市にある場合、より低い値を付加することができる。
【００６７】
スコアは特定のクエリに関連のない情報に依拠することもできる。たとえば、リストが過去に多くの異なるユーザーによって閲覧された場合、スコアに高い値を付加することができる。リストが過去に他のユーザーに多数回示されたがめったに選択されなかった場合、より低い値をスコアに付加することができる。
【００６８】
いくつかのスコアは、リストのさらなる処理が必要ないとサーバーが判定する場合があるほど低くすることができる。それに関して、或る特定のリストは、該リストがクエリに或る程度適合している場合であっても無関係とみなすことができる。
【００６９】
サーバーは、クライアントコンピューターに送信するための或る特定の数の上位スコアのリストを選択することができる。言及する目的のみで、そのようなリストを本明細書において「上位リスト」と言及することができるが、上位リストは最もスコアが高いリストであること以外に基づいて選択することもできることが理解される。
【００７０】
次に、応答リストはそのスコアに基づいて解析される。たとえば、サーバーは２つのヒストグラムを作成することができる。ここで、第１のヒストグラムはユーザーのクエリ（又はリスト内のユーザーの関心を予測することを大きく示唆するとみなされるいくつかの他の判断基準）に適合する名前又はカテゴリを有するリストを格納する。第２のヒストグラムは、ユーザーのクエリに適合する、レビュー又はウェブページ等の他の要素を有するリストを含むことができる。
【００７１】
そして、各ヒストグラムはスコアの昇順又は降順の範囲を含む帯に分割される。各リストは適切なヒストグラムの適切な帯内にソートされる。
【００７２】
サーバーは応答リストのスコアを解析して、上位リストを超えるリストが示されるべきか否かを判断することもできる。たとえば、高スコアヒストグラム内の結果がわずかであり、低スコアヒストグラム内の結果が多数である場合、サーバーは、ユーザーが残りのリストに興味を持つ可能性が低いと判定し、トリガーを「偽」に設定することができる。高スコアヒストグラム内の結果が多数である場合、又は低スコアヒストグラム内の結果がわずかであるが、高スコアヒストグラム内の結果が多数である場合、トリガーを「真」に設定することができる。
【００７３】
解析結果は、処理又は評価のためにクライアントコンピューターに送信することができる。たとえば、サーバー１０は上位リストを記述するＨＴＭＬ又はＪＳＯＮファイルを作成することができる。
【００７４】
上位リストの説明はクライアントコンピューターにテキストとして送信され、クライアントコンピューターに、少なくともマップ上にリストを示すのに十分な情報を提供することができる。１つの態様では、情報はリストの名前、所在地住所、及び電話番号を含む。情報は、リストに関連付けられたマップ上のクリック可能な領域のリスト、及びそれらの領域がクリックされたときに何が起こるかに関する情報（領域に関連付けられたリストに関するさらなる情報を表示するバブルをポップアップさせるための命令等）も含むことができる。別の態様では、上位リスト情報は、クライアントコンピューターがサーバー１１０上のリスト又はインターネット全般に関するさらなる情報を見つけることができる場所を特定する情報を含むことができる。さらに別の態様では、この情報は、異なるファイル（たとえばリストに関する比較的少ない情報を特定する第１のＪＳＯＮファイル、及び次に情報のための準備ができたことを示すクライアントコンピューターに応答した第２のＪＳＯＮファイル）において別個の時点に送信することができる。
【００７５】
サーバー１１０は、ネットワーク２９５を介してクライアントコンピューター１５０に上位リストのテキストベースの情報を送信する。
【００７６】
サーバー１１０は、ユーザーに示されるロケーションエリアに基づいてマップデータベース２７０からタイル２７２をさらに選択し送信する。サーバー１１０は、ズームレベルに基づいて、ロケーションエリアの緯度／経度境界に合致することを示す緯度／経度位置を有するすべてのタイルを読み出すことができる。サーバー１１０は、ユーザーがマップを少しパンした場合に新たなタイルが要求されることを防ぐように近隣のタイルも送信することができる。
【００７７】
クライアントコンピューターが、上位リストを超えるリストを示すべきであるというインジケーションを受信した場合、クライアントコンピューターはこれらのリストを表示する準備をする。たとえば、サーバー１１０によって送信されるがクライアントコンピュータープロセッサ１５０によって実行されるＪａｖａｓｃｒｉｐｔ命令に従って、クライアントはトリガーのためにＪＳＯＮファイルをパースする。
【００７８】
トリガーが、他の結果が表示されるべきであることを示す場合、クライアントコンピューターは、マップレイヤーと、上位リストのためのアイコンを表示するのに用いられるレイヤーとの間に表示されるグラフィックレイヤーのインスタンスを生成する。クライアントコンピューターは、他の結果を表す画像の要求も作成する。
【００７９】
クライアントコンピューターが上位リストを超える他のリストを表示することが確定されると、サーバーは、ユーザーのクエリ（「pizza」等）に応じかつ密度を反映するリストを選択する。
【００８０】
サーバー１１０は、密度に比例してリストを選択するために、マップエリアの異なる地理的エリア内のリストを比較する。たとえば、サーバーは領域セルを用いてマップエリアを解析し、マップエリアを考慮して適切な領域セルのレベルを選択することができる。サーバーは、マップがズームインされたときにより小さな領域セルが用いられるように、したがってズームを変更することによって表示のために選択されるリストを変更することができるように適切な領域セルレベルを選択する根拠としてズームレベルを用いることができる。
【００８１】
最も高い密度を有する地理的エリアを用いて、該地理的エリアの全てにおいて示されることになるリストの量を求めることができる。たとえば、サーバーは、マップエリアをカバーする領域セル毎に各セル内の応答リストの数を求めることができる。図１０は、９個のセルに分割されたマップ１０１０（破線によって表される）を示している。ここで、各セル内の数はセル内の応答リストの数を示している。たとえば、マップの北西部は３２個の応答リストを含むのに対し、マップの中央は３００個の応答リストを含む。
【００８２】
次に、最も多数のリストを有する地理的エリアが特定される。領域セルのそれぞれが比較的同じ大きさである場合、最も多数のリストを有する領域セルは密度の最も高いセルとなる。このため、図１０に示すように、中央のタイル１０２０は、マップの別のセルよりも多くのリスト（３００個）を有するので、最も高い密度を有するとして特定される。
【００８３】
最も混雑した地理的エリアに基づいて、次にエリア毎に閾値が計算される。ここで、閾値はそのエリア内にいくつのリストが示されるかを確定するのに用いられる。たとえば、そのような閾値を計算する１つの可能な式は、
ｄｅｎｓｉｔｙ＿ｔｈｒｅｓｈｏｌｄ（Ｃ）＝ｄ＊（１＋ｄｅｎｓｉｔｙ（Ｃ）／ｍａｘ＿ｄｅｎｓｉｔｙ）
であり、ここで、
Ｃは特定の領域セルを指し、
ｄｅｎｓｉｔｙ＿ｔｈｒｅｓｈｏｌｄ（Ｃ）はセルＣ内に示されることになるリストの最大数であり、
ｄは任意のセル内に示すことができるリストの最大数を設定するのに用いられる定数（自動的に、又は視覚実験に基づいて設定することができる）、
ｄｅｎｓｉｔｙ（ｃ）はセルＣ内に含まれるリストの数であり、
ｍａｘ＿ｄｅｎｓｉｔｙはほとんどのリストを有するセル内に含まれるリストの数である。
【００８４】
上記の式によって、高密度エリアが低密度エリアよりも高い閾値を有することになる。最大値は「ｄ」の２倍となるので、これは最も混雑したセルであっても密度が高くなりすぎないことを保証するのに役立つ。
【００８５】
他の式を用いて密度閾値を計算することもできる。たとえば、上記の式は、
ｄｅｎｓｉｔｙ＿ｔｈｒｅｓｈｏｌｄ（Ｃ）＝ｄ＊（１＋ａ＊ｄｅｎｓｉｔｙ（Ｃ）／ｍａｘ＿ｄｅｎｓｉｔｙ）
における「ａ」等、最高閾値と最低閾値との間の範囲を変更するスキュー乗算子を含むことができる。範囲を増大させることによって、特に密な領域が他のエリアに比べてさらに密に見えるようにすることもできる。
【００８６】
地理的エリアのための密度閾値が確定されると、該閾値は地理的エリアに関連付けられたリストに適用される。
【００８７】
密度閾値を適用する１つの方法は、セルから、密度閾値に等しいか又は密度閾値に比例する複数のリストを選択することを含む。たとえば、２つのセルの密度閾値がそれぞれ２０及び３０であった場合、第１のセルからのスコアが最も高い２０個のリストを表示用に選択することができ、第２のセルからのスコアが最も高い３０個のリストを表示用に選択することができる。
【００８８】
代替的に、データベースは、スコア情報を解析し、密度を求める目的で１度クエリすることができ、次に再度、実際のリストを得るために、クエリの一部としてスコア閾値を用いてクエリすることができる。
【００８９】
それに関して、ヒストグラムはマップエリアに関連付けられた領域セル毎に作成することができる。ヒストグラムはそのセル内に含まれるリストで埋められ、ヒストグラムの各帯は異なる範囲のスコアに関連付けられる。したがって、リストの最も高い可能なスコアが１０であり、最も低い可能なスコアが１であり、かつ特定のセル内にスコアＡ＝４、Ｂ＝６、Ｃ＝７、Ｄ＝７、Ｅ＝８、Ｆ＝９、Ｇ＝９を有する７つのリスト「Ａ」〜「Ｇ」は存在する場合、そのセルのヒストグラムは、各可能なスコアを表す１０個の帯を有し得る。４番目の帯は各可能なスコアを表す１０個の帯を有する可能性がある。４番目の帯はリストＡを含み、６番目の帯はリストＢを含み、７番目の帯はリストＣ及びＤの双方を含み、残りの帯も同様に埋められる。
【００９０】
ヒストグラムが埋められた後、サーバーはヒストグラムを最高の帯から最低の帯まで反復する。この反復は帯内のセルの数の中間結果を保持し、中間結果が密度閾値を超えるまで進行を継続する。上記のセル例を用いると、ｄｅｎｓｉｔｙ＿ｔｈｒｅｓｈｏｌｄ（Ｑ）＝５である場合、帯１０における中間結果はゼロであり、帯９における中間結果は２であり（リストＦ、Ｇ）、帯８における中間結果は３であり（Ｆ，Ｇ，Ｅ）、帯７における中間結果は５である（Ｆ，Ｇ，Ｅ，Ｃ，Ｄ）ので、サーバーはスコア７のリストで停止する。
【００９１】
セル内のリストのスコア、及びセルの密度閾値に基づいて、スコアに基づく閾値をこのようにセルに割り当てることができる。上記の例を用いると、密度閾値が５でありスコア７以上の５つのリストが存在するので、セルＱのスコア閾値は７となる。
【００９２】
次に、スコアに基づく閾値及びセルの識別情報を用いてリストを再クエリする。たとえば、元のクエリ（ロケーションなし）を再び用いてリストを引き出すが、今回は、クエリはセル及び最小スコアの双方を特定する（たとえば、「スコア９を有しかつセルＱ内にあるか、又はスコア３を有しかつセルＲ内にあるか、又はスコア９を有しセルＳ内にある「ｐｉｚｚａ」のすべてのリスト」）。これによって、マップデータベースは既に密度に関してフィルタリングされたリストの集合を返すことが可能になる。
【００９３】
上述したように、密度に基づいて検索結果を表示する１つのシステム及び方法は、１つのエリアにおけるリストを他のエリアにおけるリストと比較することを含む。エリアが重複しない場合、アーチファクトが現れ得る可能性がある。図１１〜図１３は、説明の目的で極端な例を示す。図１１に示すように、外側のセルが有するリストがわずかであり密度が低い、９個のセルが存在する。内側のセルは多くのリストを有し、密度が高い。
【００９４】
図１２は、リスト１２１０のような選択されたリストが境界１２２０等のそれらのセル境界に対してどこに現れる可能性があるかを示している。各ドットは選択されたリスト及びセル内のその位置を表している。図１２は、これらのリストがマップ上に描画されたときにどのように見えるかを示している。中心セル内のリストと他のセル内のリストとの相違に起因して、図１３に示すようにリストがマップ上に描画されるときに中央セルの境界の不明確な輪郭が見える場合がある（たとえばグリッドアーチファクト）。このため、ユーザーは領域の店がマップ１３２０の中央の正方形１３０内に群がっていると不適切に結論付ける場合がある。しかしながら、正方形形状は領域セルの位置に応じたものであり、マップの実際の地理的特徴又はその関連付けられたリストを表すものではない。
【００９５】
本システム及び本方法の１つの態様において、本システム及び本方法は密度を求めるのに用いられる地理的エリアに関連付けられた潜在的なアーチファクトを軽減するように表示されるリストを選択する。境界を曖昧にする１つの可能な方法は、平滑化プロセスを用いることである。リストは、他のセルに対する該リストのセルの密度にのみ基づくのではなく、他のセルに対する個々のリストの位置にも基づいて選択することができる。そのような平滑化プロセスが図１３のリストに適用される場合、選択されたリストは相対的密度を示し続けるが、上述した視覚アーチファクトはあまり示さない。図１４は平滑化プロセスを図１３示すリストに適用した１つの可能な結果を示している。
【００９６】
平滑化を実行する１つの技法は以下の通りである。図１５のリスト１５１０等、表示されることが検討されるリスト毎に、リストに最も近い４つのセルＣ０〜Ｃ３が特定される。
【００９７】
セルのスコア閾値が確定される。（リストが欠落していることに起因して）スコア閾値がない場合、ゼロのスコア閾値が割り当てられる。
【００９８】
セルの中心も見つけられる。リスト１５１０がこれらの中心によって形成される矩形１５２０内に位置する場合、線形補間を用いてリスト位置におけるスコア値を求めることができる。たとえば、（ｘＬ，ｙＬ）がリストの座標であり、かつ（ｘ０，ｙ０）がＣ０の座標である場合、式を以下のように導出することができる。
（１−ｕ）＊ｘ０＋ｕ＊ｘ２＝ｘＬ
（１−ｖ）＊ｙ０＋ｖ＊ｙ１＝ｙＬ
ｉｎｈ＝（１−ｖ）＊（（Ｉ−ｕ）＊ｚ０＋ｕ＊ｚ２）＋ｖ＊（（１−ｕ）＊ｚ１＋ｕ＊ｚ３）
ここで、０≦ｕ＜１及び０≦ｖ＜１であり、ｉｎｈはスコア閾値である。
【００９９】
第３の式はスコア閾値ｚ０，．．，ｚ３を、それらがセルの中心に割り当てられているかのように用いる。上記の３つのパラメーター式は、４つの中心の矩形内の双曲放物面シート（サドル）を確定するはずである。
【０１００】
このプロセスがすべての適用可能なセルに拡張される場合、セルによってカバーされるエリアの任意の点におけるスコア閾値を提供する連続平面が得られる。最初の２つの式から、ｕ及びｖを取得することができる。
ｕ＝（ｘＬ−ｘ０）／（ｘ２−ｘ０）
ｖ＝（ｙＬ−ｙ０）／（ｙｌ−ｙ０）
【０１０１】
ｉｎｈの値は、ｕ及びｖの値を上記の第３の式にプラグインするによって取得することができる。最終的には、リストのスコアがｉｎｈよりも低い場合、リストはフィルタリング除去される。
【０１０２】
これらの平滑化されたスコア閾値を用いて（上述したように）データベースをクエリすることができる。それに応答して、サーバーは応答リストを選択するが、今回は選択されたリストは平滑化なしのときよりも現れるセルアーチファクトが少なくなる。
【０１０３】
上述した技法は、線形平滑化の形式を用いてリストをフィルタリングし、セルアーチファクトを除去する。しかしながら、本システム及び本方法はいかなる特定のプロセスにも限定されない。たとえば、３次平滑化を用いることもできる。３次平滑化は、中心よりも境界においてスコア閾値をより変更する傾向があり、このため、近傍のセルの密度が比較的大きく異なる場合、より視覚的に満足のいく結果を提供する傾向にある。
【０１０４】
密度等に基づいて他のリストが選択されると、サーバーはロケーションに対する他のリストの画像を作成する。たとえば、サーバーは図１６に示すようなビットマップ画像１６１０を作成することができる。１つの態様では、画像はユーザーに表示されるマップエリアに等しくなるようにサイズ調整される。サーバーは黒いドット１６２０等の、マップの選択されたリストのインジケーションを描画する。
【０１０５】
ドットの位置はリストの地理的ロケーションに対応する。このため、他のリストに対するドット１６２０の位置は他のリストの緯度／経度位置に対するリストの緯度／経度位置に比例する。
【０１０６】
画像の背景は、領域１６３０によって示される背景等のように透明とすることができる。たとえば、画像がＰＮＧ形式で作成された場合、他のリストのアイコン（又は他のインジケーション）によって占有されていないピクセルは透明であるとしてフラグ付けされる。
【０１０７】
別の態様では、図１６に示すオーバーレイ画像はユーザーに送信されたマップタイルに合致する区画に分割することができる。
【０１０８】
次に、他のリストのオーバーレイ画像１６１０がサーバーによってクライアントコンピューターに送信される。本システム及び本方法の１つの態様において、他のリストのインジケーションがサーバーによって既に選択され描画されている場合、クライアントコンピューターのプロセッサはリスト及び該リストの位置に関して計算を一切行う必要がない。本システム及び本方法は、スコア閾値をクライアントコンピューターに送信することもできる。
【０１０９】
図１７に示すように、クライアントコンピューターはマップ及び画像オーバーレイをウェブブラウザーにおいて組み立てる。オーバーレイは、他のリストのインジケーション１７１０がマップの上のそれぞれの位置に現れるように、マップの上部のレイヤーに描画される。オーバーレイレイヤーの背景は透明であるので、マップタイルは、領域１７２０内の湖等、インジケーションがないエリアを透かして見せることになる。
【０１１０】
クライアントコンピューターは、マップの上部のレイヤー上のアイコン１７３０として上位リストを描画し、他のリストを描画する。クライアントコンピューターはマップに隣接する上位リストのテキスト説明１７４０をさらに提供する。上述したように、上位リストのアイコン１７３０は、ユーザー動作に応答して動作を実行し、テキスト説明に対して実行されたユーザー動作にも応答する。
【０１１１】
それに関して、図１７は、
（ａ）ユーザーのクエリ及び他の要因に基づいてユーザーが関心がある可能性が最も高い地理的ロケーションを有する特徴のセットを表すグラフィカルインジケーションであって、サーバーによって提供されたテキストデータをクライアントコンピューターが処理することによってアイコンが表示される、グラフィカルインジケーション、
（ｂ）ユーザーが関心がある可能性はより低いが依然としてユーザーのクエリに合致する地理的ロケーションを有する特徴の別のセットを表すグラフィカルインジケーション、
（ｃ）ユーザーの要求に応じて全ての特徴の相対的密度を表すように選択された他の特徴のグラフィカルインジケーション、
（ｄ）クライアントコンピューターが他の特徴をより簡単に表示することができるようにサーバーによって画像として予めレンダリングされるグラフィカルインジケーション、
（ｅ）特徴のうちの少なくともいくつかのテキストリスト、及び
（ｆ）サーバーによって提供されるリストに比べて、ユーザーによって選択された任意の単語を含むクエリ、
を含む組み合わせで本システム及び本方法の多岐にわたる態様を示している。
【０１１２】
本システム及び本方法の１つの態様において、クライアントコンピューターは、他のリストとのインタラクションを可能にする情報も提供される。たとえば、クライアントコンピューターのユーザーがマップ上でマウスカーソルをホバリングするとき、クライアントコンピューターはマウスカーソルの下のタイルを識別し、そのタイル（又はマウスカーソルの下の４分の１タイル等の一部分）に関連付けられた他のリストに関する情報の要求を送信することができる。それに応じて、サーバーは、リスト毎に、サーバーにおける該リストの識別番号、マップ上の該リストの位置（ピクセル単位）を特定するＪＳＯＮ形式のデータ等、タイル内の他のリストのそれぞれに関連付けられた情報を送信することができる。ユーザーがマップをクリックする場合、クライアントコンピューターはこの情報を用いてユーザーが他のリストのうちの１つをクリックしたか否かを判断し、クリックした場合、サーバーからリストに関するさらなる情報を取得し表示する。
【０１１３】
上述したように、本システム及び本方法は、サーバー及びデータベースのいかなる特定の構成にも限定されない。そうであっても、本システム及び本方法は、別個の機能を実行するデータベース及びサーバーと関連して用いたときに特に有利である。例としてのみであるが、１つのサーバーがクエリを作成し、リストを返すことができるのに対し、別のサーバーがそのクエリを解析する。それに関して、かつ上述したように、本システム及び本方法は第２のサーバーが、自身でリストを選抜し再処理するのではなく、第１のサーバーに再クエリすることが可能になる。
【０１１４】
さらに、本方法は、上述したように、サーバーとクライアントコンピューターシステムとの間で分割される必要はない。本発明の１つの態様では、サーバーは他のリストの画像をマップ上に直接組み立て、他のリストのマップ及びインジケーションを単一の合成された画像として送信することができる。
【０１１５】
上記で説明したようなユーザーが閲覧しているマップエリア及び解析されているマップエリアは同一である必要はないことも理解されよう。たとえば、本システム及び本方法は、現在ユーザーに表示されていないタイル及び地理的エリアを解析することができる。ユーザーがマップをパンしたときに、新たなクエリのセット及び解析を実行することを回避するために、そのようなタイル及び地理的エリアをクライアントコンピューターに送信することもできる。
【０１１６】
実際に、本システム及び本方法の１つの態様は、マップをパンすることによって他のリストの密度が変化しない限り特に有利である（図７及び図８に関する上記の記述を参照されたい）。
【０１１７】
上記の代替的な実施形態のほとんどは互いに矛盾するものではなく、様々な組み合わせで実施して一意の利点を達成することができる。上記で検討した特徴のこれらの変形形態及び組み合わせ、並びに他の変形形態及び組み合わせは、特許請求の範囲によって規定した本発明から逸脱することなく利用することができるので、実施形態の上述した説明は、特許請求の範囲のよって規定されるような本発明を限定するものではなく説明するものとして受け取られるべきである。
【産業上の利用可能性】
【０１１８】
本発明は、画像マッピングシステム及び方法、並びに密度分布解析及びマッピング技法を含むがそれらに限定されない幅広い産業上の利用可能性を享受する。
【図１】
0005054234.tif 000002
【図２】
0005054234.tif 000003
【図３】
0005054234.tif 000004
【図４】
0005054234.tif 000005
【図５】
0005054234.tif 000006
【図６】
0005054234.tif 000007
【図７】
0005054234.tif 000008
【図８】
0005054234.tif 000009
【図９】
0005054234.tif 000010
【図１０】
0005054234.tif 000011
【図１１】
0005054234.tif 000012
【図１２】
0005054234.tif 000013
【図１３】
0005054234.tif 000014
【図１４】
0005054234.tif 000015
【図１５】
0005054234.tif 000016
【図１６】
0005054234.tif 000017
【図１７】
0005054234.tif 000018
【図１８】
0005054234.tif 000019
【図１９】
0005054234.tif 000020
【図２０】
0005054234.tif 000021
【図２１】
0005054234.tif 000022