ユーザプロファイリングのためのポジションデータの高速クラスタ化
ポジションクラスタ化の方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持することを含む。方法は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加することをさらに含む。
【発明の詳細な説明】
【分野】
【０００１】
以下の記述は、一般的に、ワイヤレス通信に関し、さらに詳細には、ポジションクラスタ化の方法に関する。
【背景】
【０００２】
ポジションクラスタ化アルゴリズムは、Ｚｈｏｕ氏らによる、データエンジニアリングに関する国際会議，５１７−５２６頁，ＩＳＢＮ＃９７８−１−４２４４−０３８２−０の“Ｍｉｎｉｎｇ Ｐｅｒｓｏｎａｌｌｙ Ｉｍｐｏｒｔａｎｔ Ｐｌａｃｅｓ ｆｒｏｍ ＧＰＳ Ｔｒａｃｋｓ”の中で提供されている。ＤＪクラスタと呼ばれるポジションクラスタ化アルゴリズムは、各ＧＰＳポイントをループさせて、特定の半径を持つ中心ポイントにおける近傍を計算できるように、各ＧＰＳポイントを記憶する。ＤＪクラスタアルゴリズムは、セル電話機上で実行するのに十分に効率的ではない。したがって、より効率的なポジションクラスタ化アルゴリズムが必要である。
【概要】
【０００３】
本開示のある態様では、ポジションクラスタ化の方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持することを含む。方法は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加することをさらに含む。
【０００４】
本開示のある態様では、ワイヤレス端末において、データのポジションクラスタ化を提供する方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持することと；ワイヤレス端末のＧＰＳ座標を周期的に取得し、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであることと；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させることと；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加することと；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージすることと；ワイヤレス端末のディスプレイ上でクラスタのセットを表示することとを含む。
【０００５】
本開示のある態様では、ワイヤレス通信のための装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加する手段とを備える。
【０００６】
本開示のある態様では、ワイヤレス通信のための装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と、装置のＧＰＳ座標を周期的に取得する手段であって、ＧＰＳ座標は、装置のポジションの緯度および経度を含み、各緯度および経度の対はポイントである手段と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させる手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加する手段と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージする手段と；装置のディスプレイ上でクラスタのセットを表示する手段とを備える。
【０００７】
本開示のある態様では、ワイヤレス通信のための装置は、処理システムを備える。処理システムは、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するように構成されている。処理システムは、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加するようにさらに構成されている。
【０００８】
本開示のある態様では、ワイヤレス通信のための装置は、処理システムを備える。処理システムは、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するようにと；ワイヤレス端末のＧＰＳ座標を周期的に取得し、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるようにと；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成するようにと；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加するようにと；取得されたポイントが、第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、クラスタのセット中の第１のクラスタと第２のクラスタとを新たなクラスタにマージするようにと；ワイヤレス端末のディスプレイ上でクラスタのセットを表示するように構成されている。
【０００９】
本開示のある態様では、コンピュータプログラムプロダクトは、コンピュータ読み取り可能媒体を具備する。コンピュータ読み取り可能媒体は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するためのコードを含む。コンピュータ読み取り可能媒体は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加するためのコードをさらに含む。
【００１０】
本開示のある態様では、コンピュータプログラムプロダクトは、コンピュータ読み取り可能媒体を具備する。コンピュータ読み取り可能媒体は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するためのコードと；ワイヤレス端末のＧＰＳ座標を周期的に取得するためのコードであって、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるコードと；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させるためのコードと；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加するためのコードと；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージするためのコードと；ワイヤレス端末のディスプレイ上でクラスタのセットを表示するためのコードとを含む。
【図面の簡単な説明】
【００１１】
【図１】図１は、例示的な装置のハードウェア構成を図示しているブロックダイヤグラムである。
【図２】図２は、例示的な方法を図示している第１のダイヤグラムである。
【図３】図３は、例示的な方法を図示している第２のダイヤグラムである。
【図４】図４は、例示的な方法を図示している第３のダイヤグラムである。
【図５】図５は、例示的な方法を図示している第４のダイヤグラムである。
【図６】図６は、例示的な方法の構成を図示している第５のダイヤグラムである。
【図７】図７は、例示的な方法のフローチャートである。
【図８】図８は、例示的な方法の別のフローチャートである。
【図９】図９は、例示的な装置のモジュールのダイヤグラムである。
【図１０】図１０は、例示的な装置の別のモジュールのダイヤグラムである。
【詳細な説明】
【００１２】
添付した図面を参照して、新規なシステム、装置および方法のさまざまな態様をこれからさらに十分に説明する。しかしながら、教示の開示は、多くの異なる形態で具現化され、本開示全体を通して提示される何らかの特定の構造または機能に限定されるものとして解釈すべきではない。むしろ、本開示が、徹底して完全なものになるように、および、本発明の範囲を当業者に十分に伝えるために、これらの態様を提供する。ここでの教示に基づいて、本開示の範囲は、別々に実現するか、または、本発明の他の何らかの態様との組み合わせで実現するかにかかわらず、ここで開示した新規なシステム、装置および方法の何らかの態様をカバーすることを意図していることを、当業者は正しく認識すべきである。例えば、ここで示す任意の数の態様を使用して、装置を実現してもよく、または、方法を実施してもよい。さらに、ここで示す本発明のさまざまな態様に加えて、あるいは、ここで示す本発明のさまざまな態様以外の、他の構造、機能性、あるいは、構造または機能性を使用して実施する、このような装置もしくは方法をカバーすることを、本発明の範囲は意図している。ここに開示した何らかの態様は、請求項のうちの１つ以上のエレメントにより具現化してもよいことを理解すべきである。
【００１３】
本発明のさまざまな態様を組み込むのに適切な装置の例は、これには限定されないが、ワイヤレスネットワーク中で動作可能なＵＥを含む。ＵＥは、移動電話機、ユーザ端末、移動局、移動デバイス、加入者局、ワイヤレスデバイス、端末、アクセス端末、ノード、ハンドヘルドデバイス、または他のいくつかの適切な専門用語で呼ばれることがある。本開示全体を通して記述したさまざまな概念は、それらの特定の学術用語に関わらず、すべての適切な装置に適用することを意図している。
【００１４】
図１を参照して、装置のさまざまな態様をこれから提示する。図１は、装置のハードウェア構成を図示している概念ブロックダイヤグラムである。装置１００は、プロセッサ１０４と、プロセッサ１０４に結合されている機械読み取り可能媒体（メモリ）１０８と、プロセッサ１０４に結合されているディスプレイ１０２と、プロセッサ１０４に結合されているトランシーバ１０６とを備える。トランシーバ１０６は、ＧＰＳ受信機を備える。プロセッサ１０４および機械読み取り可能媒体１０８は一緒に、処理システム１１０と呼ばれることがある。しかしながら、処理システム１１０は、特定のプロセッサ１０４の構成に対して、機械読み取り可能媒体１０８を有さないプロセッサ１０４を備えているかもしれない。
【００１５】
処理システム１１０は、１つ以上のプロセッサを備えていてもよい。汎用マイクロプロセッサ、マイクロ制御装置、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートウェイアレイ（ＦＰＧＡ）、プログラマブル論理デバイス（ＰＬＤ）、制御装置、状態機械、ゲート論理、ディスクリートハードウェアコンポーネント、あるいは、情報の、計算または他の操作を実行できる他の適切な何らかのエンティティの任意の組み合わせで、１つ以上のプロセッサを実現できる。
【００１６】
処理システム１１０はまた、ソフトウェアを記憶するための機械読み取り可能媒体１０８を備えていてもよい。ソフトウェアは、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、またはその他のものと呼ばれるかに関わらず、何らかの命令のタイプを意味するように広く解釈されるものとする。命令は、（例えば、ソースコードのフォーマットで、バイナリコードフォーマットで、実行可能なコードのフォーマットで、または、他の何らかの適切なコードのフォーマットで）コードを含んでいてもよい。命令は、１つ以上のプロセッサにより実行されるとき、以下に記述するさまざまな機能とともに、他のプロトコル処理機能を処理システム１１０に実行させる。
【００１７】
機械読み取り可能媒体１０８は、プロセッサのうちの１つ以上中に一体化している記憶装置を含んでいてもよい。機械読み取り可能媒体１０８はまた、ランダムアクセスメモリ（ＲＡＭ）、フラッシュメモリ、リードオンリーメモリ（ＲＯＭ）、プログラマブルリードオンリーメモリ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、または、他の何らかの適切な記憶デバイスのような、１つ以上のプロセッサの外部にある記憶装置を含んでいてもよい。さらに、機械読み取り可能媒体１０８は、データ信号をエンコードする伝送線路または搬送波を含んでいてもよい。当業者は、処理システムに対して記述した機能性をどのように実現することが最良であるかを認識するだろう。
【００１８】
図２は、例示的な方法を図示しているダイヤグラム２００である。Ｐは、処理されることになるポイントのセットであると仮定する。各ポイントは、緯度、経度、および時間で構成されており、それゆえ、特定の時間におけるＵＥ１００のロケーションを規定する。Ｃは、クラスタの集合であると仮定する。Ｐが、処理されることになるポイントの第１のセットである場合、Ｃは空のセットに初期化されている。クラスタは、長方形、重心、およびポイントの数Ｎにより規定される。長方形は、４つの値：左経度（long_l）、右経度（long_r）、下緯度（lat_b）、上緯度（lat_t）により規定される。重心は、緯度および経度により規定され、クラスタ中のポイントの平均の緯度および経度（すなわち、密度中心）である。重心は常に長方形内にある。ポイントの数Ｎは、０よりも大きい整数である。ポイントがクラスタに追加されるとき、または、２つのクラスタがマージするときに、それぞれの長方形の境界線が、２つの定数：緯度距離（dalt）および経度距離（dlong）に関して規定される。Ｐの中の各ポイントｐに対して、ＵＥ１００は、クラスタＣの集合中の各クラスタの長方形中にｐが含まれているかを決定する。ｐがクラスタにより境界をつけられる場合に、ｐはクラスタに追加される。１つより多いクラスタがｐに境界をつける場合、それらのクラスタは互いにマージされる。どのクラスタもｐに境界をつけない場合、ポイントｐを含む新たなクラスタが生成される。
【００１９】
図２中に示されているように、ポイントｐ１はいずれのクラスタによっても境界をつけられておらず、それゆえ、ポイントｐ１を含む新たなクラスタＣ１が生成される。クラスタＣ１は、重心Ｃ１により規定され、重心Ｃ１は、ポイントｐ１の緯度および経度に等しい。上緯度（C1_lat_t）および下緯度（C1_lat_b）が重心Ｃ１からのdlatであり、かつ、左経度（C1_long_l）および右経度（C1_long_r）が、重心Ｃ１からのdlongであるように、長方形の辺が設定される。クラスタＣ１中のポイントの数Ｎは、１に設定される。
【００２０】
図３は、例示的な方法を図示しているダイヤグラム３００である。図３中に示されているように、ポイントｐ２はいずれのクラスタによっても境界をつけられておらず、それゆえ、ポイントｐ２を含む新たなクラスタＣ２が生成される。クラスタＣ２は、重心Ｃ２により規定され、重心Ｃ２は、ポイントｐ２の緯度および経度に等しい。上緯度（C2_lat_t）および下緯度（C2_lat_b）が重心Ｃ２からのdlatであり、かつ、左経度（C2_long_l）および右経度（C2_long_r）が、重心Ｃ２からのdlongであるように、長方形の辺は設定される。クラスタＣ２中のポイントの数Ｎは、１に設定される。
【００２１】
図４は、例示的な方法を図示しているダイヤグラム４００である。例示的な方法により、以前にクラスタに追加されたポイントに関する情報を保持することなく、ポイントの追加により、クラスタを成長させて、再定義することが可能になる。したがって、クラスタを成長させ、再定義するのにより少ない計算が必要とされるため、例示的な方法を効率的に実現することができる。図４中に示されているように、新たなポイントｐnewはクラスタＣ１により境界をつけられ、それゆえ、クラスタＣ１に追加される。上緯度および下緯度は、これらが新たなポイントｐnewのｄｌａｔ内である場合に、調節される。左経度および右経度は、これらが新たなポイントｐnewのｄｌｏｎｇ内である場合に、調節される。まとめると、以下の調節が、上緯度、下緯度、左経度、および右経度に対して行われる：
【数１】
【００２２】
図４では、上緯度（C1_lat_t）および右経度（C1_long_r）は、それらがそれぞれ、新たなポイントｐnewからのdlatおよびdlongであるように調節されている。重心は以下のように調節される：
【数２】
【００２３】
ポイントの数Ｎは、Ｎ＋１に等しく設定される。
【００２４】
図５は、例示的な方法を図示しているダイヤグラム５００である。ポイントが１つより多いクラスタにより境界をつけられている場合、ポイントに境界をつけるクラスタはマージされる。図５中に示されているように、クラスタＣ１およびＣ２は、クラスタＣ３を形成するように一緒にマージされている。クラスタＣ３は、２つのクラスタＣ１、Ｃ２の結合である。つまり、Ｃ３の上緯度、下緯度、左経度、および右経度は、それぞれ、Ｃ１およびＣ２の上緯度のうちの一番上と、Ｃ１およびＣ２の下緯度のうちの一番下と、Ｃ１およびＣ２の左経度のうちの一番左と、Ｃ１およびＣ２の右経度のうちの一番右とに設定されている。重心Ｃ３は以下のように計算される：
【数３】
【００２５】
Ｃ３中のポイントの数Ｎは、Ｃ１中のポイントの数にＣ２中のポイントの数を加えて設定される。
【００２６】
図６は、例示的な方法の構成を図示している第５のダイヤグラムである。上記で論じたように、各ポイントは、緯度、経度、および時間に関係している。時間エレメントにより、特定の時間期間の後にクラスタを段階的に除去し、時間に依存して新たなクラスタを段階的に導入できるようになる。本質的に、最近のユーザアクティビティを表示するために、時間エレメントによって、クラスタを“フレッシュ”にすることができるようになる。１つの構成では、特定の時間期間の後にクラスタを段階的に除去し、時間期間の満了において新たなクラスタを開始する。時間期間は、例えば、６０日であってもよい。このような構成では、古いクラスタは、時間期間の後に無視され、新たなクラスタがその後、新たに取得されたＧＰＳ座標により開始される。このような構成の例が、図６のダイヤグラム６０２中に示されている。別の構成では、古いクラスタセットの満了時間が近づくにつれて、新たなクラスタセットが、新たに取得されたＧＰＳ座標により開始される。新たなクラスタセットは、古いクラスタセットが無視されるまで、ユーザに表示または提供されない。このような構成の例が、図６のダイヤグラム６０４中に示されている。ダイヤグラム６０４では、点線の時間において、特定のクラスタはユーザに表示または提供されない。
【００２７】
別の構成では、新たなクラスタセットが周期的に、例えば、６０日毎に、開始される。しかしながら、新たなクラスタセットは、最も大きな５つくらいのクラスタセットから開始される。このような構成では、最も大きな５つのクラスタセット中のポイントの数を減少させてもよい。また別の構成では、指定された時間期間の後に、新たなポイントを捕捉しないクラスタはドロップされる。
【００２８】
図７は、例示的な方法のフローチャート７００である。方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持すること（７０２）を含む。方法は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加すること（７０４）をさらに含む。
【００２９】
１つの構成では、各ポイントは、緯度、経度、および捕捉の時間を含む。１つの構成では、長方形の境界線は、第１の緯度と、第１の緯度の北の第２の緯度と、第１の経度と、第１の経度の東の第２の経度とにより規定される。１つの構成では、ポイントがクラスタに追加されるときに、長方形の境界線が以下のように調節される：
・第１の経度を引いたポイントの経度が、予め定められている経度距離よりも短いときに、第１の経度は、予め定められている経度距離を引いたポイントの経度に等しく設定される；
・ポイントの経度を引いた第２の経度が、予め定められている経度距離よりも短いときに、第２の経度は、予め定められている経度距離を加えたポイントの経度に等しく設定される；
・第１の緯度を引いたポイントの緯度が、予め定められている緯度距離よりも短いときに、第１の緯度は、予め定められている緯度距離を引いたポイントの緯度に等しく設定される；
・ポイントの緯度を引いた第２の緯度が、予め定められている緯度距離よりも短いときに、第２の緯度は、予め定められている緯度距離を加えたポイントの緯度に等しく設定される。
【００３０】
１つの構成では、ポイントがクラスタに追加されるとき、クラスタ内のポイントの数は、１だけインクリメントされる。１つの構成では、重心は、クラスタ内のポイントの平均緯度と平均経度であり、ポイントがクラスタに追加されるとき、重心は以下のように調節される：
【数４】
【００３１】
ここで、centroid.latitudeは、重心の緯度であり、centroid.longitudeは、重心の経度であり、p.latitudeは、ポイントの緯度であり、p.longitudeは、ポイントの経度であり、Ｎは、ポイントがクラスタに追加される前の、クラスタ中のポイントの数である。
【００３２】
１つの構成では、方法は、新たなポイントが、クラスタのセット中のクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させることをさらに含む。１つの構成では、新たなポイントは、緯度および経度を含み；新たなクラスタの重心は、新たなポイントの緯度および経度を含み；長方形の境界線は、予め定められている経度距離を引いた新たなポイントの経度に等しい最も西の経度と、予め定められている経度距離を加えた新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた新たなポイントの緯度に等しい最も南の緯度と、予め定められている緯度距離を加えた新たなポイントの緯度に等しい最も北の緯度とにより規定される。
【００３３】
１つの構成では、方法は、新たなポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージすることをさらに含む。１つの構成では、新たなクラスタの長方形の境界線は、第１のクラスタおよび第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定される。さらに、新たなクラスタの重心は、以下のように計算される：
【数５】
【００３４】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、新たなクラスタの重心の緯度および経度であり；C1.Nは、第１のクラスタ中のポイントの数であり；C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、第１のクラスタの重心の緯度および経度であり、C2.Nは、第２のクラスタ中のポイントの数であり；C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、第２のクラスタの重心の緯度および経度である。さらに、新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される。
【００３５】
１つの構成では、各ポイントは、緯度、経度、および時間を含み、クラスタのセットは、クラスタの経年数に基づいて維持される。１つの構成では、周期的な予め定められている時間期間の終了において、クラスタのセット中のすべてのクラスタは削除され、クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる。１つの構成では、周期的な予め定められている時間期間の終了において、クラスタのセット中のすべてのクラスタは削除され、クラスタのセットは、対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる。１つの構成では、周期的な予め定められている時間期間の終了において、クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される。クラスタの新たなセットは、削除されなかった残りのクラスタから開始できる。
【００３６】
図８は、例示的な方法のフローチャート８００である。方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持すること（８０２）と；ワイヤレス端末のＧＰＳ座標を周期的に取得し、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであること（８０４）と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させること（８０６）と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加すること（８０８）と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージすること（８１０）と；ワイヤレス端末のディスプレイ上でクラスタのセットを表示すること（８１２）とを含む。
【００３７】
図９は、例示的な装置１００のモジュールのダイヤグラム９００である。例示的な装置１００は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するモジュール９０２を備える。例示的な装置１００は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加するモジュール９０４をさらに備える。
【００３８】
図１０は、例示的な装置１００のモジュールのダイヤグラム１０００である。 例示的な装置１００は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するモジュール１００２と；ワイヤレス端末のＧＰＳ座標を周期的に取得するモジュールであって、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるモジュール１００４と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させるモジュール１００６と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加するモジュール１００８と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージするモジュール１０１０と；ワイヤレス端末のディスプレイ上でクラスタのセットを表示するモジュール１０１２とを備える。
【００３９】
１つの構成では、装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加する手段とを備える。１つの構成では、装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と、装置のＧＰＳ座標を周期的に取得する手段であって、ＧＰＳ座標は、装置のポジションの緯度および経度を含み、各緯度および経度の対はポイントである手段と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させる手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加する手段と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージする手段と；装置のディスプレイ上でクラスタのセットを表示する手段とを備える。前述した手段は、前述した手段の各々において識別される機能を実行するように構成されている処理システム１１０である。特に、プロセッサ１０４中の前述した手段は、前述した手段の各々において識別される機能を実行するように構成されている。
【００４０】
当業者が、開示の全範囲を十分に理解できるようするために、先の説明を提供している。ここで開示したさまざまな構成に対する修正は、当業者にとって容易に明らかになるだろう。したがって、特許請求の範囲は、ここで記述した開示のさまざまな態様に限定することを意図するものではなく、特許請求の範囲の文言と矛盾しない全範囲に一致させるべきである。エレメントへの単数での言及は、“１つおよび１つのみ”と特に述べられていない限り、“１つおよび１つのみ”を意味することを意図しているのではなく、むしろ“１つ以上の”を意味することを意図している。そうでないことが特に述べられていない限り、“いくつか”という用語は、１つ以上のことを指している。当業者に知られ、または後に知られることになる、本開示全体を通して記述したさまざまな態様のエレメントに対するすべての構造的および機能的な均等物は、参照によりここに明確に組み込まれ、特許請求の範囲により含まれることを意図している。さらに、ここで開示したものは、このような開示が特許請求の範囲中に明示的に記載されているか否かにかかわらず、公共に捧げられることを意図していない。どの請求項のエレメントも、エレメントが“する手段”というフレーズを使用して明確に記載されていない限り、または、方法の請求項のケースでは、エレメントが“するステップ”というフレーズを使用して記載されていない限り、合衆国法典第３５部第１１２条第６パラグラフの規定の下で解釈すべきではない。
【分野】
【０００１】
以下の記述は、一般的に、ワイヤレス通信に関し、さらに詳細には、ポジションクラスタ化の方法に関する。
【背景】
【０００２】
ポジションクラスタ化アルゴリズムは、Ｚｈｏｕ氏らによる、データエンジニアリングに関する国際会議，５１７−５２６頁，ＩＳＢＮ＃９７８−１−４２４４−０３８２−０の“Ｍｉｎｉｎｇ Ｐｅｒｓｏｎａｌｌｙ Ｉｍｐｏｒｔａｎｔ Ｐｌａｃｅｓ ｆｒｏｍ ＧＰＳ Ｔｒａｃｋｓ”の中で提供されている。ＤＪクラスタと呼ばれるポジションクラスタ化アルゴリズムは、各ＧＰＳポイントをループさせて、特定の半径を持つ中心ポイントにおける近傍を計算できるように、各ＧＰＳポイントを記憶する。ＤＪクラスタアルゴリズムは、セル電話機上で実行するのに十分に効率的ではない。したがって、より効率的なポジションクラスタ化アルゴリズムが必要である。
【概要】
【０００３】
本開示のある態様では、ポジションクラスタ化の方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持することを含む。方法は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加することをさらに含む。
【０００４】
本開示のある態様では、ワイヤレス端末において、データのポジションクラスタ化を提供する方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持することと；ワイヤレス端末のＧＰＳ座標を周期的に取得し、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであることと；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させることと；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加することと；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージすることと；ワイヤレス端末のディスプレイ上でクラスタのセットを表示することとを含む。
【０００５】
本開示のある態様では、ワイヤレス通信のための装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加する手段とを備える。
【０００６】
本開示のある態様では、ワイヤレス通信のための装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と、装置のＧＰＳ座標を周期的に取得する手段であって、ＧＰＳ座標は、装置のポジションの緯度および経度を含み、各緯度および経度の対はポイントである手段と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させる手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加する手段と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージする手段と；装置のディスプレイ上でクラスタのセットを表示する手段とを備える。
【０００７】
本開示のある態様では、ワイヤレス通信のための装置は、処理システムを備える。処理システムは、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するように構成されている。処理システムは、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加するようにさらに構成されている。
【０００８】
本開示のある態様では、ワイヤレス通信のための装置は、処理システムを備える。処理システムは、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するようにと；ワイヤレス端末のＧＰＳ座標を周期的に取得し、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるようにと；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成するようにと；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加するようにと；取得されたポイントが、第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、クラスタのセット中の第１のクラスタと第２のクラスタとを新たなクラスタにマージするようにと；ワイヤレス端末のディスプレイ上でクラスタのセットを表示するように構成されている。
【０００９】
本開示のある態様では、コンピュータプログラムプロダクトは、コンピュータ読み取り可能媒体を具備する。コンピュータ読み取り可能媒体は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するためのコードを含む。コンピュータ読み取り可能媒体は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加するためのコードをさらに含む。
【００１０】
本開示のある態様では、コンピュータプログラムプロダクトは、コンピュータ読み取り可能媒体を具備する。コンピュータ読み取り可能媒体は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するためのコードと；ワイヤレス端末のＧＰＳ座標を周期的に取得するためのコードであって、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるコードと；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させるためのコードと；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加するためのコードと；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージするためのコードと；ワイヤレス端末のディスプレイ上でクラスタのセットを表示するためのコードとを含む。
【図面の簡単な説明】
【００１１】
【図１】図１は、例示的な装置のハードウェア構成を図示しているブロックダイヤグラムである。
【図２】図２は、例示的な方法を図示している第１のダイヤグラムである。
【図３】図３は、例示的な方法を図示している第２のダイヤグラムである。
【図４】図４は、例示的な方法を図示している第３のダイヤグラムである。
【図５】図５は、例示的な方法を図示している第４のダイヤグラムである。
【図６】図６は、例示的な方法の構成を図示している第５のダイヤグラムである。
【図７】図７は、例示的な方法のフローチャートである。
【図８】図８は、例示的な方法の別のフローチャートである。
【図９】図９は、例示的な装置のモジュールのダイヤグラムである。
【図１０】図１０は、例示的な装置の別のモジュールのダイヤグラムである。
【詳細な説明】
【００１２】
添付した図面を参照して、新規なシステム、装置および方法のさまざまな態様をこれからさらに十分に説明する。しかしながら、教示の開示は、多くの異なる形態で具現化され、本開示全体を通して提示される何らかの特定の構造または機能に限定されるものとして解釈すべきではない。むしろ、本開示が、徹底して完全なものになるように、および、本発明の範囲を当業者に十分に伝えるために、これらの態様を提供する。ここでの教示に基づいて、本開示の範囲は、別々に実現するか、または、本発明の他の何らかの態様との組み合わせで実現するかにかかわらず、ここで開示した新規なシステム、装置および方法の何らかの態様をカバーすることを意図していることを、当業者は正しく認識すべきである。例えば、ここで示す任意の数の態様を使用して、装置を実現してもよく、または、方法を実施してもよい。さらに、ここで示す本発明のさまざまな態様に加えて、あるいは、ここで示す本発明のさまざまな態様以外の、他の構造、機能性、あるいは、構造または機能性を使用して実施する、このような装置もしくは方法をカバーすることを、本発明の範囲は意図している。ここに開示した何らかの態様は、請求項のうちの１つ以上のエレメントにより具現化してもよいことを理解すべきである。
【００１３】
本発明のさまざまな態様を組み込むのに適切な装置の例は、これには限定されないが、ワイヤレスネットワーク中で動作可能なＵＥを含む。ＵＥは、移動電話機、ユーザ端末、移動局、移動デバイス、加入者局、ワイヤレスデバイス、端末、アクセス端末、ノード、ハンドヘルドデバイス、または他のいくつかの適切な専門用語で呼ばれることがある。本開示全体を通して記述したさまざまな概念は、それらの特定の学術用語に関わらず、すべての適切な装置に適用することを意図している。
【００１４】
図１を参照して、装置のさまざまな態様をこれから提示する。図１は、装置のハードウェア構成を図示している概念ブロックダイヤグラムである。装置１００は、プロセッサ１０４と、プロセッサ１０４に結合されている機械読み取り可能媒体（メモリ）１０８と、プロセッサ１０４に結合されているディスプレイ１０２と、プロセッサ１０４に結合されているトランシーバ１０６とを備える。トランシーバ１０６は、ＧＰＳ受信機を備える。プロセッサ１０４および機械読み取り可能媒体１０８は一緒に、処理システム１１０と呼ばれることがある。しかしながら、処理システム１１０は、特定のプロセッサ１０４の構成に対して、機械読み取り可能媒体１０８を有さないプロセッサ１０４を備えているかもしれない。
【００１５】
処理システム１１０は、１つ以上のプロセッサを備えていてもよい。汎用マイクロプロセッサ、マイクロ制御装置、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートウェイアレイ（ＦＰＧＡ）、プログラマブル論理デバイス（ＰＬＤ）、制御装置、状態機械、ゲート論理、ディスクリートハードウェアコンポーネント、あるいは、情報の、計算または他の操作を実行できる他の適切な何らかのエンティティの任意の組み合わせで、１つ以上のプロセッサを実現できる。
【００１６】
処理システム１１０はまた、ソフトウェアを記憶するための機械読み取り可能媒体１０８を備えていてもよい。ソフトウェアは、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、またはその他のものと呼ばれるかに関わらず、何らかの命令のタイプを意味するように広く解釈されるものとする。命令は、（例えば、ソースコードのフォーマットで、バイナリコードフォーマットで、実行可能なコードのフォーマットで、または、他の何らかの適切なコードのフォーマットで）コードを含んでいてもよい。命令は、１つ以上のプロセッサにより実行されるとき、以下に記述するさまざまな機能とともに、他のプロトコル処理機能を処理システム１１０に実行させる。
【００１７】
機械読み取り可能媒体１０８は、プロセッサのうちの１つ以上中に一体化している記憶装置を含んでいてもよい。機械読み取り可能媒体１０８はまた、ランダムアクセスメモリ（ＲＡＭ）、フラッシュメモリ、リードオンリーメモリ（ＲＯＭ）、プログラマブルリードオンリーメモリ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、または、他の何らかの適切な記憶デバイスのような、１つ以上のプロセッサの外部にある記憶装置を含んでいてもよい。さらに、機械読み取り可能媒体１０８は、データ信号をエンコードする伝送線路または搬送波を含んでいてもよい。当業者は、処理システムに対して記述した機能性をどのように実現することが最良であるかを認識するだろう。
【００１８】
図２は、例示的な方法を図示しているダイヤグラム２００である。Ｐは、処理されることになるポイントのセットであると仮定する。各ポイントは、緯度、経度、および時間で構成されており、それゆえ、特定の時間におけるＵＥ１００のロケーションを規定する。Ｃは、クラスタの集合であると仮定する。Ｐが、処理されることになるポイントの第１のセットである場合、Ｃは空のセットに初期化されている。クラスタは、長方形、重心、およびポイントの数Ｎにより規定される。長方形は、４つの値：左経度（long_l）、右経度（long_r）、下緯度（lat_b）、上緯度（lat_t）により規定される。重心は、緯度および経度により規定され、クラスタ中のポイントの平均の緯度および経度（すなわち、密度中心）である。重心は常に長方形内にある。ポイントの数Ｎは、０よりも大きい整数である。ポイントがクラスタに追加されるとき、または、２つのクラスタがマージするときに、それぞれの長方形の境界線が、２つの定数：緯度距離（dalt）および経度距離（dlong）に関して規定される。Ｐの中の各ポイントｐに対して、ＵＥ１００は、クラスタＣの集合中の各クラスタの長方形中にｐが含まれているかを決定する。ｐがクラスタにより境界をつけられる場合に、ｐはクラスタに追加される。１つより多いクラスタがｐに境界をつける場合、それらのクラスタは互いにマージされる。どのクラスタもｐに境界をつけない場合、ポイントｐを含む新たなクラスタが生成される。
【００１９】
図２中に示されているように、ポイントｐ１はいずれのクラスタによっても境界をつけられておらず、それゆえ、ポイントｐ１を含む新たなクラスタＣ１が生成される。クラスタＣ１は、重心Ｃ１により規定され、重心Ｃ１は、ポイントｐ１の緯度および経度に等しい。上緯度（C1_lat_t）および下緯度（C1_lat_b）が重心Ｃ１からのdlatであり、かつ、左経度（C1_long_l）および右経度（C1_long_r）が、重心Ｃ１からのdlongであるように、長方形の辺が設定される。クラスタＣ１中のポイントの数Ｎは、１に設定される。
【００２０】
図３は、例示的な方法を図示しているダイヤグラム３００である。図３中に示されているように、ポイントｐ２はいずれのクラスタによっても境界をつけられておらず、それゆえ、ポイントｐ２を含む新たなクラスタＣ２が生成される。クラスタＣ２は、重心Ｃ２により規定され、重心Ｃ２は、ポイントｐ２の緯度および経度に等しい。上緯度（C2_lat_t）および下緯度（C2_lat_b）が重心Ｃ２からのdlatであり、かつ、左経度（C2_long_l）および右経度（C2_long_r）が、重心Ｃ２からのdlongであるように、長方形の辺は設定される。クラスタＣ２中のポイントの数Ｎは、１に設定される。
【００２１】
図４は、例示的な方法を図示しているダイヤグラム４００である。例示的な方法により、以前にクラスタに追加されたポイントに関する情報を保持することなく、ポイントの追加により、クラスタを成長させて、再定義することが可能になる。したがって、クラスタを成長させ、再定義するのにより少ない計算が必要とされるため、例示的な方法を効率的に実現することができる。図４中に示されているように、新たなポイントｐnewはクラスタＣ１により境界をつけられ、それゆえ、クラスタＣ１に追加される。上緯度および下緯度は、これらが新たなポイントｐnewのｄｌａｔ内である場合に、調節される。左経度および右経度は、これらが新たなポイントｐnewのｄｌｏｎｇ内である場合に、調節される。まとめると、以下の調節が、上緯度、下緯度、左経度、および右経度に対して行われる：
【数１】
【００２２】
図４では、上緯度（C1_lat_t）および右経度（C1_long_r）は、それらがそれぞれ、新たなポイントｐnewからのdlatおよびdlongであるように調節されている。重心は以下のように調節される：
【数２】
【００２３】
ポイントの数Ｎは、Ｎ＋１に等しく設定される。
【００２４】
図５は、例示的な方法を図示しているダイヤグラム５００である。ポイントが１つより多いクラスタにより境界をつけられている場合、ポイントに境界をつけるクラスタはマージされる。図５中に示されているように、クラスタＣ１およびＣ２は、クラスタＣ３を形成するように一緒にマージされている。クラスタＣ３は、２つのクラスタＣ１、Ｃ２の結合である。つまり、Ｃ３の上緯度、下緯度、左経度、および右経度は、それぞれ、Ｃ１およびＣ２の上緯度のうちの一番上と、Ｃ１およびＣ２の下緯度のうちの一番下と、Ｃ１およびＣ２の左経度のうちの一番左と、Ｃ１およびＣ２の右経度のうちの一番右とに設定されている。重心Ｃ３は以下のように計算される：
【数３】
【００２５】
Ｃ３中のポイントの数Ｎは、Ｃ１中のポイントの数にＣ２中のポイントの数を加えて設定される。
【００２６】
図６は、例示的な方法の構成を図示している第５のダイヤグラムである。上記で論じたように、各ポイントは、緯度、経度、および時間に関係している。時間エレメントにより、特定の時間期間の後にクラスタを段階的に除去し、時間に依存して新たなクラスタを段階的に導入できるようになる。本質的に、最近のユーザアクティビティを表示するために、時間エレメントによって、クラスタを“フレッシュ”にすることができるようになる。１つの構成では、特定の時間期間の後にクラスタを段階的に除去し、時間期間の満了において新たなクラスタを開始する。時間期間は、例えば、６０日であってもよい。このような構成では、古いクラスタは、時間期間の後に無視され、新たなクラスタがその後、新たに取得されたＧＰＳ座標により開始される。このような構成の例が、図６のダイヤグラム６０２中に示されている。別の構成では、古いクラスタセットの満了時間が近づくにつれて、新たなクラスタセットが、新たに取得されたＧＰＳ座標により開始される。新たなクラスタセットは、古いクラスタセットが無視されるまで、ユーザに表示または提供されない。このような構成の例が、図６のダイヤグラム６０４中に示されている。ダイヤグラム６０４では、点線の時間において、特定のクラスタはユーザに表示または提供されない。
【００２７】
別の構成では、新たなクラスタセットが周期的に、例えば、６０日毎に、開始される。しかしながら、新たなクラスタセットは、最も大きな５つくらいのクラスタセットから開始される。このような構成では、最も大きな５つのクラスタセット中のポイントの数を減少させてもよい。また別の構成では、指定された時間期間の後に、新たなポイントを捕捉しないクラスタはドロップされる。
【００２８】
図７は、例示的な方法のフローチャート７００である。方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持すること（７０２）を含む。方法は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加すること（７０４）をさらに含む。
【００２９】
１つの構成では、各ポイントは、緯度、経度、および捕捉の時間を含む。１つの構成では、長方形の境界線は、第１の緯度と、第１の緯度の北の第２の緯度と、第１の経度と、第１の経度の東の第２の経度とにより規定される。１つの構成では、ポイントがクラスタに追加されるときに、長方形の境界線が以下のように調節される：
・第１の経度を引いたポイントの経度が、予め定められている経度距離よりも短いときに、第１の経度は、予め定められている経度距離を引いたポイントの経度に等しく設定される；
・ポイントの経度を引いた第２の経度が、予め定められている経度距離よりも短いときに、第２の経度は、予め定められている経度距離を加えたポイントの経度に等しく設定される；
・第１の緯度を引いたポイントの緯度が、予め定められている緯度距離よりも短いときに、第１の緯度は、予め定められている緯度距離を引いたポイントの緯度に等しく設定される；
・ポイントの緯度を引いた第２の緯度が、予め定められている緯度距離よりも短いときに、第２の緯度は、予め定められている緯度距離を加えたポイントの緯度に等しく設定される。
【００３０】
１つの構成では、ポイントがクラスタに追加されるとき、クラスタ内のポイントの数は、１だけインクリメントされる。１つの構成では、重心は、クラスタ内のポイントの平均緯度と平均経度であり、ポイントがクラスタに追加されるとき、重心は以下のように調節される：
【数４】
【００３１】
ここで、centroid.latitudeは、重心の緯度であり、centroid.longitudeは、重心の経度であり、p.latitudeは、ポイントの緯度であり、p.longitudeは、ポイントの経度であり、Ｎは、ポイントがクラスタに追加される前の、クラスタ中のポイントの数である。
【００３２】
１つの構成では、方法は、新たなポイントが、クラスタのセット中のクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させることをさらに含む。１つの構成では、新たなポイントは、緯度および経度を含み；新たなクラスタの重心は、新たなポイントの緯度および経度を含み；長方形の境界線は、予め定められている経度距離を引いた新たなポイントの経度に等しい最も西の経度と、予め定められている経度距離を加えた新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた新たなポイントの緯度に等しい最も南の緯度と、予め定められている緯度距離を加えた新たなポイントの緯度に等しい最も北の緯度とにより規定される。
【００３３】
１つの構成では、方法は、新たなポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージすることをさらに含む。１つの構成では、新たなクラスタの長方形の境界線は、第１のクラスタおよび第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定される。さらに、新たなクラスタの重心は、以下のように計算される：
【数５】
【００３４】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、新たなクラスタの重心の緯度および経度であり；C1.Nは、第１のクラスタ中のポイントの数であり；C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、第１のクラスタの重心の緯度および経度であり、C2.Nは、第２のクラスタ中のポイントの数であり；C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、第２のクラスタの重心の緯度および経度である。さらに、新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される。
【００３５】
１つの構成では、各ポイントは、緯度、経度、および時間を含み、クラスタのセットは、クラスタの経年数に基づいて維持される。１つの構成では、周期的な予め定められている時間期間の終了において、クラスタのセット中のすべてのクラスタは削除され、クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる。１つの構成では、周期的な予め定められている時間期間の終了において、クラスタのセット中のすべてのクラスタは削除され、クラスタのセットは、対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる。１つの構成では、周期的な予め定められている時間期間の終了において、クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される。クラスタの新たなセットは、削除されなかった残りのクラスタから開始できる。
【００３６】
図８は、例示的な方法のフローチャート８００である。方法は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持すること（８０２）と；ワイヤレス端末のＧＰＳ座標を周期的に取得し、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであること（８０４）と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させること（８０６）と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加すること（８０８）と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージすること（８１０）と；ワイヤレス端末のディスプレイ上でクラスタのセットを表示すること（８１２）とを含む。
【００３７】
図９は、例示的な装置１００のモジュールのダイヤグラム９００である。例示的な装置１００は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するモジュール９０２を備える。例示的な装置１００は、クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加するモジュール９０４をさらに備える。
【００３８】
図１０は、例示的な装置１００のモジュールのダイヤグラム１０００である。 例示的な装置１００は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持するモジュール１００２と；ワイヤレス端末のＧＰＳ座標を周期的に取得するモジュールであって、ＧＰＳ座標は、ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるモジュール１００４と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させるモジュール１００６と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加するモジュール１００８と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージするモジュール１０１０と；ワイヤレス端末のディスプレイ上でクラスタのセットを表示するモジュール１０１２とを備える。
【００３９】
１つの構成では、装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、クラスタのセット中のクラスタにポイントを追加する手段とを備える。１つの構成では、装置は、クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、クラスタのセットを維持する手段と、装置のＧＰＳ座標を周期的に取得する手段であって、ＧＰＳ座標は、装置のポジションの緯度および経度を含み、各緯度および経度の対はポイントである手段と；取得されたポイントが、クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、クラスタのセット中に新たなクラスタを生成させる手段と；クラスタが、クラスタの長方形の境界線と、クラスタ内の重心と、クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、クラスタのセット中のクラスタに取得されたポイントを追加する手段と；取得されたポイントが、クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、第１のクラスタと第２のクラスタとを新たなクラスタにマージする手段と；装置のディスプレイ上でクラスタのセットを表示する手段とを備える。前述した手段は、前述した手段の各々において識別される機能を実行するように構成されている処理システム１１０である。特に、プロセッサ１０４中の前述した手段は、前述した手段の各々において識別される機能を実行するように構成されている。
【００４０】
当業者が、開示の全範囲を十分に理解できるようするために、先の説明を提供している。ここで開示したさまざまな構成に対する修正は、当業者にとって容易に明らかになるだろう。したがって、特許請求の範囲は、ここで記述した開示のさまざまな態様に限定することを意図するものではなく、特許請求の範囲の文言と矛盾しない全範囲に一致させるべきである。エレメントへの単数での言及は、“１つおよび１つのみ”と特に述べられていない限り、“１つおよび１つのみ”を意味することを意図しているのではなく、むしろ“１つ以上の”を意味することを意図している。そうでないことが特に述べられていない限り、“いくつか”という用語は、１つ以上のことを指している。当業者に知られ、または後に知られることになる、本開示全体を通して記述したさまざまな態様のエレメントに対するすべての構造的および機能的な均等物は、参照によりここに明確に組み込まれ、特許請求の範囲により含まれることを意図している。さらに、ここで開示したものは、このような開示が特許請求の範囲中に明示的に記載されているか否かにかかわらず、公共に捧げられることを意図していない。どの請求項のエレメントも、エレメントが“する手段”というフレーズを使用して明確に記載されていない限り、または、方法の請求項のケースでは、エレメントが“するステップ”というフレーズを使用して記載されていない限り、合衆国法典第３５部第１１２条第６パラグラフの規定の下で解釈すべきではない。
【特許請求の範囲】
【請求項１】
ポジションクラスタ化の方法において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持することと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加することとを含む方法。
【請求項２】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項１記載の方法。
【請求項３】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項２記載の方法。
【請求項４】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項３記載の方法。
【請求項５】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項１記載の方法。
【請求項６】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数１】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項１記載の方法。
【請求項７】
新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させることをさらに含む請求項１記載の方法。
【請求項８】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項７記載の方法。
【請求項９】
新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージすることをさらに含む請求項１記載の方法。
【請求項１０】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数２】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項９記載の方法。
【請求項１１】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項１記載の方法。
【請求項１２】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項１１記載の方法。
【請求項１３】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項１１記載の方法。
【請求項１４】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項１１記載の方法。
【請求項１５】
ワイヤレス端末において、データのポジションクラスタ化を提供する方法において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持することと、
前記ワイヤレス端末のＧＰＳ座標を周期的に取得し、前記ＧＰＳ座標は、前記ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであることと、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させることと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加することと、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージすることと、
前記ワイヤレス端末のディスプレイ上に前記クラスタのセットを表示することとを含む方法。
【請求項１６】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持する手段と、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加する手段とを具備する装置。
【請求項１７】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項１６記載の装置。
【請求項１８】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項１７記載の装置。
【請求項１９】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項１８記載の装置。
【請求項２０】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項１６記載の装置。
【請求項２１】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数３】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項１６記載の装置。
【請求項２２】
新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させる手段をさらに具備する請求項１６記載の装置。
【請求項２３】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項２２記載の装置。
【請求項２４】
新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージする手段をさらに具備する請求項１６記載の装置。
【請求項２５】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数４】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項２４記載の装置。
【請求項２６】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項１６記載の装置。
【請求項２７】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項２６記載の装置。
【請求項２８】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項２６記載の装置。
【請求項２９】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項２６記載の装置。
【請求項３０】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持する手段と、
前記装置のＧＰＳ座標を周期的に取得する手段であって、前記ＧＰＳ座標は、前記装置のポジションの緯度および経度を含み、各緯度および経度の対はポイントである手段と、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させる手段と、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加する手段と、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージする手段と、
前記装置のディスプレイ上に前記クラスタのセットを表示する手段とを具備する装置。
【請求項３１】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持し、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加するように構成されている処理システムを具備する装置。
【請求項３２】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項３１記載の装置。
【請求項３３】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項３２記載の装置。
【請求項３４】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項３３記載の装置。
【請求項３５】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項３１記載の装置。
【請求項３６】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数５】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項３１記載の装置。
【請求項３７】
前記処理システムは、新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるようにさらに構成されている請求項３１記載の装置。
【請求項３８】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項３７記載の装置。
【請求項３９】
前記処理システムは、新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするようにさらに構成されている請求項３１記載の装置。
【請求項４０】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数６】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項３９記載の装置。
【請求項４１】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項３１記載の装置。
【請求項４２】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項４１記載の装置。
【請求項４３】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項４１記載の装置。
【請求項４４】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項４１記載の装置。
【請求項４５】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持するようにと、
前記ワイヤレス端末のＧＰＳ座標を周期的に取得し、前記ＧＰＳ座標は、前記ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるようにと、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるようにと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加するようにと、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするようにと、
前記ワイヤレス端末のディスプレイ上に前記クラスタのセットを表示するように構成されている処理システムを具備する装置。
【請求項４６】
コンピュータプログラムプロダクトにおいて、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持するためのコードと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加するためのコードとを含むコンピュータ読み取り可能媒体を具備するコンピュータプログラムプロダクト。
【請求項４７】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項４６記載のコンピュータプログラムプロダクト。
【請求項４８】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項４７記載のコンピュータプログラムプロダクト。
【請求項４９】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項４８記載のコンピュータプログラムプロダクト。
【請求項５０】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項４６記載のコンピュータプログラムプロダクト。
【請求項５１】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数７】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項４６記載のコンピュータプログラムプロダクト。
【請求項５２】
前記コンピュータ読み取り可能媒体は、新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるためのコードをさらに含む請求項４６記載のコンピュータプログラムプロダクト。
【請求項５３】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項５２記載のコンピュータプログラムプロダクト。
【請求項５４】
前記コンピュータ読み取り可能媒体は、新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするためのコードをさらに含む請求項４６記載のコンピュータプログラムプロダクト。
【請求項５５】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数８】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項５４記載のコンピュータプログラムプロダクト。
【請求項５６】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項４６記載のコンピュータプログラムプロダクト。
【請求項５７】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項５６記載のコンピュータプログラムプロダクト。
【請求項５８】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項５６記載のコンピュータプログラムプロダクト。
【請求項５９】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項５６記載のコンピュータプログラムプロダクト。
【請求項６０】
コンピュータプログラムプロダクトにおいて、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持するためのコードと、
ワイヤレス端末のＧＰＳ座標を周期的に取得するためのコードであって、前記ＧＰＳ座標は、前記ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるコードと、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるためのコードと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加するためのコードと、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするためのコードと、
前記ワイヤレス端末のディスプレイ上に前記クラスタのセットを表示するためのコードとを含むコンピュータ読み取り可能媒体を具備するコンピュータプログラムプロダクト。
【請求項１】
ポジションクラスタ化の方法において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持することと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加することとを含む方法。
【請求項２】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項１記載の方法。
【請求項３】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項２記載の方法。
【請求項４】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項３記載の方法。
【請求項５】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項１記載の方法。
【請求項６】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数１】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項１記載の方法。
【請求項７】
新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させることをさらに含む請求項１記載の方法。
【請求項８】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項７記載の方法。
【請求項９】
新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージすることをさらに含む請求項１記載の方法。
【請求項１０】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数２】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項９記載の方法。
【請求項１１】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項１記載の方法。
【請求項１２】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項１１記載の方法。
【請求項１３】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項１１記載の方法。
【請求項１４】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項１１記載の方法。
【請求項１５】
ワイヤレス端末において、データのポジションクラスタ化を提供する方法において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持することと、
前記ワイヤレス端末のＧＰＳ座標を周期的に取得し、前記ＧＰＳ座標は、前記ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであることと、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させることと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加することと、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージすることと、
前記ワイヤレス端末のディスプレイ上に前記クラスタのセットを表示することとを含む方法。
【請求項１６】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持する手段と、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加する手段とを具備する装置。
【請求項１７】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項１６記載の装置。
【請求項１８】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項１７記載の装置。
【請求項１９】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項１８記載の装置。
【請求項２０】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項１６記載の装置。
【請求項２１】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数３】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項１６記載の装置。
【請求項２２】
新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させる手段をさらに具備する請求項１６記載の装置。
【請求項２３】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項２２記載の装置。
【請求項２４】
新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージする手段をさらに具備する請求項１６記載の装置。
【請求項２５】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数４】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項２４記載の装置。
【請求項２６】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項１６記載の装置。
【請求項２７】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項２６記載の装置。
【請求項２８】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項２６記載の装置。
【請求項２９】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項２６記載の装置。
【請求項３０】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持する手段と、
前記装置のＧＰＳ座標を周期的に取得する手段であって、前記ＧＰＳ座標は、前記装置のポジションの緯度および経度を含み、各緯度および経度の対はポイントである手段と、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させる手段と、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加する手段と、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージする手段と、
前記装置のディスプレイ上に前記クラスタのセットを表示する手段とを具備する装置。
【請求項３１】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持し、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加するように構成されている処理システムを具備する装置。
【請求項３２】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項３１記載の装置。
【請求項３３】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項３２記載の装置。
【請求項３４】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項３３記載の装置。
【請求項３５】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項３１記載の装置。
【請求項３６】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数５】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項３１記載の装置。
【請求項３７】
前記処理システムは、新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるようにさらに構成されている請求項３１記載の装置。
【請求項３８】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項３７記載の装置。
【請求項３９】
前記処理システムは、新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするようにさらに構成されている請求項３１記載の装置。
【請求項４０】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数６】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項３９記載の装置。
【請求項４１】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項３１記載の装置。
【請求項４２】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項４１記載の装置。
【請求項４３】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項４１記載の装置。
【請求項４４】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項４１記載の装置。
【請求項４５】
ワイヤレス通信のための装置において、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持するようにと、
前記ワイヤレス端末のＧＰＳ座標を周期的に取得し、前記ＧＰＳ座標は、前記ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるようにと、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるようにと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加するようにと、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするようにと、
前記ワイヤレス端末のディスプレイ上に前記クラスタのセットを表示するように構成されている処理システムを具備する装置。
【請求項４６】
コンピュータプログラムプロダクトにおいて、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持するためのコードと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、ポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記ポイントを追加するためのコードとを含むコンピュータ読み取り可能媒体を具備するコンピュータプログラムプロダクト。
【請求項４７】
各ポイントは、緯度、経度、および捕捉の時間を含む請求項４６記載のコンピュータプログラムプロダクト。
【請求項４８】
前記長方形の境界線は、第１の緯度と、前記第１の緯度の北の第２の緯度と、第１の経度と、前記第１の経度の東の第２の経度とにより規定される請求項４７記載のコンピュータプログラムプロダクト。
【請求項４９】
前記ポイントが前記クラスタに追加されるときに、前記長方形の境界線は、
前記第１の経度を引いた前記ポイントの経度が、予め定められている経度距離よりも短いときに、前記第１の経度は、前記予め定められている経度距離を引いた前記ポイントの経度に等しく設定され、
前記ポイントの経度を引いた前記第２の経度が、前記予め定められている経度距離よりも短いときに、前記第２の経度は、前記予め定められている経度距離を加えた前記ポイントの経度に等しく設定され、
前記第１の緯度を引いた前記ポイントの緯度が、予め定められている緯度距離よりも短いときに、前記第１の緯度は、予め定められている緯度距離を引いた前記ポイントの緯度に等しく設定され、
前記ポイントの緯度を引いた前記第２の緯度が、前記予め定められている緯度距離よりも短いときに、前記第２の緯度は、前記予め定められている緯度距離を加えた前記ポイントの緯度に等しく設定されるように調節される請求項４８記載のコンピュータプログラムプロダクト。
【請求項５０】
前記ポイントが前記クラスタに追加されるとき、前記クラスタ内のポイントの数は、１だけインクリメントされる請求項４６記載のコンピュータプログラムプロダクト。
【請求項５１】
前記重心は、前記クラスタ内の前記ポイントの平均緯度と平均経度であり、前記ポイントが前記クラスタに追加されるとき、前記重心は以下のように調節され、
【数７】
ここで、centroid.latitudeは、前記重心の緯度であり、centroid.longitudeは、前記重心の経度であり、p.latitudeは、前記ポイントの緯度であり、p.longitudeは、前記ポイントの経度であり、Ｎは、前記ポイントが前記クラスタに追加される前の、前記クラスタ中のポイントの数である請求項４６記載のコンピュータプログラムプロダクト。
【請求項５２】
前記コンピュータ読み取り可能媒体は、新たなポイントが、前記クラスタのセット中のクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるためのコードをさらに含む請求項４６記載のコンピュータプログラムプロダクト。
【請求項５３】
前記新たなポイントは、緯度および経度を含み、
前記新たなクラスタの重心は、前記新たなポイントの緯度および経度を含み、
前記長方形の境界線は、予め定められている経度距離を引いた前記新たなポイントの経度に等しい最も西の経度と、前記予め定められている経度距離を加えた前記新たなポイントの経度に等しい最も東の経度と、予め定められている緯度距離を引いた前記新たなポイントの緯度に等しい最も南の緯度と、前記予め定められている緯度距離を加えた前記新たなポイントの緯度に等しい最も北の緯度とにより規定される請求項５２記載のコンピュータプログラムプロダクト。
【請求項５４】
前記コンピュータ読み取り可能媒体は、新たなポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするためのコードをさらに含む請求項４６記載のコンピュータプログラムプロダクト。
【請求項５５】
前記新たなクラスタの長方形の境界線は、前記第１のクラスタおよび前記第２のクラスタの、最も北の緯度と、最も南の緯度と、最も西の経度と、最も東の経度とにそれぞれ等しい、北緯度と、南緯度と、西経度と、東経度とより規定され、
前記新たなクラスタの重心は、以下のように計算され、
【数８】
ここで、centroid.latitudeおよびcentroid.longitudeは、それぞれ、前記新たなクラスタの重心の緯度および経度であり、C1.Nは、前記第１のクラスタ中のポイントの数であり、C1.centroid.latitudeおよびC1.centroid.longitudeは、それぞれ、前記第１のクラスタの重心の緯度および経度であり、C2.Nは、前記第２のクラスタ中のポイントの数であり、C2.centroid.latitudeおよびC2.centroid.longitudeは、それぞれ、前記第２のクラスタの重心の緯度および経度であり、
前記新たなクラスタのポイントの数Ｎは、Ｎ＝Ｃ１．Ｎ＋Ｃ２．Ｎのように計算される請求項５４記載のコンピュータプログラムプロダクト。
【請求項５６】
各ポイントは、緯度、経度および時間を含み、前記クラスタのセットは、前記クラスタの経年数に基づいて維持される請求項４６記載のコンピュータプログラムプロダクト。
【請求項５７】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、新たに捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項５６記載のコンピュータプログラムプロダクト。
【請求項５８】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中のすべてのクラスタが削除され、前記クラスタのセットは、前記対応する予め定められている時間期間の終了より前の時間期間中に捕捉されたポイントにより形成された新たなクラスタによりポピュレートされる請求項５６記載のコンピュータプログラムプロダクト。
【請求項５９】
周期的な予め定められている時間期間の終了において、前記クラスタのセット中の、最も少ない数のポイントを持つクラスタのセットが削除される請求項５６記載のコンピュータプログラムプロダクト。
【請求項６０】
コンピュータプログラムプロダクトにおいて、
クラスタのセット中の各クラスタの長方形の境界線と、各クラスタ内の重心と、各クラスタ内のポイントの数とを記憶させることにより、前記クラスタのセットを維持するためのコードと、
ワイヤレス端末のＧＰＳ座標を周期的に取得するためのコードであって、前記ＧＰＳ座標は、前記ワイヤレス端末のポジションの緯度および経度を含み、各緯度および経度の対はポイントであるコードと、
取得されたポイントが、前記クラスタのセット中の何らかのクラスタにより境界をつけられていないときに、前記クラスタのセット中に新たなクラスタを生成させるためのコードと、
クラスタが、前記クラスタの長方形の境界線と、前記クラスタ内の重心と、前記クラスタ内のポイントの数とを調節することにより、取得されたポイントに境界をつけるときに、前記クラスタのセット中の前記クラスタに前記取得されたポイントを追加するためのコードと、
取得されたポイントが、前記クラスタのセット中の第１のクラスタおよび第２のクラスタの各々により境界をつけられているときに、前記第１のクラスタと前記第２のクラスタとを新たなクラスタにマージするためのコードと、
前記ワイヤレス端末のディスプレイ上に前記クラスタのセットを表示するためのコードとを含むコンピュータ読み取り可能媒体を具備するコンピュータプログラムプロダクト。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２０１３−５２１５０１（Ｐ２０１３−５２１５０１Ａ）
【公表日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１２−５５６１８１（Ｐ２０１２−５５６１８１）
【出願日】平成２３年３月１日（２０１１．３．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２６７３７
【国際公開番号】ＷＯ２０１１／１０９４３０
【国際公開日】平成２３年９月９日（２０１１．９．９）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
【公表日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年３月１日（２０１１．３．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２６７３７
【国際公開番号】ＷＯ２０１１／１０９４３０
【国際公開日】平成２３年９月９日（２０１１．９．９）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
[ Back to top ]