(57)【特許請求の範囲】
【請求項１】
データ処理装置によって実行される方法であって、
１つ以上のネットワークアクセスポイントに関連付けられた地理的セルを１つ以上含む地理的エリアの内部でのコンピュータシステムの地理的位置を表す地理的位置情報を受信することと、
前記地理的エリアを規定する情報を記憶する、コンピュータ可読記憶媒体にアクセスすることと、
前記コンピュータシステムの前記地理的位置を判定することであって、前記記憶された情報を、地理的セルを特定するために用いることを含む、判定することと、
前記特定された地理的セルに関連付けられた複数のネットワークアクセスポイントを特定することと、
前記１つ以上の地理的セルに関連付けられたネットワークアクセスポイントの合計を求めることと、
前記合計がネットワークアクセスポイントの閾値未満である場合、前記合計に追加する追加ネットワークアクセスポイントを、前記特定された地理的セルを囲む１つ以上の追加地理的セルで探索することであって、該探索することは、前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することを含むとともに、少なくとも前記閾値の前記ネットワークアクセスポイントを特定するために継続的に実行される、探索することと、
前記地理的位置情報を前記コンピュータシステムから受信することに応じて、前記特定されたネットワークアクセスポイントのリストを前記コンピュータシステムに送信することと、
を含む、方法。
【請求項２】
前記合計に追加する追加ネットワークアクセスポイントを、前記特定された地理的セルを囲む１つ以上の追加地理的セルで探索することが、さらに、
前記特定された地理的セルに隣接する前記１つ以上の地理的セル内部で特定された１つ以上のネットワークアクセスポイントから、前記合計に追加する１つ以上のネットワークアクセスポイントを決定すること
を更に含む、請求項１に記載の方法。
【請求項３】
前記特定された地理的セルに隣接する前記１つ以上の地理的セル内部で特定された前記１つ以上のネットワークアクセスポイントから、前記地理的位置からの閾値距離を満たす1つ以上のネットワークアクセスポイントを決定することを更に含む、請求項２に記載の方法。
【請求項４】
前記特定された地理的セルに隣接する前記１つ以上の地理的セル内部で特定された前記１つ以上のネットワークアクセスポイントのうち、閾値無線ネットワークサービス精度パラメータを満たすものを、前記合計に追加する１つ以上のネットワークアクセスポイントとして決定することを更に含む、請求項２に記載の方法。
【請求項５】
前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することが、前記特定された地理的セルに隣接する複数の地理的セルを同時に特定することを含み、前記特定された地理的セルが、前記複数の地理的セルの中心に位置する、請求項１に記載の方法。
【請求項６】
前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することが、
前記特定された地理的セルに隣接する第１隣接セルを特定することと、
前記第１隣接セルから開始する前記特定された地理的セルの周囲の螺旋状経路に沿って移動することによって、１つ以上の追加的な隣接地理的セルを特定することと、
を含む、請求項１に記載の方法。
【請求項７】
各地理的セルが、対応するセルによって表される、前記地理的エリアの対応する部分の地理的境界を表す、対応する地理的境界情報に関連付けられる、請求項１から６のいずれか１項に記載の方法。
【請求項８】
前記地理的エリアに含まれる前記１つ以上の地理的セルを規定する前記情報、及び前記１つ以上の地理的セルに関連づけられた複数のネットワークアクセスポイントを定める情報を、前記コンピュータ可読記憶媒体上に記憶することを更に含み、前記情報を記憶することが、
前記地理的エリアを、前記１つ以上の地理的セルへと分割することと、
前記地理的エリア内部に位置する複数のネットワークアクセスポイント、及び前記複数のネットワークアクセスポイントのそれぞれに関連付けられた地理的位置情報を受信することと、
前記複数のネットワークアクセスポイントのそれぞれに関連付けられた前記地理的位置情報に基づいて、前記複数のネットワークアクセスポイントのそれぞれが位置する、前記１つ以上の地理的セルのうちの地理的セルを決定することと、
前記決定することに応じて、前記複数のネットワークアクセスポイントのそれぞれを、対応する地理的セル内に含めることと、
を含む、請求項１から７のいずれか１項に記載の方法。
【請求項９】
前記１つ以上の地理的セルが均一な形状を有する、請求項８に記載の方法。
【請求項１０】
前記複数のネットワークアクセスポイントのそれぞれを、対応する地理的セル内に含めることが、前記複数のネットワークアクセスポイントのそれぞれに関連付けられた地理的位置情報のハッシュを生成することを含む、請求項８に記載の方法。
【請求項１１】
前記コンピュータ可読記憶媒体が、対応する各地理的セル内の前記複数のネットワークアクセスポイントのそれぞれに関連付けられた前記地理的位置情報の前記ハッシュを含む第１のハッシュテーブルと、対応する各地理的セル内の前記複数のネットワークアクセスポイントのそれぞれを表すハッシュを含む第２のハッシュテーブルとを記憶する、請求項１０に記載の方法。
【請求項１２】
前記コンピュータシステムが、モバイル機器、無線ホットスポット機器、又はラップトップコンピュータのうちの少なくとも１つである、請求項１から１１のいずれか１項に記載の方法。
【請求項１３】
前記地理的位置情報が、緯度及び経度を含む、請求項１から１２のいずれか１項に記載の方法。
【請求項１４】
命令を有するプログラムであって、前記命令は、１つ以上のデータ処理装置によって実行された際に、
１つ以上のネットワークアクセスポイントに関連付けられた地理的セルを１つ以上含む地理的エリアの内部でのコンピュータシステムの地理的位置を表す、地理的位置情報を受信することと、
前記地理的エリアを規定する情報を記憶する、コンピュータ可読記憶媒体にアクセスすることと、
前記コンピュータシステムの前記地理的位置を判定することであって、前記記憶された情報を、地理的セルを特定するために用いることを含む、判定することと、
前記特定された地理的セルに関連づけられた複数のネットワークアクセスポイントを特定することと、
前記１つ以上の地理的セルに関連付けられたネットワークアクセスポイントの合計を求めることと、
前記合計がネットワークアクセスポイントの閾値未満である場合、前記合計に追加する追加ネットワークアクセスポイントを、前記特定された地理的セルを囲む１つ以上の追加地理的セルで探索することであって、該探索することは、前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することを含むとともに、少なくとも前記閾値の前記ネットワークアクセスポイントを特定するために継続的に実行される、探索することと、
前記地理的位置情報を前記コンピュータシステムから受信することに応じて、前記特定されたネットワークアクセスポイントのリストを前記コンピュータシステムに送信することと、
を含む動作を前記１つ以上のデータ処理装置に実行させる、プログラム。
【請求項１５】
前記合計に追加する追加ネットワークアクセスポイントを、前記特定された地理的セルを囲む１つ以上の追加地理的セルで探索することが、さらに、
前記特定された地理的セルに隣接する前記１つ以上の地理的セル内部で特定された１つ以上のネットワークアクセスポイントから、前記合計に追加する１つ以上のネットワークアクセスポイントを決定すること
を更に含む、請求項１４に記載のプログラム。
【請求項１６】
前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することが、前記特定された地理的セルに隣接する複数の地理的セルを同時に特定することを含み、前記特定された地理的セルが、前記複数の地理的セルの中心に位置する、
請求項１４に記載のプログラム。
【請求項１７】
前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することが、
前記特定された地理的セルに隣接する第１隣接セルを特定することと、
前記第１隣接セルから開始する前記特定された地理的セルの周囲の螺旋状経路に沿って移動することによって、１つ以上の追加的な隣接地理的セルを特定することと、
を含む、請求項１４に記載のプログラム。
【請求項１８】
前記地理的エリアに含まれる前記１つ以上の地理的セルを規定する前記情報、及び前記１つ以上の地理的セルに関連づけられた複数のネットワークアクセスポイントを定める情報を、前記コンピュータ可読記憶媒体上に記憶することを更に含み、前記情報を記憶することが、
前記地理的エリアを、前記１つ以上の地理的セルへと分割することと、
前記地理的エリア内部に位置する複数のネットワークアクセスポイント、及び前記複数のネットワークアクセスポイントのそれぞれに関連付けられた地理的位置情報を受信することと、
前記複数のネットワークアクセスポイントのそれぞれに関連付けられた前記地理的位置情報に基づいて、前記複数のネットワークアクセスポイントのそれぞれが位置する、前記１つ以上の地理的セルのうちの地理的セルを決定することと、
前記決定することに応じて、前記複数のネットワークアクセスポイントのそれぞれを、対応する地理的セル内に含めることと、
を含む、請求項１４から１７のいずれか１項に記載のプログラム。
【請求項１９】
システムであって、
１つ以上のデータ処理装置と、
コンピュータ可読媒体であって、
１つ以上のネットワークアクセスポイントに関連付けられた地理的セルを１つ以上含む地理的エリアの内部でのコンピュータシステムの地理的位置を表す、地理的位置情報を受信することと、
前記地理的エリアを規定する情報を記憶する、コンピュータ可読記憶媒体にアクセスすることと、
前記コンピュータシステムの前記地理的位置を判定することであって、前記記憶された情報を、地理的セルを特定するために用いることを含む、判定することと、
前記特定された地理的セルに関連づけられた複数のネットワークアクセスポイントを特定することと、
前記１つ以上の地理的セルに関連付けられたネットワークアクセスポイントの合計を求めることと、
前記合計がネットワークアクセスポイントの閾値未満である場合、前記合計に追加する追加ネットワークアクセスポイントを、前記特定された地理的セルを囲む１つ以上の追加地理的セルで探索することであって、該探索することは、前記特定された地理的セルに隣接する１つ以上の地理的セルを探索することを含むとともに、少なくとも前記閾値の前記ネットワークアクセスポイントを特定するために継続的に実行される、探索することと、
前記地理的位置情報を前記コンピュータシステムから受信することに応じて、前記特定されたネットワークアクセスポイントのリストを前記コンピュータシステムに送信することと、
を含む動作を実行するための、前記１つ以上のデータ処理装置によって実行可能な命令を記憶する、コンピュータ可読媒体と、
を備える、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本特許出願の主題は、概ね、無線ネットワークに関する。
【背景技術】
【０００２】
例えば、モバイル電話、タブレットコンピュータ、ホットスポットルータ、ラップトップコンピュータなどの、モバイル機器を含むコンピュータシステムは、無線ネットワーク、例えば、Ｗｉ−Ｆｉネットワーク及びセルラーネットワークを検出して接続するように構成することができる。モバイル機器は、例えば、機器のユーザによって、特定の地理的エリア内部の複数の地理的位置に移動させることができる。無線ネットワークサービスプロバイダーは、その地理的エリア全体にわたって、モバイル機器に無線ネットワークサービスを提供するために、インフラストラクチャ（例えば、複数の無線ネットワークサービス提供構造）を設置することができる。例えば、セルラーネットワークサービスプロバイダー及びＷｉ−Ｆｉサービスプロバイダーは、その地理的エリア内部の異なる地理的位置に、セルラーネットワークタワー及びルータを、それぞれ、若しくは双方ともに設置することができる。それらの無線ネットワークサービス提供構造のうちの１つ以上により、特定の地理的位置内部のモバイル機器にサービスを提供することができる。モバイル機器が、特定の地理的位置から別の地理的位置に、例えば、隣接する地理的位置に移動される場合、モバイル機器が無線ネットワークへの接続を喪失することがないように、その特定の地理的位置内に設置された構造は、隣接する地理的位置内に設置された構造に、モバイル機器をハンドオフすることができる。
【発明の概要】
【０００３】
本明細書は、無線ネットワークアクセスポイントを見い出すことに関連する技術を記載する。
【０００４】
一般的には、本明細書で説明される主題の革新的一態様は、データ処理装置によって実行される方法として実装することができる。地理的エリア内部でのコンピュータシステムの地理的位置を説明する、地理的位置情報が受信される。コンピュータ可読記憶媒体にアクセスする。この媒体は、複数の地理的セルを画定する情報を記憶し、各セルは、その地理的エリアの一部分を表す。この媒体は、各セルに関して、１つ以上のアクセスポイントを定める情報を記憶し、各アクセスポイントは、コンピュータシステムに無線ネットワークサービスを提供する地点であり、対応するセル内部に位置している。コンピュータ可読記憶媒体から、地理的位置情報によって説明される地理的位置が内部に位置する、特定の地理的セルを特定する。この記憶媒体から、その特定の地理的セル内部に位置する１つ以上のアクセスポイントを特定する。特定された１つ以上のアクセスポイントは、地理的位置情報の受信に応じて提供される。
【０００５】
この態様及び他の態様は、以下の特徴のうちの１つ以上を含み得る。地理的エリア内部の１つ以上の隣接する地理的セルを特定することができる。１つ以上の隣接する地理的セルのそれぞれは、特定の地理的セルに隣接する。１つ以上の隣接する地理的セル内部に位置する１つ以上のアクセスポイントを特定することができる。１つ以上の隣接する地理的セル内部に位置する特定された１つ以上のアクセスポイントを、地理的位置情報の受信に応じて提供することができる。１つ以上の隣接する地理的セル内部に位置する１つ以上のアクセスポイントのそれぞれが、その地理的位置からの閾値距離を満たすことを、判定することができる。１つ以上の隣接する地理的セル内部に位置する１つ以上のアクセスポイントのそれぞれが、閾値無線ネットワークサービス精度パラメータを満たすことを、判定することができる。地理的エリア内部の１つ以上の隣接する地理的セルを特定することは、複数の地理的セルを同時に特定することを含み得るものであり、それらの複数の地理的セルの実質的に中心に、その特定のセルが位置し得る。地理的エリア内部の１つ以上の隣接する地理的セルを特定することは、特定の地理的セルに隣接する第１隣接セルを特定することと、その隣接セルから開始する、特定のセルの周囲の螺旋状経路に沿って移動することによって、１つ以上の追加的隣接セルを特定することとを含み得る。各地理的セルは、対応するセルによって表される、地理的エリアの対応する部分の地理的境界を表す、対応する地理的境界情報に関連付けることができる。複数の地理的セルを画定する情報、及び１つ以上のアクセスポイントを定める情報を、コンピュータ可読記憶媒体上に記憶することができる。それらの情報を記憶することは、地理的エリアを複数の地理的セルへと分割することと、地理的エリア内部に位置する１つ以上のアクセスポイント、及びその１つ以上のアクセスポイントのそれぞれに関連付けられた地理的位置情報を受信することと、その１つ以上のアクセスポイントのそれぞれに関連付けられた地理的位置情報に基づいて、その１つ以上のアクセスポイントのそれぞれが位置する、複数のセルのうちの地理的セルを決定することと、その決定に応じて、その１つ以上のアクセスポイントのそれぞれを、対応するセル内に含めることと、を含み得る。複数の地理的セルは、実質的に均一な形状を有し得る。１つ以上のアクセスポイントのそれぞれを対応するセル内に含めることは、１つ以上のアクセスポイントのそれぞれに関連付けられた地理的位置情報のハッシュを生成することを含み得る。コンピュータ可読記憶媒体は、対応する各セル内の１つ以上のアクセスポイントのそれぞれに関連付けられた地理的位置情報のハッシュを含む、第１のハッシュテーブルと、対応する各セル内の１つ以上のアクセスポイントのそれぞれを表すハッシュを含み得る、第２のハッシュテーブルと、を記憶することができる。地理的エリアは、地球とすることができる。コンピュータシステムは、モバイル機器、無線ホットスポット機器、又はラップトップコンピュータのうちの少なくとも１つとすることができる。地理的位置情報は、緯度及び経度を含み得る。
【０００６】
本明細書で説明される主題の別の革新的態様は、本明細書で説明される動作を実行するための、データ処理装置によって実行可能なコンピュータソフトウェア命令を記憶する、永続的コンピュータ可読媒体として実装され得る。本明細書で説明される主題の更なる革新的態様は、データ処理装置と、本明細書で説明される動作を実行するための、そのデータ処理装置によって実行可能なコンピュータソフトウェア命令を記憶する、永続的コンピュータ可読媒体とを含む、システムとして実装され得る。
【０００７】
本明細書で説明される主題の１つ以上の実装の詳細は、同様の参照番号及び呼称は、同様の要素を指示する添付図面及び以下の説明に記載される。本主題の他の特徴、態様、及び利点は、本明細書、図面、及び特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００８】
【図１】コンピュータシステムが、地理的領域内部で、無線ネットワークサービスを提供するアクセスポイントを探索する、例示的な環境を示す図。
【図２】それぞれが地理的位置を表す複数のセルへと分割された、地球の一実施例を示す図。
【図３】アクセスポイントを説明する情報を含むハッシュテーブルを記憶する、コンピュータ可読記憶装置の一実施例を示す図。
【図４Ａ】地理的エリア内のセル内部のアクセスポイントの例示的な探索を示す図。
【図４Ｂ】地理的エリア内のセル内部のアクセスポイントの例示的な探索を示す図。
【図４Ｃ】地理的エリア内のセル内部のアクセスポイントの例示的な探索を示す図。
【図４Ｄ】地理的エリア内のセル内部のアクセスポイントの例示的な探索を示す図。
【図５】無線ネットワークアクセスポイントを発見するための、例示的なプロセスの流れ図。
【発明を実施するための形態】
【０００９】
本開示は、それぞれが無線ネットワークサービスを提供し、無線ネットワークサービスを探索しているコンピュータシステムの近傍に位置する、無線アクセスポイントを見い出すための、コンピュータにより実行される方法、コンピュータ可読媒体、及びコンピュータシステムを説明する。コンピュータシステムとしては、セルラー電話、タブレットコンピュータ、ホットスポット機器、ラップトップコンピュータなどの、モバイル機器を挙げることができる。アクセスポイントとしては、セルラーネットワークタワー、Ｗｉ−Ｆｉルータ、それらの組み合わせ、又は、コンピュータシステムに無線ネットワークサービスを提供するように構成された、任意の機器を挙げることができる。一部の実装では、アクセスポイントを、コンピュータシステムの地理的位置を表す地理的位置情報（例えば、緯度／経度の座標）と、地理的エリア全域にわたって分散された複数のアクセスポイントの地理的位置を表す地理的位置情報（例えば、緯度／経度の座標）とを比較することによって、探索することができる。これらの技術は、コンシステントハッシュ法を使用するアクセスポイントを見い出すことに関連して説明されるが、それらの技術は、緯度及び経度を含む地理的位置情報に基づく、任意の空間的アクセスアプリケーションに適用可能である。
【００１０】
コンピュータシステムの近傍のアクセスポイントを見い出す前段階として、地理的エリア全域にわたって分散された複数のアクセスポイントの地理的位置を表すデータベースを生成して、コンピュータ可読記憶装置内に記憶することができる。そうするために、一部の実装では、地理的エリアを複数の地理的セル（又はグリッド）へと分割することができ、各セルは、その地理的エリアの一部分を表す。各セルは、地理的境界によって画定され得、対応する地理的位置情報（例えば、緯度／経度／高度の座標）によって特定され得る。既知の各アクセスポイントもまた、対応する地理的位置情報によって特定することができ、セルと関連付けることができる。一部の実装では、各アクセスポイントはまた、そのアクセスポイントが発する無線信号の特徴によって特定することもできる。各アクセスポイントとセルとを関連付けるために、一部の実装では、以下で説明されるように、各アクセスポイントの地理的位置を正規化して、セルに拘束することができる。そのように形成された、アクセスポイントとセルとの関連性は、１つ以上のハッシュテーブルとして、コンピュータ可読記憶装置内に記憶することができる。特定のセル、及びその特定のセル内部に位置するアクセスポイントは、ハッシュテーブル検索アルゴリズムを実施することによって特定することができる。
【００１１】
コンピュータシステムは、そのコンピュータシステムの地理的位置を表す地理的位置情報を提供することによって、近傍のアクセスポイントに対するリクエストを送信することができる。コンピュータシステムから、アクセスポイントに対するリクエストが受信されると、コンピュータ可読記憶装置内に記憶されたデータベースを検索して、そのコンピュータシステムの近傍のアクセスポイントを発見することができる。そうするために、例えば、ハッシュテーブル検索アルゴリズムを実施することによって、データベースを検索して、そのコンピュータシステムが内部に位置するセルを特定することができる。次いで、同様にセルを検索して、コンピュータシステムに無線ネットワークサービスを提供することができる、そのセル内部のアクセスポイントを特定することができる。一部の実装では、コンピュータシステムの近傍に存在するとして特定されるアクセスポイントの閾値数を指定することができる。セル内部の全てのアクセスポイントの数が、この閾値数を超える場合には、全てのアクセスポイントよりも少ない数のアクセスポイントを、コンピュータシステムの近傍に存在するとして特定することができる。あるいは、セル内部の全てのアクセスポイントの数が、閾値数よりも少ない場合には、コンピュータシステムに無線ネットワークサービスを提供することができるアクセスポイントに関して、１つ以上の他のセル、例えば、そのコンピュータシステムが内部に位置するセルに隣接するセルを、探索することができる。更には、セル内部のアクセスポイントの数が、別の閾値数よりも少ない場合には、そのセルを１つ以上の隣接セルと結合させることにより、内部のアクセスポイントの数が他の閾値数を超える、セルの部分群を形成することができる。
【００１２】
本明細書で説明される技術を実施することによって、モバイル機器の緯度／経度の座標の受信に応じて、モバイル機器に無線ネットワークサービスを提供することが可能なアクセスポイントを特定することができる。セルを表す地理的位置情報、及び各セル内部のアクセスポイントを表す地理的情報位置を正規化して、ハッシュテーブル内に記憶することにより、セル及びアクセスポイントをツリーデータ構造（例えば、四分木、Ｒ木など）内に記憶させて、アクセスポイントを探索することと比較して、アクセスポイントの探索の間にセル及びアクセスポイントを特定することができる速度を、向上させることができる。探索の速度の向上はまた、コンピュータシステムが位置するセルに隣接する、１つ以上のセル内のアクセスポイントを探索することも可能にし得る。
【００１３】
図１は、コンピュータシステム１０２が、地理的領域内部で、無線ネットワークサービスを提供するアクセスポイントを探索する、例示的な環境１００を示す。コンピュータシステム１０２、例えば、モバイル機器は、有線又は無線ネットワーク１０８、例えば、インターネット、セルラー電話ネットワークなどを介して、アクセスポイントエンジン１０６に接続される。コンピュータシステム１０２は、無線ネットワークサービスの受信、地理的位置情報を含む情報の送信などを含めた動作を実行するための、ソフトウェア、ハードウェア、ファームウェア、又はそれらの組み合わせを実装することができる。アクセスポイントエンジン１０６は、本明細書で説明される動作を実行するための、コンピュータ可読媒体１１６上に記憶されたコンピュータソフトウェア命令を実行するように構成された、データ処理装置１１４を含む、コンピュータシステムを含む。アクセスポイントエンジン１０６は、例えば、コンピュータ可読記憶装置であり得る地理的セル記憶装置１１０内に、セルを表す地理的情報を記憶することができる。更には、アクセスポイントエンジン１０６は、セル内のアクセスポイントの修正（例えば、追加、削除）を反映するように、地理的セル記憶装置１１０を定期的に更新することができる。一部の実装では、アクセスポイントエンジン１０６は、コンピュータシステムの地理的位置を追跡することが可能な地理的位置システム１０４、例えば、全地球測位システム（ＧＰＳ）衛星、長距離航法（ＬＯＲＡＮ）システムなどに接続され得る。アクセスポイントエンジン１０６は、アクセスポイント記憶装置１１２に接続され得、このアクセスポイント記憶装置１１２は、アクセスポイントの地理的位置情報を記憶するデータベースとすることができる。アクセスポイント記憶装置１１２は、アクセスポイントエンジン１０６とは別個に記憶することができ、又はアクセスポイントエンジン１０６の一部とすることもできる。
【００１４】
一部の実装では、アクセスポイントエンジン１０６は、地理的エリア内部でのコンピュータシステム１０２の地理的位置を表す、地理的位置情報（緯度、経度の座標など）を受信することができる。アクセスポイントエンジン１０６は、それぞれが地理的エリアの一部分を表す、複数の地理的セルを画定する情報を記憶し、かつ各セルに関して、対応するセル内部に位置する１つ以上のアクセスポイントを定める情報を記憶する、地理的セル記憶装置１１０にアクセスすることができる。地理的セル記憶装置１１０から、アクセスポイントエンジン１０６は、コンピュータシステム１０２から受信された地理的位置情報によって現される地理的位置が内部に位置する、特定のセルを特定することができる。また、地理的セル記憶装置１１０から、アクセスポイントエンジン１０６は、その特定の地理的セル内部に位置する１つ以上のアクセスポイントを特定することができる。アクセスポイントエンジン１０６は、コンピュータシステム１０２からの地理的位置情報の受信に応じて、特定された１つ以上のアクセスポイントを提供することができる。この方式で、モバイル機器は、近傍に存在して、そのモバイル機器に無線ネットワークサービスを提供することが可能な、１つ以上のアクセスポイントを受信することができる。
【００１５】
一部の実装では、地理的セル記憶装置１１０及びアクセスポイント記憶装置１１２は、以下で説明されるように、それぞれ、セル及びアクセスポイントを取り込むことができる。アクセスポイントを含むことが既知の地理的エリアは、複数のセルへと分割することができる。図２は、それぞれが地理的位置を表す複数のセル（例えば、第１セル２０２、第２セル２０４、第３セル２０６）へと分割された、地球の一実施例を示す。一部の実装では、複数のセルのサイズ及び形状は、必ず均一に、例えば、赤道で０．００５’×０．００５’の正方形、５０ｍ×５０ｍの正方形、１００ｍ×１００ｍの正方形とし、いずれの場所の度数でも同じサイズにすることができる。地球との関連では、セルの形状、特に極付近のセルの形状は、地球の形状を考慮するように調整することができる。そのような実装では、セル内部のアクセスポイントの密度に関わりなく、全てのセルは、実質的に等しいサイズである。例えば、特定のセルは、５つのアクセスポイント（アクセスポイント２０８、２１０、２１２、２１４、及び２１６）を含み得る一方で、別のセルは、４つのアクセスポイント（アクセスポイント２１８、２２０、２２２、及び２２４）を含み得るが、それにも関わらず、実質的に同じサイズである。
【００１６】
地理的セル記憶装置１１０は、地球上の全ての地理的位置を定める地理的位置情報（例えば、緯度、経度の座標）を記憶することができる。地理的セル記憶装置１１０は、対応するセルに関する地理的境界を表す地理的境界情報を更に含み得る。アクセスポイントエンジン１０６は、アクセスポイント記憶装置１１２から、複数のアクセスポイントに関連付けられた地理的位置情報を受信して、アクセスポイントが位置するセルを決定し、アクセスポイントとセルとの関連性を生成することができる。例えば、アクセスポイントがセル内部に存在することを判定するために、アクセスポイントエンジン１０６は、アクセスポイントの緯度、経度の座標が、セルの地理的境界の範囲内に含まれることを判定することができる。一部の実装では、アクセスポイントエンジン１０６は、セルの地理的境界の範囲内に含まれるアクセスポイントの緯度、経度の座標に基づいて、コンシステントハッシュを作り出し、アクセスポイントとセルとを関連付けることができる。アクセスポイントエンジン１０６は、地理的セル記憶装置１１０内に、アクセスポイントと、それらのアクセスポイントが内部に位置するセルとを記憶することができる。
【００１７】
図３は、アクセスポイントを表す情報を含むハッシュテーブルを記憶する、コンピュータ可読記憶装置（例えば、地理的セル記憶装置１１０）の一実施例を示す。一部の実装では、地理的セル記憶装置１１０は、第１の縦列３０４内の、アクセスポイントに関連付けられた識別子と、第２の縦列３０６内の、アクセスポイントに関連付けられた対応する値とを記憶する、第１のハッシュテーブル３０２を含む。第２のハッシュテーブル３０８内には、地理的セル記憶装置１１０は、セル位置３１０と、１つ以上の第２の縦列３１２内の、それらのグリッド位置でのアクセスポイントの対応する値とを記憶する。アクセスポイントエンジン１０６は、第１のハッシュテーブル３０２及び第２のハッシュテーブル３０８内に記憶される、地理的セル及びアクセスポイントの識別子のコンシステントハッシュを生成するための、コンシステントハッシュアルゴリズムを実行することができるハッシュ生成器３１４を含み得る。ハッシュ生成器３１４は、アクセスポイントが位置するセルに、インデックスを提供することができる。以下で説明されるように、アクセスポイントエンジン１０６は、第１のハッシュテーブル３０２及び第２のハッシュテーブル３０８の定数時間検索によって、所定のアクセスポイント又は地理的位置の近傍の、アクセスポイントを発見することができる。２つのハッシュテーブル内に、アクセスポイントと、そのアクセスポイントを含む地理的セルとのリストが記憶されているため、アクセスポイントエンジン１０６は、特定の地理的位置の近傍のアクセスポイントに対するリクエストに、応答を提供することができる。
【００１８】
図４Ａ〜４Ｄは、地理的エリア内のセル内部のアクセスポイントの、例示的な探索を示す。この例示的な探索は、特定の地理的エリア４００（例えば、カリフォルニア州）の周囲の複数のセルに関連して説明されるが、この探索は、特定の地理的エリア４００よりも小さい地理的エリア、又は大きい地理的エリア内で、実施することができる。更には、地理的エリア４００は、より少ないセル又はより多いセルへと、分割することができる。図４Ａに示すように、アクセスポイントを探索しているコンピュータシステムは、エリア４００内部に位置するセル４０２内に位置している。このコンピュータシステム、例えば、モバイル機器は、ネットワーク１０８を介して、アクセスポイントエンジン１０６に、その緯度、経度の座標を送信するように、構成することができる。
【００１９】
アクセスポイントエンジン１０６は、コンピュータシステムの地理的位置の近傍のアクセスポイントに対する、コンピュータシステムからのリクエストである、近傍のリクエストを処理することができる。このリクエストは、ハイパーテキスト転送プロトコル（ＨＴＴＰ）ＰＯＳＴリクエストとして実施することができる。近傍のリクエストを処理するために、アクセスポイントエンジン１０６は、緯度、経度の座標を受信して、例えば、それらの座標をセルのサイズで除算することによって、それらの座標を正規化し、Ｘ値（例えば、１０００）及びＹ値（例えば、２０００）を得ることができるこの正規化された値を使用して、アクセスポイントエンジン１０６は、コンピュータシステムの緯度、経度の座標が範囲内に含まれるセルとして、セル４０２を特定することができる。セル４０２が特定されると、アクセスポイントエンジン１０６は、第１のハッシュテーブル３０２及び第２のハッシュテーブル３０８に対してハッシュテーブル検索アルゴリズムを実施することにより、セル４０２内部に位置するアクセスポイントを特定することができる。
【００２０】
一部の実装では、アクセスポイントエンジン１０６は、Ｊａｖａサーブレット及び検索オブジェクトを含むように実装することができる。このサーブレットは、例えば、ｐｒｏｔｏｂｕｆリクエストの抽出、ｐｒｏｔｏｂｕｆ応答の構成、及び管理インターフェースの提供を含めた、ＨＴＴＰ関連のタスクに関与し得る。検索オブジェクトは、全てのサーブレットインスタンスによって共有することが可能なシングルトンとして実装することができ、所定の位置に近接するアクセスポイント、又は位置特定リクエストに関連して以下で説明されるように、所定のアクセスポイントに近接するアクセスポイントを発見することに関与し得る。
【００２１】
一部の実装では、コンピュータシステムからの近傍のアクセスポイントに対するリクエストに応じて、アクセスポイントエンジン１０６は、そのコンピュータシステムが位置する同じ地理的セル内部に存在する全てのアクセスポイントを、コンピュータシステムに提供することができる。更には、場合によって、アクセスポイントエンジン１０６は、近傍のセル内に存在するアクセスポイントを提供することができる。例えば、コンピュータシステムが位置する特定のセル内部のアクセスポイントの数が、閾値数を満たさない（例えば、閾値数よりも少ない）場合には、アクセスポイントエンジン１０６は、他のセル、例えば、その特定のセルに隣接するセル内の、アクセスポイントを特定することができる。アクセスポイント位置を要求するコンピュータシステムは、閾値数、例えば、１６００個のアクセスポイントを指定することができる。
【００２２】
例えば、アクセスポイントエンジン１０６は、中心セルとしてセル４０２を指定することができ、同時に、セル４０２と境界を共有するセルとして、隣接セル（例えば、図４Ｂに示すセル４０４、セル４０６、セル４０８、及びセル４１０）を特定することができる。これらの隣接セルを特定するために、アクセスポイントエンジン１０６は、円のピクセル近似と同様の技術を実施することができる。地理的セル記憶装置１１０を使用して、アクセスポイントエンジン１０６は、次いで、セル４０４、セル４０６、セル４０８、及びセル４１０のそれぞれの内部のアクセスポイントを特定し、コンピュータシステムからのリクエストに応じて、セル４０２内のアクセスポイントと共に、それらのアクセスポイントを提供することができる。５つのセル（セル４０２、セル４０４、セル４０６、セル４０８、及びセル４１０）内のアクセスポイントの数が、閾値数を満たさない場合には、アクセスポイントエンジン１０６は、探索を１つの層だけ拡張して、追加的セル（図４Ｃに示すセル４１２、セル４１４、セル４１６、セル４１８、セル４２０、セル４２２、セル４２４、及びセル４２６）を特定し、上述のアクセスポイント特定技術を繰り返すことができる。アクセスポイントエンジン１０６は、特定されたアクセスポイントの数が閾値数を満たすまで、これらの技法を繰り返すことができる。
【００２３】
図４Ｄに関連して説明される別の実施例では、アクセスポイントエンジン１０６は、螺旋状検索技術を実施することによって、追加的アクセスポイントを特定するための隣接セルを特定することができる。そうするために、アクセスポイントエンジン１０６は、セル４０２に隣接するセル、例えば、セル４０２と境界を共有するセル４０４を、最初に特定することができる。アクセスポイントエンジン１０６は、セル４０４内部のアクセスポイントを特定して、セル４０２及びセル４０４内のアクセスポイントの数が、閾値数を満たすか否かを判定することができる。閾値数が満たされない場合には、アクセスポイントエンジン１０６は、セル４０２を中心として、セル４０４から、時計回りの方向又は反時計回りの方向のいずれかで、螺旋状経路に沿って移動することにより、別のセル、例えば、セル４０６を特定し、追加的アクセスポイントを特定するための技法を繰り返すことができる。あるいは、エンジン１０６は、セル４０２から開始する螺旋状経路に沿って移動することもできる。必要に応じて、アクセスポイントエンジン１０６は、更にセル４０８を特定して、そのセル内のアクセスポイントを特定することができる。地理的セル記憶装置１１０は、アクセスポイント及びセルについての情報をハッシュテーブル内に記憶しているため、追加的セルの探索は、四分木又はＲ木のデータ構造などの、木データ構造内に記憶されたアクセスポイント及び地理的セルの探索の実施と比較して、より速く、より演算集約度が低いものであり得る、ハッシュテーブル検索によって実施することができる。例えば、ハッシュ生成器３１４は、アクセスポイントを含む各セルを特定することができる。
【００２４】
一部の実装では、アクセスポイントエンジン１０６は、アクセスポイントの閾値数が満たされるまで、周辺から同心の数のセルを追加することによって、追加的アクセスポイントを特定するための隣接セルを特定することができる。その後、アクセスポイントエンジン１０６は、周辺のアクセスポイントのうち最も適格なものを特定することができる。一部の実装では、アクセスポイントエンジン１０６は、アクセスポイントの閾値数が満たされるまで、周辺から同心の数のセルを追加し、次いで、アクセスポイントのディスク全体のうち最も適格なものを使用することができる。一部の実装では、アクセスポイントエンジン１０６は、アクセスポイントの閾値数が満たされるまで、周辺から無作為にセルを追加することができる。
【００２５】
一部の実装では、アクセスポイントエンジン１０６は、コンピュータシステムが位置するセル内に存在すると判定されたアクセスポイントを、フィルター処理することができる。例えば、セル内の各アクセスポイントに関して、アクセスポイントエンジン１０６は、そのアクセスポイントによって送信される無線信号の強度に応じて決定される、アクセスポイントの無線精度パラメータを、受信し、判定し、又は追跡することができる。無線精度パラメータが閾値を満たさない（例えば、特定のアクセスポイントの信号強度が、閾値信号強度を下回る）ことを、アクセスポイントエンジン１０６が判定する場合には、アクセスポイントエンジン１０６は、コンピュータシステムからのリクエストに応じて提供されるアクセスポイントから、その特定のアクセスポイントを除外することができる。アクセスポイントをフィルター処理するためのパラメータとして、信号強度を使用する代替案として、アクセスポイントエンジン１０６は、距離を使用してアクセスポイントをフィルター処理することができる。例えば、コンピュータシステムが、正方形のセルの中心ではなく、特定の辺縁付近に位置する場合には、対角線上で反対側の辺縁付近のアクセスポイントは、その特定の辺縁付近の、隣接セル内の別のアクセスポイントよりも、コンピュータシステムから遠く離れている可能性がある。
【００２６】
図４Ｂ及び図４Ｃに関連して説明された、アクセスポイントエンジン１０６が、複数のセルを同時に探索する技法を実施する別の実施例では、アクセスポイントエンジン１０６は、距離と信号強度とを組み合わせて、アクセスポイントを特定することができる。モバイル機器は、その地理的位置の近傍の１６００個のアクセスポイントを要求している場合がある。アクセスポイントエンジン１０６は、図４Ｂに示すセル内で１５００個のアクセスポイントを特定している場合があり、図４Ｃに示す追加的セル内で５００個のアクセスポイントを特定している場合がある。コンピュータシステムの地理的位置に最も近い１００個のセルを特定するのではなく、アクセスポイントエンジン１０６は、距離に関わりなく、最大の信号強度を有する１００個のセルを特定することができる。アクセスポイントのフィルター処理に加えて、アクセスポイントエンジン１０６は、フィルター処理されたアクセスポイントにスコアを割り当てることができ、各スコアは、フィルター処理されたアクセスポイントがコンピュータシステムに提供することが可能な無線ネットワークサービスの評価尺度を表す。
【００２７】
モバイル機器が静止しておらず、特定の方向に移動している状況では、アクセスポイントエンジン１０６は、その移動の方向に部分的に基づいて、アクセスポイントを更にフィルター処理することができる。例えば、アクセスポイントエンジン１０６は、モバイル機器がセルＡ内に存在していることを示す、緯度、経度の座標と、そのモバイル機器がセルＢ内に存在する予定であることを示す、速度ベクトルとを、モバイル機器から受信することができる。この緯度、経度の座標、及び速度ベクトルに基づいて、アクセスポイントエンジン１０６は、モバイル機器がセルＢに到達するときに、最大数のアクセスポイントを有することになるセルを決定することができる。この態様は、進行方向の頻繁な変化又は突然の変化を考慮するために、モバイル機器の速度ベクトル、特に、方向成分の、頻繁な監視を必要とし得る。
【００２８】
一部の状況では、モバイル機器の緯度、経度の座標と、モバイル機器の進行方向を指定するマップとを結合させて、セル、及びセル内のアクセスポイントを特定することができる。例えば、モバイル機器が、延伸するハイウェイ上をモバイル機器が進行していくことを示すマップを含み、アクセスポイントエンジン１０６が、その延伸するハイウェイ上にモバイル機器が留まる可能性が高いと判定する（例えば、その延伸上に出口が存在しないため）場合には、複数のセルを探索するのではなく、アクセスポイントエンジン１０６は、その延伸するハイウェイに沿って存在するセル内のアクセスポイントのみを探索することができる。
【００２９】
図５は、無線ネットワークアクセスポイントを発見するための、例示的なプロセス５００の流れ図である。５０２では、地理的位置情報が、例えば、モバイル機器から受信される。５０４では、ハッシュテーブル、例えば、地理的セル記憶装置１１０内に記憶されたハッシュテーブルにアクセスする。５０６では、モバイル機器の位置が位置する、地理的セルを特定する。５０８では、特定された地理的セル内のアクセスポイントを特定する。５１０では、最小数のセルが特定されているか否かを判定するための確認が行われる。最小数のセルが特定されていない場合には（判定分岐「いいえ」）、５１２で、隣接セルを特定する。５１４では、隣接セル内のアクセスポイントを特定する。５１０で実行された確認を繰り返す。最小数のセルが特定された後（判定分岐「はい」）、５１６で、特定されたアクセスポイントにスコアを割り当てる。５１８では、スコアによってランク付けされたアクセスポイントが、モバイル機器からの地理的位置情報の受信に応じて提供される。
【００３０】
セルを表す地理的位置情報をハッシュテーブル内に記憶させ、ハッシュテーブル検索アルゴリズムを実施することによってセルを探索するための技法が、無線ネットワークサービスを提供するアクセスポイントの探索に関連して説明されている。しかしながら、これらの技術は、地理的位置を表すセルを探索することが必要な、いずれの環境内でも実施することができる。例えば、アクセスポイントとセルとの関連性を記憶することの代わりに、又はそれに加えて、対象の場所とセルとの新たな関連性をハッシュテーブル内に記憶することができる。対象の場所に対するリクエストがコンピュータシステムから受信されると、ハッシュテーブル検索アルゴリズムを実行して、リクエストが受信されたコンピュータシステムの近傍の、対象の場所を探索することができる。
【００３１】
一部の実装では、アクセスポイントエンジン１０６は、検索リクエストを処理することができる。そのような実装では、緯度、経度の座標を送信することの代わりに、又はそれに加えて、モバイル機器は、アクセスポイントエンジン１０６に、無線信号アドレス（例えば、Ｗｉ−Ｆｉアドレス）を送信することができる。アクセスポイントエンジン１０６は、位置検索アルゴリズムを実施することにより、その無線信号アドレスを提供するアクセスポイントを特定することができる。アクセスポイントが特定されると、アクセスポイントエンジン１０６は、引き続き、上述の技術を実施することによって、特定されたアクセスポイントの近傍の、追加的アクセスポイントを特定することができる。
【００３２】
本明細書で説明される主題及び動作の実装は、本明細書で開示される構造、及びその構造的等価物を含む、デジタル電子回路機構として、又は、コンピュータソフトウェア、ファームウェア、若しくはハードウェアとして、あるいはそれらのうちの１つ以上の組み合わせとして実装することができる。本明細書で説明される主題の実装は、１つ以上のコンピュータプログラム、すなわち、データ処理装置による実行のための、又はデータ処理装置の動作を制御するための、コンピュータ記憶媒体、例えば、永続的コンピュータ可読媒体上にコード化された、コンピュータプログラム命令の１つ以上のモジュールとして、実装することができる。あるいは、又は更には、それらのプログラム命令は、人為的に生成される伝播信号上に、例えば、データ処理装置による実行のために、好適な受信装置へ送信するための情報をコード化するように生成される、機械生成の電気信号、光信号、又は電磁信号上に、コード化することができる。コンピュータ記憶媒体、例えば、コンピュータ可読媒体は、コンピュータ可読記憶装置、コンピュータ可読記憶回路基板、ランダムアクセス又はシリアルアクセスメモリアレイ若しくはメモリ素子、あるいはそれらのうちの１つ以上の組み合わせとするか、又はその中に含めることができる。更には、コンピュータ記憶媒体は、伝播信号ではないが、コンピュータ記憶媒体は、人為的に生成される伝播信号内にコード化されたコンピュータプログラム命令の、発信元又は送信先とすることができる。コンピュータ記憶媒体はまた、１つ以上の別個の、物理的及び／又は永続的構成要素若しくは媒体（例えば、複数のＣＤ、ディスク、又は他の記憶装置）とするか、又はその中に含めることもできる。
【００３３】
本明細書で説明される動作は、１つ以上のコンピュータ可読記憶装置上に記憶されるか、又は他の発信元から受信されるデータに対して、データ処理装置、例えばデータ処理装置によって実行される動作として、実施することができる。用語「データ処理装置」は、例として、プログラマブルプロセッサ、コンピュータ、システムオンチップ、又は上述のうちの複数のもの、若しくは組み合わせを含めた、データを処理するための全ての種類の装置、機器、及び機械を包含する。それらの装置としては、専用の論理回路機構、例えば、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）又はＡＳＩＣ（特定用途向け集積回路）を挙げることができる。それらの装置はまた、ハードウェアに加えて、当該のコンピュータプログラム用の実行環境を作り出すコード、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、クロスプラットフォーム実行時環境、仮想マシン、又はそれらのうちの１つ以上の組み合わせを構成する、コードを含むこともできる。これらの装置及び実行環境は、ウェブサービス、分散コンピューティング、及びグリッドコンピューティングのインフラストラクチャなどの、多種多様なコンピューティングモデルのインフラストラクチャを実現することができる。
【００３４】
コンピュータプログラム（別名、プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、又はコード）は、コンパイル型言語又はインタプリタ型言語、宣言型言語又は手続き型言語を含めた、任意の形態のプログラミング言語で記述することができ、スタンドアロンプログラムとしての形態、又は、モジュール、コンポーネント、サブルーチン、オブジェクト、若しくはコンピューティング環境内での使用に好適な他のユニットとしての形態を含めた、任意の形態で展開することができる。コンピュータプログラムは、必ずしもその必要はないが、ファイルシステム内のファイルに対応することができる。プログラムは、他のプログラム又はデータ（例えば、マークアップ言語ドキュメント内に記憶される１つ以上のスクリプト）を保持するファイルの一部分内に、当該のプログラムに専用の単一のファイル内に、又は複数の調整されたファイル（例えば、１つ以上のモジュール、サブプログラム、又はコードの部分を記憶するファイル）内に記憶することができる。コンピュータプログラムは、１つのコンピュータ上で、又は１つのサイトに位置するか若しくは複数のサイトにわたって分散され、通信ネットワークを介して相互接続される、複数のコンピュータ上で実行されるように展開することができる。
【００３５】
本明細書で説明されるプロセス及び論理フローは、１つ以上のコンピュータプログラムを実行して、入力データに対して作用し、かつ出力を生成することによって動作を実行する、１つ以上のプログラマブルプロセッサによって実行することができる。これらのプロセス及び論理フローはまた、専用の論理回路機構、例えば、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）又はＡＳＩＣ（特定用途向け集積回路）によって実行することもでき、装置もまた、それらの専用の論理回路機構として実装することができる。
【００３６】
コンピュータプログラムの実行のために好適なプロセッサとしては、例として、汎用及び専用の双方のマイクロプロセッサ、並びに任意の種類のデジタルコンピュータの任意の１つ以上のプロセッサが挙げられる。一般的に、プロセッサは、読み出し専用メモリ又はランダムアクセスメモリ、若しくはその双方から、命令及びデータを受信する。コンピュータの本質的要素は、命令に従って動作を実行するためのプロセッサ、並びに、命令及びデータを記憶するための１つ以上のメモリ素子である。一般的に、コンピュータはまた、データを記憶するための１つ以上の大容量記憶装置、例えば、磁気ディスク、光磁気ディスク、又は光ディスクも含むか、あるいは、それらの大容量記憶装置に動作可能に結合されて、データの受信又はデータの転送、若しくはその双方を行う。しかしながら、コンピュータは、そのような装置を有する必要はない。更には、コンピュータは、別の装置、例えば、数例ではあるが、モバイル電話、個人用デジタル補助装置（ＰＤＡ）、モバイルオーディオプレーヤー若しくはモバイルビデオプレーヤー、ゲーム機、全地球測位システム（ＧＰＳ）受信機、又はポータブル記憶装置（例えば、ユニバーサルシリアルバス（ＵＳＢ）フラッシュドライブ）内に組み込むことができる。コンピュータプログラム命令及びデータを記憶するために好適な装置は、全ての形態の不揮発性メモリ、媒体、及びメモリ素子を含み、例としては、半導体メモリ素子（例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及びフラッシュメモリ素子）、磁気ディスク（例えば、内蔵ハードディスク又はリムーバブルディスク）、光磁気ディスク、並びにＣＤ−ＲＯＭ及びＤＶＤ−ＲＯＭディスクが挙げられる。これらのプロセッサ及びメモリは、専用の論理回路機構によって補完することができ、又は専用の論理回路機構内に組み込むこともできる。
【００３７】
ユーザとの対話を提供するために、本明細書で説明される主題の実装は、ユーザに情報を表示するためのディスプレイ装置、例えば、ＣＲＴ（陰極線管）モニター又はＬＣＤ（液晶ディスプレイ）モニターと、ユーザがコンピュータに入力を提供することができる、キーボード、及びポインティング装置、例えば、マウス若しくはトラックボールとを有する、コンピュータ上に実装することができる。他の種類の装置を使用して、ユーザとの対話を同様に提供することもできる。例えば、ユーザに提供されるフィードバックは、任意の形態の感覚フィードバック、例えば、視覚フィードバック、聴覚フィードバック、又は触覚フィードバックとすることができ、ユーザからの入力は、音響入力、音声入力、又は触覚入力を含めた、任意の形態で受信することができる。更には、コンピュータは、ユーザによって使用される装置にドキュメントを送信し、その装置からドキュメントを受信することによって、例えば、ユーザのクライアント機器上のウェブブラウザに、そのウェブブラウザから受信されたリクエストに応じて、ウェブページを送信することによって、ユーザと対話することができる。
【００３８】
本明細書で説明される主題の実装は、バックエンド構成要素、例えば、データサーバを含むコンピューティングシステム、又はミドルウェア構成要素、例えば、アプリケーションサーバを含むコンピューティングシステム、又はフロントエンド構成要素、例えば、ユーザが本明細書で説明される主題の実装と対話することができるグラフィカルユーザインターフェース若しくはウェブブラウザを有する、クライアントコンピュータを含むコンピューティングシステム、あるいは、１つ以上のそのようなバックエンド構成要素、ミドルウェア構成要素、又はフロントエンド構成要素の、任意の組み合わせを含むコンピューティングシステム内に実装することができる。これらのシステムの構成要素は、任意の形態又は媒体のデジタルデータ通信によって、例えば、通信ネットワーク、例えばネットワーク１２６によって、相互接続することができる。通信ネットワークの例としては、ローカルエリアネットワーク（「ＬＡＮ」）及び広域ネットワーク（「ＷＡＮ」）、相互ネットワーク（例えば、インターネット）、並びにピアツーピアネットワーク（例えば、アドホックピアツーピアネットワーク）が挙げられる。
【００３９】
コンピューティングシステムは、クライアント及びサーバを含み得る。一般的に、クライアント及びサーバは、互いに遠隔にあり、典型的には、通信ネットワークを通じて対話する。クライアントとサーバとの関係は、それぞれのコンピュータ上で実行され、かつ互いにクライアント／サーバ関係を有する、コンピュータプログラムによって生じる。一部の実装では、サーバは、クライアント機器に、（例えば、クライアント機器と対話するユーザにデータを表示し、ユーザからのユーザ入力を受信する目的のために）データ（例えば、ＨＴＭＬページ）を送信する。クライアント機器で生成されたデータ（例えば、ユーザ対話の結果）は、クライアント機器から、サーバで受信することができる。
【００４０】
セマンティックアブストラクションは、基礎となる基本データソースを表すセマンティックレイヤに関する用語である。セマンティック抽出は、リレーショナル型のオンライン分析処理（ＯＬＡＰ）、又は他のデータソース、若しくは２つ以上の既存のセマンティックレイヤの組み合わせに基づく、抽出のレベルとすることができる。ユニバースは、特定の形態のセマンティックアブストラクションであり、このセマンティックアブストラクションは、基礎となるデータソースを現し、次元、属性、及びその基礎となるデータソースに適用することができる測度を定義するデータモデルオブジェクトと、基礎となるデータソースへの接続、基礎となるデータソースに関する構造、及び基礎となるデータソースの態様を表すデータ基盤メタデータとを含む。データモデルオブジェクトは、基礎となるデータソースの次元を表し、次元と要素と属性との関係性を説明し、あるいは、基礎となるデータソースに基づいて計算を行うか、又は基礎となるデータソースに適用することを目的として計算を行う、セマンティックドメインの範囲内で定義されるオブジェクトである。典型的には、ユニバース内で、データモデルオブジェクトは、ユーザがクエリーを構築するか、又は他の方式でデータにアクセスする場合に、基礎となるデータソースの特定の論理を理解する必要がなく、熟知した用語法で作業をすることができるように、一般的なビジネス用語が割り当てられる。一般的なビジネス用語の例としては、顧客、雇用者、製品ライン、歳入、利益、削減、会計年度、四半期などが挙げられる。
【００４１】
本明細書は、多くの具体的な実装の詳細を含むが、これらは、いずれかの実装の範囲、又は特許請求することができるものの範囲に対する限定として解釈されるべきではなく、むしろ、特定の実装の、特定の実装に固有の特徴の説明として、解釈されるべきである。別個の実装との関連で本明細書で説明される特定の特徴はまた、単一の実装内に組み合わせて実装することもできる。反対に、単一の実装との関連で説明される様々な特徴もまた、別個に、又は任意の好適な部分的組み合わせで、複数の実装内に実装することができる。更には、特徴が、特定の組み合わせで作用するものとして上述されている場合があり、更に当初からそのように特許請求されている場合もあるが、場合によっては、特許請求される組み合わせからの１つ以上の特徴を、その組み合わせから削除することができ、特許請求される組み合わせは、部分的組み合わせ、又は部分的組み合わせの変形形態を目的とすることができる。
【００４２】
同様に、図面では特定の順序で動作が示されるが、このことは、望ましい結果を達成するために、図示の特定の順序で、若しくは逐次的な順序で、そのような動作を実行すること、又は、図示の全ての動作を実行することを要求するものとして、理解されるべきではない。特定の状況では、多重タスク処理及び並列処理が有利な場合がある。更には、上述の実装での様々なシステム構成要素の分離は、そのような分離を全ての実装で要求するものとして理解されるべきではなく、説明されるプログラム構成要素及びシステムは、全般的に、単一のソフトウェア製品内に一体に統合するか、又は複数のソフトウェア製品へとパッケージ化することができる点を理解するべきである。
【００４３】
それゆえ、本主題の特定の実装が説明されている。他の実装は、以下の特許請求の範囲内に含まれる。場合によっては、特許請求の範囲内に記載される動作を異なる順序で実行しても、依然として望ましい結果を達成することができる。更には、添付図面に示されるプロセスは、望ましい結果を達成するために、図示の特定の順序、又は逐次的な順序を必ずしも必要とするものではない。特定の実装では、多重タスク処理及び並列処理が有利な場合がある。
【図１】
0005925338.tif 000002
【図２】
0005925338.tif 000003
【図３】
0005925338.tif 000004
【図４Ａ】
0005925338.tif 000005
【図４Ｂ】
0005925338.tif 000006
【図４Ｃ】
0005925338.tif 000007
【図４Ｄ】
0005925338.tif 000008
【図５】
0005925338.tif 000009