(57)【要約】  本開示は、データ点のストリームをクラスタリングすることを対象とする。ある態様は、データ点のストリームを受信し、複数のクラスタ重心を決定し、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割し、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当て、複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成する。ある態様は、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当て、ここで複数のスレッドおよび/またはプロセッサの各々は、1つまたは複数のクラスタ重心を決定し、1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成し、複数のスレッドおよび/またはプロセッサの各々からの1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成する。
2016530591.tif 000002
【特許請求の範囲】
【請求項１】
データ点のストリームをクラスタリングするための方法であって、
前記データ点のストリームを受信するステップと、
複数のクラスタ重心を決定するステップと、
前記複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するステップと、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てるステップと、
前記複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するステップとを含む方法。
【請求項２】
受信する前記ステップが、
1つまたは複数のセンサから前記データ点のストリームを受信するステップを含む、請求項1に記載の方法。
【請求項３】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項2に記載の方法。
【請求項４】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサにラウンドロビン方式で割り当てられる、請求項1に記載の方法。
【請求項５】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサに階層的に割り当てられる、請求項1に記載の方法。
【請求項６】
前記データ点のストリームの前記一部分を割り当てる前記ステップが、
受信したデータ点を、前記複数のクラスタ重心のうちの1つに割り当てるステップと、
前記受信したデータ点を、前記複数のクラスタ重心のうちの前記1つに対応するスレッドまたはプロセッサに割り当てるステップとを含む、請求項5に記載の方法。
【請求項７】
前記複数のクラスタ重心中のクラスタ重心の数が、スレッドおよび/またはプロセッサの数に対応する、請求項6に記載の方法。
【請求項８】
前記複数のクラスタ重心中のクラスタ重心の数がスレッドおよび/またはプロセッサの数よりも多く、前記受信したデータ点が、前記複数のクラスタ重心の各クラスタ重心に関連したデータ点のカウントに基づいてスレッドまたはプロセッサに割り当てられる、請求項6に記載の方法。
【請求項９】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサの各々の速度に基づいて、前記複数のスレッドおよび/またはプロセッサに割り当てられる、請求項1に記載の方法。
【請求項１０】
前記複数のスレッドおよび/またはプロセッサの各々が、前記複数のスレッドおよび/またはプロセッサの各々にプロビジョニングされる、1つまたは複数の重心の周囲に1つまたは複数のクラスタを生成する、請求項1に記載の方法。
【請求項１１】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項10に記載の方法。
【請求項１２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、データ点の前記一部分の1つまたは複数のデータ点をバッファリングする、請求項10に記載の方法。
【請求項１３】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするステップをさらに含む、請求項1に記載の方法。
【請求項１４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるステップをさらに含む、請求項1に記載の方法。
【請求項１５】
クラスタの前記大域的ユニバースに対して後処理を実施するステップをさらに含む、請求項1に記載の方法。
【請求項１６】
前記複数のプロセッサおよび/またはスレッドがユーザ機器上に存在する、請求項1に記載の方法。
【請求項１７】
前記複数のプロセッサおよび/またはスレッドが複数のユーザ機器上に存在する、請求項1に記載の方法。
【請求項１８】
データ点のストリームをクラスタリングするための方法であって、
前記データ点のストリームを受信するステップと、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるステップであって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、ステップと、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するステップとを含む方法。
【請求項１９】
受信する前記ステップが、
1つまたは複数のセンサから前記データ点のストリームを受信するステップを含む、請求項18に記載の方法。
【請求項２０】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項19に記載の方法。
【請求項２１】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項18に記載の方法。
【請求項２２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、データ点の前記一部分の1つまたは複数のデータ点をバッファリングする、請求項18に記載の方法。
【請求項２３】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするステップをさらに含む、請求項18に記載の方法。
【請求項２４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるステップをさらに含む、請求項18に記載の方法。
【請求項２５】
複数のクラスタ重心を決定するステップと、
前記複数のクラスタ重心を前記複数のスレッドおよび/またはプロセッサの間で分割するステップとをさらに含む、請求項18に記載の方法。
【請求項２６】
前記複数のクラスタ重心が、クラスタ重心に加え、前記複数のスレッドおよび/またはプロセッサによって決定される、請求項25に記載の方法。
【請求項２７】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの、各々に割り当てられた部分に基づいて、前記1つまたは複数のクラスタ重心を決定する、請求項18に記載の方法。
【請求項２８】
前記複数のスレッドおよび/またはプロセッサの各々から、前記データ点のストリームのクラスタリング部分を受信するステップをさらに含む、請求項18に記載の方法。
【請求項２９】
クラスタの前記大域的ユニバースに対して後処理を実施するステップをさらに含む、請求項18に記載の方法。
【請求項３０】
前記複数のスレッドおよび/またはプロセッサがモバイルデバイス上に存在する、請求項18に記載の方法。
【請求項３１】
前記複数のスレッドおよび/またはプロセッサが複数のモバイルデバイス上に存在する、請求項18に記載の方法。
【請求項３２】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するように構成された論理手段と、
複数のクラスタ重心を決定するように構成された論理手段と、
前記複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するように構成された論理手段と、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段と、
前記複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するように構成された論理手段とを備える装置。
【請求項３３】
受信するように構成された前記論理手段が、
1つまたは複数のセンサから前記データ点のストリームを受信するように構成された論理手段を備える、請求項32に記載の装置。
【請求項３４】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項33に記載の装置。
【請求項３５】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサにラウンドロビン方式で割り当てられる、請求項32に記載の装置。
【請求項３６】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサに階層的に割り当てられる、請求項32に記載の装置。
【請求項３７】
前記データ点のストリームの前記一部分を割り当てるように構成された前記論理手段が、
受信したデータ点を、前記複数のクラスタ重心のうちの1つに割り当てるように構成された論理手段と、
前記受信したデータ点を、前記複数のクラスタ重心のうちの前記1つに対応するスレッドまたはプロセッサに割り当てるように構成された論理手段とを備える、請求項36に記載の装置。
【請求項３８】
前記複数のクラスタ重心中のクラスタ重心の数が、スレッドおよび/またはプロセッサの数に対応する、請求項37に記載の装置。
【請求項３９】
前記複数のクラスタ重心中のクラスタ重心の数がスレッドおよび/またはプロセッサの数よりも多く、前記受信したデータ点が、前記クラスタ重心のセットの各クラスタ重心に関連したデータ点のカウントに基づいてスレッドまたはプロセッサに割り当てられる、請求項37に記載の装置。
【請求項４０】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサの各々の速度に基づいて、前記複数のスレッドおよび/またはプロセッサに割り当てられる、請求項32に記載の装置。
【請求項４１】
前記複数のスレッドおよび/またはプロセッサの各々が、前記複数のスレッドおよび/またはプロセッサの各々にプロビジョニングされる、1つまたは複数の重心の周囲に1つまたは複数のクラスタを生成する、請求項32に記載の装置。
【請求項４２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項41に記載の装置。
【請求項４３】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、前記データ点のストリームの前記一部分の1つまたは複数のデータ点をバッファリングする、請求項41に記載の装置。
【請求項４４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするように構成された論理手段をさらに備える、請求項32に記載の装置。
【請求項４５】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるように構成された論理手段をさらに備える、請求項32に記載の装置。
【請求項４６】
クラスタの前記大域的ユニバースに対して後処理を実施するように構成された論理手段をさらに備える、請求項32に記載の装置。
【請求項４７】
前記複数のスレッドおよび/またはプロセッサがユーザ機器上に存在する、請求項32に記載の装置。
【請求項４８】
前記複数のスレッドおよび/またはプロセッサが複数のユーザ機器上に存在する、請求項32に記載の装置。
【請求項４９】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するように構成された論理手段と、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段であって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、論理手段と、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するように構成された論理手段とを備える装置。
【請求項５０】
受信するように構成された前記論理手段が、
1つまたは複数のセンサから前記データ点のストリームを受信するように構成された論理手段を備える、請求項49に記載の装置。
【請求項５１】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項50に記載の装置。
【請求項５２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項49に記載の装置。
【請求項５３】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、前記データ点のストリームの前記一部分の1つまたは複数のデータ点をバッファリングする、請求項49に記載の装置。
【請求項５４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項５５】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項５６】
複数のクラスタ重心を決定するように構成された論理手段と、
前記複数のクラスタ重心を前記複数のスレッドおよび/またはプロセッサの間で分割するように構成された論理手段とをさらに備える、請求項49に記載の装置。
【請求項５７】
前記複数のクラスタ重心が、クラスタ重心に加え、前記複数のスレッドおよび/またはプロセッサによって決定される、請求項56に記載の装置。
【請求項５８】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの、各々に割り当てられた部分に基づいて、前記1つまたは複数のクラスタ重心を決定する、請求項49に記載の装置。
【請求項５９】
前記複数のスレッドおよび/またはプロセッサの各々から、前記データ点のストリームのクラスタリング部分を受信するように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項６０】
クラスタの前記大域的ユニバースに対して後処理を実施するように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項６１】
前記複数のスレッドおよび/またはプロセッサがモバイルデバイス上に存在する、請求項49に記載の装置。
【請求項６２】
前記複数のスレッドおよび/またはプロセッサが複数のモバイルデバイス上に存在する、請求項49に記載の装置。
【請求項６３】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するための手段と、
複数のクラスタ重心を決定するための手段と、
前記複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するための手段と、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てるための手段と、
前記複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための手段とを備える装置。
【請求項６４】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するための手段と、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための手段であって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、手段と、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための手段とを備える装置。
【請求項６５】
データ点のストリームをクラスタリングするための非一時的コンピュータ可読媒体であって、
前記データ点のストリームを受信するための少なくとも1つの命令と、
複数のクラスタ重心を決定するための少なくとも1つの命令と、
前記複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するための少なくとも1つの命令と、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てるための少なくとも1つの命令と、
前記複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための少なくとも1つの命令とを備える非一時的コンピュータ可読媒体。
【請求項６６】
データ点のストリームをクラスタリングするための非一時的コンピュータ可読媒体であって、
前記データ点のストリームを受信するための少なくとも1つの命令と、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための少なくとも1つの命令であって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、命令と、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための少なくとも1つの命令とを備える非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示の態様は、非定常データの凝集クラスタリングのための並列化方法を対象とする。
【背景技術】
【０００２】
クラスタリングとは、データ点をクラスタにグループ化することである。クラスタリングの実際的適用例には、教師なし分類および分類法生成、最近傍探索、科学的発見(scientific discovery)、ベクトル量子化、テキスト分析、ならびにナビゲーションがある。
【０００３】
よく知られたクラスタリングアルゴリズムの1つが、k平均クラスタリングアルゴリズムである。このアルゴリズムは、クラスタリングされるべきデータ「オブジェクト」がd次元ユークリッド空間中の点(またはベクトル)として利用可能であると想定する。k平均アルゴリズムは、特定のクラスタ重心からのユークリッド距離の2乗の合計を最小にするデータの最小分散グループ化を求める。k平均アルゴリズムの普及は、その解釈の相対的容易性、実装の平易性、スケーラビリティ、収束速度、疎データへの適応性、およびコア外の(単一プロセッサのローカルメモリの外での)実装の容易性によるものであり得る。
【０００４】
クラスタリングに伴う問題は、多大なメモリおよび処理能力がかかり得ることである。たとえば、受信したデータ点は通常、メモリに記憶され、クラスタの単一ユニバースにクラスタリングされる。記憶されたデータの処理を高速化するために、データをクラスタリングするための並列処理技法が利用され得る。ただし、クラスタリングがモバイルデバイスによって実施中であり、データが、加速度計やマイクロフォンなどのセンサによって生成中である場合には、メモリに記憶し、次いで、処理するには多すぎるデータが存在する場合がある。そうではなく、データは「オンザフライ」で処理されなければならない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第6,269,376号
【非特許文献】
【０００６】
【非特許文献１】I. D. Guedalia、「An on-line agglomerative clustering method for nonstationary data」
【発明の概要】
【課題を解決するための手段】
【０００７】
本開示の態様は、データ点のストリームをクラスタリングすることを対象とする。データ点のストリームをクラスタリングするための方法は、データ点のストリームを受信するステップと、複数のクラスタ重心を決定するステップと、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するステップと、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるステップと、複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するステップとを含む。
【０００８】
データ点のストリームをクラスタリングするための方法は、データ点のストリームを受信するステップと、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるステップであって、複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、ステップと、複数のスレッドおよび/またはプロセッサの各々からの1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するステップとを含む。
【０００９】
データ点のストリームをクラスタリングするための装置は、データ点のストリームを受信するように構成された論理手段と、複数のクラスタ重心を決定するように構成された論理手段と、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するように構成された論理手段と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段と、複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するように構成された論理手段とを含む。
【００１０】
データ点のストリームをクラスタリングするための装置は、データ点のストリームを受信するように構成された論理手段と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段であって、複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、論理手段と、複数のスレッドおよび/またはプロセッサの各々からの1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するように構成された論理手段とを含む。
【００１１】
データ点のストリームをクラスタリングするための装置は、データ点のストリームを受信するための手段と、複数のクラスタ重心を決定するための手段と、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するための手段と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための手段と、複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための手段とを含む。
【００１２】
データ点のストリームをクラスタリングするための装置は、データ点のストリームを受信するための手段と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための手段であって、複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、手段と、複数のスレッドおよび/またはプロセッサの各々からの1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための手段とを含む。
【００１３】
データ点のストリームをクラスタリングするための非一時的コンピュータ可読媒体は、データ点のストリームを受信するための少なくとも1つの命令と、複数のクラスタ重心を決定するための少なくとも1つの命令と、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するための少なくとも1つの命令と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための少なくとも1つの命令と、複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための少なくとも1つの命令とを含む。
【００１４】
データ点のストリームをクラスタリングするための非一時的コンピュータ可読媒体は、データ点のストリームを受信するための少なくとも1つの命令と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための少なくとも1つの命令であって、複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、命令と、複数のスレッドおよび/またはプロセッサの各々からの1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するための少なくとも1つの命令とを含む。
【００１５】
本開示の態様およびその付随する利点の多くに関するより完全な理解は、以下の詳細な説明を参照しながら、本発明を限定するためではなく単に例示するために提示される添付の図面とともに考察することによって、本開示の態様およびその付随する利点の多くがより深く理解されるようになるときに容易に得られるであろう。
【図面の簡単な説明】
【００１６】
【図１】本発明の一態様によるワイヤレス通信システムのハイレベルシステムアーキテクチャを示す図である。
【図２】例示的なユーザ機器(UE)の様々な構成要素を示すブロック図である。
【図３】本開示の態様による、機能性を実施するように構成された論理手段を含む通信デバイスを示す図である。
【図４】k平均アルゴリズムを実装する代表的なコンピュータプログラム命令の例示的な一覧を示す図である。
【図５】UEによって実施され得る、データ点のストリームをクラスタリングするための例示的なフローを示す図である。
【図６】UEによって実施され得る、データ点のストリームをクラスタリングするための例示的なフローを示す図である。
【発明を実施するための形態】
【００１７】
以下の説明および関連する図面において様々な態様が開示される。本開示の範囲から逸脱することなく、代替の態様が考案され得る。さらに、本開示の関連する詳細を不明瞭にしないように、本開示のよく知られている要素は詳細に説明されないか、または省略される。
【００１８】
「例示的」および/または「例」という言葉は、本明細書では「例、事例、または例示として機能すること」を意味するために使用される。本明細書で「例示的」および/または「例」として説明するいかなる態様も、必ずしも他の実施形態よりも好ましいか、または有利であると解釈されるべきではない。同様に、「本開示の態様」という用語は、本開示のすべての実施形態が、論じられた特徴、利点または動作モードを含むことを要求しない。
【００１９】
さらに、多くの態様について、たとえばコンピューティングデバイスの要素によって実施されるべき、動作のシーケンスに関して説明する。本明細書で説明する様々な動作は、特定の回路(たとえば、特定用途向け集積回路(ASIC))によって、1つもしくは複数のプロセッサによって実行されるプログラム命令によって、または両方の組合せによって実施され得ることを認識されよう。加えて、本明細書で説明するこれらの動作のシーケンスは、実行時に、関連するプロセッサに本明細書で説明する機能を実施させるコンピュータ命令の対応するセットを記憶した、任意の形式のコンピュータ可読記憶媒体内で完全に具現化されるものと見なされ得る。したがって、本開示の様々な態様は、そのすべてが特許請求される主題の範囲内に入ることが企図されているいくつかの異なる形で具現され得る。さらに、本明細書で説明される態様ごとに、任意のそのような態様の対応する形は、本明細書において、たとえば、説明する動作を実施する「ように構成された論理手段」として説明される場合がある。
【００２０】
本明細書ではユーザ機器(UE)と呼ばれるクライアントデバイスは、モバイルであってもまたは固定型であってもよく、かつ無線アクセスネットワーク(RAN)と通信してよい。本明細書で使用する「UE」という用語は、「アクセス端末」または「AT」、「ワイヤレスデバイス」、「加入者デバイス」、「加入者端末」、「加入者局」、「ユーザ端末」またはUT、「モバイル端末」、「移動局」、およびそれらの変化形と互換的に参照されてよい。一般に、UEは、RANを介してコアネットワークと通信してよく、コアネットワークを通じてUEはインターネットなどの外部ネットワークに接続されてよい。もちろん、UEには、ワイヤードアクセスネットワーク、(たとえば、IEEE 802.11などに基づく)WiFiネットワークなど、コアネットワークおよび/またはインターネットに接続する他の機構も考えられる。UEは、限定はしないが、PCカード、コンパクトフラッシュ(登録商標)デバイス、外付けまたは内蔵のモデム、ワイヤレスまたは有線の電話などを含むいくつかのタイプのデバイスのうちの任意のものによって具体化されてよい。UEが信号をRANに送ることができる通信リンクは、アップリンクチャネル(たとえば、逆方向トラフィックチャネル、逆方向制御チャネル、アクセスチャネルなど)と呼ばれる。RANが信号をUEに送ることができる通信リンクは、ダウンリンクチャネルまたは順方向リンクチャネル(たとえば、ページングチャネル、制御チャネル、ブロードキャストチャネル、順方向トラフィックチャネルなど)と呼ばれる。本明細書で使用するトラフィックチャネル(TCH)という用語は、アップリンク/逆方向トラフィックチャネル、またはダウンリンク/順方向トラフィックチャネルのいずれかを指すことができる。
【００２１】
図1は、本開示の一態様によるワイヤレス通信システム100のハイレベルシステムアーキテクチャを示す。ワイヤレス通信システム100はUE1…Nを含む。UE1…Nは、携帯電話、携帯情報端末(PDA)、ページャ、ラップトップコンピュータ、デスクトップコンピュータなどを含み得る。たとえば、図1において、UE1…2は発呼側携帯電話として示され、UE3…5はタッチスクリーン携帯電話またはスマートフォンとして示され、UE Nはデスクトップコンピュータまたはパーソナルコンピュータ(PC)として示されている。
【００２２】
図1を参照すると、UE1…Nは、図1にエアインターフェース104、106、108および/または直接ワイヤード接続として示されている物理通信インターフェースまたはレイヤを介してアクセスネットワーク(たとえば、RAN120、アクセスポイント125など)と通信するように構成される。エアインターフェース104および106は、所与のセルラー通信プロトコル(たとえば、符号分割多元接続(CDMA)、エボリューションデータオプティマイズド(EV-DO)、発展型高速パケットデータ(eHRPD:Evolved High Rate Packet Data)、グローバルシステムオブモバイルコミュニケーション(GSM(登録商標))、GSM進化型高速データレート(EDGE)、ワイドバンドCDMA(W-CDMA)、ロングタームエボリューション(LTE)など)に準拠し得るが、エアインターフェース108は、ワイヤレスIPプロトコル(たとえば、IEEE802.11)に準拠し得る。RAN120は、エアインターフェース104および106などのエアインターフェースを介してUEにサービスする複数のアクセスポイントを含む。RAN120内のアクセスポイントは、アクセスノードまたはAN、アクセスポイントまたはAP、基地局またはBS、ノードB、eノードBなどと呼ばれ得る。これらのアクセスポイントは、地上アクセスポイント(もしくは地上局)、または衛星アクセスポイントであり得る。RAN120は、RAN120によってサービスされるUEとRAN120または異なるRANによってサービスされる他のUEとの間の回線交換(CS)呼を完全にブリッジングすることを含む様々な機能を実施することができ、かつインターネット175などの外部ネットワークとのパケット交換(PS)データの交換を仲介することもできるコアネットワーク140に接続するように構成される。インターネット175は、いくつかのルーティングエージェントおよび処理エージェント(便宜上図1には示されていない)を含む。図1において、UE Nはインターネット175に直接接続する(すなわち、WiFiまたは802.11ベースネットワークのイーサネット(登録商標)接続を介するなど、コアネットワーク140から分離される)ように示されている。それによって、インターネット175は、コアネットワーク140を介してUE NとUE1…Nとの間のパケット交換データ通信をブリッジングするように働いてよい。図1には、RAN120から分離されたアクセスポイント125も示されている。アクセスポイント125は、コアネットワーク140とは独立して(たとえば、FiOS、ケーブルモデムなどの光通信システムを介して)インターネット175に接続されてよい。エアインターフェース108は、一例ではIEEE 802.11などのローカルワイヤレス接続を介してUE4またはUE5にサービスしてよい。UE Nは、一例では(たとえば、ワイヤード接続性とワイヤレス接続性の両方を有するWiFiルータ用の)アクセスポイント125自体に相当してよいモデムまたはルータとの直接接続などのインターネット175とのワイヤード接続を含むデスクトップコンピュータとして示されている。
【００２３】
図1を参照すると、アプリケーションサーバ170は、インターネット175、コアネットワーク140、またはその両方に接続されるように示されている。アプリケーションサーバ170は、構造的に分離された複数のサーバとして実装されてよく、または代替として単一のサーバに対応し得る。以下により詳しく説明するように、アプリケーションサーバ170は、コアネットワーク140および/またはインターネット175を介してアプリケーションサーバ170に接続することのできるUEについて1つまたは複数の通信サービス(たとえば、ボイスオーバーインターネットプロトコル(VoIP:Voice-over-Internet Protocol)セッション、プッシュツートーク(PTT:Push-to-Talk)セッション、グループ通信セッション、ソーシャルネットワーキングサービスなど)をサポートするように構成される。
【００２４】
図2は、例示的なUE200の様々な構成要素を示すブロック図である。簡潔のために、図2のボックス図に示される様々な特徴および機能は、共通バスを使って接続されており、このことは、これらの様々な特徴および機能が、動作可能に結合されることを表すことを意図している。他の接続、機構、特徴、機能なども、実際の可搬型ワイヤレスデバイスを動作可能に結合し構成する必要に応じて提供され適応され得ることが当業者には理解されよう。さらに、図2の例に示される特徴または機能の1つまたは複数は、さらに細分してもよく、図2に示される特徴または機能の2つ以上を組み合わせてもよいことも理解されたい。
【００２５】
UE200は、1つまたは複数のアンテナ202に接続され得る1つまたは複数のワイドエリアネットワーク(WAN)トランシーバ204を含み得る。WANトランシーバ204は、アクセスポイント125などのWAN-WAPとの間で、および/またはネットワーク内の他のワイヤレスデバイスと直接信号を通信し、かつ/または検出するための、適切なデバイス、ハードウェア、および/またはソフトウェアを含む。一態様では、WANトランシーバ204は、ワイヤレス基地局のCDMAネットワークと通信するのに適したCDMA通信システムを備え得るが、他の態様では、ワイヤレス通信システムは、たとえば、TDMAやGSM(登録商標)など、別のタイプのセルラーテレフォニーネットワークを備え得る。さらに、たとえば、WiMAX(802.16)など、どの他のタイプのワイドエリアワイヤレスネットワーキング技術が使われてもよい。UE200は、1つまたは複数のアンテナ202に接続され得る1つまたは複数のローカルエリアネットワーク(LAN)トランシーバ206も含み得る。LANトランシーバ206は、アクセスポイント125などのLAN-WAPとの間で、および/またはネットワーク内の他のワイヤレスデバイスと直接信号を通信し、かつ/または検出するための、適切なデバイス、ハードウェア、および/またはソフトウェアを含む。一態様では、LANトランシーバ206は、1つまたは複数のワイヤレスアクセスポイントと通信するのに適したWi-Fi(802.11x)通信システムを備え得るが、他の態様では、LANトランシーバ206は、別のタイプのローカルエリアネットワーク、パーソナルエリアネットワーク(たとえば、Bluetooth(登録商標))を備える。さらに、たとえば、超広帯域、ZigBee、ワイヤレスUSBなど、他のどのタイプのワイヤレスネットワーキング技術も用いることができる。
【００２６】
本明細書で使用する「ワイヤレスアクセスポイント」(WAP)という短縮用語は、LAN-WAPおよび/またはWAN-WAPを指すのに使われ得る。具体的には、以下に提示する説明において、「WAP」という用語が使われる際は、実施形態は、複数のLAN-WAP、複数のWAN-WAP、またはこれら2つの任意の組合せからの信号を利用することができるUE200を含み得ることを理解されたい。UE200によって使用されるWAPの具体的タイプは、動作の環境に依存し得る。さらに、UE200は、正確な位置解に到達するために、様々なタイプのWAPの間で動的に選択を行うことができる。他の実施形態では、様々なネットワーク要素がピアツーピア方式で動作することができ、それにより、たとえば、UE200はWAPで置き換えられるか、またはその反対でもよい。他のピアツーピア実施形態は、1つまたは複数のWAPの代わりに作用する別のUE(図示せず)を含み得る。
【００２７】
UE200には、衛星測位システム(SPS)受信機208も含まれ得る。SPS受信機208は、衛星信号を受信するための1つまたは複数のアンテナ202に接続され得る。SPS受信機208は、SPS信号を受信し、処理するための適切などのハードウェアおよび/またはソフトウェアも備え得る。SPS受信機208は、他のシステムに対して、情報および動作を適宜要求し、UE200の位置を決定するのに必要な算出を、適切な任意のSPSアルゴリズムによって取得された測定値を使って実施する。
【００２８】
WANトランシーバ204、LANトランシーバ206およびSPS受信機208によって受信された信号から導出される動きデータに依存しない運動および/または配向情報を与えるために、動きセンサ212がプロセッサ210に結合され得る。
【００２９】
例として、動きセンサ212は、加速度計(たとえば、マイクロ電気機械システム(MEMS)デバイス)、ジャイロスコープ、地磁気センサ(たとえば、コンパス)、高度計(たとえば、気圧高度計)、および/または他のどのタイプの運動検出センサも使用することができる。さらに、動きセンサ212は、複数の異なるタイプのデバイスを含み、動き情報を与えるためにその出力を組み合わせ得る。たとえば、動きセンサ212は、多軸加速度計および配向センサの組合せを使って、2-Dおよび/または3-D座標系での位置を計算することが可能になる。
【００３０】
プロセッサ210は、WANトランシーバ204、LANトランシーバ206、SPS受信機208および動きセンサ212に接続され得る。プロセッサ210は、処理機能ならびに他の算出および制御機能を提供する、1つまたは複数のマイクロプロセッサ、マイクロコントローラ、および/またはデジタル信号プロセッサを含み得る。プロセッサ210は、UE200内でプログラムされた機能性を実行するためのデータおよびソフトウェア命令を記憶するためのメモリ214も含み得る。メモリ214はプロセッサ210に搭載されて(たとえば、同じ集積回路(IC)パッケージ内にあって)よく、かつ/またはメモリは、プロセッサの外部メモリであるとともにデータバスを介して機能的に結合されてよい。本開示の態様に関連した機能的詳細については、以下でより詳しく論じる。
【００３１】
いくつかのソフトウェアモジュールおよびデータテーブルは、メモリ214内に常駐し、通信機能性と測位決定機能性の両方を管理するために、プロセッサ210によって使用され得る。図2に示すように、メモリ214は、ワイヤレスベースの測位モジュール216、アプリケーションモジュール218、および測位モジュール228を含み、かつ/またはそうでなければ受け得る。図2に示すようなメモリ内容の編成は例示に過ぎず、したがってモジュールの機能性および/またはデータ構造は、UE200の実装形態に応じて、異なるように組み合わされ、分離され、かつ/または構造化され得ることを諒解されたい。
【００３２】
アプリケーションモジュール218は、UE200のプロセッサ210上で稼動するプロセスでよく、このプロセスは、ワイヤレスベースの測位モジュール216に対して位置情報を要求する。アプリケーションは通常、ソフトウェアアーキテクチャの上位層内で稼動する。ワイヤレスベースの測位モジュール216は、複数のWAPと交換される信号から測定された時間情報から導出される情報を使って、UE200の位置を導出することができる。時間ベースの技法を用いて位置を正確に決定するために、各WAPの時間を処理することによってもたらされる時間遅延の妥当な推定値を使って、信号から取得された時間測定値を較正/調整すればよい。本明細書で使用するように、これらの時間遅延は「処理遅延」と呼ばれる。
【００３３】
WAPの処理遅延をさらに洗練するための較正は、動きセンサ212によって取得された情報を使って実施され得る。一実施形態では、動きセンサ212は、プロセッサ210に位置および配向データを直接与えることができ、これらのデータは、メモリ214中で、位置/動きデータモジュール226に記憶することができる。他の実施形態では、動きセンサ212は、較正を実施するための情報を導出するために、プロセッサ210によってさらに処理されるべきデータを与え得る。たとえば、動きセンサ212は、ワイヤレスベースの測位モジュール216中で処理遅延を調整するための位置データを導出するように測位モジュール228を使って処理され得る加速度および/または配向データ(単一または多軸)を提供することができる。
【００３４】
較正の後、位置は次いで、その上述した要求に応答してアプリケーションモジュール218に出力され得る。さらに、ワイヤレスベースの測位モジュール216は、動作パラメータを交換するためのパラメータデータベース224を使用することができる。そのようなパラメータは、各WAPごとの決定された処理遅延、共通座標フレーム内のWAP位置、ネットワークに関連した様々なパラメータ、初期処理遅延推定値などを含み得る。
【００３５】
他の実施形態では、付加情報は、任意選択で、SPS測定値などからの、動きセンサ212以外の他のソースから決定され得る補助的な位置および/または動きデータを含み得る。補助的な位置データは、断続的および/またはノイズがある可能性があるが、UE200が動作している環境に応じて、WAPの処理遅延を推定するための独立情報の別のソースとして有用であり得る。
【００３６】
たとえば、いくつかの実施形態では、SPS受信機208から導出されたデータは、動きセンサ212から供給された(位置/動きデータモジュール226から直接、または測位モジュール228によって導出されたかのいずれか)位置データを補うことができる。他の実施形態では、位置データは、非RTT技法(たとえば、CDMAネットワーク内のアドバンストフォワードリンク三辺測量(AFLT))を使って、追加ネットワークを通して決定されたデータと組み合わされ得る。いくつかの実装形態では、動きセンサ212および/またはSPS受信機208は、プロセッサ210によるさらなる処理なしで、補助的な位置/動きデータ226の全部または一部を提供することができる。いくつかの実施形態では、補助的な位置/動きデータ226は、動きセンサ212および/またはSPS受信機208によってプロセッサ210に直接提供され得る。
【００３７】
図2に示すモジュールは、この例では、メモリ214に含まれるものとして示されているが、いくつかの実装形態では、そのような手順は、他のまたは追加機構を使うために提供され、または場合によっては動作可能に置かれ得ることを認識されたい。たとえば、ワイヤレスベースの測位モジュール216および/またはアプリケーションモジュール218の全部または一部は、ファームウェアで提供され得る。さらに、この例では、ワイヤレスベースの測位モジュール216およびアプリケーションモジュール218は、別々の特徴であるものとして示されているが、たとえば、そのような手順は、1つの手順として、もしくは可能性としては他の手順と組み合わされ、または場合によっては複数の下位手順にさらに分けられ得ることを認識されたい。
【００３８】
プロセッサ210は、少なくとも本明細書で提供する技法を実施するのに適したどの形の論理手段も含み得る。たとえば、プロセッサ210は、メモリ214内の命令に基づいて、UE200の他の部分で使用するための動きデータを利用する1つまたは複数のルーチンを選択的に開始するように、動作可能に構成可能であり得る。
【００３９】
UE200は、UE200とのユーザとの情報のやりとりを可能にするマイクロフォン/スピーカ252、キーパッド254、およびディスプレイ256など、適切などのインターフェースシステムも提供するユーザインターフェース250を含み得る。マイクロフォン/スピーカ252は、WANトランシーバ204および/またはLANトランシーバ206を使って音声通信サービスを提供する。キーパッド254は、ユーザ入力のためのどの適切なボタンも備える。ディスプレイ256は、バックライト液晶ディスプレイ(LCD)など、適切などのディスプレイも含み、追加ユーザ入力モードのためのタッチスクリーンディスプレイをさらに含み得る。
【００４０】
本明細書で使用するように、UE200は、1つまたは複数のワイヤレス通信デバイスまたはネットワークから送信されたワイヤレス信号を獲得し、それらのデバイスまたはネットワークにワイヤレス信号を送信するように構成可能などの可搬型または可動デバイスまたは機械でもよい。図2に示すように、UE200は、そのような可搬型ワイヤレスデバイスを表す。したがって、限定ではなく例として、UE200は、無線デバイス、セルラー電話デバイス、コンピューティングデバイス、パーソナル通信システム(PCS)デバイス、または他の同様の可動ワイヤレス通信機能搭載デバイス、アプライアンス、もしくは機械を含み得る。「ユーザ機器」という用語はまた、短距離ワイヤレス接続、赤外線接続、ワイヤライン接続、または他の接続などによって、パーソナルナビゲーションデバイス(PND)と通信するデバイスを、衛星信号受信、支援データ受信、および/もしく位置関連処理がそのデバイスにおいて行われるか、またはPNDにおいて行われるかにかかわらず含むことが意図される。また、「ユーザ機器」は、衛星信号受信、支援データ受信、および/または位置に関する処理がデバイスで生じるのか、サーバで生じるのか、またはネットワークと関連する別のデバイスで生じるのかとは関係なく、インターネット、Wi-Fi、または他のネットワークなどを経由してサーバと通信することができるワイヤレスデバイス、コンピュータ、ラップトップなどを含むすべてのデバイスを含むことが意図されている。上記の任意の動作可能な組合せも「ユーザ機器」と見なされる。
【００４１】
本明細書で使用する「ワイヤレスデバイス」、「移動局」、「モバイルデバイス」、「ユーザ機器」などという用語は、ネットワークを介して情報を転送し、位置決定および/またはナビゲーション機能性を有し得るどのタイプのワイヤレス通信デバイスも指し得る。ワイヤレスデバイスは、どのセルラーモバイル端末、パーソナル通信システム(PCS)デバイス、パーソナルナビゲーションデバイス、ラップトップ、携帯情報端末、またはネットワークおよび/もしくはSPS信号を受信し、処理することが可能な他のどの適切なデバイスでもよい。
【００４２】
図3に、機能性を実施するように構成された論理手段を含む通信デバイス300を示す。通信デバイス300は、限定はしないが、UE200、RAN120の任意の構成要素、コアネットワーク140の任意の構成要素、コアネットワーク140および/またはインターネット175に結合された任意の構成要素(たとえば、アプリケーションサーバ170)などを含む、上記の通信デバイスのうちのいずれかに対応し得る。したがって、通信デバイス300は、図1のワイヤレス通信システム100を介して1つもしくは複数の他のエンティティと通信する(または通信を容易にする)ように構成された任意の電子デバイスに対応し得る。
【００４３】
図3を参照すると、通信デバイス300は、情報を受信および/または送信するように構成された論理手段305を含む。一例では、通信デバイス300がワイヤレス通信デバイス(たとえば、UE200)に対応する場合、情報を受信および/または送信するように構成された論理手段305は、ワイヤレストランシーバおよび関連ハードウェア(たとえば、無線周波数(RF)アンテナ、モデム、変調器および/または復調器など)などのワイヤレス通信インターフェース(たとえば、Bluetooth(登録商標)、WiFi、2G、CDMA、W-CDMA、3G、4G、LTEなど)を含むことができる。別の例では、情報を受信および/または送信するように構成された論理手段305は、有線通信インターフェース(たとえば、インターネット175にアクセスする手段となり得るシリアル接続、ユニバーサルシリアルバス(USB)またはFirewire接続、Ethernet(登録商標)接続など)に対応することができる。したがって、通信デバイス300が、何らかのタイプのネットワークベースのサーバ(たとえば、アプリケーションサーバ170)に対応する場合には、情報を受信および/または送信するように構成された論理手段305は、一例では、Ethernet(登録商標)プロトコルによってネットワークベースのサーバを他の通信エンティティに接続するEthernet(登録商標)カードに対応し得る。さらなる例では、情報を受信および/または送信するように構成された論理手段305は、通信デバイス300がそのローカル環境を監視する手段となり得る感知または測定ハードウェア(たとえば、加速度計、温度センサ、光センサ、ローカルRF信号を監視するためのアンテナなど)を含むことができる。情報を受信および/または送信するように構成された論理手段305は、データ点のストリームを受信するように構成された論理手段も含み得る。情報を受信および/または送信するように構成された論理手段305は、実行されるときに、情報を受信および/または送信するように構成された論理手段305の関連ハードウェアがその受信機能および/または送信機能を実施できるようにするソフトウェアも含むことができる。しかしながら、情報を受信および/または送信するように構成された論理手段305は、ソフトウェアだけに対応するのではなく、情報を受信および/または送信するように構成された論理手段305は、その機能性を達成するためのハードウェアに少なくとも部分的に依拠する。
【００４４】
図3を参照すると、通信デバイス300は、情報を処理するように構成された論理手段310をさらに含む。一例では、情報を処理するように構成された論理手段310は、少なくともプロセッサを含み得る。情報を処理するように構成された論理手段310によって実施され得るタイプの処理の例示的な実装形態は、決定を行うこと、接続を確立すること、異なる情報オプション間で選択を行うこと、データに関係する評価を実施すること、測定動作を実施するために通信デバイス300に結合されたセンサと情報をやりとりすること、情報をあるフォーマットから別のフォーマットに(たとえば、wmvから.aviへなど、異なるプロトコル間で)変換することなどを含むが、これらに限定されない。情報を処理するように構成された論理手段310は、データ点のストリームを受信するように構成された論理手段と、複数のクラスタ重心を決定するように構成された論理手段と、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割するように構成された論理手段と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段と、複数のスレッドおよび/またはプロセッサによって生成された複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するように構成された論理手段とを含み得る。情報を処理するように構成された論理手段310はまた、データ点のストリームを受信するように構成された論理手段と、データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段であって、複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、論理手段と、複数のスレッドおよび/またはプロセッサの各々からの1つまたは複数のクラスタを組み合わせて、クラスタの大域的ユニバースを生成するように構成された論理手段とを含み得る。情報を処理するように構成された論理手段310中に含まれるプロセッサは、汎用プロセッサ、デジタル信号プロセッサ(DSP)、ASIC、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明する機能を実施するように設計されたそれらの任意の組合せに対応し得る。汎用プロセッサはマイクロプロセッサであり得るが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であり得る。プロセッサはまた、コンピューティングデバイスの組合せ、たとえば、DSPとマイクロプロセッサとの組合せ、複数のマイクロプロセッサ、DSPコアと連携する1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成として実装することができる。情報を処理するように構成された論理手段310は、実行されるとき、情報を処理するように構成された論理手段310の関連ハードウェアがその処理機能を実施できるようにするソフトウェアも含むことができる。しかしながら、情報を処理するように構成された論理手段310は、ソフトウェアだけに対応するのではなく、情報を処理するように構成された論理手段310は、その機能性を達成するためにハードウェアに少なくとも部分的に依拠する。
【００４５】
図3を参照すると、通信デバイス300は、情報を記憶するように構成された論理手段315をさらに含む。一例では、情報を記憶するように構成された論理手段315は、少なくとも非一時的メモリおよび関連ハードウェア(たとえば、メモリコントローラなど)を含み得る。たとえば、情報を記憶するように構成された論理手段315内に含まれる非一時的メモリは、RAM、フラッシュメモリ、ROM、消去可能プログラマブルROM(EPROM)、EEPROM、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野で知られている任意の他の形の記憶媒体に対応し得る。情報を記憶するように構成された論理手段315はまた、実行されるとき、情報を記憶するように構成された論理手段315の関連ハードウェアがその記憶機能を実施できるようにするソフトウェアを含み得る。しかしながら、情報を記憶するように構成された論理手段315は、ソフトウェアだけに対応するのではなく、情報を記憶するように構成された論理手段315は、その機能性を達成するためにハードウェアに少なくとも部分的に依拠する。
【００４６】
図3を参照すると、通信デバイス300は、情報を提示するように構成された論理手段320をさらにオプションで含む。一例では、情報を提示するように構成された論理手段320は、少なくとも出力デバイスおよび関連ハードウェアを含み得る。たとえば、出力デバイスは、ビデオ出力デバイス(たとえば、ディスプレイスクリーン、USB、HDMI(登録商標)のようなビデオ情報を搬送することができるポートなど)、オーディオ出力デバイス(たとえば、スピーカ、マイクロフォンジャック、USB、高精細度マルチメディアインターフェース(HDMI(登録商標))のようなオーディオ情報を搬送することができるポートなど)、振動デバイス、および/または、情報がそれによって出力のためにフォーマットされ得る、または通信デバイス300のユーザもしくは操作者によって実際に出力され得る任意の他のデバイスを含むことができる。たとえば、通信デバイス300が、図2に示されたUE200に対応する場合、情報を提示するように構成された論理手段320は、ディスプレイ256および/またはスピーカ252を含むことができる。さらなる例では、情報を提示するように構成された論理手段320は、(たとえば、ネットワークスイッチまたはルータ、リモートサーバなど)ローカルユーザを有さないネットワーク通信デバイスのようないくつかの通信デバイスでは省略されることがある。情報を提示するように構成された論理手段320は、実行されるとき、情報を提示するように構成された論理手段320の関連ハードウェアがその提示機能を実施できるようにするソフトウェアも含むことができる。しかしながら、情報を提示するように構成された論理手段320は、ソフトウェアだけに対応するのではなく、情報を提示するように構成された論理手段320は、その機能性を達成するためにハードウェアに少なくとも部分的に依拠する。
【００４７】
図3を参照すると、通信デバイス300は、ローカルユーザ入力を受信するように構成された論理手段325をさらにオプションで含む。一例では、ローカルユーザ入力を受信するように構成された論理手段325は、少なくともユーザ入力デバイスおよび関連ハードウェアを含み得る。たとえば、ユーザ入力デバイスは、ボタン、タッチスクリーンディスプレイ、キーボード、カメラ、オーディオ入力デバイス(たとえば、マイクロフォン、もしくはマイクロフォンジャックなど、オーディオ情報を搬送することができるポートなど)、および/または情報がそれによって通信デバイス300のユーザもしくはオペレータから受信され得る任意の他のデバイスを含み得る。たとえば、通信デバイス300が、図2に示されたUE200に対応する場合、ローカルユーザ入力を受け取るように構成された論理手段325は、マイクロフォン252、キーパッド254、ディスプレイ256などを含むことができる。さらなる例では、ローカルユーザ入力を受信するように構成された論理手段325は、(たとえば、ネットワークスイッチまたはルータ、リモートサーバなど)ローカルユーザを有さないネットワーク通信デバイスのようないくつかの通信デバイスでは省略されることがある。ローカルユーザ入力を受信するように構成された論理手段325は、実行されるとき、ローカルユーザ入力を受信するように構成された論理手段325の関連ハードウェアがその入力受信機能を実施できるようにするソフトウェアも含むことができる。しかしながら、ローカルユーザ入力を受信するように構成された論理手段325は、ソフトウェアだけに対応するのではなく、ローカルユーザ入力を受信するように構成された論理手段325は、その機能性を達成するためにハードウェアに少なくとも部分的に依拠する。
【００４８】
図3を参照すると、305〜325の構成された論理手段は、図3では別個または相異なるブロックとして示されているが、それぞれの構成された論理手段がその機能性を実施するためのハードウェアおよび/またはソフトウェアは、部分的に重複し得ることが諒解されよう。たとえば、305〜325の構成された論理手段の機能性を容易にするのに使われるどのソフトウェアも、情報を記憶するように構成された論理手段315に関連付けられた非一時的メモリに記憶することができ、そうすることによって、305〜325の構成された論理手段は各々、その機能性(すなわち、この場合、ソフトウェア実行)を、情報を記憶するように構成された論理手段315によって記憶されたソフトウェアの動作に部分的に基づいて実施する。同様に、構成された論理手段のうちの1つに直接関連付けられたハードウェアは、時々、他の構成された論理手段によって借用または使用され得る。たとえば、情報を処理するように構成された論理手段310のプロセッサは、データを、情報を受信および/または送信するように構成された論理手段305によって送信される前に、適切な形式にフォーマットすることができ、それにより、情報を受信および/または送信するように構成された論理手段305は、その機能性(すなわち、この場合、データの送信)を、情報を処理するように構成された論理手段310に関連付けられたハードウェア(すなわち、プロセッサ)の動作に部分的に基づいて実施する。
【００４９】
概して、別段に明示的に記載されていない限り、本開示全体にわたって使用される「ように構成された論理手段」という言い回しは、ハードウェアにより少なくとも部分的に実装される態様を起動するものとし、ハードウェアから独立したソフトウェアだけの実装形態に位置づけるものではない。様々なブロックにおける構成された論理手段または「ように構成された論理手段」は、特定の論理ゲートまたは論理要素に限定されるのではなく、概して、本明細書に記載した機能性を、(ハードウェアまたはハードウェアとソフトウェアの組合せのいずれかを介して)実施するための能力を指すことが諒解されよう。したがって、様々なブロックに示す構成された論理手段または「ように構成された論理手段」は、「論理手段」という言葉を共有するにもかかわらず、必ずしも論理ゲートまたは論理要素として実装されるわけではない。様々なブロックの論理手段間の他のやりとりまたは協働が、以下でより詳細に説明する態様の検討から、当業者には明らかになるであろう。
【００５０】
クラスタリングとは、データ点をクラスタにグループ化することである。クラスタリングの実際的適用例には、教師なし分類および分類法生成、最近傍探索、科学的発見、ベクトル量子化、テキスト分析、ならびにナビゲーションがある。
【００５１】
1つの共通クラスタリングアルゴリズムが、k平均クラスタリングアルゴリズムである。このアルゴリズムは、クラスタリングされるべきデータ「オブジェクト」がd次元ユークリッド空間中の点(またはベクトル)として利用可能であると想定する。k平均アルゴリズムは、特定のクラスタ重心からのユークリッド距離の2乗の合計を最小にするデータの最小分散グループ化を求める。k平均アルゴリズムの普及は、その解釈の相対的容易性、実装の平易性、スケーラビリティ、収束速度、疎データへの適応性、およびコア外の(単一プロセッサのローカルメモリの外での)実装の容易性によるものであり得る。
【００５２】
図4は、米国特許第6,269,376号に示されている、k平均アルゴリズムを実装する代表的なコンピュータプログラム命令の例示的な一覧を示す。k平均アルゴリズムは、本質的に以下の4つのステップを含む。
(a)初期化:k個の開始点のセットを選択する(図4の行5に示すように)。選択は、ランダムに、または何らかのヒューリスティックに従って実施され得る。
(b)距離算出:各データ点について、各クラスタ重心までのそのユークリッド距離を計算し、最も近いクラスタ重心を見つける(図4の行14〜21に示すように)。各そのようなデータ点を、最も近いクラスタ重心に割り当てる。
(c)重心再算出:各クラスタ重心について、クラスタ重心を、それに割り当てられたデータ点の平均として再算出する(図2の行22〜26に示すように)。
(d)収束条件:何らかの収束条件が満たされるまで、ステップ(b)および(c)を繰り返す(図4の行28に示すように)。
【００５３】
k平均アルゴリズムは、初期開始クラスタ重心で開始するとともに、これらの重心を、データ点の最小分散クラスタリングを減じるように繰り返し更新する勾配降下アルゴリズムと見なされ得る。このk平均アルゴリズムは、常に極小値に収束するが、特定の極小値は大域的最小値でない場合があり、特定の極小値は初期開始クラスタ点に依存する。アルゴリズムが収束する前に、ステップ(b)および(c)が数回実行されなければならない。k平均反復の数は、同一のデータセットであったとしても、初期開始クラスタ重心に依存して変わり得る正の整数である。
【００５４】
クラスタリングに伴う問題は、多大なメモリおよび処理能力がかかり得ることである。たとえば、受信したデータ点は通常、メモリに記憶され、クラスタの単一ユニバースにクラスタリングされる。記憶されたデータの処理を高速化するために、データをクラスタリングするための並列処理技法が利用され得る。
【００５５】
最も近いクラスタ重心にデータ点を割り当てるプロセス中に実施される反復が、総計算時間を左右する。図4の行14〜21に示す距離算出は、各データ点について非同期および並列に実行することができ、これらの行において実施される計算が、ステップ(b)および(c)の計算上の複雑さを左右するので、データ点の数が多いとき、計算複雑性を低減する効果的な並列化戦略が実装され得る。
【００５６】
P個のプロセッサをもつ分散メモリ機械上でk平均アルゴリズムのバージョンを実装することによって、総計算時間は、P倍近く削減され得る。その戦略は、N個のデータ点をP個のブロックに分割し(サイズは各々、おおよそN/Pである)、これらのブロックの各々について、異なるプロセッサ上で並列に行14〜21を計算することである。N個のデータ点をP個のプロセッサの間で分割することによって、大規模データセットが、P個のプロセッサの組合せメモリによって扱われ得る。たとえば、2ギガバイトのデータセットは、ほとんどの単一プロセッサにとって扱うのが難しいはずだが、256メガバイトのメインメモリを各々がもつ16個のプロセッサの間で分割されると、容易に処理され得る。
【００５７】
この方法は、P個のプロセッサの間の共有メモリも必要とする。重心は、共有メモリの中で記憶および更新され、したがって、P個のプロセッサの作業の調整を可能にする。
【００５８】
ただし、クラスタリングがモバイルデバイスによって実施中であり、データが、加速度計やマイクロフォンなどのセンサによって生成中である場合、メモリに記憶し、次いで、処理するには多すぎるデータが存在する場合がある。そうではなく、データは「オンザフライ」で処理されなければならない。
【００５９】
提案するソリューションは、受信したデータ点を、UE200などのUEのプロセッサ210などのプロセッサ上で稼動する複数のスレッド(および/または、モバイルデバイスがそのように装備される場合は複数のプロセッサ)に、ラウンドロビン方式で割り当てる。各スレッドに、重心の全体的なセットをプロビジョニングしてその周囲に入力データ点のセットをクラスタリングするのではなく、各スレッドには、重心の全体的なセットのサブセットがプロビジョニングされる。たとえば、5つのスレッドおよび100個のクラスタ重心が与えられると、100個の重心を各スレッドにプロビジョニングするのではなく、20個の重心が、5つのスレッドの各々にプロビジョニングされ得る。
【００６０】
各スレッドが、それに割り当てられたデータ点をクラスタリングすると、クラスタは、組み合わされてクラスタの単一/大域的ユニバースになる。たとえば、5つのスレッドおよび100個の重心がある場合、重心は5つのグループに分割されてよく、各グループには20個の重心がある。20個の重心からなる各グループは、データに対するクラスタリングを実施する異なるスレッドによって独立して利用される。クラスタリングが終了すると、5つのグループは、100個の重心からなる単一グループを作成するように連結される。
【００６１】
データがランダムであり定常である、つまり、各スレッドに分散されているデータ点が互いと同様である場合、各スレッドによって生成されたクラスタが、他のスレッドによって生成されたクラスタと重複する可能性が高い。その場合、後処理ステップが、冗長クラスタをマージするのに使用され得る。
【００６２】
すべてのクラスタリング技法が、データを分割し、各セグメントを独立してクラスタリングし、次いで、結果を連結するこの手法をサポートすることができるわけではない。最も注目すべきこととして、重心を動かす(すなわち、重心の値を調整する)ためのk平均基準は、到着した新たなデータに依存するだけなので、k平均クラスタリングは、乏しいデータ表現を生じ得る。したがって、k平均アルゴリズムは、データのドリフトに従う傾向がある。faddcと呼ばれる、非定常データのためのオンライン凝集クラスタリング方法は、重心を動かすための基準がシステムの「健忘症」を最小限するように企図されているので、この手法にはより適し得る。このクラスタリング方法は、I. D. Guedaliaらによる「An on-line agglomerative clustering method for nonstationary data」に記載されている。
【００６３】
ハイブリッド手法が利用されてもよく、それによって、各グループが独立して働くとき、k平均アルゴリズムが最初のステップ用に使用され、グループが連結されると、faddcアルゴリズムが後処理段階において使用される。ただし、この手法は、各重心が表したデータ点の数など、通常は省かれる付加情報がk平均クラスタリング中に記憶されることを必要とする。
【００６４】
組み合わされると、UEは、特徴抽出、またはデータマイニングを、組み合わされたクラスタに対して実施すればよい。
【００６５】
あまりにも多くのデータ点があるか、またはデータ点が冗長である場合、UEは、データ点をドロップするか、サンプリングレートを低下させればよい(たとえば、データ点が1つまたは複数のセンサによって生成中である場合)。さらに、いくつかのUEが、ワイヤードであるかワイヤレスであるかにかかわらず、高速データリンクを介して結合されている場合、並列処理は複数のUEに分散され得る。センサデータを生成するUEは、データを他のデバイスに割り当て、クラスタリング結果を受信すればよい。
【００６６】
複数のスレッドにラウンドロビンまたはランダム方式でデータ点を割り当てる代わりに、データ点は、階層分散方法を使って割り当てられてもよい。その場合、単一の、非常に小規模な、クラスタ重心のセット(たとえば、4つ)がプロビジョニングされ、各重心はスレッドに対応する。各新たなデータ点は、到着すると、重心のセットによってクラスタリングされ、次いで、「成功した(winning)」重心(すなわち、データ点がその周囲でクラスタリングされている重心)に基づいて、データ点は、対応するスレッドに割り当てられ、このスレッドは次いで、詳細なクラスタリングを実施する。
【００６７】
階層分散のより複雑な例では、スレッドが存在するよりも多くのクラスタ重心が、重心の小規模セット中に存在し得る。その場合、分散は、重心のより小規模/よりハイレベルなセット中の重心に関連したカウントによってさらに偏り得る。
【００６８】
図5は、UE200などのUEによって実施され得る、データ点のストリームをクラスタリングするための例示的なフローを示す。510で、UEは、データ点のストリームを受信する。UEは、データ点のストリームを、たとえば加速度計、ジャイロスコープ、磁力計、マイクロフォンなど、1つまたは複数のセンサから受信し得る。データ点のストリームが、複数のスレッドおよび/またはプロセッサでも効率的に処理するには多すぎるデータ点を含む場合、UEは、処理しなければならないデータ点の数を削減するために、データ点をドロップすればよい。たとえば、UEは、あらゆる他のデータ点をドロップしてもよく、10個おきにデータ点を保持するだけでもよい。代替として、UEは、処理しなければならないデータ点の数を削減するために、データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させてもよい。
【００６９】
520で、UEは、複数のクラスタ重心を決定する。代替として、複数のスレッドのうちの1つまたは複数が、ランタイム中に1つまたは複数の重心を決定することができる。これらの重心は所定の数であってもよく、必要に基づいて割り当てられてもよい。たとえば、データ点の既存の重心までのユークリッド距離があまりにも大きいと判断された場合、スレッドは、そのデータ点を新たな重心として使うと決定してよい。その重心は次いで、複数の既存重心に追加されてよく、次いで、入力データ点の今後の照合に使われてよい。
【００７０】
530で、UEは、複数のクラスタ重心を複数のスレッドおよび/またはプロセッサの間で分割する。UEは、ほぼ等しい数の重心を各スレッドおよび/またはプロセッサに割り当てればよい。スレッドおよび/またはプロセッサは、UEまたはそのUEと通信している1つもしくは複数の他のUE上に存在し得る。
【００７１】
540で、UEは、複数のスレッドおよび/またはプロセッサの各々に、データ点のストリームの一部分を割り当てる。UEは、複数のスレッドおよび/またはプロセッサに、ラウンドロビン、ランダム、階層的などの方式で、データ点を割り当てることができる。UEがデータ点を階層的に割り当てる場合、UEは、クラスタ重心の各々が異なるスレッドまたはプロセッサに対応する、クラスタ重心の小規模セットをプロビジョニングすればよい。UEは、重心のセットの1つに入力データ点を割り当て、次いで、データ点がその周囲でクラスタリングされている重心に対応するデータ点をスレッドまたはプロセッサに割り当てればよい。重心の小規模セット中の重心の数は、スレッドおよび/またはプロセッサの数に対応し得る。代替として、重心の小規模セット中のクラスタ重心の数はスレッドおよび/またはプロセッサの数よりも多い場合があり、その場合、重心のセットの各重心に関連付けられたデータ点のカウントに基づいて、スレッドまたはプロセッサにデータ点が割り当てられ得る。
【００７２】
UEは、データ点のストリームを割り当てるとき、複数のスレッドおよび/またはプロセッサの各々の速度を考慮してもよい。
【００７３】
複数のスレッドおよび/またはプロセッサの各々は、そのスレッドまたはプロセッサにプロビジョニングされた複数のクラスタ重心のサブセットの周囲に1つまたは複数のクラスタを生成する。スレッドまたはプロセッサは、データ点のストリームの担当部分を受信し始めるとすぐに、1つまたは複数のクラスタを生成し始めてよい。代替として、スレッドまたはプロセッサは、1つまたは複数のクラスタを生成し始める前に、担当データ点部分のうちの1つまたは複数のデータ点をバッファリングしてよい。
【００７４】
550で、UEは、複数のスレッドおよび/またはプロセッサの各々から1つまたは複数のクラスタを受信する。560で、UEは、受信したクラスタを組み合わせて、クラスタの大域的ユニバースを生成する。570で、UEは、データマイニングなどの後処理を、クラスタの大域的ユニバースに対して実施してよい。
【００７５】
図6は、UE200などのUEによって実施され得る、データ点のストリームをクラスタリングするための例示的なフローを示す。610で、UEは、データ点のストリームを受信する。UEは、データ点のストリームを、たとえば加速度計、ジャイロスコープ、磁力計、マイクロフォンなど、1つまたは複数のセンサから受信し得る。データ点のストリームが、複数のスレッドおよび/またはプロセッサでも効率的に処理するには多すぎるデータ点を含む場合、UEは、上述したように、処理しなければならないデータ点の数を削減するために、データ点をドロップしてもよい。
【００７６】
620で、UEは、複数のスレッドおよび/またはプロセッサの各々に、データ点のストリームの一部分を割り当てる。UEは、複数のスレッドおよび/またはプロセッサに、ラウンドロビン、ランダム、階層的などの方式で、データ点を割り当てることができる。UEは、データ点のストリームを割り当てるとき、複数のスレッドおよび/またはプロセッサの各々の速度を考慮してもよい。
【００７７】
630で、各スレッドおよび/またはプロセッサは、少なくとも1つのクラスタ重心を決定する。これらの重心は、図5の530でのように、UEによって割り当てられてもよく、各スレッドおよび/またはプロセッサが、入力データ点をクラスタリングすることによって重心を決定してもよい。たとえば、データ点の既存の重心までのユークリッド距離があまりにも大きいと判断された場合、スレッドは、そのデータ点を新たな重心として使うと決定してよい。その重心は次いで、複数の既存重心に追加されてよく、次いで、入力データ点の今後の照合に使われてよい。
【００７８】
640で、各スレッドおよび/またはプロセッサは、630で決定したクラスタ重心の周囲のデータ点のストリームの、それに割り当てられた一部分から、入力データ点をクラスタリングする。スレッドまたはプロセッサは、データ点のストリームの担当部分を受信し始めるとすぐに、1つまたは複数のクラスタを生成し始めてよい。代替として、スレッドまたはプロセッサは、1つまたは複数のクラスタを生成し始める前に、担当データ点部分のうちの1つまたは複数のデータ点をバッファリングしてよい。
【００７９】
650で、UEは、複数のスレッドおよび/またはプロセッサの各々から1つまたは複数のクラスタを受信する。660で、UEは、受信したクラスタを組み合わせて、クラスタの大域的ユニバースを生成する。670で、UEは、データマイニングなどの後処理を、クラスタの大域的ユニバースに対して実施してよい。
【００８０】
情報および信号が多種多様な技術および技法のいずれかを使用して表すことができることを、当業者は諒解されよう。たとえば、上記の説明全体を通して参照される場合があるデータ、命令、コマンド、情報、信号、ビット、シンボル、およびチップを電圧、電流、電磁波、磁場もしくは磁性粒子、光場もしくは光学粒子、またはそれらの任意の組合せによって表すことができる。
【００８１】
さらに、本明細書で開示する態様に関連して説明した様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装され得ることを当業者は理解されよう。ハードウェアおよびソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップは、一般的にそれらの機能性に関してこれまで説明されてきた。そのような機能性がハードウェアとして実現されるか、またはソフトウェアとして実現されるかは、具体的な適用例および全体的なシステムに課される設計制約によって決まる。当業者は、記載された機能を具体的な適用例ごとに様々な方法で実装することができるが、そのような実装の決定は、本開示の範囲からの逸脱をもたらすものと解釈されるべきではない。
【００８２】
本明細書で開示される実施形態に関して説明される様々な例示的な論理ブロック、モジュール、および回路は、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または、本明細書で説明される機能を実施するように設計されたそれらの任意の組合せによって、実装または実施され得る。汎用プロセッサはマイクロプロセッサであり得るが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であり得る。プロセッサはまた、コンピューティングデバイスの組合せ、たとえば、DSPとマイクロプロセッサとの組合せ、複数のマイクロプロセッサ、DSPコアと連携する1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成として実装することができる。
【００８３】
本明細書において開示する態様に関連して説明した方法、シーケンス、および/またはアルゴリズムは、ハードウェアで、プロセッサによって実行されるソフトウェアモジュールで、またはその2つの組合せで直接具現され得る。ソフトウェアモジュールは、RAM、フラッシュメモリ、ROM、EPROM、EEPROM、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野で知られている任意の他の形態の記憶媒体内に存在し得る。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読取り、そこに情報を書込みできるようにプロセッサに結合される。代替形態において、記憶媒体はプロセッサと一体であり得る。プロセッサおよび記憶媒体はASIC内に存在し得る。ASICはユーザ端末(たとえば、UE)内に存在し得る。代替形態では、プロセッサおよび記憶媒体は、ユーザ端末内に個別構成要素として存在し得る。
【００８４】
1つまたは複数の例示的な態様では、説明した機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せに実装される場合がある。ソフトウェアに実装される場合、機能は、1つもしくは複数の命令またはコードとして、コンピュータ可読媒体上に記憶することができるか、または、コンピュータ可読媒体を介して送信することができる。コンピュータ可読媒体は、ある場所から別の場所へのコンピュータプログラムの転送を可能にする任意の媒体を含む、コンピュータ記憶媒体とコンピュータ通信媒体の両方を含む。記憶媒体は、コンピュータによってアクセス可能である任意の利用可能な媒体であり得る。限定ではなく例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶デバイス、磁気ディスク記憶デバイスもしくは他の磁気記憶デバイス、あるいは、命令もしくはデータ構造の形態の所望のプログラムコードを搬送または記憶するために使用することができ、コンピュータによってアクセス可能である、任意の他の媒体を含むことができる。また、任意の接続も適切にコンピュータ可読媒体と称される。たとえば、同軸ケーブル、光ファイバケーブル、ツイストペア、デジタル加入者回線(DSL)、または赤外線、無線、およびマイクロ波などのワイヤレス技術を使用して、ウェブサイト、サーバ、または他のリモートソースからソフトウェアが送信される場合、同軸ケーブル、光ファイバケーブル、ツイストペア、DSL、または赤外線、無線、およびマイクロ波などのワイヤレス技術は、媒体の定義に含まれる。本明細書で使用する場合、ディスク(disk)およびディスク(disc)は、コンパクトディスク(disc)(CD)、レーザディスク(disc)、光ディスク(disc)、デジタル多用途ディスク(disc)(DVD)、フロッピー(登録商標)ディスク(disk)およびブルーレイディスク(disc)を含み、ディスク(disk)は、通常、データを磁気的に再生し、ディスク(disc)は、データをレーザで光学的に再生する。前述の組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。
【００８５】
上記の開示は本開示の例示的な態様を示すが、添付の特許請求の範囲によって規定される本開示の範囲から逸脱することなく、本明細書で様々な変更および修正が行われ得ることに留意されたい。本明細書で説明した本開示の態様による方法クレームの機能、ステップおよび/または動作は、特定の順序で実施される必要はない。さらに、本開示の要素は、単数形で記載または特許請求されている場合があるが、単数形に限定することが明示的に述べられていない限り、複数形が考えられる。
【符号の説明】
【００８６】
100  ワイヤレス通信システム
104  エアインターフェース
106  エアインターフェース、WAN-WAP、LAN-WAP
108  エアインターフェース
120  RAN
125  アクセスポイント
140  コアネットワーク
170  アプリケーションサーバ
175  インターネット
200  UE
202  アンテナ
204  ワイドエリアネットワーク(WAN)トランシーバ
206  ローカルエリアネットワーク(LAN)トランシーバ
208  衛星測位システム(SPS)受信機
210  プロセッサ
212  動きセンサ
214  メモリ
216  ワイヤレスベースの測位モジュール
218  アプリケーションモジュール
224  パラメータデータベース
226  位置/動きデータモジュール、補助的な位置/動きデータ
228  測位モジュール
250  ユーザインターフェース
252  マイクロフォン/スピーカ
254  キーパッド
256  ディスプレイ
300  通信デバイス
305  情報を受信および/または送信するように構成された論理手段
310  情報を処理するように構成された論理手段
315  情報を記憶するように構成された論理手段
320  情報を提示するように構成された論理手段
325  ローカルユーザ入力を受信するように構成された論理手段
【図１】
2016530591.tif 000003
【図２】
2016530591.tif 000004
【図３】
2016530591.tif 000005
【図４】
2016530591.tif 000006
【図５】
2016530591.tif 000007
【図６】
2016530591.tif 000008
【手続補正書】
【提出日】平成27年5月14日(2015.5.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ点のストリームをクラスタリングするための方法であって、
前記データ点のストリームを受信するステップと、
複数のクラスタ重心を決定するステップと、
前記複数のクラスタ重心をクラスタ重心の複数のグループに分割するステップであって、クラスタ重心の前記複数のグループの各グループが、前記複数のクラスタ重心のうちのすべて未満を含み、複数のスレッドおよび/またはプロセッサの中の異なるスレッドおよび/またはプロセッサによって独立して利用される、ステップと、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てて、複数のクラスタを生成するステップと、
前記複数のスレッドおよび/またはプロセッサによって生成された前記複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するステップとを含む方法。
【請求項２】
受信する前記ステップが、
1つまたは複数のセンサから前記データ点のストリームを受信するステップを含む、請求項1に記載の方法。
【請求項３】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項2に記載の方法。
【請求項４】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサにラウンドロビン方式で割り当てられる、請求項1に記載の方法。
【請求項５】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサに階層的に割り当てられる、請求項1に記載の方法。
【請求項６】
前記データ点のストリームの前記一部分を割り当てる前記ステップが、
受信したデータ点を、前記複数のクラスタ重心のうちの1つに割り当てるステップと、
前記受信したデータ点を、前記複数のクラスタ重心のうちの前記1つに対応するスレッドまたはプロセッサに割り当てるステップとを含む、請求項5に記載の方法。
【請求項７】
前記複数のクラスタ重心中のクラスタ重心の数が、スレッドおよび/またはプロセッサの数に対応する、請求項6に記載の方法。
【請求項８】
前記複数のクラスタ重心中のクラスタ重心の数が前記複数のスレッドおよび/またはプロセッサの数よりも多く、前記受信したデータ点が、前記複数のクラスタ重心の各クラスタ重心に関連したデータ点のカウントに基づいてスレッドまたはプロセッサに割り当てられる、請求項6に記載の方法。
【請求項９】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサの各々の速度に基づいて、前記複数のスレッドおよび/またはプロセッサに割り当てられる、請求項1に記載の方法。
【請求項１０】
前記複数のスレッドおよび/またはプロセッサの各々が、前記複数のスレッドおよび/またはプロセッサの各々にプロビジョニングされたクラスタ重心の前記複数のグループのうちの前記グループの1つまたは複数の重心の周囲に1つまたは複数のクラスタを生成する、請求項1に記載の方法。
【請求項１１】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項10に記載の方法。
【請求項１２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、データ点の前記一部分の1つまたは複数のデータ点をバッファリングする、請求項10に記載の方法。
【請求項１３】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするステップをさらに含む、請求項1に記載の方法。
【請求項１４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるステップをさらに含む、請求項1に記載の方法。
【請求項１５】
クラスタの前記大域的ユニバースに対して後処理を実施するステップをさらに含む、請求項1に記載の方法。
【請求項１６】
前記複数のプロセッサおよび/またはスレッドがユーザ機器上に存在する、請求項1に記載の方法。
【請求項１７】
前記複数のプロセッサおよび/またはスレッドが複数のユーザ機器上に存在する、請求項1に記載の方法。
【請求項１８】
データ点のストリームをクラスタリングするための方法であって、
前記データ点のストリームを受信するステップと、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるステップであって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、ステップと、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するステップとを含む方法。
【請求項１９】
受信する前記ステップが、
1つまたは複数のセンサから前記データ点のストリームを受信するステップを含む、請求項18に記載の方法。
【請求項２０】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項19に記載の方法。
【請求項２１】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項18に記載の方法。
【請求項２２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、データ点の前記一部分の1つまたは複数のデータ点をバッファリングする、請求項18に記載の方法。
【請求項２３】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするステップをさらに含む、請求項18に記載の方法。
【請求項２４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるステップをさらに含む、請求項18に記載の方法。
【請求項２５】
複数のクラスタ重心を決定するステップと、
前記複数のクラスタ重心を前記複数のスレッドおよび/またはプロセッサの間で分割するステップとをさらに含む、請求項18に記載の方法。
【請求項２６】
前記複数のクラスタ重心が、クラスタ重心に加え、前記複数のスレッドおよび/またはプロセッサによって決定される、請求項25に記載の方法。
【請求項２７】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの、各々に割り当てられた部分に基づいて、前記1つまたは複数のクラスタ重心を決定する、請求項18に記載の方法。
【請求項２８】
前記複数のスレッドおよび/またはプロセッサの各々から、前記データ点のストリームのクラスタリング部分を受信するステップをさらに含む、請求項18に記載の方法。
【請求項２９】
クラスタの前記大域的ユニバースに対して後処理を実施するステップをさらに含む、請求項18に記載の方法。
【請求項３０】
前記複数のスレッドおよび/またはプロセッサがモバイルデバイス上に存在する、請求項18に記載の方法。
【請求項３１】
前記複数のスレッドおよび/またはプロセッサが複数のモバイルデバイス上に存在する、請求項18に記載の方法。
【請求項３２】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するように構成された論理手段と、
複数のクラスタ重心を決定するように構成された論理手段と、
前記複数のクラスタ重心をクラスタ重心の複数のグループに分割するように構成された論理手段であって、クラスタ重心の前記複数のグループの各グループが、前記複数のクラスタ重心のうちのすべて未満を含み、複数のスレッドおよび/またはプロセッサの中の異なるスレッドおよび/またはプロセッサによって独立して利用される、論理手段と、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てて、複数のクラスタを生成するように構成された論理手段と、
前記複数のスレッドおよび/またはプロセッサによって生成された前記複数のクラスタを連結して、クラスタの大域的ユニバースを生成するように構成された論理手段とを備える装置。
【請求項３３】
受信するように構成された前記論理手段が、
1つまたは複数のセンサから前記データ点のストリームを受信するように構成された論理手段を備える、請求項32に記載の装置。
【請求項３４】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項33に記載の装置。
【請求項３５】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサにラウンドロビン方式で割り当てられる、請求項32に記載の装置。
【請求項３６】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサに階層的に割り当てられる、請求項32に記載の装置。
【請求項３７】
前記データ点のストリームの前記一部分を割り当てるように構成された前記論理手段が、
受信したデータ点を、前記複数のクラスタ重心のうちの1つに割り当てるように構成された論理手段と、
前記受信したデータ点を、前記複数のクラスタ重心のうちの前記1つに対応するスレッドまたはプロセッサに割り当てるように構成された論理手段とを備える、請求項36に記載の装置。
【請求項３８】
前記複数のクラスタ重心中のクラスタ重心の数が、スレッドおよび/またはプロセッサの数に対応する、請求項37に記載の装置。
【請求項３９】
前記複数のクラスタ重心中のクラスタ重心の数が前記複数のスレッドおよび/またはプロセッサの数よりも多く、前記受信したデータ点が、前記クラスタ重心のセットの各クラスタ重心に関連したデータ点のカウントに基づいてスレッドまたはプロセッサに割り当てられる、請求項37に記載の装置。
【請求項４０】
前記データ点のストリームが、前記複数のスレッドおよび/またはプロセッサの各々の速度に基づいて、前記複数のスレッドおよび/またはプロセッサに割り当てられる、請求項32に記載の装置。
【請求項４１】
前記複数のスレッドおよび/またはプロセッサの各々が、前記複数のスレッドおよび/またはプロセッサの各々にプロビジョニングされたクラスタ重心の前記複数のグループのうちの前記グループの1つまたは複数の重心の周囲に1つまたは複数のクラスタを生成する、請求項32に記載の装置。
【請求項４２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項41に記載の装置。
【請求項４３】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、前記データ点のストリームの前記一部分の1つまたは複数のデータ点をバッファリングする、請求項41に記載の装置。
【請求項４４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするように構成された論理手段をさらに備える、請求項32に記載の装置。
【請求項４５】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるように構成された論理手段をさらに備える、請求項32に記載の装置。
【請求項４６】
クラスタの前記大域的ユニバースに対して後処理を実施するように構成された論理手段をさらに備える、請求項32に記載の装置。
【請求項４７】
前記複数のスレッドおよび/またはプロセッサがユーザ機器上に存在する、請求項32に記載の装置。
【請求項４８】
前記複数のスレッドおよび/またはプロセッサが複数のユーザ機器上に存在する、請求項32に記載の装置。
【請求項４９】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するように構成された論理手段と、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるように構成された論理手段であって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、論理手段と、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するように構成された論理手段とを備える装置。
【請求項５０】
受信するように構成された前記論理手段が、
1つまたは複数のセンサから前記データ点のストリームを受信するように構成された論理手段を備える、請求項49に記載の装置。
【請求項５１】
前記1つまたは複数のセンサが、加速度計、ジャイロスコープ、磁力計、またはマイクロフォンのうちの1つまたは複数である、請求項50に記載の装置。
【請求項５２】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの前記一部分を受信し始めると、前記1つまたは複数のクラスタを生成し始める、請求項49に記載の装置。
【請求項５３】
前記複数のスレッドおよび/またはプロセッサの各々が、前記1つまたは複数のクラスタを生成し始める前に、前記データ点のストリームの前記一部分の1つまたは複数のデータ点をバッファリングする、請求項49に記載の装置。
【請求項５４】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリーム中のデータ点をドロップするように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項５５】
前記データ点のストリーム中のデータ点の数を削減するために、前記データ点のストリームを生成する1つまたは複数のセンサのサンプリングレートを低下させるように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項５６】
複数のクラスタ重心を決定するように構成された論理手段と、
前記複数のクラスタ重心を前記複数のスレッドおよび/またはプロセッサの間で分割するように構成された論理手段とをさらに備える、請求項49に記載の装置。
【請求項５７】
前記複数のクラスタ重心が、クラスタ重心に加え、前記複数のスレッドおよび/またはプロセッサによって決定される、請求項56に記載の装置。
【請求項５８】
前記複数のスレッドおよび/またはプロセッサの各々が、前記データ点のストリームの、各々に割り当てられた部分に基づいて、前記1つまたは複数のクラスタ重心を決定する、請求項49に記載の装置。
【請求項５９】
前記複数のスレッドおよび/またはプロセッサの各々から、前記データ点のストリームのクラスタリング部分を受信するように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項６０】
クラスタの前記大域的ユニバースに対して後処理を実施するように構成された論理手段をさらに備える、請求項49に記載の装置。
【請求項６１】
前記複数のスレッドおよび/またはプロセッサがモバイルデバイス上に存在する、請求項49に記載の装置。
【請求項６２】
前記複数のスレッドおよび/またはプロセッサが複数のモバイルデバイス上に存在する、請求項49に記載の装置。
【請求項６３】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するための手段と、
複数のクラスタ重心を決定するための手段と、
前記複数のクラスタ重心をクラスタ重心の複数のグループに分割するための手段であって、クラスタ重心の前記複数のグループの各グループが、前記複数のクラスタ重心のうちのすべて未満を含み、複数のスレッドおよび/またはプロセッサの中の異なるスレッドおよび/またはプロセッサによって独立して利用される、手段と、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てて、複数のクラスタを生成するための手段と、
前記複数のスレッドおよび/またはプロセッサによって生成された前記複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するための手段とを備える装置。
【請求項６４】
データ点のストリームをクラスタリングするための装置であって、
前記データ点のストリームを受信するための手段と、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための手段であって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、手段と、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するための手段とを備える装置。
【請求項６５】
データ点のストリームをクラスタリングするための非一時的コンピュータ可読媒体であって、
前記データ点のストリームを受信するための少なくとも1つの命令と、
複数のクラスタ重心を決定するための少なくとも1つの命令と、
前記複数のクラスタ重心をクラスタ重心の複数のグループに分割するための少なくとも1つの命令であって、クラスタ重心の前記複数のグループの各グループが、前記複数のクラスタ重心のうちのすべて未満を含み、複数のスレッドおよび/またはプロセッサの中の異なるスレッドおよび/またはプロセッサによって独立して利用される、命令と、
前記データ点のストリームの一部分を前記複数のスレッドおよび/またはプロセッサの各々に割り当てて、複数のクラスタを生成するための少なくとも1つの命令と、
前記複数のスレッドおよび/またはプロセッサによって生成された前記複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するための少なくとも1つの命令とを備える非一時的コンピュータ可読媒体。
【請求項６６】
データ点のストリームをクラスタリングするための非一時的コンピュータ可読媒体であって、
前記データ点のストリームを受信するための少なくとも1つの命令と、
前記データ点のストリームの一部分を複数のスレッドおよび/またはプロセッサの各々に割り当てるための少なくとも1つの命令であって、前記複数のスレッドおよび/またはプロセッサの各々が、1つまたは複数のクラスタ重心を決定し、前記1つまたは複数のクラスタ重心の周囲に1つまたは複数のクラスタを生成する、命令と、
前記複数のスレッドおよび/またはプロセッサの各々からの前記1つまたは複数のクラスタを連結して、クラスタの単一の大域的ユニバースを生成するための少なくとも1つの命令とを備える非一時的コンピュータ可読媒体。
【国際調査報告】
2016530591.tif 000009
2016530591.tif 000010