地表上の移動体の地理的位置に関する情報を収集し、使用するための技術
地表上の移動体の位置を示す情報を取得、伝達、保存、処理、配布、使用するための方法と装置。より詳細には、移動体の現在位置の緯度、経度と高度が測定され、その位置のデータが補助情報と共に中央基地局に定期的に伝達され、サーバー内にデータを永続的に保存する。これによって、このように保存されたデータは移動体の移動に関する情報を得るために各種のコンピュータアプリケーションによって使用するために移動体の過去および現在の位置について利用可能になる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的に、地表上の移動体の位置を示す情報を取得、伝達、保存、処理、配布、使用するための方法と装置に関するものである。より詳細には、移動体の現在位置の緯度、経度と高度を採取または獲得し、そのデータと補助情報をサーバー内にデータを永続的に保存するために中央基地局に定期的に伝達する技術に関するものであり、アプリケーション・プログラマー・インターフェイスが各種のコンピュータアプリケーションによって使用するために移動体の過去および現在の位置について情報を利用可能にする。
【背景技術】
【０００２】
発明の背景
所与の時間における地表上の移動体（例えば、人、車、ペット）の位置の追跡は数多くの、周知の理由のうちのいずれか一つから所望される。この必要を満たすために数多くの技術が開発された。おそらく、もっともよく知られている技術のうちの二つは、全地球測位システム（ＧＰＳ）とセルラー無線通信網の一部である移動電話に関わるものである。ＧＰＳは軌道を回る衛星に搭載された発信器を使用する。追跡される移動体の上に搭載された受信器は衛星によって伝達された信号をポーリングして該衛星からのその距離を計算する。受信器は三基以上のＧＰＳ衛星からの信号を検出して三角測量を応用し、地表上のその緯度と経度を求めるか、あるいは四基以上のＧＰＳ衛星からその緯度、経度と高度を求める。セルラー無線通信網において、ネットワークによって覆われた全サービスエリアは「セル」と呼ばれる複数個の受信可能区域に分割される。移動電話のおよその位置が分かるのはそれが位置する「セル」が分かっているからである。さらに、セル内の移動体の位置を求めることによってもっと正確な測定を得るために各種の技術が開発された。
【０００３】
これらの既知の追跡技術に共通な特徴は関心のある情報が移動体の現在位置であることである。現在位置が求められ、その情報がすぐに使用されると、情報のそれ以上の必要性はもはや存在しない。結果として、位置データは相当の時間の間保存されることはない（すなわちデータの永続的保存はない）。また、移動体の位置に意味があるのは、特定の時点であるが、移動体の位置が必要になるかもしれない次の時点は典型的にはかなり後になる。したがって、移動体がどこに位置するかのデータは短い時間間隔で収集されず、またこのように継起的に収集された位置データが保存されることもない。結果として、いくつかの有益な機能に用いるために移動体の現在位置を求めるためにそれを追跡することは周知であるが、かなり長い時間にわたって移動体の位置の履歴に基づく情報が必要なとき、先行技術の方法の価値は限定されている。先行技術では短い時間間隔で収集された移動体の位置データのかかる履歴を収集（すなわち、取得し保存）しない、また各種のコンピュータアプリケーションのプログラマーによる保存されたデータの使用を容易にするためのかかる位置データの処理も行わない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の一つの目的は、地表上の移動体の位置に関するデータを取得し、かなりの時間の間かかる位置データを保存すること（すなわち、位置データの永続的保存）である。
【０００５】
本発明のもう一つの目的は、移動体のあった場所の位置データ履歴を、短い時間間隔で自動的に取得し、すべてのかかる位置データを保存することである。
【０００６】
本発明のもう一つの目的は、要求情報を提供するために保存データを使用するタスクを容易にすることを目的として短い時間間隔で採取されたかかる位置データを処理することである。
【０００７】
本発明の一つの別の目的は、位置データを取得、伝達、保存、処理、配布、使用するための新規な方法と装置を提供することである。
【０００８】
本発明のさらに別の目的は、移動体の所在と動きの履歴に関する情報を提供する、もっと迅速で、信頼性が高く、範囲が広く、もっと確実な方法を可能にすることである。
【課題を解決するための手段】
【０００９】
これらおよびその他の目的は、地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供する技術に向けられた本発明の一つの側面にしたがって達成される。複数個の位置のそれぞれに関連する位置データが取得され、複数個の位置についての位置データが移動体の移動についての情報を提供するために要求に応じてそこから選択的に検索するための永続的データベースに保存される。
【００１０】
本発明のもう一つの側面は、地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供するための技術に向けられる。複数個の位置のそれぞれに関する位置データは永続的データベース内に収集される。特定の時間および／または位置に関する要求に応じて、永続的データベース内に保存された複数個の位置についての位置データにアクセスして特定の時間および／または位置に対応する移動体の移動についての情報が提供される。
【００１１】
本発明のさらに別の側面は、複数個の位置のそれぞれについての位置データを取得して地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供するための技術に向けられる。複数個の位置についての位置データは、要求に応じて情報を提供するためにアクセス可能な複数個の関連位置クラスターに分割される。
【００１２】
本発明のさらに別の側面は、複数個の位置のそれぞれについての位置データを取得し、複数個の位置のそれぞれについての個別マップを位置データに基づいて導き出して、地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供するための技術に向けられる。移動体の移動は前記複数個の個別マップの組み合わせによって動いて表示される。
【発明を実施するための最良の形態】
【００１３】
図１は本発明を実施するために配置された構成部品の概略的ブロック図である。
図２は本発明にしたがってサーバーが実行する演算を図示するフローチャートである。
図３は図２に示したＬＯＧＩＮ演算の詳細を示している。
図４は図２に示したＬＯＧＯＵＴ演算の詳細を示している。
図５Ａ―５Ｃは図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示している。
図６は図２に示したＤＩＳＴＡＮＣＥ演算の詳細を示している。
図７Ａ−７Ｃは図２に示したＨＩＳＴＯＲＹ演算の詳細を示している。
図８Ａ−８Ｂは図２に示したＭＡＰ演算の詳細を示している。
図９は図２に示したＡＮＩＭＡＴＩＯＮ演算の詳細を示している。
図１０は図２に示したＰＲＯＸＩＭＩＴＹ演算の詳細を示している。
図１１Ａは図２に示したＯＢＳＥＲＶＡＴＩＯＮ演算の詳細を示している。
図１１Ｂは凸閉包と境界ボックスを示している。
図１２Ａと１２Ｂは、サーバー内に保存され、地表上の移動体の移動に関連する位置情報から演繹された情報の表１から３Ｂを示している。
【００１４】
図面の詳細な説明
本書に示す本発明の説明に用いられる用語は次のように定義する：
位置：緯度／経度／高度データの組である、対応するデータポイントを有する地表に対する三次元の地理的地点。
観測：対象物に付けられた特定の携帯型装置について得られた位置の順番付け。
場所：位置の領域（単一の点、クラスター、街路アドレス、都市、凸閉包、など）。
【００１５】
本発明はサーバー・クライアント構成で組織されている。クライアントはハードウェアあるいはソフトウェアのいずれかとすることができ、また対象の場所に関する情報を提供し、対象の場所に関する情報を要求するか、あるいはその両方が可能である。サーバーは多数の対象についての場所データを同時に保存し、そのデータをサーバーからの情報を要求するクライアントからコンピュータアプリケーションによってすぐに利用できる情報に加工する。
【００１６】
図１はＧＰＳ技術を用いる本発明の一つの実施例を示している。なおここで理解しなければならないのは、本発明がＧＰＳ技術に限定されず、この特定の配置が例示に過ぎないことである。サーバー３は、一つのタイプのクライアント、すなわち対象Ａ上の携帯装置１と対象Ｂ上の携帯装置２、ならびに別のタイプのクライアント、すなわちコンピュータアプリケーションＡＰＰ１とＡＰＰ２で動作するように構成されている。第一のタイプのクライアントは、後述のごとく、対象の位置についてＡＰＩ５を介してサーバー３にデータを提供する。第二のタイプのクライアントは、同じく後述のごとく、ＡＰＩ５を介してサーバー３から対象の位置について情報を要求する。
【００１７】
ここで理解しなければならないことは、本発明に用いられる、移動体のような、クライアントの数は設計選択の問題である、ことである。二つの対象だけが示されていることは、複数個の対象の使用が可能であることを指摘しながら、本発明の説明を明瞭にするためにだけに行われたのである。以下の説明において、ただ一つの対象とそれに関連する携帯装置が詳細に説明されるが、かかる説明は全ての対象とそれらの関連する携帯装置とに当てはまるものとする。同様に、容易に理解されるだろうが、本発明に用いられる、コンピュータアプリケーションなどの、その他のタイプのクライアントの数も設計選択の問題であり、二つだけが示されているのは、複数個のかかるアプリケーションの使用が可能であることを指摘しながら、本発明の説明を明瞭にするためにだけに行われたのである。
【００１８】
図１に戻って、位置採集携帯装置（「クライアント」）を担持または密閉する対象（人、車、ペットが含まれるが、それに限定されない）が示されている。携帯装置（以下、「装置」と称する）は、例えば、車または荷物の内部におくことができるか、あるいは自転車に装着したり、人の身に付けることができる。装置は、複数個のＧＰＳ衛星７からの信号をポーリングし、地表（これには、もちろん、高層建物、高木、なども含まれる）上の装置の位置や、また推論によって、対象の位置もそこから決定するために（図示されていない）周知の回路を含んでいる。装置によって発生した位置データは特定の時点における対象の特定位置を（すなわち、緯度、経度と高度によって）識別する。本発明で用いられる時間データは（後述のごとく）ＧＰＳ衛星（およびセルタワー）によって継続的に伝達される時間情報に基づいて装置によって発生する。装置はさらに、ＧＰＳ信号を検出し、対象の位置を決定するための過程の連続を予め選択した時間間隔で自動的に引き起こすために（図示されていない）制御回路も含んでいる。このような予め選択した時間間隔も設計選択の問題であり、要求データの保存および電池の寿命に対する時間の関数としての対象の位置の解像度との兼ね合いになる。制御回路は位置データをすぐにサーバー３に伝達するか、あるいは所定の数の位置について位置データを保存し、ついでバッチ伝送の一部として全てのかかる位置のデータを伝達するように設計することができる。推奨実施態様において、装置は適切なデータベース９を備えたサーバー３に定期的間隔でバッチメッセージを無線で伝達する。このメッセージは一連の位置のデジタルエンコーディングである。
【００１９】
推奨実施態様において、携帯装置はＮｅｘｔｅｌ ｉ８８ｓまたはｉ９５ｓ移動電話であり、その中で上述の制御回路がＪ２ＭＥプログラミング環境で実装されたソフトウェアプログラムを実行している。このプログラムは対象の現在の緯度、経度と高度を計算して現在位置データを求めるためにＧＰＳ衛星をポーリングして、局所に（すなわち電話のメモリ内に）位置データを保存する。プログラムに従って、装置は、位置データと、その中に予め保存されていた、装置の全地球同定識別子（「ＧＵＩＤ」）とを通信網６を介してリモートサーバーに中継する。位置データ送信の後（またＴＣＰプロトコルを使用しているときは、例えば、サーバーがその受領を肯定応答した後に）局所保存された位置データは削除され、これらの過程が反復される。くわえて、位置計算の正確さ、対象の速度と方向、およびポーリングのときに「見えている」ＧＰＳ衛星の数などのその他いくつものパラメータの値も求められる。保存パラメータのリストは次の通りである：
ＧＵＩＤ
緯度
経度
現在観測時間
緯度／経度精度
直前観測時間
直前緯度
直前経度
セル緯度
セル経度
速度
速度不確実性
方向
高度
高度不確実性
衛星の数
支援ＧＰＳ使用の有無。
【００２０】
本発明を目的として、ＧＵＩＤ、時間、緯度、経度と高度のパラメータの使用だけに関する議論が必要である。したがって、その他のパラメータの詳細は不必要とみなされる。
【００２１】
プログラムは現在位置データを電話のメモリ内に保存し、（ラン・レングス符号化アルゴリズムを用いて）定期的に圧縮し、つぎにデータをＧＰＲＳ（汎用パケット無線サービス、詳細はｈｔｔｐ：／／ｗｗｗ．ｇｓｍｗｏｒｌｄ．ｃｏｍから入手できる）を用いる通信網６を介してサーバーに伝達する。Ｊ２ＭＥプログラムは、ユーザー（すなわち装置の所有者）がＧＰＳポーリング周波数およびサーバーへの中継頻度、プロトコルがＵＤＰであるかＴＣＰであるかを制御することを可能にするメニューを提供する。
【００２２】
サーバー３は、Ｌｉｎｕｘ（登録商標）オペレーティング・システムと、ＧＵＩＤ、時間、緯度、経度と高度を含むそれぞれの位置の属性を永続的な記憶手段に記録するＭｙＳＱＬデータベースエンジン９（ｈｔｔｐ：／／ｗｗｗ．ｍｙｓｑｌ．ｃｏｍから無料で入手できる）とを実行しているコンピュータである。複数個の位置についてのこの位置データは対象の移動を表す生データであり、かかる生データは、磁気ディスク、光ディスク、または非揮発性ＲＡＭなどの適切な永続的記憶媒体９に好適には永続的に保存される。生データは、後述のごとく、ＡＰＩ５を介してアクセスできるもっとすぐに利用可能な情報に本発明に従って変換される。
【００２３】
つぎに、ＡＰＩ５の説明を提供する。ＡＰＩは外部コンピュータアプリケーションのためにサーバー内に保存された位置データへのアクセスを可能にするインターフェイスである。該インターフェイスはＸＭＬ−ＲＰＣプロトコルを介してかかる外部コンピュータアプリケーションからの要求を処理する。サーバーはＰｅｒｌ ＲＰＣ：：ＸＭＬ：：サーバーモジュールを用いて要求を処理する。クライアントアプリケーションは、Ｐｅｒｌ ＲＰＣ：：ＸＭＬ：：クライアントモジュールなどの、任意のＸＭＬ−ＲＰＣインプリメンテーションを用いてもよい。
【００２４】
パラメータは、“Ｃｏｍｐｉｌｅｒｓ： Ｐｒｉｎｃｉｐｌｅｓ， Ｔｅｃｈｎｉｑｕｅｓ， ａｎｄ Ｔｏｏｌｓ”（ｂｙ Ａｌｆｒｅｄ Ｖ． Ａｈｏ， Ｒａｖｉ Ｓｅｔｈｉ， ａｎｄ Ｊｅｆｆｒｅｙ Ｄ． Ｕｌｌｍａｎ， Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ， １９８６）という書籍に記載の拡張Ｂａｃｋｕｓ−Ｎａｕｒ書式の、下記の定義を用いて定義される。縦の棒は代替を分離し、アステリスクは「０回以上」を意味し、プラスの符号は「１回以上」を意味する。
【００２５】
ＯＢＪＥＣＴ：：＝（ＧＵＩＤ｜ＬＯＣＡＴＩＯＮ｜ＨＵＬＬ）
ＬＯＣＡＴＩＯＮ＿ＴＹＰＥ：：＝（“ｓｔｒｅｅｔ ａｄｄｒｅｓｓ”｜“ｓｔｒｅｅｔ”｜“ｐｏｓｔａｌ ｃｏｄｅ”｜“ｃｉｔｙ”｜“ｓｔａｔｅ”｜“ｃｏｕｎｔｒｙ”｜“ｃｌｕｓｔｅｒ”｜“ｍａｒｋ”｜“ｐｏｓｉｔｉｏｎ”）
ＭＡＰ＿ＴＹＰＥ：：＝（“ｓｔｒｅｅｔ”｜“ｔｅｒｒａｉｎ”｜“ｓａｔｅｌｌｉｔｅ”）
ＰＬＯＴ＿ＴＹＰＥ：：＝（“ｐｏｉｎｔ”｜“ｔｒａｉｌ”｜“ｓｔｉｐｐｌｅ”｜“ｖｅｃｔｏｒ”）
ＧＵＩＤ：：＝ＨＥＸＤＩＧＩＴ＋
ＳＥＳＳＩＯＮ：：＝ＨＥＸＤＩＧＩＴ＋
ＬＯＣＡＴＩＯＮ：：＝（ＣＯＵＮＴＲＹ｜ＳＴＡＴＥ｜ＰＯＳＴＡＬ＿ＣＯＤＥ｜ＣＩＴＹ｜ＡＤＤＲＥＳＳ）
ＡＤＤＲＥＳＳ：：＝ＳＴＲＥＥＴ＿ＡＤＤＲＥＳＳ ［ＵＲＢＡＮＩＺＡＴＩＯＮ］ ＣＩＴＹ ＳＴＡＴＥ ［ＰＯＳＴＡＬ＿ＣＯＤＥ］ＣＯＵＮＴＲＹ
ＳＴＲＥＥＴ＿ＡＤＤＲＥＳＳ：：＝ＮＡＭＥ
ＨＵＬＬ：：＝ＰＯＳＩＴＩＯＮ＋
ＰＯＳＩＴＩＯＮ：：＝ＬＡＴＩＴＵＤＥ ＬＯＮＧＩＴＵＤＥ ＡＬＴＩＴＵＤＥ
ＬＡＴＩＴＵＤＥ：：＝［“−”］ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ［ＤＩＧＩＴ］［ＤＩＧＩＴ］［“．”ＤＩＧＩＴ＊］
ＬＯＮＧＩＴＵＤＥ：：＝［“−”］ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ［ＤＩＧＩＴ］［ＤＩＧＩＴ］［“．”ＤＩＧＩＴ＊］
ＡＬＴＩＴＵＤＥ：：＝［“−”］ＤＩＧＩＴ＊［“．”ＤＩＧＩＴ＊］
ＩＮＴＥＲＰＯＬＡＴＩＯＮ：：＝ＢＯＯＬＥＡＮ
ＳＴＲＥＡＭ：：＝ＢＯＯＬＥＡＮ
ＳＯＲＴ＿ＭＥＴＨＯＤ：：＝（“ｃｈｒｏｎｏｌｏｇｉｃａｌ”｜“ｒｅｖｅｒｓｅ＿ｃｈｒｏｎｏｌｏｇｉｃａｌ”｜“ａｓｃｅｎｄｉｎｇ”｜“ｄｅｓｃｅｎｄｉｎｇ”）
ＳＴＡＲＴ＿ＴＩＭＥ：：＝ＴＩＭＥ
ＥＮＤ＿ＴＩＭＥ：：＝ＴＩＭＥ
ＤＵＲＡＴＩＯＮ：：＝ＴＩＭＥ
ＴＩＭＥ：：＝ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ ＤＩＧＩＴ＊
ＴＩＭＥ＿ＳＴＥＰ：：＝ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ ＤＩＧＩＴ＊
ＦＲＡＭＥ＿ＲＡＴＥ：：＝ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ ＤＩＧＩＴ＊
ＣＯＵＮＴＲＹ：：＝ＮＡＭＥ
ＳＴＡＴＥ：：＝ＮＡＭＥ
ＰＯＳＴＡＬ＿ＣＯＤＥ：：＝ＮＡＭＥ
ＣＩＴＹ：：＝ＮＡＭＥ
ＰＡＳＳＰＨＲＡＳＥ：：＝ＮＡＭＥ
ＮＡＭＥ：：＝（ＬＥＴＴＥＲ｜ＤＩＧＩＴ｜“”）＋
ＩＤＥＮＴＩＦＩＥＲ：：＝（ＬＥＴＴＥＲ｜ＤＩＧＩＴ）＋
ＨＥＸＤＩＧＩＴ：：＝（ＤＩＧＩＴ｜“Ａ”｜“Ｂ”｜“Ｃ”｜“Ｄ”｜“Ｅ”｜“Ｆ”）
ＬＥＴＴＥＲ：：＝（“Ａ”｜“Ｂ”｜“Ｃ”｜“Ｄ”｜“Ｅ”｜“Ｆ”｜“Ｇ”｜“Ｈ”｜“Ｉ”|“Ｊ”｜“Ｋ”｜“Ｌ”｜“Ｍ”｜“Ｎ”｜“Ｏ”｜“Ｐ”｜“Ｑ”｜“Ｒ”｜“Ｓ”｜“Ｔ”｜“Ｕ”｜“Ｖ”｜“Ｗ”｜“Ｘ”｜“Ｙ”｜“Ｚ”｜“ａ”｜“ｂ”｜“ｃ”｜“ｄ”｜“ｅ”｜“ｆ”｜“ｇ”｜“ｈ”｜“ｉ”｜“ｊ”｜“ｋ”｜“ｌ”｜“ｍ”｜“ｎ”｜“ｏ”｜“ｐ”｜“ｑ”｜“ｒ”｜“ｓ”｜“ｔ”｜“ｕ”｜“ｖ”｜“ｗ”｜“ｘ”｜“ｙ”｜“ｚ”）
ＤＩＧＩＴ：：＝（“０”｜ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ）
ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ：：＝（“１”｜“２”｜“３”｜“４”｜“５”｜“６”｜“７”｜“８”｜“９”）
ＢＯＯＬＥＡＮ：：＝（“０”｜“１”）
【００２６】
図２は、本発明に従ってサーバー３によって実行される演算を説明するのに有益なフローチャートである。クライアントの一つ一つは要求を送り、それはステップ１０で、ＡＰＩ５を介してサーバーによって受信される。サーバーはどの要求が受信されたかの決定と適切な応答に進む。以下の議論において、演算の最初の記述はそれが使用するパラメータを括弧内に指定する。随意のパラメータは角括弧内にある。
【００２７】
クライアントがサーバー３と通信するために、ＬＯＧＩＮ要求１２｛［ＬＯＧＩＮ（ＧＵＩＤ，ＰＡＳＳＰＨＲＡＳＥ）］｝が処理される。この演算はクライアントのＧＵＩＤおよび予め割り当てられたＰＡＳＳＰＨＲＡＳＥに基づいてアプリケーション要求を取り扱う。図３に示したごとく、サーバーは、ユーザーによって入力された暗号化ＰＡＳＳＰＨＲＡＳＥを、１４によって、受信する。そのＧＵＩＤのためにサーバー内に予め保存されていたＰＡＳＳＰＨＲＡＳＥが、１６で、検索され、１８によって、受信ＰＡＳＳＰＨＲＡＳＥと比較される。それらが一致しないとき、２０で、適切なエラーメッセージが装置に返される（すなわち、伝達される）。それらが一致したとき、２２で、サーバーは現在のセッションに固有の、ＳＥＳＳＩＯＮ ＩＤと呼ばれる、コードを発生する。ＳＥＳＳＩＯＮ ＩＤはサーバー内に記憶され、後で説明するように、他のクライアント要求を認証するのにその後必要になったときに、その後のエントリのためにクライアントに知られるように、２４によって、やはりクライアントに返される。
【００２８】
サーバーが取り扱うことのできるもう一つの要求はＯＢＳＥＲＶＡＴＩＯＮ要求２６で、その詳細は図１１Ａに示されている。ＯＢＳＥＲＶＡＴＩＯＮ要求に対する応答は装置から受信した生位置データを処理する。それは、装置から受信したＳＥＳＳＩＯＮ ＩＤがサーバー内に記憶されたＳＥＳＳＩＯＮ ＩＤと一致するか否かに基づいて、２６で、ユーザーを認証することから始まる。認証に成功すると、２８で、サーバーは生データを受信し保存する。３０で、ＴＣＰプロトコルが装置からの伝達に用いられていることが判明したら、サーバーは、３２で、肯定応答を装置に返す。ＵＤＰなどの、別のプロトコルが使用されていたとき、一切の肯定応答は無用である。もちろん、認証２６に失敗したとき、３４で、適切なエラーメッセージが装置に返される。
【００２９】
上述の生位置データは、先に説明したとおり、生位置データのそれぞれのデータポイントが特定位置を（すなわち特定の時点でのその緯度、経度と高度によって）識別するようにステップ２８によって保存されるが、かなりの処理をしない限り、このデータはコンピュータアプリケーションによってすぐには利用できない。もっとすぐに利用可能な形式にするために、位置データは地表の三次元領域（例えば、街路の交差点または都市）を特定する場所情報に変換される。以下にさらに詳細に説明するごとく、ある位置データは、例えば、街路名、家屋番号、都市、州などによって指定された完全な街路アドレスに変換される。
【００３０】
サーバー３内（実際にはデータベース９内）に保存された生位置データの表からのサンプルエントリは図１２Ａの表Ｎｏ．１に示した。１６進法（１６ベース）が時間、緯度、経度と高度フィールドを除いて用いられる。ＧＵＩＤ８７Ｆ３はクライアントを一意的に同定し、一つの例において、クライアントは対象Ａによって担持された装置１とすることができる。「時間」フィールドに入力したデータは１９７０年１月１日から数えた秒数である。もちろん、他の時間指標を用いることもできる。緯度、経度および高度は自明である。表１は、ＧＵＩＤ８７Ｆ３が割り当てられた対象についての二つの観測と、ＧＵＩＤ５ＥＡ５が割り当てられた対象についての三つの観測とを示している。
【００３１】
図１１Ａのステップ３６は、ステップ２８で保存された生位置データを街路アドレスなどの場所情報に変換する。このプロセスはリバース・ジオコーディングとして知られている。リバース・ジオコーディングを実行するための推奨ソフトウェア製品はＳｐａｔｉａｌＦＸと呼ばれ、ＯｂｊｅｃｔＦＸ社から入手できる。いくつものｗｅｂサービスもリバース・ジオコーディングを実施している。保存データのサンプルエントリは図１２Ａの表２Ａと２Ｂに示されている。（印書したページの紙面の制約のため表２は図１２Ａの表２Ａと２Ｂに分離されている。表２Ｂは表２Ａのデータへの連結を示すだけのために 「ＧＵＩＤ」フィールドと「観測」フィールドの反復を含むように示されている。）「観測」フィールドは観測の配列を示す識別子である。それは時間フィールドから演繹できるが、表内にそれが明示的に含まれていることによりいくつかの共通計算、例えば、「私の車の最近１００の位置を示しなさい」などのユーザーによる要求、が容易になる。表２Ａ内のその他のフィールドは、フィールドの表題から自明である。表２Ｂ内のフィールドは以下に詳細に説明する。その結果は、コンピュータアプリケーションが対象の場所を効率的に問い合わせ、後述のごとく、最寄りの街路アドレスとしてそれを返すことを可能にするデータベース内の表である。
【００３２】
ステップ３８は３６で得られたアドレスをいくつもの逆索引に変換する。例えば、一つの逆索引は完全な街路アドレスをステップ３６がかかるアドレスに変換した全ての観測位置に変換する。これが全てのアドレスについて行われる。したがって、あるユーザーが「私が［ａｄｄｒｅｓｓ］に最後にいたのはいつか？」を知りたいとき、解答は逆索引から迅速かつ効率的に作成することができる。逆索引がなければ、サーバーはデータベース９内の全ての保存された位置データを処理しなければならないだろう。都市、郵便番号、州および国についても同様な逆索引が作られる。
【００３３】
それぞれの観測された位置についてステップ３６によってアドレスが導かれる。同様に、ステップ３６からそれぞれのアドレスについて逆索引内にエントリが作成される。しかしながら、ある観測にだけ対応するエントリは好適には一時間後に削除される。
【００３４】
ステップ４０はステップ３６によって得られたそれぞれの街路アドレスを街路アドレスの近傍を示す街路図に変換する。これはマイクロソフト社のＭａｐＰｏｉｎｔなどの製品を用いて達成される。全ての鍵となる場所（例えば、後述のごとくサーバーによって場所ＩＤを割り当てられたもの）についての街路図は永久に保持される。鍵とならない場所の街路図はメモリ内にスペースを確保するために一時間後に好適には削除される。この情報は図１２Ａの表２Ｂの「街路図」フィールド内に保存される。それがデータベース内のかかる地図が保存されるところへのパスを構成して、コンピュータアプリケーションが対象の場所の街路図を効果的に発生するのを可能にする。
【００３５】
かかる街路図は数多くの用途を有することができる。例えば、ユーザーは装置１を自分の犬に取り付けることができる。ユーザーが自分の犬がどこにいるかを知りたいと思えば、本発明は犬がどこで見つかるかを示す街路図を（後述のごとく）発生することができる。別の例において、装置１がユーザーに取り付けられているとき、ユーザーが他の人に電子的に送信することができる街路図を発生するために本発明を用いてどこであれ自分が現在いる場所への指示を誰にでも与えることができる。
【００３６】
ステップ４０はさらに、ステップ２８によって保存された生位置データを衛星地図に変換する。これはＫｅｙｈｏｌｅ社からのＥａｒｔｈＶｉｅｗｅｒなどの製品を用いて達成される。この情報は図１２Ａ内の表２Ｂの「衛星図」フィールド内に保存される。これはかかる地図が保存されるところへのパスを構成して、コンピュータアプリケーションが対象の場所の衛星地図を効率的に発生することを可能にする。例えば、ユーザーが興味のある区域がどのように見えるかの「俯瞰」観測を得たいと思うとき、衛星地図を発生するために本発明を使用することができるだろう。街路図はどこで左右に曲がるかについて二次元支援を提供することができる、しかし衛星地図は三次元であり、例えば、関心のある区域がどのように見えるか、その周囲の建物はどのように見えるか、また道路の広さはどのくらいか、についてはるかに詳細に見せることができる。
【００３７】
ＡＮＩＭＡＴＩＯＮ要求２３０に応じて、本発明は「動画」街路図、地形図および／または衛星地図を発生することもできるが、これはビデオで、対象の動きを、それぞれ、街路、地形および／または衛星地図上に重ねることによって対象の動きを見せる。
【００３８】
ステップ４０はさらに、ステップ２８によって保存された生位置データを地形図に変換する。これはＭａｐｔｅｃｈ社からのＭａｐＳｅｒｖｅｒなどの製品を用いて達成される。この情報は図１２Ａの表２Ｂの「地形図」フィールド内に保存される。それはかかる地図が保存されたところへのパスを構成して、コンピュータアプリケーションが対象の場所の地形図を効果的に発生するのを可能にする。例えば、ユーザーが山で遭難したとき、本発明を用いて地形図を発生し、それを移動電話で救助者に向けることができるだろう。地形図は地勢の特徴を示して手掛かりを提供するが、これは緯度、経度と高度だけではできないことである。
【００３９】
ステップ４２はステップ２８によって保存された生位置データをクラスター化された位置に変換する。全ての位置特定技術には、ＧＰＳをはじめとして、固有の不正確さが在るので、位置測定は対象の真の位置の周囲で変動することが多い。さらに、意味のある場所（街路アドレスなど）は明確な境界が示されないことが多い。これらの問題を解決するために、また重要区域を決定するために、近隣位置が一緒にまとめられ、それぞれ、単一の地理的場所として処理される。一緒にまとめるべき位置を識別する技術はクラスター化と呼ばれ、本発明はＩＳＯＤＡＴＡクラスター化アルゴリズムを用いてこれを達成する。このアルゴリズムはＴｈｅｒｒｉｅｎ，Ｃ．Ｗ． “Ｄｅｃｉｓｉｏｎ， Ｅｓｔｉｍａｔｉｏｎ ａｎｄ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ”， Ｊｏｈｎ Ｗｉｌｅｙ ＆ Ｓｏｎｓ， １９９９に開示され、そこに含まれているこのアルゴリズムの説明は、参照として本書に含めた。結果はデータベース内の（以下に詳しく述べる）表であり、アプリケーションが対象の頻繁に訪れる場所を効率的に決定するのを可能にする。クラスター化によって得られたサンプルエントリは図１２Ｂの表Ｎｏ．３に示されている。（表Ｎｏ．３は印書したページ上の紙面の制約のために図１２Ｂの表３Ａと３Ｂに分離されている。表３Ｂが「ＧＵＩＤ」フィールドと「場所ＩＤ」フィールドの反復を含むように示されているのは、ただそれが表３Ａのデータに連結されていることを示すためである。）場所ＩＤはサーバーによって次の領域に割り当てられる：クラスター、街路アドレス、都市、郵便番号、州、国および（割当て半径とともに）クライアントによって特に指定された任意の位置。
【００４０】
地球がほぼ球形であることを計算に入れるために、ＩＳＯＤＡＴＡには予備処理過程と後処理過程が要求される。緯度のそれぞれの一度は同じ距離であるが、経度はそうではない。経度の一度の地理的距離は極よりも赤道の方が大きい。例えば、北極においては、旋回するだけで経度の３６０゜を移動することができるが、赤道では、経度の３６０゜を踏破するには地球の円周の周りを旅行しなければならない。予備および後処理過程がなければ結果ははるかに不正確になるだろう、とくに対象の動きが大きな南北距離を踏破したときにはそうである。
【００４１】
したがって、予備処理過程を適用して、緯度と経度を（経度が原因であるこの非線形性の影響を受けない）ユニバーサル横メルカトル座標系に「ゆがめ」、それをＩＳＯＤＡＴＡへの入力として使用する。後処理過程ではゆがみを戻す、すなわちユニバーサル横メルカトル位置を元の緯度と経度に変換する。緯度／経度とユニバーサル横メルカトルの間の変換は直接的である。この方法についての情報はｈｔｔｐ：／／ｗｗｗ．ｕｗｇｂ．ｅｄｕ／ｄｕｔｃｈｓ／ＵｓｅｆｕｌＤａｔａ／ＵＴＭＦｏｒｍｕｌａｓ．ＨＴＭで入手可能であり、それを印刷した参照はページの終わりにある。
【００４２】
ＩＳＯＤＡＴＡは（多数のことがある）多くの位置について位置データを処理し、それらをクラスターに分割する。その結果は点の集合（そこから凸閉包が後述のごとく計算される）とセントロイドである。図１１Ａから明らかなように、クラスター化はそれぞれの新しいデータポイントについて実行される。しかしながら、これによって処理負荷が高くなるときは、クラスター化アルゴリズムは、毎時のように、選択した時間間隔でのみ実施される。
【００４３】
今説明したように、クラスター化過程４２はクラスターにまとめられた位置を決定する。凸閉包アルゴリズム４４はつぎにそのクラスターの場所を定義する点の最小数を決定する。例えば、ユーザーの家の中、および周囲に散在した５００００の観測があるとき、クラスター化は（ＩＳＯＤＡＴＡアルゴリズムを介して）これら全ての位置を一つのクラスターにまとめる。凸閉包アルゴリズムはそのクラスターの境界の位置を識別する。もっと具体的には、ステップ４４は、全ての位置が境界内またはその上に来るように、一つのクラスターに区分された位置についてステップ２８によって保存された生位置データから境界を決定する。もちろん、それぞれの異なるクラスターについて異なる境界がある可能性がある。凸閉包アルゴリズムの直感的説明は次のように提供することができる。多数の釘を無作為に板に打ち込み、つぎにゴムバンドを全ての釘の周囲に掛けると、何本かの釘はゴムバンドの内側になり、他のものはゴムバンドに接触するだろう。ゴムバンドに接触している釘が凸閉包を構成する。この項の数学的定義は「凸閉包」が対象の一集合を含む最小凸サブセットであるというものである。図１１Ｂは凸閉包を黒い円で示し、白い円は凸閉包内の位置を示している。
【００４４】
凸閉包は、いったん凸閉包がある対象について保存されたら、新しいデータポイントが到着するたびに、反復して拡大または縮小することができるという変更を加えて、参照として本書に含めたＯｒｗａｎｔ ｅｔ ａｌ．， “Ｍａｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ Ｐｅｒｌ”， Ｏ’Ｒｅｉｌｌｙ ＆ Ａｓｓｏｃｉａｔｅｓ， １９９９， ｐ．４５４に記載のＰｅｒｌのサブルーチンで、好適には発生される。図１１Ａから明らかなように、凸閉包は全ての新しいデータポイントについて実行される。しかしながら、これによって処理負荷が高くなるときは、凸閉包アルゴリズムは、毎時のように、選択した時間間隔でのみ実施される。
【００４５】
凸閉包を定義するデータポイントは図１２Ｂに示した表Ｎｏ．３Ａ内の「ポイント」フィールド内に秩序だった対（すなわち、緯度と経度）として保存される。例えば、場所ＩＤフィールド内に１６進数ＣＢ０１８によって識別されたクラスターが「ゴムバンド」の形状を定義するのに１５本の「釘」を必要とする凸閉包を有するとき、「＃ポイント」フィールドはその中に数１５を有するであろう、また「ポイント」フィールドは、それぞれ、これらの「釘」に対応する１５の秩序だった対を有するであろう。特殊な例として、表３ＡはそのＧＵＩＤとして８７Ｆ３を有する対象のための場所ＩＤとして１６進数ＣＢ０１８を挙げている。このクラスターのセントロイドは緯度４２．４４６８０３９６、経度−７１．２２５４４９５４、高度１４．１０３４８にあるものとして決定される。凸閉包アルゴリズムはこのクラスターの形状が円であると決定した（これは、一つのだけの点、すなわちセントロイドと、それにくわえて５．１０６６の平均半径が形状の定義に要求されることを示す「＃ポイント」フィールド内の「１」のエントリから明らかである）。反対に、場所ＩＤ ＣＢ９Ａ４はその凸閉包の形状を特定するために３つの位置（または点）を要求し、これらについての秩序だった対は「ポイント」フィールド内に見つかる。
【００４６】
場所ＩＤ ＣＢ０１８についてのセントロイドの位置、したがって、クラスターの場所はステップ３６の結果から得られた１５ Ｄａｌｔｏｎ Ｒｄ．， Ｂｏｓｔｏｎ， ＭＡ． ０２１４９ ＵＳＡの住所に対応する。
【００４７】
凸閉包が入手できると、ある位置がその中にあるかの判定は電子計算機的にきわめて容易である。凸閉包はこの目的のために特に設計されている。もちろん、対象が訪問した実際の場所に対応しないような仮想線によって囲まれた／定義された領域としてクラスターを表示することも可能である。
【００４８】
サーバーが取り扱うことができるもう一つの要求はＬＯＧＯＵＴ要求４６｛ｌｏｇｏｕｔ（ＳＥＳＳＩＯＮ）｝である。これはセッションを終結する要求である。図４に示したごとく、認証ステップ４８に成功した後、保存されたＳＥＳＳＩＯＮ ＩＤは、５０によって、データベース９から削除され、５２によって、適切な成功メッセージが装置に返される。サーバーがセッションのＬＯＧＯＵＴ要求を受信したとき、サーバーはクライアントのＳＥＳＳＩＯＮ ＩＤを無効にして、クライアントが再度ログインするまで他の呼び出しを禁止する。
【００４９】
サーバー３はＬＯＣＡＴＩＯＮ要求５４｛ｌｏｃａｔｉｏｎ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＬＯＣＡＴＩＯＮ＿ＴＹＰＥ， ［ＴＩＭＥ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］）｝を取り扱うこともできる。この演算は「場所」方法を介して対象の場所を決定するためにアプリケーション要求を取り扱う。クライアントは認証のためにＳＥＳＳＩＯＮ ＩＤを提供し、場所を同定する対象を指定し、所望の出力形式を特定するために場所タイプを指定する。追加として、クライアントは、場所観測の所望時間と、できる限り正確に時間に合わせる試みにおいて対象の場所をシステムが推定するべきかを指示するブール補間ビットとを指定することもできる。
【００５０】
図５Ａ―５Ｃに示したごとく、認証５６に成功すると、ステップ５８はユーザーが指定された時間における場所を要求しているかを点検する。その場合、つぎにステップ６０は位置データが正確な時間を有するかを検査する。該当する場合、つぎにステップ６２が実行される（下記参照）。該当しない場合、ステップ６４は補間が許可されたかを検査する。該当する場合、つぎにステップ６６がデータベース内に保存された二つの時間の間で補間された位置を計算する。補間がＯＦＦの場合、つぎにステップ６８が指定された時間に一番近いいずれかの保存された時間に対するいずれかの位置データを選択する。
【００５１】
ステップ５８がどんな時間も指定されていないことを明らかにしたとき、つぎにステップ７０は最後の既知の位置についての位置データを検索する。７２によって、補間がＯＮのとき、つぎにステップ７４は位置を現在時間に外挿する。７２によって、補間がＯＦＦのときは、最後の既知の位置データがそのまま単に使用される。
【００５２】
このように、ユーザーが場所を要求したとき、ステップ６２への入力はその要求に応えるために必要な位置である。ステップ６２はユーザーがこの情報を生位置データの形で所望するか否かを判定する。該当する場合、そのデータがステップ７６によって提供され、フローはつぎに、図２に示すごとく、要求判定の最初の段階に回帰する。該当しないときは、ステップ７８で場所タイプが街路アドレスであるか否かを判定する。該当する場合は、ステップ８０で、その街路アドレスがステップ３８で獲得した街路アドレス逆索引内にあるかを判定する。該当する場合は、ステップ８２でそのアドレスをユーザーに提供する。該当しないときは、８４で、リバース・ジオコーディング・プロセスを実行し、８６で、情報を将来利用するために索引内に保存し、８２で、ユーザーに返す。
【００５３】
郵便番号のためのステップ８８、９０、９２、９４と９６は、それぞれ、上述のステップ７８、８０、８２、８４と８６に対応する。同様に、対応は都市については９８、１００、１０２、１０４、１０６、州については１０８、１１０、１１２、１１４、１１６、また国については１１８、１２０、１２２、１２４と１２６に適用される。
【００５４】
１２８で、指定された場所タイプがクラスターであるときは、ステップ１３０で、指定された位置が既存のクラスター内であるか否かが判定される。該当する場合、１３２で、凸閉包が返される。該当しない場合は、１３４でクラスター化が実行され、１３６で、凸閉包アルゴリズムが実行され、１３２で結果がクライアントに返される。
【００５５】
サーバーによって扱われるもう一つの要求はＤＩＳＴＡＮＣＥ要求１４０｛ｄｉｓｔａｎｃｅ（ＳＥＳＳＩＯＮ，ＯＢＪＥＣＴ，ＯＢＪＥＣＴ）｝である。サーバーは二つの対象の間の距離を決定するためにアプリケーション要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤと二つの対象を提供する。結果は、適切なステップを使用してそれぞれの対象の１０進数緯度と経度を決定し、ついでこれらの場所のセントロイドの間の球面距離（すなわち、ほぼ地球の表面にそった距離）を計算して求められる。
【００５６】
図６に示したごとく、ステップ１４２と１４４は指定された各対象についてのそれぞれのＧＵＩＤをデータベースから検索する。ステップ１４６は第一の対象の最後の既知の位置を決定し、ステップ１４８は第二の対象について同様に決定する。ついでステップ１５０はそれらの間の球面距離を計算する。計算結果は、１５２で、クライアントに伝達される。
【００５７】
サーバーによって扱われるもう一つの要求はＨＩＳＴＯＲＹ要求１５４｛ｈｉｓｔｏｒｙ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＬＯＣＡＴＩＯＮ＿ＴＹＰＥ， ［ＴＩＭＥ＿ＳＴＥＰ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］）｝である。サーバーはＨＩＳＴＯＲＹ要求を取り扱って対象の移動の履歴を求める。クライアントはＳＥＳＳＩＯＮ ＩＤ、対象、場所タイプと、随意に、時間ステップ、補間ビット、開始時間、および終了時間を提供する。
【００５８】
時間ステップが提供されたとき、サーバーは固定間隔で観測を、例えば、その時刻の場所を返す。補間ビットが設定されているとき、所与の時間における位置を求めるために推定値が用いられる。そうでなければ、最も近い現実の観測が用いられる。結果は一連のタイムスタンプ付きの観測として返される。観測は、提供されていれば開始時間に、いなければ第一の観測で始まる。観測は、提供されていれば終了時間に、いなければ最後の観測で終わる。
【００５９】
図７Ａから７Ｃに示したごとく、認証が成功した後、ステップ１５６は対象のＧＵＩＤを決定する。つぎにステップ１６０（図７Ｂ参照）はクライアント要求が開始時間を指定しているかを検査する。該当しない場合は、ステップ１６２はその対象について記録された第一の観測を使用する。いずれにしても、つぎにステップ１６４は終了時間が提供されたか否かを検査する。そうでない場合は、ステップ１６６はその対象について記録された最後の観測を使用する。したがって、ステップ１６０−１６６の終わりに、このＨＩＳＴＯＲＹ演算の処理に要した開始および終了時間が分かる。
【００６０】
ついで、ステップ１７０（図７Ｃ参照）はクライアント要求が時間ステップを指定しているかを検査する。該当する場合、ステップ１７２で、補間がＯＮであれば（すなわち補間ビットが提供された）、ステップ１７４は時間ステップを括弧に入れる時間の間を補間する。例えば、もし時間ステップが５分であれば。しかしながら、５分間隔で位置が検出されないで、４分３２秒に一つの位置、７分１５秒にもう一つの位置あれば、ステップ１７４はかかる二つの位置についてのデータを用いて５分間隔の補間位置データを提供することになる。他方で、補間がＯＦＦのとき、ステップ１７６は４分３２秒に得られた位置データを選択することになる。なぜなら、それが５分間隔の時間に一番近いからである。
【００６１】
図７Ａに示した関数１５８は図７Ｂに示した全てのステップを表している。同様に、図７Ｃに示した全てのステップは図７Ｂの関数１６８によって表される。関数１５８と１６８の結論で、特定の位置についてのデータポイントはステップ１７４または１７６から知られ、ＨＩＳＴＯＲＹ演算に従ってその後の処理に利用できる。
【００６２】
図７Ａに示したごとく、その既知の部分が図５Ａのステップ６２に入力される。したがって、クライアント要求が街路アドレスとして提供されるべき移動についてのものであるとき、そのアドレスはステップ７８によって決定され、上述の既知の位置（すなわちステップ１７４または１７６から）に対応する街路アドレスがステップ８２によってクライアントに返されることになる。
【００６３】
ＨＩＳＴＯＲＹ演算のためのこの一連のステップは全ての位置が処理されるまで（すなわち、終了時間まで）１６９で（図７Ａ参照）、ループに従う。
【００６４】
サーバー３によって取り扱われるもう一つの要求はＭＡＰ要求１７８｛ｍａｐ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＭＡＰ＿ＴＹＰＥ， ＰＬＯＴ＿ＴＹＰＥ， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］）｝である。サーバーは対象の場所の地図を発生してこの要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤ、対象、地図タイプ、プロットタイプと、随意に、開始時間、終了時間、および補間ビットを提供する。サーバーは、表２Ｂから入手可能なときはデータベースから地図を検索し、そうでないときは地図を作製する。
【００６５】
地図タイプは「街路」、「地形」、または「衛星」タイプのいずれか一つである。プロットタイプは「点」、「軌跡」、または「ベクトル」のいずれか一つであり、発生した地図の中で対象のパスがどのように線描されるかを設定する。開始時間が提供されているとき、その時間からはじめて対象の場所が使用され、そうでなければ、システムによって記録された第一の観測になる。終了時間が提供されているとき、その時間に終わる対象の場所が使用され、そうでなければ、システムによって記録された最後の観測になる。補間ビットが設定されているとき、システムは従来の補間アルゴリズムを用いて現実の観測の間のデータを埋める。つぎに、地図イメージがクライアントに返される。
【００６６】
図８Ａと８Ｂに示すごとく、１８０での、ＧＵＩＤへの変換が続く通常の認証ステップがうまく完了したとき、上述の関数１５８のステップは、上述のごとく、開始時間と終了時間を決定する。ついで、上述の関数１６８のステップが、先に説明したように、処理される観測位置を決定する。
【００６７】
この段階で、作製される地図は「境界ボックス」を有する必要がある、なぜなら（上述のＭａｐＰｏｉｎｔなどの）地図サービスは何を地図にするかを知る必要があるからである。例えば、４３緯度、−７１経度で地図を要求するだけでは十分ではない、なぜなら地図サービスは縮尺を知らないからである：それは平方ヤードであるべきか？平方マイルであるべきか？したがって、地図サービスが用いられるとき、本発明の場合がそれだが、地図の長方形の周辺を定義する「境界ボックス」が提供されなければならない。
【００６８】
本発明は閉包内の点の全てをとおってループを作り、最小緯度、最大緯度、最小経度、および最大経度を計算して場所の凸閉包から境界ボックスを計算する。境界ボックスはこのときその左上角が最小緯度と最小経度の点にあり、その右下角が最大緯度と最大経度の点にある長方形になる。図１１Ｂにおいて、角の括弧は凸閉包に対する境界ボックスを示している。
【００６９】
図８Ａのステップ１８２は上述のアルゴリズムに従って境界ボックスを計算する。
【００７０】
境界ボックスが計算されると、ＭＡＰ演算１７８は、詳細を図８Ｂに示した、図８Ａに関数１８４として表示されているものを実行する。この図に戻る前に述べておかなければならないが、サーバーはマッピングサービスのために（街路図に一つ、地形図に一つ、衛星地図に一つの）三つのＵＲＩ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｉｄｅｎｔｉｆｉｅｒｓ）待ち行列を維持する。それぞれの待ち行列はシステムの寿命期間（すなわち、経験的に、マッピングサービスを使用する直前の試みの成功または失敗から）にわたって観測された信頼性の順に配置される。これらの待ち行列は一つ以上のマッピングサービスが利用できない事象の際に維持される。したがって、一つのマッピングサービスが応答しないとき、サーバーは次のマッピングサービスを選択するために待ち行列にアクセスする。
【００７１】
ステップ１８６はクライアント要求に指定された地図タイプが地形図であるか否かを判定する。該当する場合は、ステップ１８８は地形待ち行列から第一のＵＲＩの抽出に着手し、１９０で、地図が検索される。１９２で、検索に成功すると、情報は要求されたプロットタイプに重ねられる。どのプロットタイプを使用するかはステップ２１６、２２０と２２４で決定され、ステップ２１８、２２２と２２６の中から適切なものが地図オバーレイを実施する。１９２で、地図検索に成功しなかったとき、ステップ１９４は待ち行列の中の次のＵＲＩに移行して、ステップ１９０から１９２までを再度ループする。
【００７２】
ステップ１９６、１９８、２００、２０２と２０４は衛星地図のために実行され、それぞれ上述のステップ１８６、１８８、１９０、１９２と１９４に対応している。
【００７３】
同様に、街路図のためのステップ２０６、２０８、２１０、２１２と２１４はそれぞれ上述のステップ１８６、１８８、１９０、１９２と１９４に対応している。
【００７４】
ＵＲＩ抽出ステップ１８８、１９８と２０８はＵＲＩによって指名されたサービスからマップを抽出するユティリティを用いる。かかるユティリティの一つがｈｔｔｐ：／／ｓｅａｒｃｈ．ｃｐａｎ．ｏｒｇから入手できるＰｅｒｌ ＷＷＷ：：Ｍｅｃｈａｎｉｚｅモジュールである。システムは該ユティリティを用いてステップ１８２で計算した境界ボックスのある地図を検索し、１８５で地図はクライアントに返される。
【００７５】
もう一つの可能なクライアント要求はＡＮＩＭＡＴＩＯＮ要求２３０｛ａｎｉｍａｔｉｏｎ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＭＡＰ＿ＴＹＰＥ， ＰＬＯＴ＿ＴＹＰＥ， ＤＵＲＡＴＩＯＮ， ＦＲＡＭＥ＿ＲＡＴＥ， ［ＳＴＲＥＡＭ］， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］）｝である。この方法は対象の動きの動画を発生するためにアプリケーション要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤ、対象、地図タイプ、プロットタイプ、持続、フレームレートと、随意に、ストリームビット、開始時間、終了時間を提供する。最初の四つのパラメータについては前のステップで論じた。持続は動画が継続するべき時間の長さである。フレームレートは毎秒あたりのフレーム数である。ストリームビットはクライアントが動画全体をダウンロードしたいのか、あるいは発生の都度フレーム単位で受信したいのかを示すブーリアンである。開始時間は対象の最初の観測の時間である。終了時間は対象の最後の観測の時間である。サーバーは双線形補間を介して代表的観測の一集合を決定し、それぞれのかかる観測について地図を発生し、マップの配列を組み合わせて動画にして、ストリームビットが設定されているときは結果をクライアントにストリーミングし、その他の場合は動画全体を送信する。
【００７６】
図９に示したごとく、認証とＧＵＩＤへの変換はステップ２３２で最初に行われる。ついで、上述の関数１５８を実行して開始および終了時間を決定する。ステップ２３４はフレームレートがクライアント要求に含まれているかを判定する。含まれていないとき、このパラメータは１フレーム／秒に設定される。（フレームレートが指定されているときは）２３４からの、（指定されていないときは）２３６からのフレームレートがステップ２３８に入力され、円滑な動画のために観測が要求される時間を決定する。これは指定フレームレートパラメータの値（またはフレームレートが指定されていないときは１）をＤＵＲＡＴＩＯＮパラメータの値に分割して行われる（あるいは、ＤＵＲＡＴＩＯＮが省略されているときは、終了時間パラメータの値から開始時間パラメータの値を引いて、終了時間のデフォルトは最後に記録された観測で、開始時間のデフォルトは最初に記録された観測である）。もちろん、ＤＵＲＡＴＩＯＮは動画シーケンスの所望の時間長さである。このステップの結果は対象の位置が動画に現れるべき均等に配分された時間の配列である。
【００７７】
ステップ２４０は必要な補間を実行し、ステップ２４２は位置のそれぞれの対について境界ボックスを計算する。ついで、演繹された情報を上述の関数１８４（図８Ｂ参照）に用いて要求プロットタイプを使用する要求地図タイプで地図を作製する。
【００７８】
ステップ２４４はＡＮＩＭＡＴＩＯＮ演算の処理が位置の最後の対に到達したかを判定する。該当しない場合、この演算の処理は位置の最後の対に到達するまで関数１８４を通って反復ループする。なお、この段階で、関数１８４を通るループによって導き出された全ての地図は個別にサーバーに局所的に保存される。ステップ２４６はこれら全ての地図をＧＩＦ画像フォーマットに変換するユティリティを使用する。かかるユティリティの一つがｐｂｍｐｌｕｓであり、ｈｔｔｐ：／／ｗｗｗ．ａｃｍｅ．ｃｏｍ／ｓｏｆｔｗａｒｅ／ｐｂｍｐｌｕｓ／から入手できる。
【００７９】
つぎに、ステップ２４８は、得られた各ＧＩＦ画像を組み合わせて、フレームレートパラメータで指定されたフレームレートで動画ｇｉｆにするユティリティを使用する。かかるユティリティの一つがＭｕｌｔｉＧＩＦで、ｈｔｔｐ：／／ｗｗｗ．ｋｆｓ．ｏｒｇ／〜ａｂｗ／ｃｏｄｅ／ｍｕｌｔｉｇｉｆ．ｈｔｍｌから入手できる。結果は地図動画で、つづいてクライアントに返送されるものである。
【００８０】
動画は、ステップ２５０、２５２と２５４に基づいて、ファイルまたはストリームとしてクライアントに返される。ストリーミングは、Ｑｕｉｃｋｔｉｍｅ（登録商標）（Ａｐｐｌｅ， Ｉｎｃ．； ｈｔｔｐ：／／ｄｅｖｅｌｏｐｅｒ．ａｐｐｌｅ．ｃｏｍ／ｑｕｉｃｋｔｉｍｅ）またはＲｅａｌＶｉｄｅｏ（登録商標）（ＲｅａｌＮｅｔｗｏｒｋｓ， Ｉｎｃ．； ｈｔｔｐ：／／ｗｗｗ．ｒｅａｌ．ｃｏｍ）によって提供されているような、任意の従来のインターネット・ビデオ・ストリーミング技術を用いて達成できる。
【００８１】
図２に示された最後の要求はＰＲＯＸＩＭＩＴＹ２５６要求｛ｐｒｏｘｉｍｉｔｙ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＯＢＪＥＣＴ， ＳＯＲＴ＿ＭＥＴＨＯＤ， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］， ［ＴＩＭＥ＿ＳＴＥＰ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］）｝である。この方法は二つの対象の間の距離のリストを作成するためにアプリケーション要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤ、二つの対象、前方または後方のいずれかへの距離または時間を指定するデータの順序を提供する。クライアントは、前のステップで解釈されたような、随意の開始時間、終了時間、時間ステップ、または、補間ビットを提供してもよい。
【００８２】
図１０に示したごとく、二つの対象はステップ２７０と２７２によってそれらのそれぞれのＧＵＩＤに変換される。関数１５８は開始時間と終了時間を決定する。上述の関数１６８と同じ機能を有する関数１６８ａは、第一の対象の位置を提供する。同様に、関数１６８ｂは他方の対象の位置を提供する。この演算のためのそれぞれのステップは、第一の対象について一つの位置を、第二の対象について一つの位置を有することになる。ステップ２７４は二つの対象のこれらの位置の間の球面距離を計算する。つぎにこれがそれぞれの時間ステップについて行われる。二つの対象が静止しているとき、それらの間の距離は明らかに同じままである。一方の対象が移動し、他方が静止しているとき、両対象の間の距離は動いている対象の運動にだけ依存する。両方の対象が移動しているとき、距離はそれらの組み合わせた運動に応じて変動することになる。
【００８３】
ＰＲＯＸＩＭＩＴＹ演算の結果を表すのにいくつかの分類方法が利用可能である。両対象の間の距離は、時系列で、あるいは逆時系列で時間関数として表すことができる。また、結果は両対象の間の距離の大きさについて表し、距離を昇順または降順で表すことができる。クライアント要求がこれらの分類方法のどれにも対応しないとき、ステップ２９０でエラーメッセージが返される。
【００８４】
ステップ２７６−２７９はどの分類方法がクライアント要求に含まれたかを判定する。ステップ２８０−２８３はそれぞれ要求された分類方法を実行し、ステップ２８４−２８７は要求された情報をクライアントに返す。
【００８５】
以上のように本発明の推奨実施態様を詳細に述べたが、当業者には自明のごとくさまざまな変更を加えることができる。例えば、本発明はハードウェアもしくはソフトウェアに、または両者の組み合わせに実装しても良い。また、ＩＳＯＤＡＴＡアルゴリズムは場所決定のためのいくつもの技術のうちの一つである。ファジー・クラスター化、階層クラスター化、およびコホーネンの自己組織地図などの、他の技術も可能である。ＨＳＣＳＤおよび８０２．１１プロトコル・ファミリーのような、ＧＰＲＳの使用への代案もある。さらに、ＭｕｌｔｉＧＩＦを使う代わりに、ＧＩＦフォーマットの地図は、ｈｔｔｐ：／／ｗｗｗ．ｕｌｅａｄ．ｃｏｍから入手可能なＵｌｅａｄなどのソフトウェア製品をスクリプトしてＧＩＦ８９ａ動画に変換することができる。また、Ｃｅｌｌ ＩＤ、ＢｌｕｅｔｏｏｔｈまたはＲＦＩＤなどの、位置決め技術としてのＧＰＳの使用への代案もある。これらおよびその他の変更をもって請求の範囲に定義された本発明の範囲を逸脱できないものとする。
【図面の簡単な説明】
【００８６】
【図１】本発明を実施するために配置された構成部品の概略的ブロック図
【図２】本発明にしたがってサーバーが実行する演算を図示するフローチャート
【図３】図２に示したＬＯＧＩＮ演算の詳細を示す図
【図４】図２に示したＬＯＧＯＵＴ演算の詳細を示す図
【図５Ａ】図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示す図
【図５Ｂ】図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示す図
【図５Ｃ】図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示す図
【図６】図２に示したＤＩＳＴＡＮＣＥ演算の詳細を示す図
【図７Ａ】図２に示したＨＩＳＴＯＲＹ演算の詳細を示す図
【図７Ｂ】図２に示したＨＩＳＴＯＲＹ演算の詳細を示す図
【図７Ｃ】図２に示したＨＩＳＴＯＲＹ演算の詳細を示す図
【図８Ａ】図２に示したＭＡＰ演算の詳細を示す図
【図８Ｂ】図２に示したＭＡＰ演算の詳細を示す図
【図９】図２に示したＡＮＩＭＡＴＩＯＮ演算の詳細を示す図
【図１０】図２に示したＰＲＯＸＩＭＩＴＹ演算の詳細を示す図
【図１１Ａ】図２に示したＯＢＳＥＲＶＡＴＩＯＮ演算の詳細を示す図
【図１１Ｂ】凸閉包と境界ボックスを示す図
【図１２Ａ】地表上の移動体の移動に関連する位置情報のサンプリエントリの表１〜２Ｂを示す図
【図１２Ｂ】地表上の移動体の移動に関連する位置情報のサンプリエントリの表３Ａ〜３Ｂを示す図
【符号の説明】
【００８７】
１ 携帯装置
２ 携帯装置
３ サーバー
６ 通信網
７ ＧＰＳ衛星
９ データベース
【技術分野】
【０００１】
本発明は一般的に、地表上の移動体の位置を示す情報を取得、伝達、保存、処理、配布、使用するための方法と装置に関するものである。より詳細には、移動体の現在位置の緯度、経度と高度を採取または獲得し、そのデータと補助情報をサーバー内にデータを永続的に保存するために中央基地局に定期的に伝達する技術に関するものであり、アプリケーション・プログラマー・インターフェイスが各種のコンピュータアプリケーションによって使用するために移動体の過去および現在の位置について情報を利用可能にする。
【背景技術】
【０００２】
発明の背景
所与の時間における地表上の移動体（例えば、人、車、ペット）の位置の追跡は数多くの、周知の理由のうちのいずれか一つから所望される。この必要を満たすために数多くの技術が開発された。おそらく、もっともよく知られている技術のうちの二つは、全地球測位システム（ＧＰＳ）とセルラー無線通信網の一部である移動電話に関わるものである。ＧＰＳは軌道を回る衛星に搭載された発信器を使用する。追跡される移動体の上に搭載された受信器は衛星によって伝達された信号をポーリングして該衛星からのその距離を計算する。受信器は三基以上のＧＰＳ衛星からの信号を検出して三角測量を応用し、地表上のその緯度と経度を求めるか、あるいは四基以上のＧＰＳ衛星からその緯度、経度と高度を求める。セルラー無線通信網において、ネットワークによって覆われた全サービスエリアは「セル」と呼ばれる複数個の受信可能区域に分割される。移動電話のおよその位置が分かるのはそれが位置する「セル」が分かっているからである。さらに、セル内の移動体の位置を求めることによってもっと正確な測定を得るために各種の技術が開発された。
【０００３】
これらの既知の追跡技術に共通な特徴は関心のある情報が移動体の現在位置であることである。現在位置が求められ、その情報がすぐに使用されると、情報のそれ以上の必要性はもはや存在しない。結果として、位置データは相当の時間の間保存されることはない（すなわちデータの永続的保存はない）。また、移動体の位置に意味があるのは、特定の時点であるが、移動体の位置が必要になるかもしれない次の時点は典型的にはかなり後になる。したがって、移動体がどこに位置するかのデータは短い時間間隔で収集されず、またこのように継起的に収集された位置データが保存されることもない。結果として、いくつかの有益な機能に用いるために移動体の現在位置を求めるためにそれを追跡することは周知であるが、かなり長い時間にわたって移動体の位置の履歴に基づく情報が必要なとき、先行技術の方法の価値は限定されている。先行技術では短い時間間隔で収集された移動体の位置データのかかる履歴を収集（すなわち、取得し保存）しない、また各種のコンピュータアプリケーションのプログラマーによる保存されたデータの使用を容易にするためのかかる位置データの処理も行わない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の一つの目的は、地表上の移動体の位置に関するデータを取得し、かなりの時間の間かかる位置データを保存すること（すなわち、位置データの永続的保存）である。
【０００５】
本発明のもう一つの目的は、移動体のあった場所の位置データ履歴を、短い時間間隔で自動的に取得し、すべてのかかる位置データを保存することである。
【０００６】
本発明のもう一つの目的は、要求情報を提供するために保存データを使用するタスクを容易にすることを目的として短い時間間隔で採取されたかかる位置データを処理することである。
【０００７】
本発明の一つの別の目的は、位置データを取得、伝達、保存、処理、配布、使用するための新規な方法と装置を提供することである。
【０００８】
本発明のさらに別の目的は、移動体の所在と動きの履歴に関する情報を提供する、もっと迅速で、信頼性が高く、範囲が広く、もっと確実な方法を可能にすることである。
【課題を解決するための手段】
【０００９】
これらおよびその他の目的は、地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供する技術に向けられた本発明の一つの側面にしたがって達成される。複数個の位置のそれぞれに関連する位置データが取得され、複数個の位置についての位置データが移動体の移動についての情報を提供するために要求に応じてそこから選択的に検索するための永続的データベースに保存される。
【００１０】
本発明のもう一つの側面は、地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供するための技術に向けられる。複数個の位置のそれぞれに関する位置データは永続的データベース内に収集される。特定の時間および／または位置に関する要求に応じて、永続的データベース内に保存された複数個の位置についての位置データにアクセスして特定の時間および／または位置に対応する移動体の移動についての情報が提供される。
【００１１】
本発明のさらに別の側面は、複数個の位置のそれぞれについての位置データを取得して地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供するための技術に向けられる。複数個の位置についての位置データは、要求に応じて情報を提供するためにアクセス可能な複数個の関連位置クラスターに分割される。
【００１２】
本発明のさらに別の側面は、複数個の位置のそれぞれについての位置データを取得し、複数個の位置のそれぞれについての個別マップを位置データに基づいて導き出して、地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供するための技術に向けられる。移動体の移動は前記複数個の個別マップの組み合わせによって動いて表示される。
【発明を実施するための最良の形態】
【００１３】
図１は本発明を実施するために配置された構成部品の概略的ブロック図である。
図２は本発明にしたがってサーバーが実行する演算を図示するフローチャートである。
図３は図２に示したＬＯＧＩＮ演算の詳細を示している。
図４は図２に示したＬＯＧＯＵＴ演算の詳細を示している。
図５Ａ―５Ｃは図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示している。
図６は図２に示したＤＩＳＴＡＮＣＥ演算の詳細を示している。
図７Ａ−７Ｃは図２に示したＨＩＳＴＯＲＹ演算の詳細を示している。
図８Ａ−８Ｂは図２に示したＭＡＰ演算の詳細を示している。
図９は図２に示したＡＮＩＭＡＴＩＯＮ演算の詳細を示している。
図１０は図２に示したＰＲＯＸＩＭＩＴＹ演算の詳細を示している。
図１１Ａは図２に示したＯＢＳＥＲＶＡＴＩＯＮ演算の詳細を示している。
図１１Ｂは凸閉包と境界ボックスを示している。
図１２Ａと１２Ｂは、サーバー内に保存され、地表上の移動体の移動に関連する位置情報から演繹された情報の表１から３Ｂを示している。
【００１４】
図面の詳細な説明
本書に示す本発明の説明に用いられる用語は次のように定義する：
位置：緯度／経度／高度データの組である、対応するデータポイントを有する地表に対する三次元の地理的地点。
観測：対象物に付けられた特定の携帯型装置について得られた位置の順番付け。
場所：位置の領域（単一の点、クラスター、街路アドレス、都市、凸閉包、など）。
【００１５】
本発明はサーバー・クライアント構成で組織されている。クライアントはハードウェアあるいはソフトウェアのいずれかとすることができ、また対象の場所に関する情報を提供し、対象の場所に関する情報を要求するか、あるいはその両方が可能である。サーバーは多数の対象についての場所データを同時に保存し、そのデータをサーバーからの情報を要求するクライアントからコンピュータアプリケーションによってすぐに利用できる情報に加工する。
【００１６】
図１はＧＰＳ技術を用いる本発明の一つの実施例を示している。なおここで理解しなければならないのは、本発明がＧＰＳ技術に限定されず、この特定の配置が例示に過ぎないことである。サーバー３は、一つのタイプのクライアント、すなわち対象Ａ上の携帯装置１と対象Ｂ上の携帯装置２、ならびに別のタイプのクライアント、すなわちコンピュータアプリケーションＡＰＰ１とＡＰＰ２で動作するように構成されている。第一のタイプのクライアントは、後述のごとく、対象の位置についてＡＰＩ５を介してサーバー３にデータを提供する。第二のタイプのクライアントは、同じく後述のごとく、ＡＰＩ５を介してサーバー３から対象の位置について情報を要求する。
【００１７】
ここで理解しなければならないことは、本発明に用いられる、移動体のような、クライアントの数は設計選択の問題である、ことである。二つの対象だけが示されていることは、複数個の対象の使用が可能であることを指摘しながら、本発明の説明を明瞭にするためにだけに行われたのである。以下の説明において、ただ一つの対象とそれに関連する携帯装置が詳細に説明されるが、かかる説明は全ての対象とそれらの関連する携帯装置とに当てはまるものとする。同様に、容易に理解されるだろうが、本発明に用いられる、コンピュータアプリケーションなどの、その他のタイプのクライアントの数も設計選択の問題であり、二つだけが示されているのは、複数個のかかるアプリケーションの使用が可能であることを指摘しながら、本発明の説明を明瞭にするためにだけに行われたのである。
【００１８】
図１に戻って、位置採集携帯装置（「クライアント」）を担持または密閉する対象（人、車、ペットが含まれるが、それに限定されない）が示されている。携帯装置（以下、「装置」と称する）は、例えば、車または荷物の内部におくことができるか、あるいは自転車に装着したり、人の身に付けることができる。装置は、複数個のＧＰＳ衛星７からの信号をポーリングし、地表（これには、もちろん、高層建物、高木、なども含まれる）上の装置の位置や、また推論によって、対象の位置もそこから決定するために（図示されていない）周知の回路を含んでいる。装置によって発生した位置データは特定の時点における対象の特定位置を（すなわち、緯度、経度と高度によって）識別する。本発明で用いられる時間データは（後述のごとく）ＧＰＳ衛星（およびセルタワー）によって継続的に伝達される時間情報に基づいて装置によって発生する。装置はさらに、ＧＰＳ信号を検出し、対象の位置を決定するための過程の連続を予め選択した時間間隔で自動的に引き起こすために（図示されていない）制御回路も含んでいる。このような予め選択した時間間隔も設計選択の問題であり、要求データの保存および電池の寿命に対する時間の関数としての対象の位置の解像度との兼ね合いになる。制御回路は位置データをすぐにサーバー３に伝達するか、あるいは所定の数の位置について位置データを保存し、ついでバッチ伝送の一部として全てのかかる位置のデータを伝達するように設計することができる。推奨実施態様において、装置は適切なデータベース９を備えたサーバー３に定期的間隔でバッチメッセージを無線で伝達する。このメッセージは一連の位置のデジタルエンコーディングである。
【００１９】
推奨実施態様において、携帯装置はＮｅｘｔｅｌ ｉ８８ｓまたはｉ９５ｓ移動電話であり、その中で上述の制御回路がＪ２ＭＥプログラミング環境で実装されたソフトウェアプログラムを実行している。このプログラムは対象の現在の緯度、経度と高度を計算して現在位置データを求めるためにＧＰＳ衛星をポーリングして、局所に（すなわち電話のメモリ内に）位置データを保存する。プログラムに従って、装置は、位置データと、その中に予め保存されていた、装置の全地球同定識別子（「ＧＵＩＤ」）とを通信網６を介してリモートサーバーに中継する。位置データ送信の後（またＴＣＰプロトコルを使用しているときは、例えば、サーバーがその受領を肯定応答した後に）局所保存された位置データは削除され、これらの過程が反復される。くわえて、位置計算の正確さ、対象の速度と方向、およびポーリングのときに「見えている」ＧＰＳ衛星の数などのその他いくつものパラメータの値も求められる。保存パラメータのリストは次の通りである：
ＧＵＩＤ
緯度
経度
現在観測時間
緯度／経度精度
直前観測時間
直前緯度
直前経度
セル緯度
セル経度
速度
速度不確実性
方向
高度
高度不確実性
衛星の数
支援ＧＰＳ使用の有無。
【００２０】
本発明を目的として、ＧＵＩＤ、時間、緯度、経度と高度のパラメータの使用だけに関する議論が必要である。したがって、その他のパラメータの詳細は不必要とみなされる。
【００２１】
プログラムは現在位置データを電話のメモリ内に保存し、（ラン・レングス符号化アルゴリズムを用いて）定期的に圧縮し、つぎにデータをＧＰＲＳ（汎用パケット無線サービス、詳細はｈｔｔｐ：／／ｗｗｗ．ｇｓｍｗｏｒｌｄ．ｃｏｍから入手できる）を用いる通信網６を介してサーバーに伝達する。Ｊ２ＭＥプログラムは、ユーザー（すなわち装置の所有者）がＧＰＳポーリング周波数およびサーバーへの中継頻度、プロトコルがＵＤＰであるかＴＣＰであるかを制御することを可能にするメニューを提供する。
【００２２】
サーバー３は、Ｌｉｎｕｘ（登録商標）オペレーティング・システムと、ＧＵＩＤ、時間、緯度、経度と高度を含むそれぞれの位置の属性を永続的な記憶手段に記録するＭｙＳＱＬデータベースエンジン９（ｈｔｔｐ：／／ｗｗｗ．ｍｙｓｑｌ．ｃｏｍから無料で入手できる）とを実行しているコンピュータである。複数個の位置についてのこの位置データは対象の移動を表す生データであり、かかる生データは、磁気ディスク、光ディスク、または非揮発性ＲＡＭなどの適切な永続的記憶媒体９に好適には永続的に保存される。生データは、後述のごとく、ＡＰＩ５を介してアクセスできるもっとすぐに利用可能な情報に本発明に従って変換される。
【００２３】
つぎに、ＡＰＩ５の説明を提供する。ＡＰＩは外部コンピュータアプリケーションのためにサーバー内に保存された位置データへのアクセスを可能にするインターフェイスである。該インターフェイスはＸＭＬ−ＲＰＣプロトコルを介してかかる外部コンピュータアプリケーションからの要求を処理する。サーバーはＰｅｒｌ ＲＰＣ：：ＸＭＬ：：サーバーモジュールを用いて要求を処理する。クライアントアプリケーションは、Ｐｅｒｌ ＲＰＣ：：ＸＭＬ：：クライアントモジュールなどの、任意のＸＭＬ−ＲＰＣインプリメンテーションを用いてもよい。
【００２４】
パラメータは、“Ｃｏｍｐｉｌｅｒｓ： Ｐｒｉｎｃｉｐｌｅｓ， Ｔｅｃｈｎｉｑｕｅｓ， ａｎｄ Ｔｏｏｌｓ”（ｂｙ Ａｌｆｒｅｄ Ｖ． Ａｈｏ， Ｒａｖｉ Ｓｅｔｈｉ， ａｎｄ Ｊｅｆｆｒｅｙ Ｄ． Ｕｌｌｍａｎ， Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ， １９８６）という書籍に記載の拡張Ｂａｃｋｕｓ−Ｎａｕｒ書式の、下記の定義を用いて定義される。縦の棒は代替を分離し、アステリスクは「０回以上」を意味し、プラスの符号は「１回以上」を意味する。
【００２５】
ＯＢＪＥＣＴ：：＝（ＧＵＩＤ｜ＬＯＣＡＴＩＯＮ｜ＨＵＬＬ）
ＬＯＣＡＴＩＯＮ＿ＴＹＰＥ：：＝（“ｓｔｒｅｅｔ ａｄｄｒｅｓｓ”｜“ｓｔｒｅｅｔ”｜“ｐｏｓｔａｌ ｃｏｄｅ”｜“ｃｉｔｙ”｜“ｓｔａｔｅ”｜“ｃｏｕｎｔｒｙ”｜“ｃｌｕｓｔｅｒ”｜“ｍａｒｋ”｜“ｐｏｓｉｔｉｏｎ”）
ＭＡＰ＿ＴＹＰＥ：：＝（“ｓｔｒｅｅｔ”｜“ｔｅｒｒａｉｎ”｜“ｓａｔｅｌｌｉｔｅ”）
ＰＬＯＴ＿ＴＹＰＥ：：＝（“ｐｏｉｎｔ”｜“ｔｒａｉｌ”｜“ｓｔｉｐｐｌｅ”｜“ｖｅｃｔｏｒ”）
ＧＵＩＤ：：＝ＨＥＸＤＩＧＩＴ＋
ＳＥＳＳＩＯＮ：：＝ＨＥＸＤＩＧＩＴ＋
ＬＯＣＡＴＩＯＮ：：＝（ＣＯＵＮＴＲＹ｜ＳＴＡＴＥ｜ＰＯＳＴＡＬ＿ＣＯＤＥ｜ＣＩＴＹ｜ＡＤＤＲＥＳＳ）
ＡＤＤＲＥＳＳ：：＝ＳＴＲＥＥＴ＿ＡＤＤＲＥＳＳ ［ＵＲＢＡＮＩＺＡＴＩＯＮ］ ＣＩＴＹ ＳＴＡＴＥ ［ＰＯＳＴＡＬ＿ＣＯＤＥ］ＣＯＵＮＴＲＹ
ＳＴＲＥＥＴ＿ＡＤＤＲＥＳＳ：：＝ＮＡＭＥ
ＨＵＬＬ：：＝ＰＯＳＩＴＩＯＮ＋
ＰＯＳＩＴＩＯＮ：：＝ＬＡＴＩＴＵＤＥ ＬＯＮＧＩＴＵＤＥ ＡＬＴＩＴＵＤＥ
ＬＡＴＩＴＵＤＥ：：＝［“−”］ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ［ＤＩＧＩＴ］［ＤＩＧＩＴ］［“．”ＤＩＧＩＴ＊］
ＬＯＮＧＩＴＵＤＥ：：＝［“−”］ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ［ＤＩＧＩＴ］［ＤＩＧＩＴ］［“．”ＤＩＧＩＴ＊］
ＡＬＴＩＴＵＤＥ：：＝［“−”］ＤＩＧＩＴ＊［“．”ＤＩＧＩＴ＊］
ＩＮＴＥＲＰＯＬＡＴＩＯＮ：：＝ＢＯＯＬＥＡＮ
ＳＴＲＥＡＭ：：＝ＢＯＯＬＥＡＮ
ＳＯＲＴ＿ＭＥＴＨＯＤ：：＝（“ｃｈｒｏｎｏｌｏｇｉｃａｌ”｜“ｒｅｖｅｒｓｅ＿ｃｈｒｏｎｏｌｏｇｉｃａｌ”｜“ａｓｃｅｎｄｉｎｇ”｜“ｄｅｓｃｅｎｄｉｎｇ”）
ＳＴＡＲＴ＿ＴＩＭＥ：：＝ＴＩＭＥ
ＥＮＤ＿ＴＩＭＥ：：＝ＴＩＭＥ
ＤＵＲＡＴＩＯＮ：：＝ＴＩＭＥ
ＴＩＭＥ：：＝ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ ＤＩＧＩＴ＊
ＴＩＭＥ＿ＳＴＥＰ：：＝ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ ＤＩＧＩＴ＊
ＦＲＡＭＥ＿ＲＡＴＥ：：＝ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ ＤＩＧＩＴ＊
ＣＯＵＮＴＲＹ：：＝ＮＡＭＥ
ＳＴＡＴＥ：：＝ＮＡＭＥ
ＰＯＳＴＡＬ＿ＣＯＤＥ：：＝ＮＡＭＥ
ＣＩＴＹ：：＝ＮＡＭＥ
ＰＡＳＳＰＨＲＡＳＥ：：＝ＮＡＭＥ
ＮＡＭＥ：：＝（ＬＥＴＴＥＲ｜ＤＩＧＩＴ｜“”）＋
ＩＤＥＮＴＩＦＩＥＲ：：＝（ＬＥＴＴＥＲ｜ＤＩＧＩＴ）＋
ＨＥＸＤＩＧＩＴ：：＝（ＤＩＧＩＴ｜“Ａ”｜“Ｂ”｜“Ｃ”｜“Ｄ”｜“Ｅ”｜“Ｆ”）
ＬＥＴＴＥＲ：：＝（“Ａ”｜“Ｂ”｜“Ｃ”｜“Ｄ”｜“Ｅ”｜“Ｆ”｜“Ｇ”｜“Ｈ”｜“Ｉ”|“Ｊ”｜“Ｋ”｜“Ｌ”｜“Ｍ”｜“Ｎ”｜“Ｏ”｜“Ｐ”｜“Ｑ”｜“Ｒ”｜“Ｓ”｜“Ｔ”｜“Ｕ”｜“Ｖ”｜“Ｗ”｜“Ｘ”｜“Ｙ”｜“Ｚ”｜“ａ”｜“ｂ”｜“ｃ”｜“ｄ”｜“ｅ”｜“ｆ”｜“ｇ”｜“ｈ”｜“ｉ”｜“ｊ”｜“ｋ”｜“ｌ”｜“ｍ”｜“ｎ”｜“ｏ”｜“ｐ”｜“ｑ”｜“ｒ”｜“ｓ”｜“ｔ”｜“ｕ”｜“ｖ”｜“ｗ”｜“ｘ”｜“ｙ”｜“ｚ”）
ＤＩＧＩＴ：：＝（“０”｜ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ）
ＮＯＮＺＥＲＯ＿ＤＩＧＩＴ：：＝（“１”｜“２”｜“３”｜“４”｜“５”｜“６”｜“７”｜“８”｜“９”）
ＢＯＯＬＥＡＮ：：＝（“０”｜“１”）
【００２６】
図２は、本発明に従ってサーバー３によって実行される演算を説明するのに有益なフローチャートである。クライアントの一つ一つは要求を送り、それはステップ１０で、ＡＰＩ５を介してサーバーによって受信される。サーバーはどの要求が受信されたかの決定と適切な応答に進む。以下の議論において、演算の最初の記述はそれが使用するパラメータを括弧内に指定する。随意のパラメータは角括弧内にある。
【００２７】
クライアントがサーバー３と通信するために、ＬＯＧＩＮ要求１２｛［ＬＯＧＩＮ（ＧＵＩＤ，ＰＡＳＳＰＨＲＡＳＥ）］｝が処理される。この演算はクライアントのＧＵＩＤおよび予め割り当てられたＰＡＳＳＰＨＲＡＳＥに基づいてアプリケーション要求を取り扱う。図３に示したごとく、サーバーは、ユーザーによって入力された暗号化ＰＡＳＳＰＨＲＡＳＥを、１４によって、受信する。そのＧＵＩＤのためにサーバー内に予め保存されていたＰＡＳＳＰＨＲＡＳＥが、１６で、検索され、１８によって、受信ＰＡＳＳＰＨＲＡＳＥと比較される。それらが一致しないとき、２０で、適切なエラーメッセージが装置に返される（すなわち、伝達される）。それらが一致したとき、２２で、サーバーは現在のセッションに固有の、ＳＥＳＳＩＯＮ ＩＤと呼ばれる、コードを発生する。ＳＥＳＳＩＯＮ ＩＤはサーバー内に記憶され、後で説明するように、他のクライアント要求を認証するのにその後必要になったときに、その後のエントリのためにクライアントに知られるように、２４によって、やはりクライアントに返される。
【００２８】
サーバーが取り扱うことのできるもう一つの要求はＯＢＳＥＲＶＡＴＩＯＮ要求２６で、その詳細は図１１Ａに示されている。ＯＢＳＥＲＶＡＴＩＯＮ要求に対する応答は装置から受信した生位置データを処理する。それは、装置から受信したＳＥＳＳＩＯＮ ＩＤがサーバー内に記憶されたＳＥＳＳＩＯＮ ＩＤと一致するか否かに基づいて、２６で、ユーザーを認証することから始まる。認証に成功すると、２８で、サーバーは生データを受信し保存する。３０で、ＴＣＰプロトコルが装置からの伝達に用いられていることが判明したら、サーバーは、３２で、肯定応答を装置に返す。ＵＤＰなどの、別のプロトコルが使用されていたとき、一切の肯定応答は無用である。もちろん、認証２６に失敗したとき、３４で、適切なエラーメッセージが装置に返される。
【００２９】
上述の生位置データは、先に説明したとおり、生位置データのそれぞれのデータポイントが特定位置を（すなわち特定の時点でのその緯度、経度と高度によって）識別するようにステップ２８によって保存されるが、かなりの処理をしない限り、このデータはコンピュータアプリケーションによってすぐには利用できない。もっとすぐに利用可能な形式にするために、位置データは地表の三次元領域（例えば、街路の交差点または都市）を特定する場所情報に変換される。以下にさらに詳細に説明するごとく、ある位置データは、例えば、街路名、家屋番号、都市、州などによって指定された完全な街路アドレスに変換される。
【００３０】
サーバー３内（実際にはデータベース９内）に保存された生位置データの表からのサンプルエントリは図１２Ａの表Ｎｏ．１に示した。１６進法（１６ベース）が時間、緯度、経度と高度フィールドを除いて用いられる。ＧＵＩＤ８７Ｆ３はクライアントを一意的に同定し、一つの例において、クライアントは対象Ａによって担持された装置１とすることができる。「時間」フィールドに入力したデータは１９７０年１月１日から数えた秒数である。もちろん、他の時間指標を用いることもできる。緯度、経度および高度は自明である。表１は、ＧＵＩＤ８７Ｆ３が割り当てられた対象についての二つの観測と、ＧＵＩＤ５ＥＡ５が割り当てられた対象についての三つの観測とを示している。
【００３１】
図１１Ａのステップ３６は、ステップ２８で保存された生位置データを街路アドレスなどの場所情報に変換する。このプロセスはリバース・ジオコーディングとして知られている。リバース・ジオコーディングを実行するための推奨ソフトウェア製品はＳｐａｔｉａｌＦＸと呼ばれ、ＯｂｊｅｃｔＦＸ社から入手できる。いくつものｗｅｂサービスもリバース・ジオコーディングを実施している。保存データのサンプルエントリは図１２Ａの表２Ａと２Ｂに示されている。（印書したページの紙面の制約のため表２は図１２Ａの表２Ａと２Ｂに分離されている。表２Ｂは表２Ａのデータへの連結を示すだけのために 「ＧＵＩＤ」フィールドと「観測」フィールドの反復を含むように示されている。）「観測」フィールドは観測の配列を示す識別子である。それは時間フィールドから演繹できるが、表内にそれが明示的に含まれていることによりいくつかの共通計算、例えば、「私の車の最近１００の位置を示しなさい」などのユーザーによる要求、が容易になる。表２Ａ内のその他のフィールドは、フィールドの表題から自明である。表２Ｂ内のフィールドは以下に詳細に説明する。その結果は、コンピュータアプリケーションが対象の場所を効率的に問い合わせ、後述のごとく、最寄りの街路アドレスとしてそれを返すことを可能にするデータベース内の表である。
【００３２】
ステップ３８は３６で得られたアドレスをいくつもの逆索引に変換する。例えば、一つの逆索引は完全な街路アドレスをステップ３６がかかるアドレスに変換した全ての観測位置に変換する。これが全てのアドレスについて行われる。したがって、あるユーザーが「私が［ａｄｄｒｅｓｓ］に最後にいたのはいつか？」を知りたいとき、解答は逆索引から迅速かつ効率的に作成することができる。逆索引がなければ、サーバーはデータベース９内の全ての保存された位置データを処理しなければならないだろう。都市、郵便番号、州および国についても同様な逆索引が作られる。
【００３３】
それぞれの観測された位置についてステップ３６によってアドレスが導かれる。同様に、ステップ３６からそれぞれのアドレスについて逆索引内にエントリが作成される。しかしながら、ある観測にだけ対応するエントリは好適には一時間後に削除される。
【００３４】
ステップ４０はステップ３６によって得られたそれぞれの街路アドレスを街路アドレスの近傍を示す街路図に変換する。これはマイクロソフト社のＭａｐＰｏｉｎｔなどの製品を用いて達成される。全ての鍵となる場所（例えば、後述のごとくサーバーによって場所ＩＤを割り当てられたもの）についての街路図は永久に保持される。鍵とならない場所の街路図はメモリ内にスペースを確保するために一時間後に好適には削除される。この情報は図１２Ａの表２Ｂの「街路図」フィールド内に保存される。それがデータベース内のかかる地図が保存されるところへのパスを構成して、コンピュータアプリケーションが対象の場所の街路図を効果的に発生するのを可能にする。
【００３５】
かかる街路図は数多くの用途を有することができる。例えば、ユーザーは装置１を自分の犬に取り付けることができる。ユーザーが自分の犬がどこにいるかを知りたいと思えば、本発明は犬がどこで見つかるかを示す街路図を（後述のごとく）発生することができる。別の例において、装置１がユーザーに取り付けられているとき、ユーザーが他の人に電子的に送信することができる街路図を発生するために本発明を用いてどこであれ自分が現在いる場所への指示を誰にでも与えることができる。
【００３６】
ステップ４０はさらに、ステップ２８によって保存された生位置データを衛星地図に変換する。これはＫｅｙｈｏｌｅ社からのＥａｒｔｈＶｉｅｗｅｒなどの製品を用いて達成される。この情報は図１２Ａ内の表２Ｂの「衛星図」フィールド内に保存される。これはかかる地図が保存されるところへのパスを構成して、コンピュータアプリケーションが対象の場所の衛星地図を効率的に発生することを可能にする。例えば、ユーザーが興味のある区域がどのように見えるかの「俯瞰」観測を得たいと思うとき、衛星地図を発生するために本発明を使用することができるだろう。街路図はどこで左右に曲がるかについて二次元支援を提供することができる、しかし衛星地図は三次元であり、例えば、関心のある区域がどのように見えるか、その周囲の建物はどのように見えるか、また道路の広さはどのくらいか、についてはるかに詳細に見せることができる。
【００３７】
ＡＮＩＭＡＴＩＯＮ要求２３０に応じて、本発明は「動画」街路図、地形図および／または衛星地図を発生することもできるが、これはビデオで、対象の動きを、それぞれ、街路、地形および／または衛星地図上に重ねることによって対象の動きを見せる。
【００３８】
ステップ４０はさらに、ステップ２８によって保存された生位置データを地形図に変換する。これはＭａｐｔｅｃｈ社からのＭａｐＳｅｒｖｅｒなどの製品を用いて達成される。この情報は図１２Ａの表２Ｂの「地形図」フィールド内に保存される。それはかかる地図が保存されたところへのパスを構成して、コンピュータアプリケーションが対象の場所の地形図を効果的に発生するのを可能にする。例えば、ユーザーが山で遭難したとき、本発明を用いて地形図を発生し、それを移動電話で救助者に向けることができるだろう。地形図は地勢の特徴を示して手掛かりを提供するが、これは緯度、経度と高度だけではできないことである。
【００３９】
ステップ４２はステップ２８によって保存された生位置データをクラスター化された位置に変換する。全ての位置特定技術には、ＧＰＳをはじめとして、固有の不正確さが在るので、位置測定は対象の真の位置の周囲で変動することが多い。さらに、意味のある場所（街路アドレスなど）は明確な境界が示されないことが多い。これらの問題を解決するために、また重要区域を決定するために、近隣位置が一緒にまとめられ、それぞれ、単一の地理的場所として処理される。一緒にまとめるべき位置を識別する技術はクラスター化と呼ばれ、本発明はＩＳＯＤＡＴＡクラスター化アルゴリズムを用いてこれを達成する。このアルゴリズムはＴｈｅｒｒｉｅｎ，Ｃ．Ｗ． “Ｄｅｃｉｓｉｏｎ， Ｅｓｔｉｍａｔｉｏｎ ａｎｄ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ”， Ｊｏｈｎ Ｗｉｌｅｙ ＆ Ｓｏｎｓ， １９９９に開示され、そこに含まれているこのアルゴリズムの説明は、参照として本書に含めた。結果はデータベース内の（以下に詳しく述べる）表であり、アプリケーションが対象の頻繁に訪れる場所を効率的に決定するのを可能にする。クラスター化によって得られたサンプルエントリは図１２Ｂの表Ｎｏ．３に示されている。（表Ｎｏ．３は印書したページ上の紙面の制約のために図１２Ｂの表３Ａと３Ｂに分離されている。表３Ｂが「ＧＵＩＤ」フィールドと「場所ＩＤ」フィールドの反復を含むように示されているのは、ただそれが表３Ａのデータに連結されていることを示すためである。）場所ＩＤはサーバーによって次の領域に割り当てられる：クラスター、街路アドレス、都市、郵便番号、州、国および（割当て半径とともに）クライアントによって特に指定された任意の位置。
【００４０】
地球がほぼ球形であることを計算に入れるために、ＩＳＯＤＡＴＡには予備処理過程と後処理過程が要求される。緯度のそれぞれの一度は同じ距離であるが、経度はそうではない。経度の一度の地理的距離は極よりも赤道の方が大きい。例えば、北極においては、旋回するだけで経度の３６０゜を移動することができるが、赤道では、経度の３６０゜を踏破するには地球の円周の周りを旅行しなければならない。予備および後処理過程がなければ結果ははるかに不正確になるだろう、とくに対象の動きが大きな南北距離を踏破したときにはそうである。
【００４１】
したがって、予備処理過程を適用して、緯度と経度を（経度が原因であるこの非線形性の影響を受けない）ユニバーサル横メルカトル座標系に「ゆがめ」、それをＩＳＯＤＡＴＡへの入力として使用する。後処理過程ではゆがみを戻す、すなわちユニバーサル横メルカトル位置を元の緯度と経度に変換する。緯度／経度とユニバーサル横メルカトルの間の変換は直接的である。この方法についての情報はｈｔｔｐ：／／ｗｗｗ．ｕｗｇｂ．ｅｄｕ／ｄｕｔｃｈｓ／ＵｓｅｆｕｌＤａｔａ／ＵＴＭＦｏｒｍｕｌａｓ．ＨＴＭで入手可能であり、それを印刷した参照はページの終わりにある。
【００４２】
ＩＳＯＤＡＴＡは（多数のことがある）多くの位置について位置データを処理し、それらをクラスターに分割する。その結果は点の集合（そこから凸閉包が後述のごとく計算される）とセントロイドである。図１１Ａから明らかなように、クラスター化はそれぞれの新しいデータポイントについて実行される。しかしながら、これによって処理負荷が高くなるときは、クラスター化アルゴリズムは、毎時のように、選択した時間間隔でのみ実施される。
【００４３】
今説明したように、クラスター化過程４２はクラスターにまとめられた位置を決定する。凸閉包アルゴリズム４４はつぎにそのクラスターの場所を定義する点の最小数を決定する。例えば、ユーザーの家の中、および周囲に散在した５００００の観測があるとき、クラスター化は（ＩＳＯＤＡＴＡアルゴリズムを介して）これら全ての位置を一つのクラスターにまとめる。凸閉包アルゴリズムはそのクラスターの境界の位置を識別する。もっと具体的には、ステップ４４は、全ての位置が境界内またはその上に来るように、一つのクラスターに区分された位置についてステップ２８によって保存された生位置データから境界を決定する。もちろん、それぞれの異なるクラスターについて異なる境界がある可能性がある。凸閉包アルゴリズムの直感的説明は次のように提供することができる。多数の釘を無作為に板に打ち込み、つぎにゴムバンドを全ての釘の周囲に掛けると、何本かの釘はゴムバンドの内側になり、他のものはゴムバンドに接触するだろう。ゴムバンドに接触している釘が凸閉包を構成する。この項の数学的定義は「凸閉包」が対象の一集合を含む最小凸サブセットであるというものである。図１１Ｂは凸閉包を黒い円で示し、白い円は凸閉包内の位置を示している。
【００４４】
凸閉包は、いったん凸閉包がある対象について保存されたら、新しいデータポイントが到着するたびに、反復して拡大または縮小することができるという変更を加えて、参照として本書に含めたＯｒｗａｎｔ ｅｔ ａｌ．， “Ｍａｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ Ｐｅｒｌ”， Ｏ’Ｒｅｉｌｌｙ ＆ Ａｓｓｏｃｉａｔｅｓ， １９９９， ｐ．４５４に記載のＰｅｒｌのサブルーチンで、好適には発生される。図１１Ａから明らかなように、凸閉包は全ての新しいデータポイントについて実行される。しかしながら、これによって処理負荷が高くなるときは、凸閉包アルゴリズムは、毎時のように、選択した時間間隔でのみ実施される。
【００４５】
凸閉包を定義するデータポイントは図１２Ｂに示した表Ｎｏ．３Ａ内の「ポイント」フィールド内に秩序だった対（すなわち、緯度と経度）として保存される。例えば、場所ＩＤフィールド内に１６進数ＣＢ０１８によって識別されたクラスターが「ゴムバンド」の形状を定義するのに１５本の「釘」を必要とする凸閉包を有するとき、「＃ポイント」フィールドはその中に数１５を有するであろう、また「ポイント」フィールドは、それぞれ、これらの「釘」に対応する１５の秩序だった対を有するであろう。特殊な例として、表３ＡはそのＧＵＩＤとして８７Ｆ３を有する対象のための場所ＩＤとして１６進数ＣＢ０１８を挙げている。このクラスターのセントロイドは緯度４２．４４６８０３９６、経度−７１．２２５４４９５４、高度１４．１０３４８にあるものとして決定される。凸閉包アルゴリズムはこのクラスターの形状が円であると決定した（これは、一つのだけの点、すなわちセントロイドと、それにくわえて５．１０６６の平均半径が形状の定義に要求されることを示す「＃ポイント」フィールド内の「１」のエントリから明らかである）。反対に、場所ＩＤ ＣＢ９Ａ４はその凸閉包の形状を特定するために３つの位置（または点）を要求し、これらについての秩序だった対は「ポイント」フィールド内に見つかる。
【００４６】
場所ＩＤ ＣＢ０１８についてのセントロイドの位置、したがって、クラスターの場所はステップ３６の結果から得られた１５ Ｄａｌｔｏｎ Ｒｄ．， Ｂｏｓｔｏｎ， ＭＡ． ０２１４９ ＵＳＡの住所に対応する。
【００４７】
凸閉包が入手できると、ある位置がその中にあるかの判定は電子計算機的にきわめて容易である。凸閉包はこの目的のために特に設計されている。もちろん、対象が訪問した実際の場所に対応しないような仮想線によって囲まれた／定義された領域としてクラスターを表示することも可能である。
【００４８】
サーバーが取り扱うことができるもう一つの要求はＬＯＧＯＵＴ要求４６｛ｌｏｇｏｕｔ（ＳＥＳＳＩＯＮ）｝である。これはセッションを終結する要求である。図４に示したごとく、認証ステップ４８に成功した後、保存されたＳＥＳＳＩＯＮ ＩＤは、５０によって、データベース９から削除され、５２によって、適切な成功メッセージが装置に返される。サーバーがセッションのＬＯＧＯＵＴ要求を受信したとき、サーバーはクライアントのＳＥＳＳＩＯＮ ＩＤを無効にして、クライアントが再度ログインするまで他の呼び出しを禁止する。
【００４９】
サーバー３はＬＯＣＡＴＩＯＮ要求５４｛ｌｏｃａｔｉｏｎ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＬＯＣＡＴＩＯＮ＿ＴＹＰＥ， ［ＴＩＭＥ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］）｝を取り扱うこともできる。この演算は「場所」方法を介して対象の場所を決定するためにアプリケーション要求を取り扱う。クライアントは認証のためにＳＥＳＳＩＯＮ ＩＤを提供し、場所を同定する対象を指定し、所望の出力形式を特定するために場所タイプを指定する。追加として、クライアントは、場所観測の所望時間と、できる限り正確に時間に合わせる試みにおいて対象の場所をシステムが推定するべきかを指示するブール補間ビットとを指定することもできる。
【００５０】
図５Ａ―５Ｃに示したごとく、認証５６に成功すると、ステップ５８はユーザーが指定された時間における場所を要求しているかを点検する。その場合、つぎにステップ６０は位置データが正確な時間を有するかを検査する。該当する場合、つぎにステップ６２が実行される（下記参照）。該当しない場合、ステップ６４は補間が許可されたかを検査する。該当する場合、つぎにステップ６６がデータベース内に保存された二つの時間の間で補間された位置を計算する。補間がＯＦＦの場合、つぎにステップ６８が指定された時間に一番近いいずれかの保存された時間に対するいずれかの位置データを選択する。
【００５１】
ステップ５８がどんな時間も指定されていないことを明らかにしたとき、つぎにステップ７０は最後の既知の位置についての位置データを検索する。７２によって、補間がＯＮのとき、つぎにステップ７４は位置を現在時間に外挿する。７２によって、補間がＯＦＦのときは、最後の既知の位置データがそのまま単に使用される。
【００５２】
このように、ユーザーが場所を要求したとき、ステップ６２への入力はその要求に応えるために必要な位置である。ステップ６２はユーザーがこの情報を生位置データの形で所望するか否かを判定する。該当する場合、そのデータがステップ７６によって提供され、フローはつぎに、図２に示すごとく、要求判定の最初の段階に回帰する。該当しないときは、ステップ７８で場所タイプが街路アドレスであるか否かを判定する。該当する場合は、ステップ８０で、その街路アドレスがステップ３８で獲得した街路アドレス逆索引内にあるかを判定する。該当する場合は、ステップ８２でそのアドレスをユーザーに提供する。該当しないときは、８４で、リバース・ジオコーディング・プロセスを実行し、８６で、情報を将来利用するために索引内に保存し、８２で、ユーザーに返す。
【００５３】
郵便番号のためのステップ８８、９０、９２、９４と９６は、それぞれ、上述のステップ７８、８０、８２、８４と８６に対応する。同様に、対応は都市については９８、１００、１０２、１０４、１０６、州については１０８、１１０、１１２、１１４、１１６、また国については１１８、１２０、１２２、１２４と１２６に適用される。
【００５４】
１２８で、指定された場所タイプがクラスターであるときは、ステップ１３０で、指定された位置が既存のクラスター内であるか否かが判定される。該当する場合、１３２で、凸閉包が返される。該当しない場合は、１３４でクラスター化が実行され、１３６で、凸閉包アルゴリズムが実行され、１３２で結果がクライアントに返される。
【００５５】
サーバーによって扱われるもう一つの要求はＤＩＳＴＡＮＣＥ要求１４０｛ｄｉｓｔａｎｃｅ（ＳＥＳＳＩＯＮ，ＯＢＪＥＣＴ，ＯＢＪＥＣＴ）｝である。サーバーは二つの対象の間の距離を決定するためにアプリケーション要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤと二つの対象を提供する。結果は、適切なステップを使用してそれぞれの対象の１０進数緯度と経度を決定し、ついでこれらの場所のセントロイドの間の球面距離（すなわち、ほぼ地球の表面にそった距離）を計算して求められる。
【００５６】
図６に示したごとく、ステップ１４２と１４４は指定された各対象についてのそれぞれのＧＵＩＤをデータベースから検索する。ステップ１４６は第一の対象の最後の既知の位置を決定し、ステップ１４８は第二の対象について同様に決定する。ついでステップ１５０はそれらの間の球面距離を計算する。計算結果は、１５２で、クライアントに伝達される。
【００５７】
サーバーによって扱われるもう一つの要求はＨＩＳＴＯＲＹ要求１５４｛ｈｉｓｔｏｒｙ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＬＯＣＡＴＩＯＮ＿ＴＹＰＥ， ［ＴＩＭＥ＿ＳＴＥＰ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］）｝である。サーバーはＨＩＳＴＯＲＹ要求を取り扱って対象の移動の履歴を求める。クライアントはＳＥＳＳＩＯＮ ＩＤ、対象、場所タイプと、随意に、時間ステップ、補間ビット、開始時間、および終了時間を提供する。
【００５８】
時間ステップが提供されたとき、サーバーは固定間隔で観測を、例えば、その時刻の場所を返す。補間ビットが設定されているとき、所与の時間における位置を求めるために推定値が用いられる。そうでなければ、最も近い現実の観測が用いられる。結果は一連のタイムスタンプ付きの観測として返される。観測は、提供されていれば開始時間に、いなければ第一の観測で始まる。観測は、提供されていれば終了時間に、いなければ最後の観測で終わる。
【００５９】
図７Ａから７Ｃに示したごとく、認証が成功した後、ステップ１５６は対象のＧＵＩＤを決定する。つぎにステップ１６０（図７Ｂ参照）はクライアント要求が開始時間を指定しているかを検査する。該当しない場合は、ステップ１６２はその対象について記録された第一の観測を使用する。いずれにしても、つぎにステップ１６４は終了時間が提供されたか否かを検査する。そうでない場合は、ステップ１６６はその対象について記録された最後の観測を使用する。したがって、ステップ１６０−１６６の終わりに、このＨＩＳＴＯＲＹ演算の処理に要した開始および終了時間が分かる。
【００６０】
ついで、ステップ１７０（図７Ｃ参照）はクライアント要求が時間ステップを指定しているかを検査する。該当する場合、ステップ１７２で、補間がＯＮであれば（すなわち補間ビットが提供された）、ステップ１７４は時間ステップを括弧に入れる時間の間を補間する。例えば、もし時間ステップが５分であれば。しかしながら、５分間隔で位置が検出されないで、４分３２秒に一つの位置、７分１５秒にもう一つの位置あれば、ステップ１７４はかかる二つの位置についてのデータを用いて５分間隔の補間位置データを提供することになる。他方で、補間がＯＦＦのとき、ステップ１７６は４分３２秒に得られた位置データを選択することになる。なぜなら、それが５分間隔の時間に一番近いからである。
【００６１】
図７Ａに示した関数１５８は図７Ｂに示した全てのステップを表している。同様に、図７Ｃに示した全てのステップは図７Ｂの関数１６８によって表される。関数１５８と１６８の結論で、特定の位置についてのデータポイントはステップ１７４または１７６から知られ、ＨＩＳＴＯＲＹ演算に従ってその後の処理に利用できる。
【００６２】
図７Ａに示したごとく、その既知の部分が図５Ａのステップ６２に入力される。したがって、クライアント要求が街路アドレスとして提供されるべき移動についてのものであるとき、そのアドレスはステップ７８によって決定され、上述の既知の位置（すなわちステップ１７４または１７６から）に対応する街路アドレスがステップ８２によってクライアントに返されることになる。
【００６３】
ＨＩＳＴＯＲＹ演算のためのこの一連のステップは全ての位置が処理されるまで（すなわち、終了時間まで）１６９で（図７Ａ参照）、ループに従う。
【００６４】
サーバー３によって取り扱われるもう一つの要求はＭＡＰ要求１７８｛ｍａｐ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＭＡＰ＿ＴＹＰＥ， ＰＬＯＴ＿ＴＹＰＥ， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］）｝である。サーバーは対象の場所の地図を発生してこの要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤ、対象、地図タイプ、プロットタイプと、随意に、開始時間、終了時間、および補間ビットを提供する。サーバーは、表２Ｂから入手可能なときはデータベースから地図を検索し、そうでないときは地図を作製する。
【００６５】
地図タイプは「街路」、「地形」、または「衛星」タイプのいずれか一つである。プロットタイプは「点」、「軌跡」、または「ベクトル」のいずれか一つであり、発生した地図の中で対象のパスがどのように線描されるかを設定する。開始時間が提供されているとき、その時間からはじめて対象の場所が使用され、そうでなければ、システムによって記録された第一の観測になる。終了時間が提供されているとき、その時間に終わる対象の場所が使用され、そうでなければ、システムによって記録された最後の観測になる。補間ビットが設定されているとき、システムは従来の補間アルゴリズムを用いて現実の観測の間のデータを埋める。つぎに、地図イメージがクライアントに返される。
【００６６】
図８Ａと８Ｂに示すごとく、１８０での、ＧＵＩＤへの変換が続く通常の認証ステップがうまく完了したとき、上述の関数１５８のステップは、上述のごとく、開始時間と終了時間を決定する。ついで、上述の関数１６８のステップが、先に説明したように、処理される観測位置を決定する。
【００６７】
この段階で、作製される地図は「境界ボックス」を有する必要がある、なぜなら（上述のＭａｐＰｏｉｎｔなどの）地図サービスは何を地図にするかを知る必要があるからである。例えば、４３緯度、−７１経度で地図を要求するだけでは十分ではない、なぜなら地図サービスは縮尺を知らないからである：それは平方ヤードであるべきか？平方マイルであるべきか？したがって、地図サービスが用いられるとき、本発明の場合がそれだが、地図の長方形の周辺を定義する「境界ボックス」が提供されなければならない。
【００６８】
本発明は閉包内の点の全てをとおってループを作り、最小緯度、最大緯度、最小経度、および最大経度を計算して場所の凸閉包から境界ボックスを計算する。境界ボックスはこのときその左上角が最小緯度と最小経度の点にあり、その右下角が最大緯度と最大経度の点にある長方形になる。図１１Ｂにおいて、角の括弧は凸閉包に対する境界ボックスを示している。
【００６９】
図８Ａのステップ１８２は上述のアルゴリズムに従って境界ボックスを計算する。
【００７０】
境界ボックスが計算されると、ＭＡＰ演算１７８は、詳細を図８Ｂに示した、図８Ａに関数１８４として表示されているものを実行する。この図に戻る前に述べておかなければならないが、サーバーはマッピングサービスのために（街路図に一つ、地形図に一つ、衛星地図に一つの）三つのＵＲＩ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｉｄｅｎｔｉｆｉｅｒｓ）待ち行列を維持する。それぞれの待ち行列はシステムの寿命期間（すなわち、経験的に、マッピングサービスを使用する直前の試みの成功または失敗から）にわたって観測された信頼性の順に配置される。これらの待ち行列は一つ以上のマッピングサービスが利用できない事象の際に維持される。したがって、一つのマッピングサービスが応答しないとき、サーバーは次のマッピングサービスを選択するために待ち行列にアクセスする。
【００７１】
ステップ１８６はクライアント要求に指定された地図タイプが地形図であるか否かを判定する。該当する場合は、ステップ１８８は地形待ち行列から第一のＵＲＩの抽出に着手し、１９０で、地図が検索される。１９２で、検索に成功すると、情報は要求されたプロットタイプに重ねられる。どのプロットタイプを使用するかはステップ２１６、２２０と２２４で決定され、ステップ２１８、２２２と２２６の中から適切なものが地図オバーレイを実施する。１９２で、地図検索に成功しなかったとき、ステップ１９４は待ち行列の中の次のＵＲＩに移行して、ステップ１９０から１９２までを再度ループする。
【００７２】
ステップ１９６、１９８、２００、２０２と２０４は衛星地図のために実行され、それぞれ上述のステップ１８６、１８８、１９０、１９２と１９４に対応している。
【００７３】
同様に、街路図のためのステップ２０６、２０８、２１０、２１２と２１４はそれぞれ上述のステップ１８６、１８８、１９０、１９２と１９４に対応している。
【００７４】
ＵＲＩ抽出ステップ１８８、１９８と２０８はＵＲＩによって指名されたサービスからマップを抽出するユティリティを用いる。かかるユティリティの一つがｈｔｔｐ：／／ｓｅａｒｃｈ．ｃｐａｎ．ｏｒｇから入手できるＰｅｒｌ ＷＷＷ：：Ｍｅｃｈａｎｉｚｅモジュールである。システムは該ユティリティを用いてステップ１８２で計算した境界ボックスのある地図を検索し、１８５で地図はクライアントに返される。
【００７５】
もう一つの可能なクライアント要求はＡＮＩＭＡＴＩＯＮ要求２３０｛ａｎｉｍａｔｉｏｎ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＭＡＰ＿ＴＹＰＥ， ＰＬＯＴ＿ＴＹＰＥ， ＤＵＲＡＴＩＯＮ， ＦＲＡＭＥ＿ＲＡＴＥ， ［ＳＴＲＥＡＭ］， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］）｝である。この方法は対象の動きの動画を発生するためにアプリケーション要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤ、対象、地図タイプ、プロットタイプ、持続、フレームレートと、随意に、ストリームビット、開始時間、終了時間を提供する。最初の四つのパラメータについては前のステップで論じた。持続は動画が継続するべき時間の長さである。フレームレートは毎秒あたりのフレーム数である。ストリームビットはクライアントが動画全体をダウンロードしたいのか、あるいは発生の都度フレーム単位で受信したいのかを示すブーリアンである。開始時間は対象の最初の観測の時間である。終了時間は対象の最後の観測の時間である。サーバーは双線形補間を介して代表的観測の一集合を決定し、それぞれのかかる観測について地図を発生し、マップの配列を組み合わせて動画にして、ストリームビットが設定されているときは結果をクライアントにストリーミングし、その他の場合は動画全体を送信する。
【００７６】
図９に示したごとく、認証とＧＵＩＤへの変換はステップ２３２で最初に行われる。ついで、上述の関数１５８を実行して開始および終了時間を決定する。ステップ２３４はフレームレートがクライアント要求に含まれているかを判定する。含まれていないとき、このパラメータは１フレーム／秒に設定される。（フレームレートが指定されているときは）２３４からの、（指定されていないときは）２３６からのフレームレートがステップ２３８に入力され、円滑な動画のために観測が要求される時間を決定する。これは指定フレームレートパラメータの値（またはフレームレートが指定されていないときは１）をＤＵＲＡＴＩＯＮパラメータの値に分割して行われる（あるいは、ＤＵＲＡＴＩＯＮが省略されているときは、終了時間パラメータの値から開始時間パラメータの値を引いて、終了時間のデフォルトは最後に記録された観測で、開始時間のデフォルトは最初に記録された観測である）。もちろん、ＤＵＲＡＴＩＯＮは動画シーケンスの所望の時間長さである。このステップの結果は対象の位置が動画に現れるべき均等に配分された時間の配列である。
【００７７】
ステップ２４０は必要な補間を実行し、ステップ２４２は位置のそれぞれの対について境界ボックスを計算する。ついで、演繹された情報を上述の関数１８４（図８Ｂ参照）に用いて要求プロットタイプを使用する要求地図タイプで地図を作製する。
【００７８】
ステップ２４４はＡＮＩＭＡＴＩＯＮ演算の処理が位置の最後の対に到達したかを判定する。該当しない場合、この演算の処理は位置の最後の対に到達するまで関数１８４を通って反復ループする。なお、この段階で、関数１８４を通るループによって導き出された全ての地図は個別にサーバーに局所的に保存される。ステップ２４６はこれら全ての地図をＧＩＦ画像フォーマットに変換するユティリティを使用する。かかるユティリティの一つがｐｂｍｐｌｕｓであり、ｈｔｔｐ：／／ｗｗｗ．ａｃｍｅ．ｃｏｍ／ｓｏｆｔｗａｒｅ／ｐｂｍｐｌｕｓ／から入手できる。
【００７９】
つぎに、ステップ２４８は、得られた各ＧＩＦ画像を組み合わせて、フレームレートパラメータで指定されたフレームレートで動画ｇｉｆにするユティリティを使用する。かかるユティリティの一つがＭｕｌｔｉＧＩＦで、ｈｔｔｐ：／／ｗｗｗ．ｋｆｓ．ｏｒｇ／〜ａｂｗ／ｃｏｄｅ／ｍｕｌｔｉｇｉｆ．ｈｔｍｌから入手できる。結果は地図動画で、つづいてクライアントに返送されるものである。
【００８０】
動画は、ステップ２５０、２５２と２５４に基づいて、ファイルまたはストリームとしてクライアントに返される。ストリーミングは、Ｑｕｉｃｋｔｉｍｅ（登録商標）（Ａｐｐｌｅ， Ｉｎｃ．； ｈｔｔｐ：／／ｄｅｖｅｌｏｐｅｒ．ａｐｐｌｅ．ｃｏｍ／ｑｕｉｃｋｔｉｍｅ）またはＲｅａｌＶｉｄｅｏ（登録商標）（ＲｅａｌＮｅｔｗｏｒｋｓ， Ｉｎｃ．； ｈｔｔｐ：／／ｗｗｗ．ｒｅａｌ．ｃｏｍ）によって提供されているような、任意の従来のインターネット・ビデオ・ストリーミング技術を用いて達成できる。
【００８１】
図２に示された最後の要求はＰＲＯＸＩＭＩＴＹ２５６要求｛ｐｒｏｘｉｍｉｔｙ（ＳＥＳＳＩＯＮ， ＯＢＪＥＣＴ， ＯＢＪＥＣＴ， ＳＯＲＴ＿ＭＥＴＨＯＤ， ［ＳＴＡＲＴ＿ＴＩＭＥ］， ［ＥＮＤ＿ＴＩＭＥ］， ［ＴＩＭＥ＿ＳＴＥＰ］， ［ＩＮＴＥＲＰＯＬＡＴＩＯＮ］）｝である。この方法は二つの対象の間の距離のリストを作成するためにアプリケーション要求を取り扱う。クライアントはＳＥＳＳＩＯＮ ＩＤ、二つの対象、前方または後方のいずれかへの距離または時間を指定するデータの順序を提供する。クライアントは、前のステップで解釈されたような、随意の開始時間、終了時間、時間ステップ、または、補間ビットを提供してもよい。
【００８２】
図１０に示したごとく、二つの対象はステップ２７０と２７２によってそれらのそれぞれのＧＵＩＤに変換される。関数１５８は開始時間と終了時間を決定する。上述の関数１６８と同じ機能を有する関数１６８ａは、第一の対象の位置を提供する。同様に、関数１６８ｂは他方の対象の位置を提供する。この演算のためのそれぞれのステップは、第一の対象について一つの位置を、第二の対象について一つの位置を有することになる。ステップ２７４は二つの対象のこれらの位置の間の球面距離を計算する。つぎにこれがそれぞれの時間ステップについて行われる。二つの対象が静止しているとき、それらの間の距離は明らかに同じままである。一方の対象が移動し、他方が静止しているとき、両対象の間の距離は動いている対象の運動にだけ依存する。両方の対象が移動しているとき、距離はそれらの組み合わせた運動に応じて変動することになる。
【００８３】
ＰＲＯＸＩＭＩＴＹ演算の結果を表すのにいくつかの分類方法が利用可能である。両対象の間の距離は、時系列で、あるいは逆時系列で時間関数として表すことができる。また、結果は両対象の間の距離の大きさについて表し、距離を昇順または降順で表すことができる。クライアント要求がこれらの分類方法のどれにも対応しないとき、ステップ２９０でエラーメッセージが返される。
【００８４】
ステップ２７６−２７９はどの分類方法がクライアント要求に含まれたかを判定する。ステップ２８０−２８３はそれぞれ要求された分類方法を実行し、ステップ２８４−２８７は要求された情報をクライアントに返す。
【００８５】
以上のように本発明の推奨実施態様を詳細に述べたが、当業者には自明のごとくさまざまな変更を加えることができる。例えば、本発明はハードウェアもしくはソフトウェアに、または両者の組み合わせに実装しても良い。また、ＩＳＯＤＡＴＡアルゴリズムは場所決定のためのいくつもの技術のうちの一つである。ファジー・クラスター化、階層クラスター化、およびコホーネンの自己組織地図などの、他の技術も可能である。ＨＳＣＳＤおよび８０２．１１プロトコル・ファミリーのような、ＧＰＲＳの使用への代案もある。さらに、ＭｕｌｔｉＧＩＦを使う代わりに、ＧＩＦフォーマットの地図は、ｈｔｔｐ：／／ｗｗｗ．ｕｌｅａｄ．ｃｏｍから入手可能なＵｌｅａｄなどのソフトウェア製品をスクリプトしてＧＩＦ８９ａ動画に変換することができる。また、Ｃｅｌｌ ＩＤ、ＢｌｕｅｔｏｏｔｈまたはＲＦＩＤなどの、位置決め技術としてのＧＰＳの使用への代案もある。これらおよびその他の変更をもって請求の範囲に定義された本発明の範囲を逸脱できないものとする。
【図面の簡単な説明】
【００８６】
【図１】本発明を実施するために配置された構成部品の概略的ブロック図
【図２】本発明にしたがってサーバーが実行する演算を図示するフローチャート
【図３】図２に示したＬＯＧＩＮ演算の詳細を示す図
【図４】図２に示したＬＯＧＯＵＴ演算の詳細を示す図
【図５Ａ】図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示す図
【図５Ｂ】図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示す図
【図５Ｃ】図２に示したＬＯＣＡＴＩＯＮ演算の詳細を示す図
【図６】図２に示したＤＩＳＴＡＮＣＥ演算の詳細を示す図
【図７Ａ】図２に示したＨＩＳＴＯＲＹ演算の詳細を示す図
【図７Ｂ】図２に示したＨＩＳＴＯＲＹ演算の詳細を示す図
【図７Ｃ】図２に示したＨＩＳＴＯＲＹ演算の詳細を示す図
【図８Ａ】図２に示したＭＡＰ演算の詳細を示す図
【図８Ｂ】図２に示したＭＡＰ演算の詳細を示す図
【図９】図２に示したＡＮＩＭＡＴＩＯＮ演算の詳細を示す図
【図１０】図２に示したＰＲＯＸＩＭＩＴＹ演算の詳細を示す図
【図１１Ａ】図２に示したＯＢＳＥＲＶＡＴＩＯＮ演算の詳細を示す図
【図１１Ｂ】凸閉包と境界ボックスを示す図
【図１２Ａ】地表上の移動体の移動に関連する位置情報のサンプリエントリの表１〜２Ｂを示す図
【図１２Ｂ】地表上の移動体の移動に関連する位置情報のサンプリエントリの表３Ａ〜３Ｂを示す図
【符号の説明】
【００８７】
１ 携帯装置
２ 携帯装置
３ サーバー
６ 通信網
７ ＧＰＳ衛星
９ データベース
【特許請求の範囲】
【請求項１】
地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供する方法において、
複数個の位置のそれぞれに関連する位置データが取得される過程と、
複数個の位置についての位置データが移動体の移動についての情報を提供するために要求に応じてそこから選択的に検索するための永続的データベースに保存される過程、
とから成る、ことを特徴とする方法。
【請求項２】
複数個の位置の位置データが自動的に取得され、および／または定期的時間間隔でなされた位置測定に関係づけられることを特徴とする、請求項１に記載の方法。
【請求項３】
保存ステップが位置データを前記複数個の位置の少なくとも一つに関連づけられた場所情報に変換する過程を含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記場所情報が、街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つであることを特徴とする、請求項３に記載の方法。
【請求項５】
複数個の位置についての位置データが、緯度と経度または緯度、経度と高度を含むことを特徴とする、請求項1〜４のいずれか一つに記載の方法。
【請求項６】
要求が、時間に、あるいは前記複数個の位置の少なくとも一つに基づいていることを特徴とする、請求項１〜５のいずれか一つに記載の方法。
【請求項７】
要求が、位置データから演繹され、前記複数個の位置の少なくとも一つに関連づけられた場所情報に基づくことを特徴とする、請求項３または４に記載の方法。
【請求項８】
前記場所情報が、前記複数個の位置の少なくとも一つの前記位置データを、前記要求に応答して、移動体の移動についての情報を提供するために街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つに関連づける索引を含むことを特徴とする、請求項７に記載の方法。
【請求項９】
場所情報が、前記街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つを、前記要求に応答して、移動体の移動についての情報を提供するために前記複数個の位置に関連づける逆索引を含むことを特徴とする、請求項７または８に記載の方法。
【請求項１０】
前記場所情報が、前記複数個の位置の少なくとも一つを、前記要求に応答して、移動体の移動についての情報を提供するために街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つに関連づける街路図、地形図および衛星地図のうちの少なくとも一つであることを特徴とする、請求項７に記載の方法。
【請求項１１】
請求項１〜１０のいずれか一つに記載の方法において、複数個の位置についての位置データを要求に応じて情報を提供するためにアクセス可能な関連位置の複数個のクラスターに分割する過程をさらに含む、ことを特徴とする方法。
【請求項１２】
位置データを分割する過程が、関連位置の複数個のクラスターを要求に応じて移動体の移動についての情報を提供するためにそこから選択的に検索するための永続的データベース内に保存する過程を含むことを特徴とする、請求項１１に記載の方法。
【請求項１３】
前記分割過程が、地球はほぼ球形であることを計算に入れるために位置データをゆがめる予備処理過程を含むことを特徴とする、請求項１１に記載の方法。
【請求項１４】
前記分割過程が、前記予備処理過程を補正するために分割過程の出力のゆがみを戻す後処理過程を含むことを特徴とする、請求項１３に記載の方法。
【請求項１５】
前記分割過程が、新しい位置データを取得した都度分割を実施する過程を含むことを特徴とする、請求項１４に記載の方法。
【請求項１６】
請求項１１に記載の方法において、前記複数個のクラスターの一つに分類された前記複数個の位置の中から全ての位置の境界を示す周縁を決定する過程をさらに含む、ことを特徴とする方法。
【請求項１７】
地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供する装置において、
複数個の位置のそれぞれに関連する位置データを取得する手段と、
複数個の位置についての位置データを移動体の移動についての情報を提供するために要求に応じてそこから選択的に検索するための永続的データベースに保存する手段、
とから成る、ことを特徴とする装置。
【請求項１８】
特定の時間および／または位置に関する要求に応じて、前記永続的データベース内に保存された複数個の位置についての位置データにアクセスして特定の時間および／または位置に対応する移動体の移動についての情報を提供するための手段を含むことを特徴とする、請求項１７に記載の装置。
【請求項１９】
複数個の位置についての位置データを関連位置の複数個のクラスターに分割するための手段を含むことを特徴とする、請求項１７または１８に記載の装置。
【請求項２０】
前記複数個の位置のそれぞれについての個別マップを位置データに基づいて演繹する手段と、
前記複数個の個別マップを組み合わせて移動体の移動を動画にする手段、
とを含むことを特徴とする、請求項１７または１８に記載の装置。
【請求項１】
地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供する方法において、
複数個の位置のそれぞれに関連する位置データが取得される過程と、
複数個の位置についての位置データが移動体の移動についての情報を提供するために要求に応じてそこから選択的に検索するための永続的データベースに保存される過程、
とから成る、ことを特徴とする方法。
【請求項２】
複数個の位置の位置データが自動的に取得され、および／または定期的時間間隔でなされた位置測定に関係づけられることを特徴とする、請求項１に記載の方法。
【請求項３】
保存ステップが位置データを前記複数個の位置の少なくとも一つに関連づけられた場所情報に変換する過程を含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記場所情報が、街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つであることを特徴とする、請求項３に記載の方法。
【請求項５】
複数個の位置についての位置データが、緯度と経度または緯度、経度と高度を含むことを特徴とする、請求項1〜４のいずれか一つに記載の方法。
【請求項６】
要求が、時間に、あるいは前記複数個の位置の少なくとも一つに基づいていることを特徴とする、請求項１〜５のいずれか一つに記載の方法。
【請求項７】
要求が、位置データから演繹され、前記複数個の位置の少なくとも一つに関連づけられた場所情報に基づくことを特徴とする、請求項３または４に記載の方法。
【請求項８】
前記場所情報が、前記複数個の位置の少なくとも一つの前記位置データを、前記要求に応答して、移動体の移動についての情報を提供するために街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つに関連づける索引を含むことを特徴とする、請求項７に記載の方法。
【請求項９】
場所情報が、前記街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つを、前記要求に応答して、移動体の移動についての情報を提供するために前記複数個の位置に関連づける逆索引を含むことを特徴とする、請求項７または８に記載の方法。
【請求項１０】
前記場所情報が、前記複数個の位置の少なくとも一つを、前記要求に応答して、移動体の移動についての情報を提供するために街路アドレス、郵便番号、都市、州および国のうちの少なくとも一つに関連づける街路図、地形図および衛星地図のうちの少なくとも一つであることを特徴とする、請求項７に記載の方法。
【請求項１１】
請求項１〜１０のいずれか一つに記載の方法において、複数個の位置についての位置データを要求に応じて情報を提供するためにアクセス可能な関連位置の複数個のクラスターに分割する過程をさらに含む、ことを特徴とする方法。
【請求項１２】
位置データを分割する過程が、関連位置の複数個のクラスターを要求に応じて移動体の移動についての情報を提供するためにそこから選択的に検索するための永続的データベース内に保存する過程を含むことを特徴とする、請求項１１に記載の方法。
【請求項１３】
前記分割過程が、地球はほぼ球形であることを計算に入れるために位置データをゆがめる予備処理過程を含むことを特徴とする、請求項１１に記載の方法。
【請求項１４】
前記分割過程が、前記予備処理過程を補正するために分割過程の出力のゆがみを戻す後処理過程を含むことを特徴とする、請求項１３に記載の方法。
【請求項１５】
前記分割過程が、新しい位置データを取得した都度分割を実施する過程を含むことを特徴とする、請求項１４に記載の方法。
【請求項１６】
請求項１１に記載の方法において、前記複数個のクラスターの一つに分類された前記複数個の位置の中から全ての位置の境界を示す周縁を決定する過程をさらに含む、ことを特徴とする方法。
【請求項１７】
地表に沿って複数個の位置のそれぞれについて移動体の移動についての情報を提供する装置において、
複数個の位置のそれぞれに関連する位置データを取得する手段と、
複数個の位置についての位置データを移動体の移動についての情報を提供するために要求に応じてそこから選択的に検索するための永続的データベースに保存する手段、
とから成る、ことを特徴とする装置。
【請求項１８】
特定の時間および／または位置に関する要求に応じて、前記永続的データベース内に保存された複数個の位置についての位置データにアクセスして特定の時間および／または位置に対応する移動体の移動についての情報を提供するための手段を含むことを特徴とする、請求項１７に記載の装置。
【請求項１９】
複数個の位置についての位置データを関連位置の複数個のクラスターに分割するための手段を含むことを特徴とする、請求項１７または１８に記載の装置。
【請求項２０】
前記複数個の位置のそれぞれについての個別マップを位置データに基づいて演繹する手段と、
前記複数個の個別マップを組み合わせて移動体の移動を動画にする手段、
とを含むことを特徴とする、請求項１７または１８に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【公表番号】特表２００７−５１７２０３（Ｐ２００７−５１７２０３Ａ）
【公表日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願番号】特願２００６−５４６０２９（Ｐ２００６−５４６０２９）
【出願日】平成１６年１２月２０日（２００４．１２．２０）
【国際出願番号】ＰＣＴ／ＥＰ２００４／０１４５２３
【国際公開番号】ＷＯ２００５／０６４３５８
【国際公開日】平成１７年７月１４日（２００５．７．１４）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
【公表日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願日】平成１６年１２月２０日（２００４．１２．２０）
【国際出願番号】ＰＣＴ／ＥＰ２００４／０１４５２３
【国際公開番号】ＷＯ２００５／０６４３５８
【国際公開日】平成１７年７月１４日（２００５．７．１４）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
[ Back to top ]