(57)【要約】【課題】処理量を抑制した高速なクラスタリング処理を可能にする。【解決手段】情報処理装置１００は、Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間１００１の位置情報を有するデータ１０１１について、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を各次元について順に１桁ずつ配列したＮ進数値を生成するＮ進数値生成部１０１と、Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通するデータ１０１１を同一のクラスタ１０２１に分類するクラスタリング部１０３とを備える。【選択図】図７
2012113625.tif 000002
【特許請求の範囲】
【請求項１】
Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間の位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を前記各次元について順に１桁ずつ配列したＮ進数値を生成するＮ進数値生成部と、
前記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する前記データを同一のクラスタに分類するクラスタリング部と、
を備える情報処理装置。
【請求項２】
前記クラスタリング部は、ｋ＝Ｄ×ｍ（ｍ＝１，２，・・・）である場合に、前記Ｎ進数値の上位ｋ桁が共通する前記データを、ＮＤ分木構造クラスタのｍ層目で同一のクラスタに分類する、
請求項１に記載の情報処理装置。
【請求項３】
前記クラスタリング部は、前記データを前記Ｎ進数値の順にソートするクラスタリング用ソート部を含み、前記ソートの結果から、前記同一のクラスタに分類される前記データを特定する、
請求項１または２に記載の情報処理装置。
【請求項４】
前記クラスタリング部は、前記ソートの結果において、一のクラスタに分類された前記データが現れる最初の位置と、当該一のクラスタに分類された前記データの数とによって、当該一のクラスタを特定するクラスタ特定情報を生成する、
請求項３に記載の情報処理装置。
【請求項５】
前記Ｄ次元の座標に基づく第１の順位決定処理の結果に基づいて、前記特徴空間における第１の方向について前記クラスタをソートするマージ用ソート部と、
前記第１の方向についてソートされたクラスタが、前記第１の方向で互いに隣接するか否かを判定する隣接判定部と、
を含み、前記第１の方向について互いに隣接すると判定されたクラスタをマージするマージ部をさらに備える、請求項１〜４のいずれか１項に記載の情報処理装置。
【請求項６】
前記マージ用ソート部は、前記Ｄ次元の座標に基づく第２の順位決定処理の結果に基づいて、前記特徴空間における第２の方向について前記クラスタをソートし、
前記隣接判定部は、前記第２の方向についてソートされたクラスタが、前記第２の方向で互いに隣接するか否かを判定し、
前記マージ部は、さらに、前記第２の方向について互いに隣接すると判定されたクラスタをマージする、
請求項５に記載の情報処理装置。
【請求項７】
前記特徴空間は、地表面であり、
前記Ｄ次元の座標は、緯度および経度からなる２次元の座標であり、
前記クラスタは、前記２次元の座標によって前記地表面上に定義されるグリッドに含まれる前記データの位置情報を包含する領域であり、
前記第１の順位決定処理は、前記第１の方向について前記グリッドをソートし、各グリッドに含まれるクラスタに当該グリッドのソート順を順位として与える処理である、
請求項５に記載の情報処理装置。
【請求項８】
前記特徴空間は、３次元空間であり、
前記Ｄ次元の座標は、直交座標系を構成する３次元の座標であり、
前記クラスタは、前記３次元の座標によって前記３次元空間内に定義されるブロックに含まれる前記データの位置情報を包含する領域である、
請求項１に記載の情報処理装置。
【請求項９】
Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間における位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を前記各次元について順に１桁ずつ配列したＮ進数値を生成するステップと、
前記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する前記データを同一のクラスタに分類するステップと、
を含む情報処理方法。
【請求項１０】
Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間における位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を前記各次元について順に１桁ずつ配列したＮ進数値を生成する処理と、
前記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する前記データを同一のクラスタに分類する処理と、
をコンピュータに実行させるプログラム。
【請求項１１】
前記Ｄ次元の座標に基づく第１の順位決定処理の結果に基づいて、前記特徴空間における第１の方向について前記クラスタをソートする処理と、
前記第１の方向についてソートされたクラスタが、前記第１の方向で互いに隣接するか否かを判定する処理と、
前記第１の方向について互いに隣接すると判定されたクラスタをマージする処理と、
をさらにコンピュータに実行させる、請求項１０に記載のプログラム。
【請求項１２】
前記クラスタをマージする処理は、
前記クラスタの相互間の距離を算出する処理と、
前記算出された距離が所定の閾値以下である場合に、前記クラスタをマージする処理と、
を含む、請求項１１に記載のプログラム。
【請求項１３】
前記クラスタをマージする処理は、
前記クラスタの相互間の距離を算出する処理と、
前記算出された距離が所定の閾値以下である場合に、前記クラスタをマージ候補クラスタとして記憶する処理と、
前記記憶されたマージ候補クラスタのうち、前記相互間の距離が小さいマージ候補クラスタから順にマージする処理と、
を含む、請求項１１に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処置装置、情報処置方法およびプログラムに関する。
【背景技術】
【０００２】
特徴空間上のデータを、データが有する位置情報に基づいてクラスタリングする技術が知られている。クラスタリングによって同一のクラスタに分類されたデータは、特徴空間において近い位置にあるデータ、すなわち特徴空間によって表される特徴が似ているデータであると考えられる。このようなクラスタリングを利用する技術として、例えば、特許文献１には、画像データに撮影場所の位置情報を付加し、この位置情報に基づいたクラスタリングによって画像データを撮影場所ごとに分類する技術が記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−１４０３８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、クラスタリングの処理は、位置情報を有する複数のデータのそれぞれについて相互間の距離を算出するため、距離計算の処理負荷が大きくなる傾向がある。また、大量のメモリを必要とする傾向がある。それゆえ、クラスタリングの処理の処理速度の向上が課題となっている。
【０００５】
本発明は、上記課題に鑑みてなされたものであり、本発明の目的とするところは、処理量を抑制した高速なクラスタリング処理が可能な、新規かつ改良された情報処置装置、情報処置方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明のある観点によれば、Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間の位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を上記各次元について順に１桁ずつ配列したＮ進数値を生成するＮ進数値生成部と、上記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する上記データを同一のクラスタに分類するクラスタリング部とを備える情報処理装置が提供される。
【０００７】
上記クラスタリング部は、ｋ＝Ｄ×ｍ（ｍ＝１，２，・・・）である場合に、上記Ｎ進数値の上位ｋ桁が共通する上記データを、ＮＤ分木構造クラスタのｍ層目で同一のクラスタに分類してもよい。
【０００８】
上記クラスタリング部は、上記データを上記Ｎ進数値の順にソートするクラスタリング用ソート部を含み、上記ソートの結果から、上記同一のクラスタに分類される上記データを特定してもよい。
【０００９】
上記クラスタリング部は、上記ソートの結果において、一のクラスタに分類された上記データが現れる最初の位置と、当該一のクラスタに分類された上記データの数とによって、当該一のクラスタを特定するクラスタ特定情報を生成してもよい。
【００１０】
上記情報処理装置は、上記Ｄ次元の座標に基づく第１の順位決定処理の結果に基づいて、上記特徴空間における第１の方向について上記クラスタをソートするマージ用ソート部と、上記第１の方向についてソートされたクラスタが、上記第１の方向で互いに隣接するか否かを判定する隣接判定部と、を含み、上記第１の方向について互いに隣接すると判定されたクラスタをマージするマージ部をさらに備えてもよい。
【００１１】
上記マージ用ソート部は、上記Ｄ次元の座標に基づく第２の順位決定処理の結果に基づいて、上記特徴空間における第２の方向について上記クラスタをソートし、上記隣接判定部は、上記第２の方向についてソートされたクラスタが、上記第２の方向で互いに隣接するか否かを判定し、上記マージ部は、さらに、上記第２の方向について互いに隣接すると判定されたクラスタをマージしてもよい。
【００１２】
上記特徴空間は、地表面であり、上記Ｄ次元の座標は、緯度および経度からなる２次元の座標であり、上記クラスタは、上記２次元の座標によって上記地表面上に定義されるグリッドに含まれる上記データの位置情報を包含する領域であり、上記第１の順位決定処理は、上記第１の方向について上記グリッドをソートし、各グリッドに含まれるクラスタに当該グリッドのソート順を順位として与える処理であってもよい。
【００１３】
上記特徴空間は、３次元空間であり、上記Ｄ次元の座標は、直交座標系を構成する３次元の座標であり、上記クラスタは、上記３次元の座標によって上記３次元空間内に定義されるブロックに含まれる上記データの位置情報を包含する領域であってもよい。
【００１４】
また、上記課題を解決するために、本発明の別の観点によれば、Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間における位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を上記各次元について順に１桁ずつ配列したＮ進数値を生成するステップと、上記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する上記データを同一のクラスタに分類するステップとを含む情報処理方法が提供される。
【００１５】
また、上記課題を解決するために、本発明のさらに別の観点によれば、Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間における位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を上記各次元について順に１桁ずつ配列したＮ進数値を生成する処理と、上記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する上記データを同一のクラスタに分類する処理とをコンピュータに実行させるプログラムが提供される。
【００１６】
上記プログラムは、上記Ｄ次元の座標に基づく第１の順位決定処理の結果に基づいて、上記特徴空間における第１の方向について上記クラスタをソートする処理と、上記第１の方向についてソートされたクラスタが、上記第１の方向で互いに隣接するか否かを判定する処理と、上記第１の方向について互いに隣接すると判定されたクラスタをマージする処理とをさらにコンピュータに実行させてもよい。
【００１７】
上記クラスタをマージする処理は、上記クラスタの相互間の距離を算出する処理と、上記算出された距離が所定の閾値以下である場合に、上記クラスタをマージする処理とを含んでもよい。
【００１８】
上記クラスタをマージする処理は、上記クラスタの相互間の距離を算出する処理と、上記算出された距離が所定の閾値以下である場合に、上記クラスタをマージ候補クラスタとして記憶する処理と、上記記憶されたマージ候補クラスタのうち、上記相互間の距離が小さいマージ候補クラスタから順にマージする処理とを含んでもよい。
【発明の効果】
【００１９】
以上説明したように本発明によれば、処理量を抑制した高速なクラスタリング処理が可能になる。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施形態におけるコンテンツ、クラスタ、およびグリッドの関係の例を示す図である。
【図２】本発明の第１の実施形態におけるグリッドの階層構造の例を示す図である。
【図３】本発明の第１の実施形態におけるクラスタリングの結果の例を示す図である。
【図４】本発明の第１の実施形態におけるグリッドベースのクラスタリングと、一般的な距離ベースのクラスタリングとを比較して説明するための図である。
【図５】本発明の第１の実施形態におけるグリッドベースのクラスタリングと、一般的な距離ベースのクラスタリングとを比較して説明するための図である。
【図６】本発明の第１の実施形態に係る情報処理装置の構成を示すブロック図である。
【図７】本発明の第１の実施形態におけるクラスタリングについて説明するための図である。
【図８】本発明の第１の実施形態におけるクラスタのマージについて説明するための図である。
【図９】本発明の第１の実施形態におけるクラスタリングおよびマージ処理を示すフローチャートである。
【図１０】本発明の第１の実施形態におけるクラスタリングについて説明するための図である。
【図１１】本発明の第１の実施形態におけるクラスタ特定情報について説明するための図である。
【図１２】本発明の第１の実施形態におけるマージ関連処理を示すフローチャートである。
【図１３】本発明の第１の実施形態におけるマージ設定情報の例を示す図である。
【図１４】本発明の第１の実施形態におけるマージ設定選択処理を示すフローチャートである。
【図１５】本発明の第１の実施形態における探索順マージ処理を示すフローチャートである。
【図１６】本発明の第１の実施形態におけるフルマッチマージ処理を示すフローチャートである。
【図１７Ａ】本発明の第１の実施形態における水平方向でのグリッド探索を示す図である。
【図１７Ｂ】本発明の第１の実施形態における垂直方向でのグリッド探索を示す図である。
【図１７Ｃ】本発明の第１の実施形態における斜め右下方向でのグリッド探索を示す図である。
【図１７Ｄ】本発明の第１の実施形態における斜め右上方向でのグリッド探索を示す図である。
【図１８Ａ】本発明の第１の実施形態における１方向探索について説明するための図である。
【図１８Ｂ】本発明の第１の実施形態における２方向探索について説明するための図である。
【図１８Ｃ】本発明の第１の実施形態における４方向探索について説明するための図である。
【図１９】本発明の第１の実施形態における近傍探索マージ処理（上位探索なし）を示すフローチャートである。
【図２０】本発明の第１の実施形態における隣接探索処理（上位探索なし）を示すフローチャートである。
【図２１】本発明の第１の実施形態における近傍探索マージ処理（上位探索あり）を示すフローチャートである。
【図２２】本発明の第１の実施形態における上位グリッドリストの例を示す図である。
【図２３】本発明の第１の実施形態における上位グリッドリストの例を示す図である。
【図２４】本発明の第１の実施形態における隣接探索処理（上位探索あり）について説明するための図である。
【図２５】本発明の第１の実施形態における隣接探索処理（上位探索あり）を示すフローチャートである。
【図２６】本発明の第１の実施形態における隣接探索処理（上位探索あり）について説明するための図である。
【図２７】本発明の第１の実施形態における近傍探索マージ処理（上位探索あり）のマージ対象グリッドの例を示す図である。
【図２８】本発明の第１の実施形態における距離順ソートの概要について説明するための図である。
【図２９】本発明の第１の実施形態における距離順マージ処理を示すフローチャートである。
【図３０Ａ】本発明の第２の実施形態におけるコンテンツ、クラスタ、およびブロックの関係の例を示す図である。
【図３０Ｂ】本発明の第２の実施形態におけるコンテンツおよびクラスタの表示の例を示す図である。
【図３１】本発明の第２の実施形態におけるブロックによる地表面の分割について説明するための図である。
【図３２】本発明の第２の実施形態におけるブロックによる地表面の分割について説明するための図である。
【図３３】本発明の第２の実施形態におけるブロックによる地表面の分割について説明するための図である。
【図３４】本発明の第２の実施形態におけるクラスタリングについて説明するための図である。
【図３５】本発明の実施形態に係る情報処理装置のハードウェア構成を説明するためのブロック図である。
【発明を実施するための形態】
【００２１】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書および図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２２】
なお、説明は以下の順序で行うものとする。
１．第１の実施形態
１−１．グリッドベースの位置クラスタリングの概要
１−２．情報処理装置の構成
１−３．クラスタリングおよびマージ処理の詳細
２．第２の実施形態
２−１．ブロックベースの位置クラスタリングの概要
３．本発明の実施形態に係る情報処理装置のハードウェア構成
４．まとめ
【００２３】
＜１．第１の実施形態＞
本発明の第１の実施形態では、地表面が特徴空間に相当する。また、本実施形態において、地表面における位置情報は、緯度および経度という２次元の座標によって表される。また、本実施形態において、クラスタは、緯度および経度によって地表面上に定義されるグリッドに含まれるコンテンツの位置情報を包含する領域である。
【００２４】
（１−１．グリッドベースの位置クラスタリングの概要）
まず、図１〜図５を参照して、本発明の第１の実施形態におけるクラスタリングの概要について説明する。本実施形態におけるクラスタリングは、緯度および経度という２次元の座標によって定義されるグリッドを基準にして、位置情報を有するコンテンツをクラスタに分類するものであり、グリッドベースの位置クラスタリングともいえるものである。
【００２５】
（グリッドについて）
図１は、本発明の第１の実施形態におけるコンテンツ、クラスタ、およびグリッドの関係の例を示す図である。図１には、地表面１００１、コンテンツ１０１１、クラスタ１０２１、およびグリッド１０３１が図示されている。
【００２６】
地表面１００１は、地球の表面の全部または一部の領域である。本実施形態において、地表面１００１は、緯度および経度という２次元の座標によって位置情報が表される２次元平面として扱われる。
【００２７】
コンテンツ１０１１は、地表面１００１上の位置を特定する位置情報を有するデータである。コンテンツ１０１１は、位置情報そのものであってもよく、また、何らかの情報に対する付加的な情報として位置情報が付加されたデータであってもよい。コンテンツ１０１１は、例えば、撮影場所の位置情報が付加された画像データでありうる。
【００２８】
クラスタ１０２１は、地表面１００１において互いに近い位置にあるコンテンツ１０１１を含む領域である。クラスタ１０２１は、略矩形として図示されているが、その他の形状であってもよい。クラスタ１０２１は、クラスタ１０２１に含まれるコンテンツ１０１１の外接図形であってもよい。
【００２９】
グリッド１０３１は、地表面１００１に設定されたグリッドである。グリッド１０３１は、地表面１００１上で緯度および経度の範囲によって定義される矩形の領域でありうる。グリッド１０３１の大きさは、後述するように、コンテンツ１０１１の数、およびクラスタリングの対象となる領域の大きさなど、クラスタリングの条件に応じて、適切な大きさに設定されうる。
【００３０】
図示されているように、本実施形態においては、同じグリッド１０３１に含まれるコンテンツ１０１１が、同じクラスタ１０２１に分類される。クラスタ１０２１のマージが実行される場合を除いて、コンテンツ１０１１が分類される一のクラスタ１０２１の領域は、一のグリッド１０３１の領域に含まれる。つまり、本実施形態におけるグリッドベースの位置クラスタリング処理においては、同じグリッド１０３１に含まれるか否かが、クラスタリングの基本的な基準になる。
【００３１】
ここで、一般的な距離ベースの位置クラスタリングでは、コンテンツ間の距離を算出し、その距離を所定の閾値または他のコンテンツ間の距離と比較する処理が行われる。かかる処理では、コンテンツの組み合わせの数だけ距離計算をするため、距離計算の処理負荷が大きくなる。また、コンテンツ間の距離を他のコンテンツ間の距離と比較する場合、算出された距離を一時的に保持しておくために多くの記憶領域が使用される。
【００３２】
一方、本実施形態におけるグリッドベースの位置クラスタリングでは、コンテンツ１０１１の位置情報そのものが、コンテンツ１０１１が含まれるグリッド１０３１を表している。後述するように、コンテンツ１０１１を、緯度および経度の値を順に１桁ずつ配列したＮ進数値の順にソートすると、同一のグリッド１０３１の領域に含まれるコンテンツ１０１１は、ソートの結果において互いに隣接する。ソートの結果において隣接したコンテンツ１０１１同士が同一のグリッド１０３１に含まれるか否かは、例えば、上記のＮ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通するか否かによって判定されうる。ここで、上述のように、同一のグリッド１０３１に含まれるコンテンツ１０１１は、同一のクラスタ１０２１に分類されるコンテンツである。それゆえ、本実施形態におけるグリッドベースの位置クラスタリングでは、コンテンツ１０１１の位置情報から生成した数値をソートすることが、クラスタリングの主な処理になる。ソート処理は、上記の距離計算よりも処理負荷が小さく、また処理回数も少なくて済む。従って、本実施形態におけるグリッドベースの位置クラスタリングでは、処理速度が向上し、使用する記憶領域も削減される。
【００３３】
（グリッドの階層構造について）
図２は、本発明の第１の実施形態におけるグリッドの階層構造の例を示す図である。図２には、レベル０グリッド１０３２、レベル１グリッド１０３３、およびレベル２グリッド１０３４が図示されている。
【００３４】
レベル０グリッド１０３２は、地表面１００１の全体を範囲とする、階層構造の最上位のグリッドである。つまり、階層構造の最上位においては、地表面１００１全体が１つのグリッドに含まれる。
【００３５】
レベル１グリッド１０３３は、レベル０グリッド１０３２を、緯度方向および経度方向でそれぞれ２分割したグリッドである。換言すれば、レベル１グリッド１０３３は、レベル０グリッド１０３２の領域である地表面１００１全体を４分割する。
【００３６】
レベル２グリッド１０３４は、レベル１グリッド１０３３を、緯度方向および経度方向でそれぞれ２分割したグリッドである。換言すれば、レベル２グリッド１０３４は、レベル１グリッド１０３３の領域を４分割する。つまり、レベル２グリッド１０３４は、レベル０グリッド１０３２の領域である地表面１００１全体を１６分割する。
【００３７】
グリッドの階層構造は、同様にしてさらに下位のレベルに拡張される。具体的には、レベル２グリッド１０３４の領域を４分割したレベル３グリッド、レベル３グリッドの領域を４分割したレベル４グリッド、・・・というように、さらに細かい領域のグリッドが定義されうる。クラスタリング処理に用いられるグリッドのレベルを調整することによって、クラスタリングの粒度と処理負荷をバランスさせることが可能である。
【００３８】
このように、本実施形態においては、あるレベルのグリッドを緯度方向および経度方向にそれぞれ２分割したグリッドが、１つ下位のレベルのグリッドになる。換言すれば、下位のレベルのグリッドは、上位のレベルのグリッドの領域を４分割する。従って、本実施形態におけるグリッド１０３１の階層構造は、レベル０グリッド１０３２をルートノードとし、以下の各レベルのグリッドをノードとする４分木構造を有し、グリッド１０３１に従って定義されるクラスタ１０２１もまた、同様の４分木構造を有する。
【００３９】
ここで、一般的な距離ベースの位置クラスタリングでは、クラスタの木構造が定義された場合、その木構造の情報を保持する記憶領域が消費される。一方、本実施形態におけるグリッドベースの位置クラスタリングでは、上述のようにグリッド１０３１の４分木構造が一意に定まっているため、グリッド１０３１がどのレベルのグリッドであるかという情報が保持されていれば、グリッド１０３１の４分木構造に基づいて、クラスタ１０２１の木構造を容易に把握することが可能である。
【００４０】
（クラスタリングの結果について）
図３は、本発明の第１の実施形態におけるクラスタリングの結果の例を示す図である。図３には、地図１００２、コンテンツアイコン１０１２、クラスタ領域１０２２、クラスタ中心１０２３、およびグリッド線１０３５が図示されている。
【００４１】
地図１００２は、地表面１００１の一部または全部の領域を表す画像である。地図１００２は、コンテンツ１０１１の位置と、コンテンツ１０１１のクラスタリングの結果であるクラスタ１０２１の領域をユーザに示すために表示される。地図１００２によって表される地表面１００１の領域は、地表面１００１においてコンテンツ１０１１が存在する範囲に応じて設定されてもよく、またユーザの操作に応じて設定されてもよい。
【００４２】
コンテンツアイコン１０１２は、地表面１００１におけるコンテンツ１０１１の位置に対応する地図１００２上の位置に表示される。コンテンツアイコン１０１２は、ピンの形のアイコンとして図示されているが、これには限られず、様々な形のアイコンでありうる。また、コンテンツアイコン１０１２は、コンテンツ１０１１に含まれる文字または画像などの情報の、一部または全部を表示していてもよい。
【００４３】
クラスタ領域１０２２は、地表面１００１におけるクラスタ１０２１の領域に対応する地図１００２上の位置に表示される。クラスタ領域１０２２は、クラスタ１０２１の領域と同様の形状で表示されてもよく、また、例えばコンテンツアイコン１０１２と表示が重複することを避け、コンテンツアイコン１０１２を見やすくするために、クラスタ１０２１の領域よりも若干拡張されていてもよい。
【００４４】
クラスタ中心１０２３は、クラスタ領域１０２２の中心、または地表面１００１におけるクラスタ１０２１の中心の位置に対応する地図１００２上の位置に表示される。クラスタ中心１０２３は、例えばクラスタ１０２１に含まれるコンテンツ１０１１から抽出された要約的な情報（コンテンツ１０１１が画像データであれば、代表画像またはサムネイル画像など）をユーザに示すために表示されてもよいが、必ずしも表示されなくてもよい。
【００４５】
グリッド線１０３５は、コンテンツ１０１１をクラスタ１０２１に分類するクラスタリングで用いられたグリッド１０３１を示す線である。グリッド線１０３５は、クラスタリングの結果の表示である地図１００２に表示されない。しかし、例えばユーザがクラスタリングの粒度の設定を変更する場合などに、参考情報としてグリッド線１０３５が表示されてもよい。
【００４６】
（距離ベースのクラスタリングとの比較〜グリッドベースの利点）
図４は、本発明の第１の実施形態におけるグリッドベースのクラスタリングと、一般的な距離ベースのクラスタリングとを比較して説明するための図である。図４には、コンテンツ１０１１ａ〜１０１１ｋを、距離ベースでクラスタリングした場合（ａ）と、本実施形態においてグリッドベースでクラスタリングした場合（ｂ）とが図示されている。
【００４７】
（ａ）に示されるように、コンテンツ１０１１ａ〜１０１１ｋを距離ベースでクラスタリングした場合、コンテンツ１０１１ａ〜１０１１ｅがクラスタ１０２１ａに分類され、コンテンツ１０１１ｆ〜１０１１ｊがクラスタ１０２１ｂに分類され、コンテンツ１０１１ｋがクラスタ１０２１ｃに分類される。図示されているように、クラスタ１０２１ａ〜１０２１ｃの領域を楕円形で図示すると、クラスタ１０２１ａの領域とクラスタ１０２１ｂの領域とはその一部で重複しており、クラスタ１０２１ｃの領域はクラスタ１０２１ｂの領域に包含されている。距離ベースのクラスタリングの場合、例えば距離の算出および比較の手順によっては、このように互いに入り組んだ領域のクラスタ構造が生成されうる。
【００４８】
一方、（ｂ）に示されるように、コンテンツ１０１１ａ〜１０１１ｋをグリッドベースでクラスタリングした場合、コンテンツ１０１１ａ，１０１１ｂがクラスタ１０２１ｄに分類され、コンテンツ１０１１ｃがクラスタ１０２１ｅに分類され、コンテンツ１０１１ｄ〜１０１１ｇがクラスタ１０２１ｆに分類され、コンテンツ１０１１ｈ〜１０１１ｋがクラスタ１０２１ｇに分類される。図示されているように、クラスタ１０２１ｄ〜１０２１ｇは、互いに入り組むことなく、明確に分離されている。上述のように、グリッドベースの位置クラスタリングの場合、コンテンツ１０１１が同じグリッド１０３１に含まれるか否かがクラスタリングの基本的な基準になるため、クラスタ１０２１の領域は原則としてグリッド１０３１の領域に含まれる。従って、互いに入り組んだ領域のクラスタ構造は形成されないであろう。
【００４９】
（距離ベースのクラスタリングとの比較〜グリッドベースの弱点）
図５は、本発明の第１の実施形態におけるクラスタリングと、一般的な距離ベースのクラスタリングとを比較して説明するための別の例を示す図である。図５には、コンテンツ１０１１ｍ〜１０１１ｑを、距離ベースでクラスタリングした場合（ａ）と、本実施形態においてグリッドベースでクラスタリングした場合（ｂ）とが図示されている。
【００５０】
（ａ）に示されるように、コンテンツ１０１１ｍ〜１０１１ｑを距離ベースでクラスタリングした場合、コンテンツ１０１１ｍ，１０１１ｎがクラスタ１０２１ｈに分類され、コンテンツ１０１１ｏ〜１０１１ｑがクラスタ１０２１ｉに分類される。距離ベースのクラスタリングの場合、基本的には、このように距離の近いコンテンツ１０１１同士が同じクラスタ１０２１に分類される。
【００５１】
一方、（ｂ）に示されるように、コンテンツ１０１１ｍ〜１０１１ｑをグリッドベースでクラスタリングした場合、コンテンツ１０１１ｍ，１０１１ｎがクラスタ１０２１ｊに分類され、コンテンツ１０１１ｏがクラスタ１０２１ｋに分類され、コンテンツ１０１１ｐ，１０１１ｑがクラスタ１０２１ｍに分類される。上述のように、グリッドベースの位置クラスタリングの場合、コンテンツ１０１１が同じグリッド１０３１に含まれるか否かがクラスタリングの基本的な基準になるため、異なるグリッド１０３１に含まれるコンテンツ１０１１は、コンテンツ１０１１同士の距離が近くても同じクラスタ１０２１に分類されない場合がある。
【００５２】
さらに、（ｂ）では、グリッド境界１０３６および上位グリッド境界１０３７が図示されている。グリッド境界１０３６は、グリッド１０３１の境界である。上位グリッド境界１０３７は、グリッド１０３１の境界であり、かつ、４つのグリッド１０３１を含む上位レベルのグリッドの境界である。図示されている例において、コンテンツ１０１１ｍ，１０１１ｎはグリッド１０３１ａに含まれ、コンテンツ１０１１ｏはグリッド１０３１ｅに含まれ、コンテンツ１０１１ｐ，１０１１ｑはグリッド１０３１ｃに含まれる。
【００５３】
ここで、グリッド１０３１の上位グリッドでのクラスタリングが実行された場合を考える。図示されているように、グリッド１０３１ａとグリッド１０３１ｅとは、同じ上位グリッドに含まれる。そのため、上位グリッドでのクラスタリングが実行された場合、コンテンツ１０１１ｍ，１０１１ｎ，１０１１ｏは、同じクラスタ１０２１ｎに分類される。一方、グリッド１０３１ｃは、グリッド１０３１ａ，１０３１ｅとは異なる上位グリッドに含まれる。そのため、上位グリッドでのクラスタリングが実行されても、コンテンツ１０１１ｐ，１０１１ｑのクラスタはクラスタ１０２１ｍで変化しない。
【００５４】
このように、グリッドベースの位置クラスタリングは、処理が非常に高速であるという大きな利点を有するが、グリッド１０３１の境界が間にある場合、距離が近いコンテンツ１０１１同士であっても同じクラスタ１０２１に分類されない場合がありうることに留意すべきである。このような場合には、後述するマージ処理によって、クラスタリングの結果を自然な形に近づけることが可能である。なお、後述するように、このマージ処理も、グリッドベースのクラスタリングの性質を活かした高速な処理によって実現されうる。
【００５５】
（１−２．情報処理装置の構成）
次に、図６〜図８を参照して、本発明の第１の実施形態に係る情報処理装置の構成について説明する。
【００５６】
図６は、本発明の第１の実施形態に係る情報処理装置の構成を示すブロック図である。図６では、情報処理装置１００と、情報処理装置１００に主に含まれるＮ進数値生成部１０１、クラスタリング部１０３、マージ部１０７、入力部１１３、表示制御部１１５、および表示部１１７が図示されている。
【００５７】
情報処理装置１００は、上述のコンテンツ１０１１をデータとして扱う。コンテンツ１０１１は、例えば、静止画コンテンツもしくは動画コンテンツなどの画像コンテンツ、またはユーザ同士が各種情報の共有を行うためにサーバ等に登録した各種の文字情報もしくは画像情報等などでありうる。また、コンテンツ１０１１は、メール、楽曲、スケジュール、電子マネー使用履歴、通話履歴、コンテンツ視聴履歴、観光情報や地域情報、ニュースや天気予報、着信音モード履歴等のコンテンツであってもよい。以下の説明では、静止画コンテンツまたは動画コンテンツなどの画像コンテンツを例として説明する。しかし、情報処理装置１００では、特徴空間における位置を表す位置情報が例えばメタデータとして添付されているデータであれば、任意の情報やコンテンツデータを扱うことが可能である。
【００５８】
また、上述のようなコンテンツデータや各種情報を表すデータは、情報処理装置１００の内部に格納されていることが好ましい。しかしながら、情報処理装置１００の外部に設けられたサーバ等の装置にデータ本体が格納されており、情報処理装置１００には、これらのデータ本体に対応するメタデータが格納されていてもよい。以下では、情報処理装置１００が、コンテンツデータや各種情報を表すデータをメタデータとともに格納している場合を例として説明する。
【００５９】
（Ｎ進数値生成部）
Ｎ進数値生成部１０１は、例えば、ＣＰＵ（Central  Processing  Unit）、ＲＯＭ（Read  Only  Memory）、ＲＡＭ（Random  Access  Memory）等によって実現される。Ｎ進数値生成部１０１は、緯度および経度の２次元の座標によって規定される地表面１００１の位置情報を有するコンテンツ１０１１について、所定の桁数の２進数で表現された緯度および経度の値を、緯度および経度について順に１桁ずつ配列した２進数値を生成する。
【００６０】
例えば、所定の桁数として２９桁を設定した場合、Ｎ進数値生成部１０１は、緯度および経度の値をそれぞれ２９桁の２進数値で表現する。ここで、２進数で表現された緯度を“ａ２８ａ２７ａ２６・・・ａ０”とし、２進数で表現された経度を“ｂ２８ｂ２７ｂ２６・・・ｂ０”とすると、これらの値を各次元について順に１桁ずつ配列した２進数値は、“ｂ２８ａ２８ｂ２７ａ２７ｂ２６ａ２６・・・ｂ０ａ０”という５８桁の２進数値になる。なお、所定の桁数が２９桁である場合、緯度の最小分解能は、地球の半径を２００００ｋｍとすると２００００ｋｍ／２２９＝０．０４ｍ相当になる。また、この場合、経度の最小分解能は、地球の直径を４００００ｋｍとすると４００００ｋｍ／２２９＝０．０７ｍ相当になる。所定の桁数は、例えば、必要な最小分解能、および情報処理装置１００で扱われるデータ単位のサイズ（例えば３２ビット、６４ビットなど）を考慮した適切な値に設定されうる。
【００６１】
このように、Ｎ進数値生成部１０１が位置および経度の値から１つの２進数値を生成することによって、２次元座標である位置情報を１つの数値として保持することが可能になる。また、２進数値において緯度の２進数値の値と経度の２進数値の値とが順に配列されていることによって、後述するようにクラスタリングの処置が容易になる。
【００６２】
（クラスタリング部）
クラスタリング部１０３は、ＣＰＵ、ＲＯＭ、ＲＡＭ等によって実現される。クラスタリング部１０３は、後述するクラスタリング用ソート部１０５を含む。クラスタリング部１０３は、Ｎ進数値生成部１０１が生成した２進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通するコンテンツ１０１１を同一のクラスタに分類する。ｋ＝２×ｍ（ｍ＝１，２，・・・）である場合、２進数値の上位ｋ桁が共通するコンテンツ１０１１が分類されるクラスタは、２２＝４分木構造クラスタのｍ層目になる。
【００６３】
クラスタリング用ソート部１０５は、クラスタリング部１０３に含まれ、ＣＰＵ、ＲＯＭ、ＲＡＭ等によって実現される。クラスタリングソート部１０５は、コンテンツ１０１１を、Ｎ進数値生成部１０１が生成した２進数値の順にソートする。後述するように、クラスタリング部１０３は、クラスタリング用ソート部１０５によるソートの結果から、同一のクラスタに分類されるコンテンツ１０１１を特定する。
【００６４】
ここで、図７を参照して、クラスタリング部１０３の機能について説明する。図７は、本発明の第１の実施形態におけるクラスタリングについて説明するための図である。図７では、地表面１００１上に定義されたグリッド１０３１、グリッド１０３１の上位レベルのグリッドである上位グリッド１０４１、および、クラスタリングの対象になるコンテンツ１０１１ｕ〜１０１１ｗが図示されている。
【００６５】
なお、図１を参照して説明したように、本実施形態において、コンテンツ１０１１が分類されるクラスタ１０２１は、コンテンツ１０１１が属するグリッド１０３１によって定義される。すなわち、クラスタリングの段階では、コンテンツ１０１１が属するグリッド１０３１が特定されれば、自動的にコンテンツ１０１１が分類されるグリッド１０３１が特定される。それゆえ、クラスタリング部１０３がコンテンツ１０１１をクラスタ１０２１に分類することは、コンテンツ１０１１が属するグリッド１０３１を決定することと実質的に同じである。従って、図７を用いた説明では、クラスタリング部１０３が、コンテンツ１０１１が属するグリッド１０３１を特定する処理について主に説明している。
【００６６】
図７では、簡単のために、コンテンツ１０１１の位置情報の緯度および経度がそれぞれ３桁の２進数値で表現される例を示している。この例において、Ｎ進数値生成部１０１は、コンテンツ１０１１の緯度および経度を、それぞれ０００〜１１１の範囲の３桁の２進数値で表現し、これらの２進数値を順に１桁ずつ配置して、００００００〜１１１１１１の範囲の６桁の２進数値を生成する。従って、経度が０００、緯度が１１１であるコンテンツ１０１１ｕには、“０１０１０１”という２進数値が対応付けられる。また、経度が００１、緯度が１１０であるコンテンツ１０１１ｖには、“０１０１１０”という２進数値が対応付けられる。さらに、経度が０００、緯度が１０１であるコンテンツ１０１１ｗには、“０１０００１”という２進数値が対応付けられる。
【００６７】
一方、図示されている例において、地表面１００１は、４つの上位グリッド１０４１に分割され、各上位グリッド１０４１は、さらに、４つのグリッド１０３１に分割される。つまり、図示されている例において、グリッドは、４分木構造を有する。地表面全体を、この４分木構造の０層目のグリッドとすると、上位グリッド１０４１は１層目のグリッドであり、グリッド１０３１は２層目のグリッドである。上述のように、本実施形態のクラスタリングでは、クラスタ１０２１とグリッド１０３１とは対応している。そのため、図示されている例において、クラスタもグリッドと同様の４分木構造を有する。具体的には、地表面１００１にあるコンテンツ１０１１の全体を含むクラスタが４分木構造のルートノード、すなわち０層目に相当し、各上位グリッド１０４１に含まれるコンテンツ１０１１を含むクラスタが１層目のクラスタ、各グリッド１０３１に含まれるコンテンツ１０１１を含むクラスタが２層目のクラスタになる。
【００６８】
ここで、「Ｎ進数値生成部１０１が生成した２進数値の上位ｋ桁が共通する複数のコンテンツ１０１１が同一のクラスタに分類される」ことについて説明する。
【００６９】
例えば、図の左上にある上位グリッド１０４１には、経度が０００〜０１１、緯度が１００〜１１１であるコンテンツ１０１１が属する。これらの範囲において、経度の１桁目は“０”であり、緯度の１桁目は“１”である。従って、コンテンツ１０１１に対応付けられた２進数値の上位２桁は、“０１”となり、この上位グリッド１０４１に属するコンテンツ１０１１の２進数値は、“０１ｘｘｘｘ”と表される。同様に、他の上位グリッドに属するコンテンツ１０１１の２進数値は、“１１ｘｘｘｘ”、“００ｘｘｘｘ”、および“１０ｘｘｘｘ”と表される。つまり、４分木構造グリッドの１層目のグリッドである上位グリッド１０４１について、コンテンツ１０１１がどの上位グリッド１０４１に属するかは、コンテンツ１０１１に対応付けられた２進数値の上位２桁によって決定される。従って、２進数値の上位２桁が共通する複数のコンテンツ１０１１は、同一の上位グリッド１０４１に属し、同一の上位グリッド１０４１に対応する同一のクラスタ、すなわち４分木構造クラスタの１層目において同一のクラスタに分類される。
【００７０】
また、例えば、図の左上端にあるグリッド１０３１には、経度が０００または００１、緯度が１１０または１１１であるコンテンツ１０１１が属する。これらの範囲において、経度の上位２桁は“００”であり、緯度の上位２桁は“１１”である。従って、コンテンツ１０１１に対応付けられた２進数値の上位４桁は“０１０１”となり、このグリッド１０３１に属するコンテンツ１０１１の２進数値は、“０１０１ｘｘ”と表される。同様に、他のグリッドに属するコンテンツ１０１１の２進数値も、上位４桁が特定された形で表される。つまり、４分木構造グリッドの２層目のグリッドであるグリッド１０３１について、コンテンツ１０１１がどのグリッド１０３１に属するかは、コンテンツ１０１１に対応付けられた２進数値の上位４桁によって決定される。従って、２進数値の上位４桁が共通する複数のコンテンツ１０１１は、同一のグリッド１０３１に属し、同一のグリッド１０３１に対応する同一のクラスタ、すなわち４分木構造クラスタの２層目の同一のクラスタに分類される。
【００７１】
さらに、図７を参照して、クラスタリングの具体例として、コンテンツ１０１１ｕ〜１０１１ｗのクラスタリングについて説明する。まず、コンテンツ１０１１ｕは、２進数値“０１０１０１”に対応付けられている。この２進数値の上位４桁は“０１０１”であるため、コンテンツ１０１１ｕは、“０１０１ｘｘ”で表される２進数値に対応する図の左上端にあるグリッド１０３１に属すると判定される。
【００７２】
次に、コンテンツ１０１１ｖは、２進数値“０１０００１”に対応付けられている。この２進数値の上位４桁は“０１００”であるため、コンテンツ１０１１ｖは、“０１００ｘｘ”で表される２進数値に対応するグリッド１０３１、すなわち、コンテンツ１０１１ｕとは異なるグリッド１０３１に属すると判定される。
【００７３】
次に、コンテンツ１０１１ｗは、２進数値“０１０１１０”に対応付けられている。この２進数値の上位４桁は“０１０１”であるため、コンテンツ１０１１ｖは、“０１０１ｘｘ”で表される２進数値に対応する図の左上端にあるグリッド１０３１、つまりコンテンツ１０１１ｕと同じグリッドに属すると判定される。
【００７４】
ここで、クラスタリング用ソート部１０５が、コンテンツ１０１１ｕ〜１０１１ｗを、２進数値の順にソートした場合を考える。コンテンツ１０１１ｕ〜１０１１ｗを、２進数値の順にソートすると、
コンテンツ１０１１ｖ“０１０００１”
コンテンツ１０１１ｕ“０１０１０１”
コンテンツ１０１１ｗ“０１０１１０”
となる。同一のグリッドに属するコンテンツ、すなわち、同一のクラスタに分類されるコンテンツであるコンテンツ１０１１ｕとコンテンツ１０１１ｗとは、このソート結果において互いに隣接する。従って、クラスタリング部１０３は、クラスタリング用ソート部１０５によるソートの結果から、同一のクラスタ１０２１に分類されるコンテンツ１０１１を特定しうる。
【００７５】
なお、クラスタリング部１０３およびクラスタリング用ソート部１０５の処理の詳細については後述する。
【００７６】
（マージ部）
マージ部１０７は、ＣＰＵ、ＲＯＭ、ＲＡＭ等によって実現される。マージ部１０７は、後述するマージ用ソート部１０９および隣接判定部１１１を含む。マージ部１０７は、隣接判定部１１１によって、地表面のある方向について互いに隣接すると判定されたクラスタ１０２１を処理対象にする。マージ部１０７が実行するマージ処理には、後述すように探索順マージと距離順マージがある。また、マージ部１０７は、マージ処理の対象とするクラスタ１０２１を決定するために、マージ用ソート部１０９および隣接判定部１１１の処理結果を利用する場合がある。さらに、マージ部１０７は、マージ処理の条件を設定するために、記憶部１１９に格納された所定のマージ設定情報を参照してもよい。
【００７７】
マージ用ソート部１０９は、マージ部１０７に含まれ、ＣＰＵ、ＲＯＭ、ＲＡＭ等によって実現される。マージ用ソート部１０９は、緯度および経度に基づく順位決定処理の結果に基づいて、地表面のある方向についてクラスタ１０２１をソートする。マージ用ソート部１０９は、ソートの結果を隣接判定部１１１に提供する。ここで、本実施形態において、順位決定処理は、グリッド１０３１を地表面における方向、例えば東西方向、南北方向、北西−南東方向または南西−北東方向など、についてソートし、各グリッド１０３１に含まれるクラスタ１０２１に、グリッド１０３１のソート順を順位として与える処理でありうる。
【００７８】
隣接判定部１１１は、マージ部１０７に含まれ、ＣＰＵ、ＲＯＭ、ＲＡＭ等によって実現される。隣接判定部１１１は、マージ用ソート部１０９によって地表面のある方向にソートされたクラスタが、当該方向で互いに隣接するか否かを判定する。隣接判定部１１１は、判定の結果をマージ部１０７に提供する。ここで、本実施形態において、隣接判定処理は、クラスタ１０２１を含むグリッド１０３１が隣接しているか否かを判定する処理でありうる。
【００７９】
ここで、図８を参照して、マージ部１０７の機能について説明する。図８は、本発明の第１の実施形態におけるクラスタのマージについて説明するための図である。図８では、経度方向について互いに隣接するグリッド１０３１ｘ，１０３１ｙと、それぞれのグリッドに含まれるクラスタ１０２１ｘ，１０２１ｙが図示されている。
【００８０】
図示された例において、マージ部１０７は、クラスタ１０２１ｘとクラスタ１０２１ｙのように、対応するグリッド１０３１が隣接しているクラスタ１０２１を、互いに隣接するクラスタ１０２１として、このようなクラスタ１０２１の間で、クラスタ間の距離ｄを算出してもよい。クラスタ間の距離ｄは、例えば、それぞれのクラスタ１０２１の中心間の距離であってもよい。マージ部１０７は、クラスタ間の距離ｄが所定の閾値以下である場合に、クラスタ１０２１ｘとクラスタ１０２１ｙとをマージしてクラスタ１０２１ｚとする。
【００８１】
このように、マージ部１０７は、クラスタ１０２１が緯度または経度の方向で互いに隣接する場合に、これらのクラスタ１０２１についてクラスタ間の距離を算出してもよい。また、マージ部１０７は、クラスタ１０２１が互いに隣接するか否かとは関係なく、クラスタ間の距離を算出してもよい。さらに、マージ部１０７は、クラスタ間の距離が所定の閾値以下である場合に、これらのクラスタ１０２１をすぐにはマージせず、マージ候補クラスタとして記憶部１１９に記憶してもよい。この場合、マージ部１０７は、その後、マージ候補クラスタのうちクラスタ間の距離が小さいマージ候補クラスタから順にクラスタ１０２１をマージする。
【００８２】
なお、マージ部１０７、マージ用ソート部１０９、および隣接判定部１１１の処理の詳細については後述する。
【００８３】
（入力部）
図６に戻って、入力部１１３は、本実施形態に係る情報処理装置１００が備える入力装置の一例である。この入力部１１３は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ、入力装置等により実現される。入力部１１３は、情報処理装置１００が備えるキーボード、マウス、タッチパネル等になされたユーザ操作を、なされたユーザ操作に対応する電気的な信号に変換して、Ｎ進数値生成部１０１および表示制御部１１５に通知する。例えば、ユーザによって、クラスタリングの実行を指示する操作や、クラスタリングの粒度の変更を指示するする操作がなされた場合、入力部１１３は、かかる指示を表す情報を生成して、Ｎ進数値生成部１０１などに出力する。
【００８４】
（表示制御部）
表示制御部１１５は、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ等により実現される。表示制御部１１５は、例えば、入力部１１３から、クラスタリング結果の表示を指示するユーザ操作がなされた旨の通知を受けると、クラスタリング部１０３およびマージ部１０７によって記憶部１１９などに格納されている、コンテンツ１０１１のクラスタリング結果を取得する。その後、表示制御部１１５は、例えば、図３を参照して説明したようなクラスタリング結果の画像を構成し、この画像を後述する表示部１１７に表示させる表示制御を行ってもよい。
【００８５】
（表示部）
表示部１１７は、本実施形態に係る情報処理装置１００が備える表示装置の一例である。表示部１１７は、情報処理装置１００が実行可能な各種のコンテンツや、各種のアプリケーションの実行画面等を表示する表示部である。また、表示部１１７には、各種コンテンツの動作や、各種アプリケーションの実行状況等を操作するために利用される各種のオブジェクトが表示されてもよい。表示部１１７が備える表示画面には、表示制御部１１５による制御によって、例えば図３を用いて説明したようなクラスタリング結果の画像など、様々な情報が表示される。
【００８６】
（記憶部）
記憶部１１９は、本実施形態に係る情報処理装置１００が備えるストレージ装置の一例である。この記憶部１１９には、情報処理装置１００が有する各種のコンテンツデータ、および、コンテンツデータに対応付けられたメタデータ等が格納されてもよい。また、記憶部１１９には、Ｎ進数値生成部１０１が生成した２進数値、クラスタリング部１０３がコンテンツ１０１１をクラスタ１０２１に分類した結果、およびマージ部１０７がクラスタ１０２１をマージした結果が格納されてもよい。また、記憶部１１９には、表示制御部１１５が、各種の情報を表示部１１７に表示するために利用する各種のアプリケーションに対応する実行データが格納されてもよい。また、この記憶部１１９には、情報処理装置１００が何らかの処理を行う際に保存する必要が生じた様々なパラメータや処理の途中経過など、または、各種のデータベースなどが適宜格納される。この記憶部１１９には、本実施形態に係る情報処理装置１００が備える各処理部が、自由に読み書きを行うことが可能である。
【００８７】
（情報処理装置についての補足）
なお、本実施形態に係る情報処理装置１００は、コンテンツ１０１１に対応付けられる位置情報を、コンテンツ１０１１自身や付加的なデータファイルから取得する機能を有する装置であればよい。情報処理装置１００の例としては、デジタルスチルカメラ、デジタルビデオカメラ等の撮像装置、記憶装置内蔵マルチメディアコンテンツビューワー、コンテンツを記録保存閲覧することが可能な携帯情報端末、ネットワーク上の地図サービスと連携したコンテンツ管理閲覧サービス、パーソナルコンピュータのアプリケーションソフト、写真データ管理機能を有する携帯ゲーム端末、記憶装置を有するカメラ付き携帯電話機、記憶装置、写真データ管理機能を有するデジタル家電やゲーム機などがある。
【００８８】
以上、本実施形態に係る情報処理装置１００の機能の一例を示した。上記の各構成要素は、汎用的な部材や回路を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。また、各構成要素の機能を、ＣＰＵ等が全て行ってもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用する構成を変更することが可能である。
【００８９】
なお、上述のような本実施形態に係る情報処理装置の各機能を実現するためのコンピュータプログラムを作製し、パーソナルコンピュータ等に実装することが可能である。また、このようなコンピュータプログラムが格納された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信されてもよい。
【００９０】
（１−３．クラスタリングおよびマージ処理の詳細）
次に、図９〜図２９を参照して、本発明の第１の実施形態におけるクラスタリング処理およびマージ処理の詳細について説明する。
【００９１】
図９は、本発明の第１の実施形態におけるクラスタリングおよびマージの処理を示すフローチャートである。図６を参照して説明したように、本実施形態に係る情報処理装置１００では、クラスタリング部１０３によるクラスタリングの結果として特定されたクラスタ１０２１について、マージ部１０７がマージ処理を実行する。従って、処理の流れとしては、まずクラスタリング処理が実行され（ステップＳ１０１）、続いてマージ関連処理が実行される（ステップＳ１０３）。なお、マージ関連処理とは、マージ処理にパラメータ設定などの関連処理を加えた処理の総称である。クラスタリング処理、およびマージ関連処理の詳細については、後述する。
【００９２】
【表１】
2012113625.tif 000003
【００９３】
表１は、クラスタリング処理において設定されるグリッドレベルと、マージ処理において設定されるマージ閾値との組み合わせの例を示す表である。例えば、グリッドレベルが１０、マージ閾値が５０ｋｍの組が選択された場合、クラスタリング処理では、レベル１０グリッドが用いられる。ここで、図２を参照して説明したグリッドの階層構造では、１レベルごとに上位のグリッドが４分割される。従って、レベル１０グリッドは、レベル０グリッドの範囲である地表面の全体を４１０分割したグリッドである。また、マージ閾値は、図８を参照して説明したクラスタ間の距離ｄの閾値である。上記の場合、互いに隣接するグリッド１０３１に含まれる複数のクラスタ１０２１について、クラスタ間の距離ｄが５０ｋｍ以下であれば、これらのクラスタ１０２１はマージされる。
【００９４】
上記のようなグリッドレベルとマージ閾値とは、それぞれ任意の値に設定されうる。表１において示されたグリッドレベルとマージ閾値との組み合わせは、北緯４０度付近で、マージ閾値を半径とする円内にグリッドが包含されるようなグリッドレベルとマージ閾値との組み合わせの例である。マージ閾値に対して相対的にグリッドレベルを大きく（グリッドサイズを小さく）すると、グリッドの隣接判定の時点で隣接ではないと判定され、グリッドに含まれるクラスタ間の距離がマージ閾値以下であっても、クラスタがマージされない場合がある。ただし、後述する４方向探索、または上位レベル探索などを利用し、グリッドの隣接判定の範囲を広げられる場合には、グリッドサイズを小さくするほど、演算量は増えるものの、クラスタリングの結果が自然な形に近づく。
【００９５】
（クラスタリング処理の詳細）
図１０を参照して、クラスタリング部１０３によるクラスタリング処理について、さらに詳細に説明する。図１０は、本発明の第１の実施形態におけるクラスタリングについて説明するための図である。図１０では、クラスタリング用ソート部１０５が、Ｎ進数値生成部１０１によって生成され、コンテンツ１０１１に対応付けられた２進数値の順に、コンテンツ１０１１をソートした状態が示されている。クラスタリング用ソート部１０５によるソートの結果では、コンテンツ１０１１が、１層目のクラスタ１０２４、および２層目のクラスタ１０２５において分類されるクラスタの順に並んでいる。なお、図１０でも、簡単のために、コンテンツ１０１１の位置情報の緯度および経度がそれぞれ３桁の２進数値で表現される例を示している。
【００９６】
上述のように、本実施形態のクラスタリングでは、Ｎ進数値生成部１０１が生成した２進数値の上位ｋ桁が共通する複数のコンテンツ１０１１が同一のクラスタに分類される。また、ｋ＝２×ｍ（ｍ＝１，２，・・・）である場合、２進数値の上位ｋ桁が共通するコンテンツ１０１１が分類されるクラスタは、２２＝４分木構造クラスタのｍ層目になる。例えば、２進数値の上位２桁が共通する複数のコンテンツ１０１１は、４分木構造の１層目において同一のクラスタに分類される。つまり、４分木構造の１層目のクラスタは、“００ｘｘｘｘ”、“０１ｘｘｘｘ”、“１０ｘｘｘｘ”、または“１１ｘｘｘｘ”でそれぞれ表される２進数値に対応する４つのクラスタである。また、４分木構造の２層目のクラスタは、“００００ｘｘ”、“０００１ｘｘ”、“００１０ｘｘ”、・・・“１１１１ｘｘ”でそれぞれ表される２進数値に対応する１６のクラスタである。
【００９７】
なお、図１０の例では、１層目のクラスタ１０２４の例として、“００ｘｘｘｘ”に対応する１層目のクラスタ１０２４ａ、および“０１ｘｘｘｘ”に対応する１層目のクラスタ１０２４ｂが図示されている。また、２層目のクラスタ１０２５の例として、“００００ｘｘ”に対応する２層目のクラスタ１０２５ａ、“０００１ｘｘ”に対応する２層目のクラスタ１０２５ｂ、“００１０ｘｘ”に対応する２層目のクラスタ１０２５ｃ、および“００１１ｘｘ”に対応する２層目のクラスタ１０２５ｄが図示されている。
【００９８】
例えば、２層目のクラスタについていえば、ソートされた２進数値の先頭にある“００００１０”が対応付けられたコンテンツ１０１１は、２層目のクラスタ１０２５ａに分類される。また、次の“０００１００”から“０００１１１”までの４つの２進数値がそれぞれ対応付けられたコンテンツ１０１１は、２層目のクラスタ１０２５ｂに分類される。さらに、次の“００１００１”が対応付けられたコンテンツ１０１１は２層目のクラスタ１０２５ｃに分類され、その次の“００１１１０”が対応付けられたコンテンツ１０１１は２層目のクラスタ１０２５ｄに分類される。
【００９９】
また、１層目のクラスタについていえば、ソートされた２進数値の先頭にある“００００１０”から“００１１１０”までの７つの２進数値がそれぞれ対応付けられたコンテンツ１０１１は、１層目のクラスタ１０２４ａに分類される。また、次の“０１００１１”から“０１１１０１”までの４つの２進数値にそれぞれ対応付けられたコンテンツ１０１１は、１層目のクラスタ１０２４ｂに分類される。
【０１００】
このように、本実施形態におけるクラスタリングでは、Ｎ進数値生成部１０１によって生成された２進数値の順にコンテンツ１０１１をソートすると、コンテンツ１０１１は、分類されるクラスタ単位に並ぶ。つまり、本実施形態におけるクラスタリング処理は、コンテンツ１０１１を、Ｎ進数値生成部１０１によって生成された２進数値の順にソートすることによって実現される。
【０１０１】
ここで、一般的な距離ベースの位置クラスタリングでは、距離の近いコンテンツのペアを探索するため、処理回数がコンテンツの組み合わせの数になり、コンテンツの数をＮとすると処理回数はＯ（Ｎ２）になる。一方、本実施形態におけるクラスタリングでは、クラスタリング処理が実質的にはソート処理であるため、コンテンツの数をＮとすると処理回数はＯ（ＮｌｏｇＮ）になり、より少ない処理回数で済む。しかも、一般的な距離ベースの位置クラスタリングでの１回の処理が２次元座標間の距離計算であるのに対し、本実施形態におけるクラスタリングの１回の処理は数値の大小比較であり、１回の処理あたりの負荷がより低くなる。
【０１０２】
図１１は、本発明の第１の実施形態におけるクラスタ特定情報について説明するための図である。図１１には、コンテンツ１０１１を特定するコンテンツ特定情報、およびクラスタ１０２１を特定するクラスタ特定情報の配列が図示されている。
【０１０３】
本実施形態において、クラスタリング部１０３は、クラスタリング用ソート部１０５によるソートの結果において、あるクラスタ１０２１に分類されたコンテンツ１０１１が現れる最初の位置と、このクラスタ１０２１に分類されたコンテンツ１０１１の数とによって、このクラスタ１０２１を特定するクラスタ特定情報を生成する。
【０１０４】
図示された例において、コンテンツ１０１１は、Itemというデータ構造によって定義される。Itemは、例えば下記のようなデータ構造でありうる。
【０１０５】
struct  Item  {
uint32  id;
uint64  geocode;
};
【０１０６】
ここで、idは、それぞれのコンテンツ１０１１を識別するために与えられる固有のＩＤである。geocodeは、それぞれのコンテンツ１０１１について、Ｎ進数値生成部１０１が生成した２進数値である。図示されているItemの配列において、それぞれのItemはgeocodeに従ってソートされている。
【０１０７】
また、図示された例において、クラスタ１０２１は、Clusterというデータ構造によって定義される。Clusterは、例えば下記のようなデータ構造である。
【０１０８】
struct  Cluster  {
uint64_t  clusterid;
uint32_t  latcode;
uint32_t  lngcode;
float  latitude;
float  longitude;
float  halfEW;
float  halfNS;
uint32  numLeaves;
Item  *pLeaves;
};
【０１０９】
ここで、clusteridは、それぞれのクラスタ１０２１を識別するために与えられる固有のＩＤである。latcodeおよびlngcodeは、クラスタ１０２１に対応するグリッド１０３１の緯度および経度のコードである。例えば、クラスタ１０２１に対応するグリッド１０３１が、２進数値“１００１１１”に対応するものであれば、latcodeは“０１１”、lngcodeは“１０１”になる。latitude、longitude、halfEW、およびhalfNSは、クラスタ１０２１の領域を定義するための情報である。
【０１１０】
また、numLeavesは、クラスタ１０２１に分類されるコンテンツ１０１１の数である。*pLeavesは、クラスタリング用ソート部１０５がItemをgeocodeでソートした配列における、クラスタ１０２１に分類される最初のコンテンツ１０１１の位置を示すポインタである。これらの２つの要素は、クラスタ１０２１に分類されるコンテンツ１０１１を特定するための情報である。図８を参照して説明した例と同様に、geocodeでソートされたItem配列は、Itemによって定義されるコンテンツ１０１１が分類されるクラスタの順に並ぶ。従って、「配列のどこ（*pLeaves）からいくつ（numLeaves）分」という情報によって、クラスタ１０２１に分類されるコンテンツ１０１１を特定することが可能である。
【０１１１】
ここで、一般的なクラスタリングでは、クラスタにコンテンツが分類されている場合、クラスタを定義する情報として、分類されているコンテンツをそれぞれ特定する情報、例えばコンテンツＩＤ配列などを保持する。この場合、クラスタに分類されるコンテンツの数が増えるとコンテンツＩＤ配列も大きくなるため、クラスタを定義する情報も大きくなる。一方、本実施形態におけるクラスタリングでは、上述のように「配列のどこからいくつ分」という情報によってクラスタ１０２１に分類されるコンテンツ１０１１が特定されるため、クラスタ１０２１に分類されるコンテンツ１０１１の数が増えても、クラスタ１０２１を定義する情報のサイズが抑えられる。
【０１１２】
（マージ関連処理の詳細）
図１２は、本発明の第１の実施形態におけるマージ関連処理を示すフローチャートである。マージ関連処理では、マージ設定情報（config）が設定されているか否かによって、マージ処理をするか否かが判定され、マージ処理をする場合、マージ設定情報（config）の内容に応じて、探索順マージまたは距離順マージが実行される。なお、マージ設定情報（config）は、探索順マージおよび距離順マージにおけるパラメータの設定にも用いられる。
【０１１３】
まず、マージ部１０７は、マージ設定選択処理を実行する（ステップＳ２０１）。このマージ設定選択処理において、マージ設定情報（config）が選択される。なお、マージ設定選択処理の詳細については後述する。
【０１１４】
続いて、マージ部１０７は、マージ設定情報（config）にデータが設定されているか否かを判定する（ステップＳ２０３）。
【０１１５】
ステップＳ２０３において、マージ設定情報（config）が設定されている場合、マージ部１０７は、マージ設定情報（config）の距離順マージフラグ（sortPair）が“true”であるか、つまり距離順マージが有効であるか否かを判定する（ステップＳ２０５）。
【０１１６】
ステップＳ２０５において、マージ設定情報（config）の距離順マージフラグ（sortPair）が“false”である場合、つまり距離順マージが有効ではない場合、マージ部１０７は、探索順マージ処理を実行する（ステップＳ２０７）。探索順マージ処理の詳細については後述する。
【０１１７】
一方、ステップS２０５において、マージ設定情報（config）の距離順マージフラグ（sortPair）が“true”である場合、つまり距離順マージが有効である場合、マージ部１０７は、距離順マージ処理を実行する（ステップＳ２０９）。距離順マージ処理の詳細については後述する。
【０１１８】
一方、ステップＳ２０３において、マージ設定情報（config）がnull、つまりデータが設定されていない状態である場合、マージ部１０７は、探索順マージ処理も距離順マージ処理も実行せずに処理を終了する。
【０１１９】
（マージ設定選択処理の詳細）
図１３は、本発明の第１の実施形態におけるマージ設定情報の例を示す図である。図１３では、マージ設定情報の要素として、適用最大グリッド数（maxGrid）、探索手法（searchType）、上位レベル探索（upperLevel）、距離順マージ（sortPair）、および距離計算が図示されている。
【０１２０】
これらのマージ設定情報は、例えば図示されているようなテーブルの形で情報処理装置１００の記憶部１１９に格納されていてもよい。それぞれのマージ設定情報は、マージ設定レコード１０５１の形で格納され、マージ設定レコード１０５１は、インデックス（index）によって識別されてもよい。以下、マージ設定情報の各要素について説明する。
【０１２１】
適用最大グリッド数（maxGrid）は、マージ設定情報が設定されうる最大のグリッド数である。マージ処理に用いられるマージ設定情報（config）は、グリッド数がこの適用最大グリッド数以下になるマージ設定情報から選択される。なお、ここでいうグリッド数は、クラスタリング処理の結果、クラスタ１０２１が含まれるグリッド１０３１の数でありうる。従って、グリッドレベルが大きい（グリッドサイズが小さい）場合でも、コンテンツ１０１１の数が少ない、または特定のグリッドに偏って分布しているような場合には、比較的小さい適用最大グリッド数のマージ設定情報が選択されうる。
【０１２２】
探索手法（searchType）は、マージ処理における探索手法を指定する。“Full  Match”は、クラスタ１０２１が含まれるグリッド１０３１のすべての組み合わせをマージ処理の対象とする探索手法である。この探索手法によるマージ処理を、以下、フルマッチマージ処理という。また、“4  Dir”、“2  Dir”、および“1  Dir”は、それぞれ４方向探索、２方向探索、および１方向探索を表し、特定の方向について隣接するグリッドをマージ処理の対象とする探索手法である。これらの探索手法を、以下、近傍探索マージ処理という。なお、フルマッチマージ処理および近傍探索マージ処理の詳細については後述する。
【０１２３】
上位レベル探索（upperLevel）は、上位レベル探索を実行するか否か、および上位レベル探索が実行される場合は、いくつ上のレベルまで探索を実行するかを指定する。“２”および“１”は、上位レベル探索を実行することを示し、それぞれ２レベル上位、１レベル上位までの上位レベル探索を示す。“０”（disable）は、上位レベル探索を実行しないことを示す。フルマッチマージ処理では、クラスタ１０２１が含まれるグリッド１０３１のすべての組み合わせがマージ処理の対象となるため、上位レベル探索は必要なく、従って上位レベル探索（upperLevel）は定義されない。なお、上位レベル探索の詳細については後述する。
【０１２４】
距離順マージフラグ（sortPair）は、距離順マージを実行するか否かを指定する。距離順マージとは、クラスタ１０２１が含まれるグリッド１０３１のペアのうち、クラスタ１０２１の距離が近いペアから順にマージするマージ手法である。距離順マージを実行した場合、互いに近接しているクラスタ１０２１を確実にマージすることが可能になるが、グリッドのペアを一時的に保持しておくため、その分の記憶容量が占有される。“true”は、距離順マージを実行することを示し、“false”は、距離順マージではなく、後述する探索順マージを実行することを示す。なお、距離順マージの詳細については後述する。
【０１２５】
距離計算は、クラスタ間の距離を算出する際に用いられる距離計算手法を指定する。“大圏距離”が用いられる場合、例えば２つのクラスタ１０２１の中心の座標（経度，緯度）を、それぞれ（lon1，lat1）、および（lon2，lat2）とすると、クラスタ間の距離ｄは以下の数式（１）によって算出される。
【０１２６】
【数１】
2012113625.tif 000004
【０１２７】
また、“近似大圏距離”が用いられる場合、同様の場合においてクラスタ間の距離ｄは以下の数式（２）によって算出される。
【０１２８】
【数２】
2012113625.tif 000005
【０１２９】
このようなマージ設定情報は、例えば予め設定されて記憶部１１９に格納されていてもよい。図示されたマージ設定情報は、適用最大グリッド数（maxGrid）が小さいほど高度なマージであり、適用最大グリッド数（maxGrid）が大きいほど簡素なマージであるように設定されている。グリッド数が５００００を超える場合に対応するマージ設定情報は定義されておらず、この場合、マージ処理は実行されない。これは、グリッド数が多くなるほどマージ処理の負荷が増大するため、グリッド数に応じてマージの設定を変更して演算の最大負荷を調整するためである。
【０１３０】
図１４は、本発明の第１の実施形態におけるマージ設定選択処理を示すフローチャートである。マージ設定選択処理では、図１３を参照して説明したマージ設定情報から、マージ処理に用いられるマージ設定情報（config）が選択される。なお、上述のように、マージ設定情報（config）が設定されず、マージ処理を実行しないことが指定される場合もある。
【０１３１】
まず、マージ部１０７は、クラスタ１０２１が含まれるグリッド１０３１のリストであるグリッドリスト（glist）の長さ、すなわちグリッド数が、マージ設定リストmlistの末尾の要素tailでの適用最大グリッド数（maxGrid）以下であるか否かを判定する（ステップＳ３０１）。
【０１３２】
ステップＳ３０１において、グリッド数がマージ設定リストmlistの末尾の要素tailでの適用最大グリッド数（maxGrid）以下であると判定された場合、マージ部１０７は、マージ設定リストmlistの各要素について順に、以下のステップＳ３０５およびステップＳ３０７を繰り返す（ステップＳ３０３：マージ設定リストループ）。
【０１３３】
ステップＳ３０５は、グリッドリスト（glist）の長さlengthを、マージ設定リストmlistのインデックスｉの要素の適用最大グリッド数（maxGrid）と比較するステップである。
【０１３４】
ステップＳ３０５において、グリッドリスト（glist）の長さlengthが適用最大グリッド数（maxGrid）以下であると判定された場合、マージ部１０７は、マージ設定情報（config）にマージ設定リストmlistのインデックスｉの要素を設定する（ステップＳ３０７）。既に設定されているマージ設定情報（config）が存在する場合は、新たに設定されるマージ設定リストmlistのインデックスｉの要素で上書きされる。
【０１３５】
一方、ステップＳ３０５において、グリッドリスト（glist）の長さlengthが適用最大グリッド数（maxGrid）を超えると判定された場合、マージ設定情報（config）の設定には変化がなく、マージ設定リストループが続行される。
【０１３６】
ステップＳ３０３のマージ設定リストループが終了すると、マージ部１０７はマージ設定選択処理を終了する。
【０１３７】
一方、ステップＳ３０１において、グリッド数がマージ設定リストmlistの末尾の要素tailでの適用最大グリッド数（maxGrid）を超えると判定された場合、マージ部１０７は、マージ設定情報（config）にnullを設定する（ステップＳ３０９）。nullは、データが設定されない状態を示す。上述のように、マージ設定情報（config）がnullである場合、マージ部１０７は後続のマージ処理を実行しない。
【０１３８】
（探索順マージ処理の詳細）
探索順マージ処理は、相互間の距離が所定の閾値以下であるクラスタ１０２１を探索し、そのようなクラスタ１０２１を探索された順に順次マージする処理を含む。なお、後述するフルマッチマージ処理では、クラスタ１０２１が含まれるグリッド１０３１のすべての組み合わせについて、クラスタ１０２１の相互間の距離が算出される。また、同じく後述する近傍探索マージ処理では、クラスタ１０２１が含まれるグリッド１０３１が特定の方向にソートされ、当該方向について隣接するグリッド１０３１に含まれるクラスタ１０２１について、相互間の距離が算出される。
【０１３９】
図１５は、本発明の第１の実施形態における探索順マージ処理を示すフローチャートである。探索順マージでは、マージ設定情報（config）の内容に応じて、フルマッチマージ処理、近傍探索マージ処理のいずれかが実行される。また、近傍探索マージ処理が実行される場合、マージ設定情報（config）の内容に応じて、上位探索あり、または上位探索なしのいずれかで実行される。
【０１４０】
まず、マージ部１０７は、マージ設定情報（config）の探索手法（searchType）が、“Full  Match”であるか否かを判定する（ステップＳ４０１）。
【０１４１】
ステップＳ４０１において、マージ設定情報（config）の探索手法（searchType）が、“Full  Match”である場合、マージ部１０７は、フルマッチマージ処理を実行する（ステップＳ４０３）。フルマッチマージ処理のさらなる詳細については後述する。
【０１４２】
一方、ステップＳ４０１において、マージ設定情報（config）の探索手法（searchType）が、“Full  Match”ではない場合、マージ部１０７は、さらに、マージ設定情報（config）の上位レベル探索（upperLevel）が、“０”であるか否かを判定する（ステップＳ４０５）。
【０１４３】
ステップＳ４０５において、マージ設定情報（config）の上位レベル探索（upperLevel）が“０”である場合、マージ部１０７は、上位探索なしの近傍探索マージ処理を実行する（ステップＳ４０７）。この上位探索なし近傍探索マージ処理の詳細については、後述する。
【０１４４】
一方、ステップＳ４０５において、マージ設定情報（config）の上位レベル探索（upperLevel）が“０”ではない場合、マージ部１０７は、上位探索ありの近傍探索マージ処理を実行する（ステップS４０９）。この上位探索あり近傍探索マージ処理の詳細については、後述する。
【０１４５】
以上のように、マージ部１０７は、フルマッチマージ処理、上位探索なし近傍探索マージ処理、または上位探索あり近傍探索マージ処理のいずれかのマージ処理を実行して、探索順マージ処理を終了する。
【０１４６】
（フルマッチマージ処理の詳細）
図１６は、本発明の第１の実施形態におけるフルマッチマージ処理を示すフローチャートである。フルマッチマージ処理では、クラスタ１０２１が含まれるグリッド１０３１のすべての組み合わせを探索の対象とする。
【０１４７】
まず、ステップＳ５０１において、マージ部１０７は、クラスタ１０２１が含まれるグリッド１０３１のリストであるグリッドリスト（glist）の各要素について順に、以下のステップＳ５０３を繰り返す（マージするグリッドループ）。なお、このステップＳ５０１のループにおいて処理対象となっているグリッドリスト（glist）の要素を、グリッドリスト（glist）のインデックスｉの要素とする。
【０１４８】
ステップＳ５０３において、マージ部は、グリッドリスト（glist）の、現在処理対象としているインデックスｉの要素の次の要素である要素から順に、以下のステップＳ５０５〜Ｓ５０９を繰り返す（マージされるグリッドループ）。なお、このステップＳ５０３のループにおいて処理対象となっているグリッドリスト（glist）の要素を、グリッドリスト（glist）のインデックスｊの要素とする。
【０１４９】
続くステップＳ５０５において、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素（マージするグリッド）とインデックスｊの要素（マージされるグリッド）との間の距離ｄの算出処理（distance）を実行する。ここで、インデックスｉの要素とインデックスｊの要素との距離は、例えば、インデックスｉの要素であるグリッド１０３１に含まれるクラスタ１０２１と、インデックスｊの要素であるグリッド１０３１に含まれるクラスタ１０２１との中心距離であってもよい。
【０１５０】
続くステップＳ５０７は、ステップＳ５０５において算出された距離ｄを、所定の閾値ｔｈと比較するステップである。ここで、閾値ｔｈは、例えば、表１を参照して説明されたマージ閾値でありうる。
【０１５１】
ここで、ステップＳ５０７において、距離ｄが閾値ｔｈ以下であると判定された場合、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素とインデックスｊの要素とをマージする（merge：ステップＳ５０９）。ここで、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素であるグリッド１０３１に対応するクラスタ１０２１と、インデックスｊの要素であるグリッド１０３１に対応するクラスタ１０２１とをマージした新たなクラスタ１０２１を生成し、この新たなクラスタ１０２１を、マージされる前の各クラスタ１０２１が対応付けられていたグリッド１０３１に対応付ける。つまり、このマージの後、インデックスｉの要素であるグリッド１０３１に対応するクラスタ１０２１と、インデックスｊの要素であるグリッド１０３１に対応するクラスタ１０２１とは、いずれもこの新たなクラスタ１０２１になる。
【０１５２】
一方、ステップＳ５０７において、距離ｄが閾値ｔｈを超えると判定された場合、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素とインデックスｊの要素とをマージせず、インデックスｊをインクリメントして、グリッドリスト（glist）の次の要素を参照する（ステップＳ５０３）。
【０１５３】
ステップＳ５０３のループによってグリッドリスト（glist）の要素が末尾まで参照された場合、マージ部１０７は、インデックスｉをインクリメントしてグリッドリスト（glist）の次の要素を参照する（ステップＳ５０１）。
【０１５４】
ステップＳ５０１のループによってグリッドリスト（glist）の要素が末尾まで参照された場合、マージ部１０７は、フルマッチマージの処理を終了する。
【０１５５】
上記のステップＳ５０９における処理は、例えばマージ部１０７がソフトウェアとして実装される場合における具体的な処理の一例である。この場合、マージ部１０７は、記憶部１１９に格納された単一のグリッドリスト（glist）を、インデックスｉとインデックスｊとの両方で参照し、逐次グリッドリスト（glist）の内容を更新する。なお、マージ部１０７がソフトウェア以外で実装される場合、およびマージ部１０７が上記の例とは仕様の異なるソフトウェアで実装される場合、実質的な処理内容が上記のフローチャートに沿ったものであれば、例えば処理対象とするグリッド１０３１の参照の仕方、およびクラスタのマージをデータに反映させるタイミングなどは、適宜設計されうる。
【０１５６】
（近傍探索マージ処理の詳細）
続いて、本実施形態における近傍探索マージ処理について説明する。近傍探索マージ処理では、マージ用ソート部１０９が、緯度および経度に基づく第１の順位決定処理の結果に基づいて、地表面のある方向についてクラスタ１０２１をソートする。また、隣接判定部１１１が、当該方向についてソートされたクラスタが、この方向について互いに隣接するか否かを判定する。さらに、マージ部１０７が、この方向について互いに隣接すると判定されたクラスタについて、クラスタ相互間の距離を算出する。マージ部１０７、マージ用ソート部１０９、および隣接判定部１１１は、地表面における別の方向についても、同様の処理によってクラスタをマージしてもよい。
【０１５７】
ここで、本実施形態において、地表面における方向は、例えば、水平方向、垂直方向、斜め右下方向、または斜め右上方向でありうる。マージ用ソート部１０９を含むマージ部１０７は、これらの方向のうちの１つについて、以下の近傍探索マージ処理を実行してもよい。この場合の近傍探索は、１方向探索とも呼ばれる。また、マージ用ソート部１０９を含むマージ部１０７は、上記の方向のうちの２つについて、以下の近傍探索マージ処理を実行してもよい。この場合の近傍探索は、２方向探索とも呼ばれる。また、マージ用ソート部１０９を含むマージ部１０７は、上記の４つの方向について、以下の近傍探索マージ処理を実行してもよい。この場合の近傍探索は、４方向探索とも呼ばれる。
【０１５８】
また、本実施形態において、マージ用ソート部１０９は、第１の順位決定処理として、地表面のある方向についてグリッド１０３１をソートして与えられたソート順を、各グリッド１０３１に含まれるクラスタ１０２１に順位として与えてもよい。図１を参照して説明したように、本実施形態において、グリッド１０３１とこれに含まれるクラスタ１０２１とは１対１に対応する。従って、グリッドに与えられたソート順を、そのままクラスタの順位として与えることが可能である。グリッド１０３１は、既知の境界で定義された領域であるため、地表面における特定の方向についてソートすることは容易である。それゆえ、グリッド１０３１のソート結果に基づいてクラスタ１０２１に順位を与える本実施形態に構成によって、クラスタ１０２１のソートを高速化することが可能である。
【０１５９】
図１７Ａ〜図１７Ｄは、本発明の第１の実施形態における近傍探索マージ処理で、グリッドの探索が実行される方向を示す図である。近傍探索マージ処理では、クラスタ１０２１が含まれるグリッド１０３１のリストであるグリッドリスト（glist）を、ある特定の方向についてソートし、ソートされたグリッドリスト（glist）において互いに隣接するグリッド１０３１を、マージ処理の対象とする。図１７Ａ〜図１７Ｄでは、それぞれの方向を基準にしてグリッドリスト（glist）のソート順を定義した場合に、各グリッドに与えられるインデックスが示されている。なお、図１７Ａ〜図１７Ｄにおいて、グリッド自体の配置は同じである。
【０１６０】
図１７Ａは、グリッドリスト（glist）の探索が水平方向に実行される場合を示す図である。地表面１００１での水平方向は、東西方向とも呼ばれる。なお、以下の図では、経度方向がｘ軸方向、緯度方向がｙ軸方向として図示されている。ここでの水平方向とは、ｘ軸方向のことである。
【０１６１】
この場合、グリッドリスト（glist）は、水平方向についてソートされる。グリッドリスト（glist）のソート順は、例えば、座標が（ｘ１，ｙ１）、（ｘ２，ｙ２）である２つのグリッドの前後関係を以下のように定義することで決定される。
【０１６２】
if(ｙ２≠ｙ１)
ｙ１，ｙ２の大小に基づき判定（より小さい方が前）
else
ｘ１，ｘ２の大小に基づき判定（より小さい方が前）
【０１６３】
図１７Ｂは、グリッドリスト（glist）の探索が垂直方向に実行される場合を示す図である。地表面１００１での垂直方向は、南北方向とも呼ばれる。この場合、グリッドリスト（glist）は、垂直方向についてソートされる。グリッドリスト（glist）のソート順は、例えば、座標が（ｘ１，ｙ１）、（ｘ２，ｙ２）である２つのグリッドの前後関係を以下のように定義することで決定される。
【０１６４】
if(ｘ２≠ｘ１)
ｘ１，ｘ２の大小に基づき判定（より小さい方が前）
else
ｙ１，ｙ２の大小に基づき判定（より小さい方が前）
【０１６５】
図１７Ｃは、グリッドリスト（glist）の探索が斜め右下方向に実行される場合を示す図である。地表面１００１での斜め右下方向は、北西−南東方向とも呼ばれる。この場合、グリッドリスト（glist）は、斜め右下方向についてソートされる。グリッドリスト（glist）のソート順は、例えば、座標が（ｘ１，ｙ１）、（ｘ２，ｙ２）である２つのグリッドの前後関係を以下のように定義することで決定される。
【０１６６】
ｓｕｍ１＝ｘ１＋ｙ１
ｓｕｍ２＝ｘ２＋ｙ２
if(ｓｕｍ１≠ｓｕｍ２)
ｓｕｍ１，ｓｕｍ２の大小に基づき判定（より小さい方が前）
else
ｙ１，ｙ２の大小に基づき判定（より大きい方が前）
【０１６７】
図１７Ｄは、グリッドリスト（glist）の探索が斜め右上方向に実行される場合を示す図である。地表面１００１での斜め右上方向は、南西−北東方向とも呼ばれる。この場合、グリッドリスト（glist）は、斜め右上方向についてソートされる。グリッドリスト（glist）のソート順は、例えば、座標が（ｘ１，ｙ１）、（ｘ２，ｙ２）である２つのグリッドの前後関係を以下のように定義することで決定される。
【０１６８】
最大のｙ座標からｙ１，ｙ２までの距離をｙ１’，ｙ２’とする
ｓｕｍ１＝ｘ１＋ｙ１’
ｓｕｍ２＝ｘ２＋ｙ２’
if(ｓｕｍ１≠ｓｕｍ２)
ｓｕｍ１，ｓｕｍ２の大小に基づき判定（より小さい方が前）
else
ｙ１，ｙ２の大小に基づき判定（より小さい方が前）
【０１６９】
図１８Ａ〜図１８Ｃは、本発明の第１の実施形態における近傍探索マージ処理での、１方向探索、２方向探索、および４方向探索について説明するための図である。本実施形態における近傍探索マージ処理では、図１７Ａ〜図１７Ｄを参照して説明したグリッド探索の方向を選択し、または組み合わせた、１方向探索、２方向探索、および４方向探索の３種類の探索手法が設定されている。
【０１７０】
図１８Ａは、１方向探索を示す図である。１方向探索では、グリッド探索の方向が１つだけ選択される。図示された例では、水平方向が選択されている。この場合、あるグリッドに対して水平方向で隣接する２つのグリッドが、マージ処理の対象になる。探索の方向が１つであるため、マージ処理におけるグリッドリスト（glist）のソート回数も１回でよい。なお、選択されるグリッド探索の方向は、水平方向には限られず、垂直方向、斜め右下方向、または斜め右上方向のいずれかであってもよい。このような１方向探索の場合、ソート回数は１回であり、マージ処理での最大距離計算回数は、クラスタの数をＮとすると、約Ｎ（回）になる。
【０１７１】
図１８Ｂは、２方向探索を示す図である。２方向探索では、グリッド探索の方向が２つ組み合わされる。図示された例では、水平方向と垂直方向とが組み合わされている。この場合、あるグリッドに対して水平方向、または垂直方向で隣接する４つのグリッドが、マージ処理の対象になる。探索の方向が２つであるため、マージ処理におけるグリッドリスト（glist）のソート回数は２回になる。なお、組み合わされるグリッド探索の方向は、水平方向と垂直方向とには限られず、これらの方向に代えて、斜め右下方向または斜め右上方向のいずれか、または両方が組み合わされてもよい。このような２方向探索の場合、ソート回数は２回であり、マージ処理での最大距離計算回数は、クラスタの数をＮとすると、約２Ｎ（回）になる。
【０１７２】
図１８Ｃは、４方向探索を示す図である。４方向探索では、グリッド探索の方向が４つ組み合わされる。本実施形態では、水平方向、垂直方向、斜め右下方向、および斜め右上方向の４つが組み合わされる。この場合、あるグリッドに対して水平方向、垂直方向、または斜め方向で近傍に位置するグリッドが、マージ処理の対象になる。ここで、斜め方向で隣にあるグリッドまでの距離が水平方向または垂直方向で隣接するグリッドよりも長くなることを考慮して、水平方向および垂直方向については、図示されているように２つ隣にあるグリッドまでを「隣接するグリッド」としてマージ処理の対象にしてもよい。この場合、マージ処理の対象になるのは、水平方向、垂直方向、および斜め方向の近傍にある１２のグリッドである。このような４方向探索の場合、ソート回数は４回であり、マージ処理での最大距離計算回数は、クラスタの数をＮとすると、約４Ｎ（回）になる。
【０１７３】
なお、上記の１方向探索、２方向探索、および４方向探索の最大距離計算回数は、いずれもＯ（Ｎ）になる。また、ソートは高速なものでＯ（ＮｌｏｇＮ）であるため、クラスタの数が膨大になれば、ソートの処理の方が演算量的に支配的になることも考えられる。
【０１７４】
図１９は、本発明の第１の実施形態における近傍探索マージ処理（上位探索なし）を示すフローチャートである。なお、近傍探索マージ処理（上位探索あり）については、上位探索の詳細とともに後述する。
【０１７５】
まず、マージ部１０７は、方向（dir）を“水平”として、隣接探索処理（上位探索なし）を実行する（ステップＳ６０１）。隣接探索処理（上位探索なし）については後述する。
【０１７６】
続いて、マージ部１０７は、マージ設定情報（config）の探索手法（searchType）が“2  Dir”または“4  Dir”であるか否かを判定する（ステップＳ６０３）。ここで、マージ設定情報（config）の探索手法（searchType）が“2  Dir”でも“4  Dir”でもない場合、マージ部１０７は、１方向探索が指定されているものと判断し、処理を終了する。
【０１７７】
ここで、ステップＳ６０３において、探索手法（searchType）が“2  Dir”または“4  Dir”であった場合、マージ部１０７は、方向（dir）を“垂直”として、隣接探索処理（上位探索なし）を実行する（ステップＳ６０５）。
【０１７８】
続いて、マージ部１０７は、マージ設定情報（config）の探索手法（searchType）が“4  Dir”であるか否かを判定する（ステップＳ６０７）。ここで、マージ設定情報（config）の探索手法（searchType）が“4  Dir”ではない場合、マージ部１０７は、２方向探索が指定されているものと判断し、処理を終了する。
【０１７９】
ここで、ステップＳ６０７において、探索手法（searchType）が“4  Dir”であった場合、マージ部１０７は、４方向探索が指定されているものと判断する。この場合、マージ部１０７は、方向（dir）を“斜め右下”として隣接探索処理（上位探索なし）を実行し（ステップＳ６０９）、続いて、方向を“斜め右上”として隣接探索処理（上位探索なし）を実行し（ステップＳ６１１）、処理を終了する。
【０１８０】
図２０は、本発明の第１の実施形態における隣接探索処理（上位探索なし）を示すフローチャートである。なお、隣接探索処理（上位探索あり）については、上位探索の詳細とともに後述する。
【０１８１】
まず、隣接判定部１１１が、マージ設定情報（config）の探索手法（searchType）が“4  Dir”であり、かつ、方向（dir）が“水平”または“垂直”であるか否かを判定する（ステップＳ７０１）。
【０１８２】
ここで、ステップＳ７０１において、マージ設定情報（config）の探索手法（searchType）が“4  Dir”であり、かつ、方向（dir）が“水平”または“垂直”である場合、隣接判定部１１１は、隣接判定閾値ｔｈ＿ｎとして２を設定する（ステップＳ７０３）。本実施形態において、隣接判定閾値ｔｈ＿ｎは、グリッド間隔を単位として設定されうる。隣接判定閾値ｔｈ＿ｎは、後述するグリッド間の隣接判定に用いられる閾値であり、マージ判定に用いられる所定の閾値ｔｈとは別個に設定されうる。
【０１８３】
一方、ステップＳ７０１において、マージ設定情報（config）の探索手法（searchType）が“4  Dir”ではない、すなわち“1  Dir”または“2  Dir”である場合、または、方向（dir）が“水平”でも“垂直”でもない場合、隣接判定部１１１は、隣接判定閾値ｔｈ＿ｎとして１を設定する（ステップＳ７０５）。なお、本実施形態において隣接探索処理が実行されるのは、マージ設定情報（config）の探索手法（searchType）が“1  Dir”、“2  Dir”、または“4  Dir”の場合である。
【０１８４】
ここで、マージ設定情報（config）の探索手法（searchType）に応じて隣接判定閾値ｔｈ＿ｎが設定されるのは、図１８Ａ〜図１８Ｃを参照して説明したように、１方向探索および２方向探索では、あるグリッドに対して水平方向または垂直方向に隣接するグリッド（グリッド間の距離が１グリッド分）がマージ処理の対象になるのに対して、４方向探索では、あるグリッドに対して水平方向および垂直方向では２つ隣にあるグリッド（グリッド間の距離が２グリッド分）までが「隣接するグリッド」としてマージ処理の対象になりうることに対応したものである。
【０１８５】
続いて、マージ用ソート部１０９が、グリッドリスト（glist）を、方向(dir)で一時的にソートする（tmpSort）（ステップＳ７０７）。ここで、方向（dir）は、例えば図１９のステップＳ６０１、ステップＳ６０５、ステップＳ６０９およびステップＳ６１１において、隣接探索処理（上位探索なし）が実行されるときにパラメータとして指定される。一時的なソート（tmpSort）は、図１７Ａ〜図１７Ｄを参照して説明したように、グリッドリスト（glist）の各グリッドにインデックスを一時的に与える処理でありうる。具体的には、例えば、方向（dir）が“水平”である場合、グリッドリスト（glist）の各グリッドには、図１７Ａを参照して説明したようなインデックスが一時的に与えられる。方向（dir）が“垂直”である場合、グリッドリスト（glist）の各グリッドには、図１７Ｂを参照して説明したようなインデックスが一時的に与えられる。方向（dir）が“斜め右下”である場合、グリッドリスト（glist）のグリッドには、図１７Ｃを参照して説明したようなインデックスが一時的に与えられる。方向（dir）が“斜め右上”である場合、グリッドリスト（glist）のグリッドには、図１７Ｄを参照して説明したようなインデックスが一時的に与えられる。後述のステップＳ７０９のループ処理は、この一時的に与えられたインデックスに従って実行される。なお、その後、グリッドリスト（glist）のインデックスは、保存されていた当初のインデックスに戻される。
【０１８６】
続くステップＳ７０９において、マージ部１０７および隣接判定部１１１は、ステップＳ７０７において設定されたインデックスに従って、グリッドリスト（glist）の先頭の要素から順に、以下のステップＳ７１１〜Ｓ７１７を繰り返す（マージするグリッドループ）。なお、このステップＳ７０９のループにおいて処理対象となっているグリッドリスト（glist）の要素を、グリッドリスト（glist）のインデックスｉの要素とする。
【０１８７】
ステップＳ７１１において、隣接判定部１１１は、グリッドリスト（glist）のインデックスｉの要素と、その次の要素（インデックスｉ＋１の要素）とが隣接しているか否かを判定する。ここで、本実施形態におけるグリッド間の隣接は、例えば方向（dir）が“水平”である場合、それぞれのグリッド１０３１の垂直方向の位置（図１７Ａの例でいえばｙ座標）が同じで、かつ水平方向の位置（図１７Ａの例でいえばｘ座標）の差が隣接判定閾値ｔｈ＿ｎ以下であるか否かによって判定されうる。それゆえ、ステップＳ７１１におけるグリッド間の隣接の判定処理は、任意座標間の距離の算出などの演算を含む処理と比較すると、処理負荷が小さい処理である。
【０１８８】
ここで、ステップＳ７１１において、グリッドリスト（glist）のインデックスｉの要素と、その次の要素（インデックスｉ＋１の要素）とが隣接していると判定された場合、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素とインデックスｉ＋１の要素との間の距離ｄの算出処理（distance）を実行する（ステップＳ７１３）。ここで、インデックスｉの要素とインデックスｉ＋１の要素との間の距離ｄは、例えば、インデックスｉの要素であるグリッド１０３１に含まれるクラスタ１０２１と、インデックスｉ＋１の要素であるグリッド１０３１に含まれるクラスタ１０２１との中心距離でありうる。
【０１８９】
続くステップＳ７１５は、ステップＳ７１３において算出された距離ｄを、所定の閾値ｔｈと比較するステップである。ここで、所定の閾値ｔｈは、例えば、表１を参照して説明されたマージ閾値でありうる。
【０１９０】
ここで、ステップＳ７１５において、距離ｄが閾値ｔｈ以下であると判定された場合、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素とインデックスｉ＋１の要素とをマージする（merge：ステップＳ７１７）。ここで、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素であるグリッド１０３１に対応するクラスタ１０２１と、インデックスｉ＋１の要素であるグリッド１０３１に対応するクラスタ１０２１とをマージした新たなクラスタ１０２１を生成し、この新たなクラスタ１０２１を、マージされる前の各クラスタ１０２１が対応付けられていたグリッド１０３１に対応付ける。つまり、このマージの後、インデックスｉの要素であるグリッド１０３１に対応するクラスタ１０２１と、インデックスｉ＋１の要素であるグリッド１０３１に対応するクラスタ１０２１とは、いずれもこの新たなクラスタ１０２１になる。
【０１９１】
一方、ステップＳ７１１において、グリッドリスト（glist）のインデックスｉの要素と、その次の要素（インデックスｉ＋１の要素）とが隣接していないと判定された場合、マージ部１０７は、ステップＳ７１３〜ステップＳ７１７の処理をスキップして、インデックスｉをインクリメントし、グリッドリスト（glist）の次の要素を参照する（ステップＳ７０９）。このように、処理負荷が比較的小さいグリッド間の隣接判定処理（ステップＳ７１１）によって、処理負荷が比較的大きい距離ｄの算出処理（ステップＳ７１３）を実行するか否かを判断することによって、処理全体の負荷を軽減することが可能になる。
【０１９２】
また、上記の隣接探索処理では、ソートされたグリッドリスト（glist）において隣接するグリッド間に限定してクラスタ間の距離を計算するため、ある方向（dir）についての最大計算回数は、クラスタの数をＮとすると、Ｎ−１（回）になる。ただし、これに、上述のようにＯ（ＮｌｏｇＮ）でソート処理の処理回数が加わる。
【０１９３】
（上位探索処理の詳細）
図２１は、本発明の第１の実施形態における近傍探索マージ処理（上位探索あり）を示すフローチャートである。
【０１９４】
まず、マージ部１０７は、上位グリッドリスト（ulist）を生成する（ステップＳ８０１）。ここで生成される上位グリッドリスト（ulist）について、図２２および図２３を参照して説明する。
【０１９５】
図２２および図２３は、本発明の第１の実施形態における上位探索において生成される上位グリッドリストについて説明するための図である。ここでは、水平方向に上位探索が実行される場合を例として説明する。なお、上位探索は、垂直方向、斜め右下方向、および斜め右下方向についても同様に実行されうる。
【０１９６】
図２２において示されるように、この例では、０〜１１の番号が付されたグリッドが、Ｉ〜ＶＩの６つの上位グリッドにそれぞれ属している。このような配置のグリッドおよび上位グリッドに対して、図２３において示されるように、０〜１１のグリッドを配列したグリッドリスト（glist）から、Ｉ〜ＶＩのそれぞれの上位グリッドに属するグリッドの先頭にあたるグリッド（各上位グリッドに属するグリッドは、水平方向にソートされている）を抽出したリストが上位グリッドリスト（ulist）である。後述されるように、上位グリッドリスト（ulist）は、例えば水平方向にソートされうる。
【０１９７】
図２１に戻って、次に、マージ部１０７は、上位グリッド内でのマージ処理を実行する（ステップＳ８０３）。ここで実行される上位グリッド内でのマージ処理について、図２４を参照して説明する。
【０１９８】
図２４には、図２２の例におけるＩの上位グリッドにおける、上位グリッド内のマージ処理の例が示されている。図２４において示されているように、Ｉの上位グリッドに属する各グリッドの総当りの組み合わせ１組が対象になる。このような上位グリッド内でのマージ処理における最大距離計算回数は、クラスタの数をＮとすると、約Ｎ／４×６＝１．５Ｎ（回）になる。
【０１９９】
図２１に戻って、続いて、マージ部１０７は、方向（dir）を“水平”として、隣接探索処理（上位探索あり）を実行する（ステップＳ８０５）。隣接探索処理（上位探索あり）については後述する。
【０２００】
続いて、マージ部１０７は、マージ設定情報（config）の探索手法（searchType）が“2  Dir”または“4  Dir”であるか否かを判定する（ステップＳ８０７）。ここで、マージ設定情報（config）の探索手法（searchType）が“2  Dir”でも“4  Dir”でもない場合、マージ部１０７は、１方向探索が指定されているものと判断し、処理を終了する。
【０２０１】
ここで、ステップＳ８０７において、探索手法（searchType）が“2  Dir”または“4  Dir”であった場合、マージ部１０７は、方向（dir）を“垂直”として、隣接探索処理（上位探索あり）を実行する（ステップＳ８０９）。
【０２０２】
続いて、マージ部１０７は、マージ設定情報（config）の探索手法（searchType）が“4  Dir”であるか否かを判定する（ステップＳ８１１）。ここで、マージ設定情報（config）の探索手法（searchType）が“4  Dir”ではない場合、マージ部１０７は、２方向探索が指定されているものと判断し、処理を終了する。
【０２０３】
ここで、ステップＳ８１１において、探索手法（searchType）が“4  Dir”であった場合、マージ部１０７は、４方向探索が指定されているものと判断する。この場合、マージ部１０７は、方向（dir）を“斜め右下”として隣接探索処理（上位探索あり）を実行し（ステップＳ８１３）、続いて、方向を“斜め右上”として隣接探索処理（上位探索あり）を実行し（ステップＳ８１５）、処理を終了する。
【０２０４】
図２５は、本発明の第１の実施形態における隣接探索処理（上位探索あり）を示すフローチャートである。
【０２０５】
まず、隣接判定部１１１が、マージ設定情報（config）の探索手法（searchType）が“4  Dir”であり、かつ、方向（dir）が“水平”または“垂直”であるか否かを判定する（ステップＳ９０１）。
【０２０６】
ここで、ステップＳ９０１において、マージ設定情報（config）の探索手法（searchType）が“4  Dir”であり、かつ、方向（dir）が“水平”または“垂直”である場合、隣接判定部１１１は、隣接判定閾値ｔｈ＿ｎとして２を設定する（ステップＳ９０３）。本実施形態において、隣接判定閾値ｔｈ＿ｎは、上位グリッド間隔を単位として設定されうる。なお、上位グリッド間隔はグリッド間隔の２倍である。隣接判定閾値ｔｈ＿ｎは、後述する上位グリッド間の隣接判定に用いられる閾値であり、マージ判定に用いられる所定の閾値ｔｈとは別個に設定されうる。
【０２０７】
一方、ステップＳ９０１において、マージ設定情報（config）の探索手法（searchType）が“4  Dir”ではない、すなわち“1  Dir”または“2  Dir”である場合、または、方向（dir）が“水平”でも“垂直”でもない場合、隣接判定部１１１は、隣接判定閾値ｔｈ＿ｎとして１を設定する（ステップＳ９０５）。なお、本実施形態において隣接探索処理が実行されるのは、マージ設定情報（config）の探索手法（searchType）が“1  Dir”、“2  Dir”、または“4  Dir”の場合である。
【０２０８】
ここで、マージ設定情報（config）の探索手法（searchType）に応じて隣接判定閾値ｔｈ＿ｎが設定されるのは、図１８Ａ〜図１８Ｃを参照して説明したように、１方向探索および２方向探索では、あるグリッドに対して水平方向または垂直方向に隣接するグリッド（グリッド間の距離が１グリッド分）がマージ処理の対象になるのに対して、４方向探索では、あるグリッドに対して水平方向および垂直方向では２つ隣にあるグリッド（グリッド間の距離が２グリッド分）までが「隣接するグリッド」としてマージ処理の対象になりうることに対応したものである。
【０２０９】
続いて、マージ用ソート部１０９が、図２３を参照して説明したように、上位グリッドリスト（ulist）を方向(dir)についてソートする（sort）（ステップＳ９０７）。ここで、方向（dir）は、例えば図２１のステップＳ８０５、ステップＳ８０９、ステップＳ８１３およびステップＳ８１５において、隣接探索処理（上位探索あり）が実行されるときにパラメータとして指定される。ソート（sort）は、図１７Ａ〜図１７Ｄを参照して説明したようなグリッドリスト（glist）の各グリッドにインデックスを与える処理を、上位グリッドリスト（ulist）に含まれる各上位グリッドの先頭のグリッドに対して実行するものでありうる。
【０２１０】
続くステップＳ９０９において、マージ部１０７および隣接判定部１１１は、ステップＳ９０７のソートの結果に従って、上位グリッドリスト（ulist）の先頭の要素から順に、以下のステップＳ９１３〜Ｓ９２３を繰り返す（上位グリッドリストループ）。なお、このステップＳ９０９のループにおいて処理対象となっている上位グリッドリスト（ulist）の要素を、上位グリッドリスト（ulist）のインデックスｉの要素とする。
【０２１１】
ステップＳ９１１において、隣接判定部１１１は、上位グリッドリスト（ulist）のインデックスｉの要素に対応する上位グリッドと、その次の要素（インデックスｉ＋１の要素）に対応する上位グリッドとが隣接しているか否かを判定する。ここで、本実施形態における上位グリッド間の隣接は、例えば方向（dir）が“水平”である場合、それぞれのグリッド１０３１の垂直方向の位置（図１７Ａの例でいえばｙ座標）が同じで、かつ水平方向の位置（図１７Ａの例でいえばｘ座標）の差が隣接判定閾値ｔｈ＿ｎ以下であるか否かによって判定されうる。それゆえ、ステップＳ９１１における上位グリッド間の隣接の判定処理は、任意座標間の距離の算出などの演算を含む処理と比較すると、処理負荷が小さい処理である。
【０２１２】
ここで、ステップＳ９１１において、上位グリッドリスト（ulist）のインデックスｉの要素に対応する上位グリッドと、その次の要素（インデックスｉ＋１の要素）に対応する上位グリッドとが隣接していると判定された場合、ステップＳ９１３において、マージ部１０７は、上位グリッドリスト（ulist）のインデックスｉの要素に対応する上位グリッド（第１の上位グリッド）に属するグリッド（サブグリッド：subgrids）のそれぞれについて、以下のステップＳ９１５〜Ｓ９２１を繰り返す（第１の上位グリッドのサブグリッドループ）。ここで、ステップＳ９１３のループの処理対象となっているグリッド（サブグリッド）をａとする。
【０２１３】
さらに、ステップＳ９１５において、マージ部１０７は、上位グリッドリスト（ulist）のインデックスｉ＋１の要素に対応する上位グリッド（第２の上位グリッド）に属するグリッド（サブグリッド：subgrids）のそれぞれについて、以下のステップＳ９１７〜Ｓ９２１を繰り返す（第２の上位グリッドのサブグリッドループ）。ここで、ステップＳ９１５のループの処理対象となっているグリッド（サブグリッド）をｂとする。
【０２１４】
ステップＳ９１７において、マージ部１０７は、グリッドａとグリッドｂとの間の距離ｄの算出処理（distance）を実行する（ステップＳ９１７）。ここで、グリッドａとグリッドｂとの間の距離ｄは、例えば、グリッドａに含まれるクラスタと、グリッドｂに含まれるクラスタとの中心距離でありうる。
【０２１５】
続くステップＳ９１９は、ステップＳ９１７において算出された距離ｄを、所定の閾値ｔｈと比較するステップである。ここで、所定の閾値ｔｈは、例えば、表１を参照して説明されたマージ閾値でありうる。
【０２１６】
ここで、ステップＳ９１９において、距離ｄが閾値ｔｈ以下であると判定された場合、マージ部１０７は、グリッドａに含まれるクラスタと、グリッドｂに含まれるクラスタとをマージする（merge：ステップＳ９２１）。ここで、マージ部１０７は、グリッドａに対応するクラスタと、グリッドｂに対応するクラスタとをマージした新たなクラスタを生成し、この新たなクラスタを、グリッドａおよびグリッドｂの両方に対応付ける。つまり、このマージの後、グリッドａに対応するクラスタと、グリッドｂに対応するクラスタとは、いずれもこの新たなクラスタになる。
【０２１７】
一方、ステップＳ９１１において、上位グリッドリスト（ulist）のインデックスｉの要素に対応する上位グリッドと、その次の要素（インデックスｉ＋１の要素）に対応する上位グリッドとが隣接していないと判定された場合、マージ部１０７は、ステップＳ９１３〜ステップＳ９２１の処理をスキップして、インデックスｉをインクリメントし、上位グリッドリスト（ulist）の次の要素を参照する（ステップＳ９０９）。このように、処理負荷が比較的小さい上位グリッド間の隣接判定処理（ステップＳ９１１）によって、処理負荷が比較的大きい距離ｄの算出処理（ステップＳ９１７）を実行するか否かを判断することによって、処理全体の負荷を軽減することが可能になる。
【０２１８】
ここで、図２６を参照して、上記のステップＳ９１３〜Ｓ９２１の処理についてさらに説明する。図２６には、方向（dir）が“水平”で、図２２の例におけるＩおよびＩＩＩの上位グリッドが、それぞれ第１の上位グリッドおよび第２の上位グリッドになった場合の、ステップＳ９１３〜Ｓ９２１の処理の例が示されている。
【０２１９】
図示された例において、ステップＳ９１３のループ処理の対象（グリッドａ）になるグリッドは、Ｉの上位グリッドに属する各グリッドである。また、ステップＳ９１５のループ処理の対象になるグリッドは、ＩＩＩの上位グリッドに属する各グリッドである。従って、ステップＳ９１７〜Ｓ９２１におけるグリッドａとグリッドｂとの間のマージ処理の対象になるグリッドの組み合わせは、図２５において示されているように、Ｉの上位グリッドに属する各グリッドと、ＩＩＩの上位グリッドに属する各グリッドとの総当りの組み合わせで、合計６組になる。このような上位グリッド間でのマージ処理における最大距離計算回数は、クラスタの数をＮとすると、約Ｎ／４×４２＝４Ｎ（回）になる。
【０２２０】
図２７は、本発明の第１の実施形態において、近傍探索マージ処理（上位探索あり）が実行された場合の、あるグリッド（濃いハッチングで表されているグリッド）に対するマージ処理の対象グリッド（薄いハッチングで表されているグリッド）を示す図である。図２７には、マージ設定情報（config）の探索種類（searchType）が“4  Dir”、上位レベル探索（upperLevel）が１である場合の例が示されている。
【０２２１】
この場合、４つの方向について近傍にある１２の上位グリッド（太線で表されている）が、上位探索でのマージ処理対象となる。さらに、上記のあるグリッドが属する上位グリッド内の３つのグリッドが、上位グリッド内のマージ処理の対象となる。従って、上位探索処理を含む近傍探索マージ処理によってマージ処理の対象となるグリッドは、全部で５１のグリッドになる。４方向探索なので、ソート回数は４回になり、最大距離計算回数は、クラスタの数をＮとすると、（４×４Ｎ）＋１．５Ｎ＝１７．５Ｎ（回）になる。
【０２２２】
上記のような上位探索処理は、１方向探索、２方向探索で実行されてもよいが、本実施形態における探索範囲の形状的には、４方向探索で実行されるのが好ましい。また、上位探索処理を実行する場合としない場合とで、ソート回数は変わらないが、距離計算回数は増加する。
【０２２３】
（距離順マージ処理の詳細）
距離順マージ処理は、相互間の距離が所定の閾値以下であるクラスタ１０２１を探索し、そのようなクラスタ１０２１をマージ候補クラスタとして記憶する処理と、記憶されたマージ候補クラスタのうち、相互間の距離が小さいマージ候補クラスタから順にマージする処理とを含む。
【０２２４】
図２８は、本発明の第１の実施形態における距離順ソートの概要について説明するための図である。図２８では、水平方向（この例における探索方向とする）に隣接した３つのグリッド１０３１にそれぞれ含まれるクラスタ１０２１ｓ〜１０２１ｕが図示されている。ここで、クラスタ１０２１ｓとクラスタ１０２１ｔとの間の中心距離をｄ１、クラスタ１０２１ｔとクラスタ１０２１ｕとの間の中心距離をｄ２とする。ｄ１およびｄ２は、いずれも、マージ処理のための所定の閾値ｔｈを下回っており、ｄ１＞ｄ２であるものとする。
【０２２５】
ここで、図示されているような向きで、上述のような隣接探索処理が実行された場合、先にマージ処理の対象となるのは、クラスタ１０２１ｓとクラスタ１０２１ｔの組み合わせである。クラスタ１０２１ｓとクラスタ１０２１ｔとの中心距離ｄ１は、マージ処理のための所定の閾値ｔｈを下回っているため、クラスタ１０２１ｓとクラスタ１０２１ｔはマージされ、クラスタ１０２１ｖとなる。ここで、クラスタ１０２１ｖとクラスタ１０２１ｕとの間の中心距離をｄ３とする。ｄ３は、ｄ１およびｄ２よりも大きく、マージ処理のための所定の閾値ｔｈを上回っているものとする。
【０２２６】
この後、クラスタ１０２１ｖとクラスタ１０２１ｕがマージ処理の対象となる。しかし、クラスタ１０２１ｖとクラスタ１０２１ｕとの間の中心距離ｄ３は、マージ処理のための所定の閾値ｔｈを上回っているため、クラスタ１０２１ｖとクラスタ１０２１ｕとはマージされず、クラスタ１０２１ｓ〜１０２１ｕがマージされたクラスタ１０２１ｗは生成されない。
【０２２７】
このように、探索順にマージ処理が実行される場合、クラスタ間の中心距離では、クラスタ１０２１ｓとクラスタ１０２１ｔとの間のｄ１よりも、クラスタ１０２１ｔとクラスタ１０２１ｕとの間のｄ２の方が小さいにもかかわらず、クラスタ１０２１ｓとクラスタ１０２１ｔとがマージされ、クラスタ１０２１ｕはマージされないという問題が生じうる。
【０２２８】
かかる問題を解決するために、距離順マージが実行される。本実施形態では、上述のように、マージ設定情報（config）に距離順マージフラグ（sortPair）が含まれ、この距離順マージフラグ（sortPair）が“true”の場合に、距離順マージが実行される。
【０２２９】
図２９は、本発明の第１の実施形態における距離順マージ処理を示すフローチャートである。
【０２３０】
まず、マージ部１０７は、図１５を参照して説明した説明した探索順マージ処理を実行する（ステップＳ１００１）。ただし、探索順マージ処理から呼び出される、フルマッチマージ処理または近傍探索マージ処理において、マージ（merge）に代えて、距離順マージ処理では、ペアリスト（pairList）に、それぞれのグリッドに含まれるクラスタをマージ候補クラスタとして追加する処理（add）が実行される。例えば、図２０を参照して説明した隣接探索処理（上位探索なし）のステップＳ７１７は、距離順マージ処理の場合以下のように書き換えられる。
【０２３１】
「ここで、ステップＳ７１５において、距離ｄが閾値ｔｈ以下であると判定された場合、マージ部１０７は、グリッドリスト（glist）のインデックスｉの要素に含まれるクラスタと、インデックスｉ＋１の要素に含まれるクラスタとを、マージ候補クラスタとしてペアリスト（pairList）に追加する（add）。」
【０２３２】
続いて、マージ部１０７は、ペアリスト（pairList）を、要素であるクラスタのペアを、クラスタ間の距離ｄの順にソートする（ステップＳ１００３）。このために、ステップＳ１００１において、ペアになるクラスタの情報に加えてクラスタ間の距離ｄの情報も一緒にペアリスト（pairList）に追加されてもよい。
【０２３３】
続いて、ステップＳ１００５において、マージ部１０７は、ステップＳ１００３においてソートされた順番に従って、ペアリスト（pairList）の先頭から順に、ステップＳ１００７を繰り返す（ペアリストループ）。ここで、ステップＳ１００５のループで処理対象になっているペアリスト（pairList）の要素のインデックスをｋとする。ペアリストがクラスタ間の距離ｄの順にソートされ、そのソートされた順番に従ってマージのための処理が実行されることで、相互間の距離が小さいマージ候補クラスタから順にマージされることになる。
【０２３４】
ステップＳ１００７では、ペアリスト（pairList）のインデックスｋの要素であるクラスタのペアについて、それぞれのクラスタをマージした新たなクラスタを生成する（merge）。この新たなクラスタの情報には、マージされている元のクラスタの情報が含まれていてもよい。ステップＳ１００７において、処理対象の一方のクラスタが、先に行われたステップＳ１００５のループ処理で他のクラスタとマージされていた場合、マージは、処理対象のもう一方のクラスタと、そのマージされたクラスタとの間で実行されうる。また、ステップＳ１００７において、処理対象の両方のクラスタが、先に行われたステップＳ１００５のループ処理で他のクラスタとマージされていた場合、マージ部１０７は、マージを実行せず、ペアリスト（pairList）の次の要素の処理に移ってもよい（ステップＳ１００５）。
【０２３５】
なお、距離順マージを有効にした場合、ペアリスト（pairList）を保持するための記憶領域が消費される。ペアリスト（pairList）のサイズは、マージされる可能性があるマージ候補クラスタの数である。それゆえ、ペアリスト（pairList）のサイズは、ワーストケース（最もサイズが大きくなるケース）において、最大距離計算回数に一致し、また、隣接判定の範囲が広がるほど大きくなる。ここで、最大距離計算回数は、処理対象のグリッド数、近傍探索の方向、および上位レベル探索を実行する上位レベルの数が多くなるほど増加する。従って、使用可能な記憶領域が限られる環境では、例えば図１３を参照して説明したマージ設定情報を利用するなどして、処理対象のグリッド数がある程度以下である場合に距離順マージを有効にすることが望ましい。
【０２３６】
以上、本発明の第１の実施形態におけるマージ処理について説明した。一般的なマージ処理では、クラスタ全体の組み合わせに対してそれぞれ距離計算の処理が発生し、処理負荷が高い。また、一般的なマージ処理では、処理負荷を調整することが難しい。これに対して、本実施形態におけるマージ処理では、例えばクラスタ１０２１を含むグリッド１０３１の数に応じて、マージをするか否か、探索順マージか距離順マージか、フルマッチマージか近傍探索マージかといったマージの設定を選択し、マージの精度と処理負荷とを調整することが可能である。近傍探索マージでは、マージのためのクラスタ間の距離計算をするクラスタを、ある方向についてソートした場合に隣接するクラスタに限定することによって、距離計算の回数を減らし、処理負荷を低減させている。
【０２３７】
＜２．第２の実施形態＞
本発明の第２の実施形態では、地球を含む３次元空間が特徴空間に相当する。また、本実施形態において、３次元空間における位置情報は、例えばｘ座標、ｙ座標、およびｚ座標のような、３次元の直交座標系を用いて表される。また、本実施形態において、クラスタは、ｘ座標、ｙ座標、およびｚ座標によって３次元空間内に定義されるブロックに含まれるコンテンツの位置情報を包含する領域である。
【０２３８】
なお、本発明の第２の実施形態は、クラスタリングが２次元座標によって定義されるグリッドではなく、３次元座標によって定義されるブロックに基づいて行われる点において本発明の第１の実施形態と相違するが、それ以外の構成は第１の実施形態と略同一であるため、ここでは詳細説明を省略する。
【０２３９】
（２−１．ブロックベースの位置クラスタリングの概要）
図３０Ａ〜図３４を参照して、本発明の第２の実施形態におけるクラスタリングの概要について説明する。本実施形態におけるクラスタリングは、３次元の直交座標系を用いて定義されるブロックを基準にして、位置情報を有するコンテンツをクラスタに分類するものであり、ブロックベースの位置クラスタリングともいえるものである。
【０２４０】
（ブロックについて）
図３０Ａは、本発明の第２の実施形態におけるコンテンツ、クラスタ、およびブロックの関係の例を示す図である。図３０Ａには、３次元空間２００１、コンテンツ２０１１、クラスタ２０２１、およびブロック２０３１が図示されている。
【０２４１】
３次元空間２００１は、地球の一部または全部を含む空間である。本実施形態において、３次元空間２００１は、ｘ座標、ｙ座標、およびｚ座標という３次元の座標によって位置情報が表される３次元空間である。
【０２４２】
コンテンツ２０１１は、３次元空間２００１内の位置を特定する位置情報を有するデータである。コンテンツ２０１１は、位置情報そのものであってもよく、また、何らかの情報に対する付加的な情報として位置情報が付加されたデータであってもよい。コンテンツ２０１１は、例えば、撮影場所の位置情報が付加された画像データでありうる。
【０２４３】
クラスタ２０２１は、３次元空間２００１において互いに近い位置にあるコンテンツ２０１１を含む領域である。クラスタ２０２１は、直方体として図示されているが、その他の形状であってもよい。また、クラスタ２０２１は、コンテンツ２０１１に外接する立体であってもよい。図示されている例において、コンテンツ２０１１は、地表面上に位置する。そのため、コンテンツ２０１１は、クラスタ２０２１の地表面による切断面２０２１ｓ上にある。
【０２４４】
ブロック２０３１は、３次元空間２００１に設定されたブロックである。ブロック２０３１は、３次元空間２００１内でｘ座標、ｙ座標およびｚ座標の範囲によって定義される直方体形状の領域でありうる。ブロック２０３１の大きさは、コンテンツ２０１１の数、およびクラスタリングの対象となる領域の大きさなど、クラスタリングの条件に応じて、適切な大きさに設定されうる。
【０２４５】
図示されているように、本実施形態においては、同じブロック２０３１に含まれるコンテンツ２０１１が、同じクラスタ２０２１に分類される。つまり、本実施形態におけるブロックベースの位置クラスタリング処理においては、同じブロック２０３１に含まれるか否かが、クラスタリングの基本的な基準になる。図示されたコンテンツ２０１１は、そのすべてが同じブロック２０３１に含まれるため、同じクラスタ２０２１に分類される。
【０２４６】
なお、図示されている例では、コンテンツ２０１１はいずれも地表面上に位置している。しかし、コンテンツ２０１１は、例えば地球の内側＝地下に位置していてもよい。この場合、コンテンツ２０１１は、クラスタ２０２１の地表面による切断面２０２１ｓよりも奥側にある。また、コンテンツ２０１１は、地球の外側＝空中に位置していてもよい。この場合、コンテンツ２０１１は、クラスタ２０２１の地表面による切断面２０２１ｓよりも手前側にある。クラスタリングの基準が、地球の内側と外側とにまたがるブロック２０３１であることによって、そのような場合でも、コンテンツ２０１１に対してクラスタ２０２１を設定することが可能である。
【０２４７】
図３０Ｂは、本発明の第２の実施形態におけるコンテンツおよびクラスタの表示の例を示す図である。図３０Ｂでは、図３０Ａの例におけるコンテンツ２０１１およびクラスタ２０２１が、地表面上の図形として表示された例が示されている。
【０２４８】
図示された例では、コンテンツ２０１１と、クラスタ２０２１の地表面による切断面２０２１ｓに外接する円であるクラスタ表示領域２０２１ｄとが表示されている。このように、クラスタ表示領域２０２１ｄは、クラスタ２０２１の地表面による切断面２０２１ｓの外接図形でありうる。また、上述のようにコンテンツ２０１１が地下や空中に位置する場合には、クラスタ表示領域２０２１ｄは立体的な図形であってもよい。
【０２４９】
本実施形態におけるブロックベースの位置クラスタリングでは、コンテンツ２０１１の位置情報そのものが、コンテンツ２０１１が含まれるブロック２０３１を表している。上述の第１の実施形態と同様にして、コンテンツ２０１１を、ｘ座標、ｙ座標およびｚ座標の値を順に１桁ずつ配列したＮ進数値の順にソートすると、同一のブロック２０３１の領域に含まれるコンテンツ２０１１は、ソートの結果において互いに隣接する。ソートの結果において隣接したコンテンツ２０１１同士が同一のブロック２０３１に含まれるか否かは、例えば、上記のＮ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通するか否かによって判定されうる。ここで、上述のように、同一のブロック２０３１に含まれるコンテンツ２０１１は、同一のクラスタ２０２１に分類されるコンテンツである。それゆえ、本実施形態におけるブロックベースの位置クラスタリングでは、コンテンツ２０１１の位置情報から生成した数値をソートすることが、クラスタリングの主な処理になる。
【０２５０】
（ブロックの階層構造について）
本実施形態におけるブロック２０３１も、第１の実施形態におけるグリッド１０３１と同様に、階層構造にすることが可能である。ここでは、中心が地球の中心と一致し、地球全体を包含するブロックがレベル０ブロックである場合を例として説明する。この場合、レベル１ブロックは、レベル０ブロックをｘ座標、ｙ座標、およびｚ座標についてそれぞれ２分割したブロックである。また、レベル２ブロックは、レベル１ブロックをｘ座標、ｙ座標、およびｚ座標についてそれぞれ２分割したブロックである。さらに、同様にして、レベル２ブロックの領域をｘ座標、ｙ座標、およびｚ座標についてそれぞれ２分割したレベル３ブロック、レベル３ブロックの領域をｘ座標、ｙ座標、およびｚ座標についてそれぞれ２分割したレベル４ブロック、・・・というように、さらに下位のレベルのブロックが定義されうる。
【０２５１】
図３１は、本発明の第２の実施形態におけるブロックによる地表面の分割について説明するための図である。レベル０ブロックの中心が地球の中心と一致している場合、地表面２０１０は、図示されているように、レベル１ブロックによって８つの領域２０３２ａ〜２０３２ｈに分割される。図３１は、地球を外部から見た図であり、レベル１ブロックによって分割された領域のうち２０３２ａ〜２０３２ｅが図示されている。
【０２５２】
図３２は、本発明の第２の実施形態におけるブロックによる地表面の分割について説明するための図である。図３２では、地球を平面に展開した図であり、レベル１ブロックによって分割された地表面２０１０の８つの領域２０３２ａ〜２０３２ｈと、レベル１ブロックをさらに分割したレベル２ブロックによって分割された地表面２０１０の領域２０３３とが図示されている。本実施形態において、レベル１ブロックは、レベル２ブロックによって８つに分割されるが、レベル２ブロックのうち１つは地球の内側にあるため、地表面２０１０と交わらない。それゆえ、レベル１ブロックによって分割された地表面２０１０の８つの領域２０３２ａ〜２０３２ｈは、それぞれ、レベル２ブロックによって分割されて、８−１＝７つの領域２０３３になる。
【０２５３】
図３３は、本発明の第２の実施形態におけるブロックによる地表面の分割について説明するための図である。図３３では、上記のレベル０ブロック〜レベル２ブロックと同様にして順次定義される下位のブロックのうち、レベル５ブロックによって分割された地表面２０１０の領域が図示されている。図示された例のように、レベル５ブロックは、例えば、日本の地域ごとにコンテンツ２０１１を分類するのに適したサイズになる。本実施形態におけるブロックベースの位置クラスタリングにおいても、クラスタリング処理に用いられるブロックのレベルを調整することによって、クラスタリングの粒度と処理負荷とをバランスさせることが可能である。
【０２５４】
このように、本実施形態においては、あるレベルのブロックをｘ座標、ｙ座標、およびｚ座標についてそれぞれ２分割したブロックが、１つ下位のレベルのブロックになる。換言すれば、下位のレベルのブロックは、上位のレベルのブロックの領域を８分割する。従って、本実施形態におけるブロック２０３１の階層構造は、レベル０ブロックをルートノードとし、以下の各レベルのブロックをノードとする８分木構造を有し、ブロック２０３１に従って定義されるクラスタ２０２１もまた、同様の８分木構造を有するといえる。
【０２５５】
ここで、一般的な距離ベースの位置クラスタリングでは、クラスタの木構造が定義された場合、その木構造の情報を保持する記憶領域が消費される。一方、本実施形態におけるブロックベースの位置クラスタリングでは、上述のようにブロック２０３１の８分木構造が一意に定まっているため、ブロック２０３１がどのレベルのブロックであるかという情報が保持されていれば、ブロック２０３１の８分木構造に基づいて、クラスタ２０２１の木構造を容易に把握することが可能である。
【０２５６】
（グリッドベースとの比較）
上述の第１の実施形態におけるグリッドベースの位置クラスタリングでは、地表面を、緯度および経度という２次元の座標によって位置情報が表される２次元平面として扱う。この場合、グリッドサイズは、例えば、緯度１度×経度１度、といったように定義される。しかし、周知のように、緯度１度あたりの距離が約１１１ｋｍでほぼ一定であるのに対して、経度１度あたりの距離は、高緯度になるほど短くなる。具体的には、緯度０度の赤道上での経度１度あたりの距離が約１１１ｋｍであるのに対し、緯度６０度での経度１度あたりの距離は約５５．７ｋｍである。従って、グリッドサイズを実際の距離で表すと、赤道付近では１１１ｋｍ×１１１ｋｍであるのに対し、緯度６０度付近では１１１ｋｍ×５５．７ｋｍと、面積では半分程度になってしまう。
【０２５７】
これに対して、本実施形態におけるブロックベースの位置クラスタリングでは、地表面２０１０上のコンテンツ２０１１を、３次元空間２００１に定義されたブロック２０３１で囲むことによってクラスタ２０２１を設定する。従って、ブロック２０３１のサイズは、緯度の高低によって変化しない。なお、ブロック２０３１の地表面２０１０との交わり方の違いによって、地表面２０１０で占める領域のサイズは、同緯度のブロック２０３１の間でも互いに異なりうる。このようなブロックベースの位置クラスタリングにマージ処理を合わせて行うことによって、地球全体にわたって、緯度によらずに均一な粒度のクラスタリングが実現される。
【０２５８】
（ブロックに対応付けられるＮ進数値）
図３４は、本発明の第２の実施形態におけるクラスタリングについて説明するための図である。各ブロック２０３１に付されている番号は、これらのブロックをＮ進数値の大小でソートした場合のインデックスである。
【０２５９】
本実施形態においても、情報処理装置１００のＮ進数値生成部１０１によって、Ｎ進数値が生成される。本実施形態におけるＮ進数値は、３次元空間２００１において３次元の座標によって表される位置情報を有するデータについて、所定の桁数の２進数で表現された各次元の座標の値を各次元について順に１桁ずつ配列した２進数値でありうる。
【０２６０】
例えば、所定の桁数として２１桁を設定した場合、Ｎ進数値生成部１０１は、ｘ座標、ｙ座標、およびｚ座標の値をそれぞれ２１桁の２進数値で表現する。ここで、２進数で表現されたｘ座標を“ｘ２０ｘ１９ｘ１８・・・ｘ０”とし、２進数で表現された経度を“ｙ２０ｙ１９ｙ１８・・・ｙ０”とし、２進数で表現されたｚ座標を“ｚ２０ｚ１９ｚ１８・・・ｚ０”とすると、これらの値を各次元について順に１桁ずつ配列した２進数値は、“ｘ２０ｙ２０ｚ２０ｘ１９ｙ１９ｚ１９ｘ１８ｙ１８ｚ１８・・・ｘ０ｙ０ｚ０”という６３桁の２進数値になる。なお、所定の桁数が２１桁である場合、ブロック２０３１の対角線方向での最小分解能は１１ｍ相当になる。所定の桁数は、例えば、必要な最小分解能、および情報処理装置１００で扱われるデータ単位のサイズ（例えば３２ビット、６４ビットなど）を考慮した適切な値に設定されうる。
【０２６１】
図示された例では、３次元空間２００１において、各次元の座標が３桁の２進数値で表現される。ここで、ブロック２０３１は、この２進数値のうち上位の２桁によって規定されるブロックである。かかるブロック２０３１は、３次元空間２００１を（２３）２＝６４分割する。図では、各ブロック２０３１に０〜６３のインデックスが与えられている。このインデックスは、当該ブロック２０３１に含まれうるコンテンツ２０１１のとりうる２進数値の順にブロック２０３１をソートした場合のソート順に対応する。この場合における、インデックス０〜８，５５〜６３のブロック２０３１に含まれうるコンテンツ２０１１の、座標およびＮ進数値生成部１０１によって生成される２進数値は、以下の表２のようになる。なお、表中「００ｘ」「００ｙ」「００ｚ」という表記「ｘ」「ｙ」「ｚ」は、任意の値（０または１）を示す。
【０２６２】
【表２】
2012113625.tif 000006
【０２６３】
本実施形態において、クラスタリング部１０３は、Ｎ進数値生成部１０１が生成した２進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する複数のコンテンツ２０１１を同一のクラスタに分類する。ｋ＝３×ｍ（ｍ＝１，２，・・・）である場合、２進数値の上位ｋ桁が共通するコンテンツ２０１１が分類されるクラスタは、２３＝８分木構造クラスタのｍ層目になる。
【０２６４】
ここで、表２を参照すると、インデックス０〜７のブロック２０３１に含まれるコンテンツ２０１１は、いずれも２進数値の上位３桁が“０００”で共通している。図３４を参照すると、これらのコンテンツ２０１１が含まれるブロック２０３１は、図中の左下奥に位置する８つのブロック２０３１であることがわかる。図示されているように、これらのブロック２０３１は、１階層上位のブロックである上位ブロック２０４１を構成する８つのブロック２０３１である。従って、例えば、インデックス１のブロック２０３１に含まれるコンテンツ２０１１と、インデックス５のブロック２０３１に含まれるコンテンツ２０１１とは、同じ上位ブロック２０４１に含まれる。
【０２６５】
本実施形態においても、上述の第１の実施形態におけるグリッドとクラスタとの関係と同様に、また図３０Ａおよび図３０Ｂを参照して説明したように、ブロック２０３１はそれぞれクラスタ２０２１と対応付けられている。従って、上記の例から、２進数値の上位ｋ桁が共通するコンテンツ２０１１が同一のクラスタ２０２１に分類されることがわかる。
【０２６６】
なお、本実施形態のクラスタリングおよびマージ処理に関するその他の処理は、上述の第１の実施形態と同様に行われうる。
【０２６７】
＜３．本発明の実施形態に係る情報処理装置のハードウェア構成＞
次に、図３５を参照しながら、本発明の実施形態に係る情報処理装置１００のハードウェア構成について、詳細に説明する。図３５は、本発明の実施形態に係る情報処理装置１００のハードウェア構成を説明するためのブロック図である。
【０２６８】
情報処理装置１００は、主に、ＣＰＵ９０１と、ＲＯＭ９０３と、ＲＡＭ９０５と、を備える。また、情報処理装置１００は、更に、ホストバス９０７と、ブリッジ９０９と、外部バス９１１と、インターフェース９１３と、入力装置９１５と、出力装置９１７と、ストレージ装置９１９と、ドライブ９２１と、接続ポート９２３と、通信装置９２５とを備える。
【０２６９】
ＣＰＵ９０１は、演算処理装置および制御装置として機能し、ＲＯＭ９０３、ＲＡＭ９０５、ストレージ装置９１９、またはリムーバブル記録媒体９２７に記録された各種プログラムに従って、情報処理装置１００内の動作全般またはその一部を制御する。ＲＯＭ９０３は、ＣＰＵ９０１が使用するプログラムや演算パラメータ等を記憶する。ＲＡＭ９０５は、ＣＰＵ９０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を一次記憶する。これらはＣＰＵバス等の内部バスにより構成されるホストバス９０７により相互に接続されている。
【０２７０】
ホストバス９０７は、ブリッジ９０９を介して、ＰＣＩ（Peripheral  Component  Interconnect/Interface）バスなどの外部バス９１１に接続されている。
【０２７１】
入力装置９１５は、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチおよびレバーなどユーザが操作する操作手段である。また、入力装置９１５は、例えば、赤外線やその他の電波を利用したリモートコントロール手段（いわゆる、リモコン）であってもよいし、情報処理装置１００の操作に対応した携帯電話やＰＤＡ等の外部接続機器９２９であってもよい。さらに、入力装置９１５は、例えば、上記の操作手段を用いてユーザにより入力された情報に基づいて入力信号を生成し、ＣＰＵ９０１に出力する入力制御回路などから構成されている。情報処理装置１００のユーザは、この入力装置９１５を操作することにより、情報処理装置１００に対して各種のデータを入力したり処理動作を指示したりすることができる。
【０２７２】
出力装置９１７は、取得した情報をユーザに対して視覚的または聴覚的に通知することが可能な装置で構成される。このような装置として、ＣＲＴディスプレイ装置、液晶ディスプレイ装置、プラズマディスプレイ装置、ＥＬディスプレイ装置およびランプなどの表示装置や、スピーカおよびヘッドホンなどの音声出力装置や、プリンタ装置、携帯電話、ファクシミリなどがある。出力装置９１７は、例えば、情報処理装置１００が行った各種処理により得られた結果を出力する。具体的には、表示装置は、情報処理装置１００が行った各種処理により得られた結果を、テキストまたはイメージで表示する。他方、音声出力装置は、再生された音声データや音響データ等からなるオーディオ信号をアナログ信号に変換して出力する。
【０２７３】
ストレージ装置９１９は、情報処理装置１００の記憶部の一例として構成されたデータ格納用の装置である。ストレージ装置９１９は、例えば、ＨＤＤ（Hard  Disk  Drive）等の磁気記憶部デバイス、半導体記憶デバイス、光記憶デバイス、または光磁気記憶デバイス等により構成される。このストレージ装置９１９は、ＣＰＵ９０１が実行するプログラムや各種データ、および外部から取得した各種のデータなどを格納する。
【０２７４】
ドライブ９２１は、記録媒体用リーダライタであり、情報処理装置１００に内蔵、あるいは外付けされる。ドライブ９２１は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体９２７に記録されている情報を読み出して、ＲＡＭ９０５に出力する。また、ドライブ９２１は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体９２７に記録を書き込むことも可能である。リムーバブル記録媒体９２７は、例えば、ＤＶＤメディア、ＨＤ−ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア等である。また、リムーバブル記録媒体９２７は、コンパクトフラッシュ（登録商標）（Compact  Flash：ＣＦ）、フラッシュメモリ、または、ＳＤメモリカード（Secure  Digital  memory  card）等であってもよい。また、リムーバブル記録媒体９２７は、例えば、非接触型ＩＣチップを搭載したＩＣカード（Integrated  Circuit  card）または電子機器等であってもよい。
【０２７５】
接続ポート９２３は、機器を情報処理装置１００に直接接続するためのポートである。接続ポート９２３の一例として、ＵＳＢ（Universal  Serial  Bus）ポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ（Small  Computer  System  Interface）ポート等がある。接続ポート９２３の別の例として、ＲＳ−２３２Ｃポート、光オーディオ端子、ＨＤＭＩ（High-Definition  Multimedia  Interface）ポート等がある。この接続ポート９２３に外部接続機器９２９を接続することで、情報処理装置１００は、外部接続機器９２９から直接各種のデータを取得したり、外部接続機器９２９に各種のデータを提供したりする。
【０２７６】
通信装置９２５は、例えば、通信網９３１に接続するための通信デバイス等で構成された通信インターフェースである。通信装置９２５は、例えば、有線または無線ＬＡＮ（Local  Area  Network）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、またはＷＵＳＢ（Wireless  USB）用の通信カード等である。また、通信装置９２５は、光通信用のルータ、ＡＤＳＬ（Asymmetric  Digital  Subscriber  Line）用のルータ、または、各種通信用のモデム等であってもよい。この通信装置９２５は、例えば、インターネットや他の通信機器との間で、例えばＴＣＰ／ＩＰ等の所定のプロトコルに則して信号等を送受信することができる。また、通信装置９２５に接続される通信網９３１は、有線または無線によって接続されたネットワーク等により構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、ラジオ波通信または衛星通信等であってもよい。
【０２７７】
以上、本発明の実施形態に係る情報処理装置１００の機能を実現可能なハードウェア構成の一例を示した。上記の各構成要素は、汎用的な部材を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用するハードウェア構成を変更することが可能である。
【０２７８】
＜４．まとめ＞
（実施形態の構成と効果の例）
以上説明した本発明の実施形態では、Ｄ次元の座標（Ｄ＝２，３，・・・）によって規定される特徴空間の位置情報を有するデータについて、所定の桁数のＮ進数（Ｎ＝２，３，・・・）で表現された各次元の座標の値を上記各次元について順に１桁ずつ配列したＮ進数値を生成するＮ進数値生成部と、上記Ｎ進数値の上位ｋ桁（ｋ＝１，２，・・・）が共通する上記データを同一のクラスタに分類するクラスタリング部とを備える情報処理装置が提供される。
【０２７９】
かかる構成によれば、位置情報を有するデータのクラスタリング処理を、各データに対応付けられたＮ進数値のソートの処理に置き換えることが可能になる。位置情報間の距離計算処理が数値の大小比較処理によって代替され、さらに処理回数自体も少なくて済むため、例えばクラスタリングに要するプロセッサや記憶領域のリソースがより少なくなり、クラスタリングの処理が高速化される。
【０２８０】
上記クラスタリング部は、ｋ＝Ｄ×ｍ（ｍ＝１，２，・・・）である場合に、上記Ｎ進数値の上位ｋ桁が共通する上記データを、ＮＤ分木構造クラスタのｍ層目で同一のクラスタに分類してもよい。
【０２８１】
かかる構成によれば、クラスタの階層構造が容易に構成できる。さらに、階層構造全体を保持しなくてもよいので、記憶領域のリソースを節約できる。
【０２８２】
上記クラスタリング部は、上記データを上記Ｎ進数値の順にソートするクラスタリング用ソート部を含み、上記ソートの結果から、上記同一のクラスタに分類される上記データを特定してもよい。
【０２８３】
かかる構成によれば、ソートの結果によって、同一のクラスタに分類されるデータを容易に特定することができる。
【０２８４】
上記クラスタリング部は、上記ソートの結果において、一のクラスタに分類された上記データが現れる最初の位置と、当該一のクラスタに分類された上記データの数とによって、当該一のクラスタを特定するクラスタ特定情報を生成してもよい。
【０２８５】
かかる構成によれば、クラスタ特定情報が、クラスタに分類されるデータを個々に特定する情報を必ずしも含まなくてもよくなるため、クラスタ特定情報の生成および記憶に要するリソースがより少なくなり、クラスタリングの処理が高速化される。
【０２８６】
上記情報処理装置は、上記Ｄ次元の座標に基づく第１の順位決定処理の結果に基づいて、上記特徴空間における第１の方向について上記クラスタをソートするマージ用ソート部と、上記第１の方向についてソートされたクラスタが、上記第１の方向で互いに隣接するか否かを判定する隣接判定部と、を含み、上記第１の方向について互いに隣接すると判定されたクラスタをマージするマージ部をさらに備えてもよい。
【０２８７】
かかる構成によれば、ソートの結果隣接すると判定されたクラスタを対象にしてマージが実行されるため、すべてのクラスタを対象としてマージを実行するのと比べて処理に要するリソースがより少なくなり、生成されたクラスタのマージの処理を含むクラスタリングの処理が高速化される。
【０２８８】
上記マージ用ソート部は、上記Ｄ次元の座標に基づく第２の順位決定処理の結果に基づいて、上記特徴空間における第２の方向について上記クラスタをソートし、上記隣接判定部は、上記第２の方向についてソートされたクラスタが、上記第２の方向で互いに隣接するか否かを判定し、上記マージ部は、さらに、上記第２の方向について互いに隣接すると判定されたクラスタをマージしてもよい。
【０２８９】
かかる構成によれば、特徴空間における２つの方向について、クラスタが隣接するか否かを判定するため、互いに近傍に位置するクラスタをより確実にマージすることができる。
【０２９０】
上記特徴空間は、地表面であり、上記Ｄ次元の座標は、緯度および経度からなる２次元の座標であり、上記クラスタは、上記２次元の座標によって上記地表面上に定義されるグリッドに含まれる上記データの位置情報を包含する領域であり、上記第１の順位決定処理は、上記第１の方向について上記グリッドをソートし、各グリッドに含まれるクラスタに当該グリッドのソート順を順位として与える処理であってもよい。
【０２９１】
かかる構成によれば、地表面における位置情報を有するデータを、緯度および経度によって定義されるグリッドを用いて高速にクラスタリングすることができる。また、このグリッドのソートによってクラスタに順位を与えることによって、クラスタのソートを高速化することができる。
【０２９２】
上記特徴空間は、３次元空間であり、上記Ｄ次元の座標は、直交座標系を構成する３次元の座標であり、上記クラスタは、上記３次元の座標によって上記３次元空間内に定義されるブロックに含まれる上記データの位置情報を包含する領域であってもよい。
【０２９３】
かかる構成によれば、３次元空間における位置情報を有するデータを、直交座標系によって定義されるブロックを用いて高速にクラスタリングすることができる。また、地表面をブロックによって分割する場合、地表面に緯度によるひずみが生じないクラスタによってデータをクラスタリングすることができる。
【０２９４】
また、本発明の実施形態において、クラスタをマージする処理は、上記クラスタの相互間の距離を算出する処理と、上記算出された距離が所定の閾値以下である場合に、上記クラスタをマージする処理とを含みうる。
【０２９５】
かかる構成によれば、マージ処理に要する処理をより少なくすることができ、生成されたクラスタのマージの処理を含むクラスタリングの処理がさらに高速化される。
【０２９６】
上記クラスタをマージする処理は、上記クラスタの相互間の距離を算出する処理と、上記算出された距離が所定の閾値以下である場合に、上記クラスタをマージ候補クラスタとして記憶する処理と、上記記憶されたマージ候補クラスタのうち、上記相互間の距離が小さいマージ候補クラスタから順にマージする処理とを含んでもよい。
【０２９７】
かかる構成によれば、より距離の近いクラスタを確実にマージすることができ、生成されたクラスタのマージの処理を含むクラスタリングの精度を向上させることができる。
【０２９８】
（実施形態の変形例）
ここで、第１の実施形態では、特徴空間は地表面であり、第２の実施形態では、特徴空間は地球を含む３次元空間である。しかし、本発明はかかる例に限定されない。例えば、特徴空間は、実空間ではなく、ＲＧＢ、ＹＵＶなどの色空間であってもよく、画像特徴量を表現するためのより高次の特徴量空間であってもよい。
【０２９９】
また、第１の実施形態では、Ｄ＝２、Ｎ＝２であり、第２の実施形態では、Ｄ＝３、Ｎ＝２である。しかし、本発明はかかる例に限定されない。例えば、Ｄ＝４以上であってもよい。つまり、データは４次元以上の高次元の座標によって規定される特徴空間の位置情報を有してもよい。一例として、Ｄ＝４で、各次元の座標を１６桁の２進数で表現する場合、Ｎ進数値生成部は、１６×４＝６４桁の２進数値を生成する。また、例えば、Ｎ進数値生成部は、８進数、１０進数、または１６進数など、任意の基数を用いて表されるＮ進数を生成してもよい。一例として、Ｄ＝２で、各次元の座標を２９桁の１６進数で表現する場合、Ｎ進数値生成部は、２９×２＝５８桁の１６進数値を生成し、データは１６２＝２５６分木構造クラスタに分類される。
【０３００】
また、第１の実施形態では、２次元の座標は緯度および経度であり、第２の実施形態では、３次元の座標はｘ座標、ｙ座標、およびｚ座標からなる直交座標系である。しかし、本発明はかかる例に限定されない。２次元、３次元、およびＤ次元の座標は、直交座標系であってもよく、斜交座標系であってもよく、極座標系であってもよい。
【０３０１】
以上、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明はかかる例に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０３０２】
１００    情報処理装置
１０１    Ｎ進数値生成部
１０３    クラスタリング部
１０５    マージ部
１０７    ソート部
１０９    隣接判定部
１１９    記憶部
１００１    地表面
１０１１，２０１１    コンテンツ
１０２１，２０２１    クラスタ
１０３１    グリッド
２００１    ３次元空間
２０３１    ブロック
【図１】
2012113625.tif 000007
【図２】
2012113625.tif 000008
【図３】
2012113625.tif 000009
【図４】
2012113625.tif 000010
【図５】
2012113625.tif 000011
【図６】
2012113625.tif 000012
【図７】
2012113625.tif 000013
【図８】
2012113625.tif 000014
【図９】
2012113625.tif 000015
【図１０】
2012113625.tif 000016
【図１１】
2012113625.tif 000017
【図１２】
2012113625.tif 000018
【図１３】
2012113625.tif 000019
【図１４】
2012113625.tif 000020
【図１５】
2012113625.tif 000021
【図１６】
2012113625.tif 000022
【図１７Ａ】
2012113625.tif 000023
【図１７Ｂ】
2012113625.tif 000024
【図１７Ｃ】
2012113625.tif 000025
【図１７Ｄ】
2012113625.tif 000026
【図１８Ａ】
2012113625.tif 000027
【図１８Ｂ】
2012113625.tif 000028
【図１８Ｃ】
2012113625.tif 000029
【図１９】
2012113625.tif 000030
【図２０】
2012113625.tif 000031
【図２１】
2012113625.tif 000032
【図２２】
2012113625.tif 000033
【図２３】
2012113625.tif 000034
【図２４】
2012113625.tif 000035
【図２５】
2012113625.tif 000036
【図２６】
2012113625.tif 000037
【図２７】
2012113625.tif 000038
【図２８】
2012113625.tif 000039
【図２９】
2012113625.tif 000040
【図３０Ａ】
2012113625.tif 000041
【図３０Ｂ】
2012113625.tif 000042
【図３１】
2012113625.tif 000043
【図３２】
2012113625.tif 000044
【図３３】
2012113625.tif 000045
【図３４】
2012113625.tif 000046
【図３５】
2012113625.tif 000047