(57)【要約】【課題】新たなクラスタリング技術を提供する。【解決手段】撮影日時順に一列に並べた写真データpic1,pic2,picnewの並びにおいて、注目している注目データpicnewが配置される位置を注目位置として、クラスタツリーのノードに対応するクラスタのうちの、注目データpicnewに隣接するクラスタC3の間近の写真データpic2と、注目データとの距離dnが、写真データの撮影日時や撮影位置に基づいて求められ、その距離dnに基づいて、注目データpicnewに割り当てられる注目ノードNnewを子ノードとする新たなノードN5が、クラスタツリーに追加される。【選択図】図９
2006344005.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータを、木構造のノードに割り当てて階層化することにより、前記複数のデータを、前記木構造のノードに対応するクラスタにクラスタリングする情報処理装置において、
前記データのメタデータを取得する取得手段と、
前記メタデータに基づいて一列に並べた前記複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、前記木構造のノードに対応するクラスタのうちの、前記注目位置に配置された前記注目データに隣接する隣接クラスタに属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離、および、前記注目データと、前記隣接クラスタに属するデータのうちの前記注目データに隣接するデータとの前記所定の距離尺度による第２の距離を、前記メタデータに基づいて求め、前記第１および第２の距離に基づいて、前記注目データに割り当てられる注目ノードを子ノードとする新たなノードを、前記木構造に追加する木構造処理手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記データは、撮影装置で撮影された画像データであり、
前記メタデータは、前記画像データが撮影された撮影日時と撮影位置とを含み、
前記注目位置は、前記撮影日時に基づいて並べた前記画像データの並びにおいて、前記注目データが配置される位置であり、
前記木構造処理手段は、前記撮影日時、または前記撮影位置に基づいて、前記第１および第２の距離を求める
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記木構造処理手段は、１の画像データが撮影されてから次の１の画像データが撮影されるまでの前記撮影装置の移動速度、前記撮影日時、または前記撮影位置に基づいて、前記第１および第２の距離を求める
ことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記木構造は、１つのノードに２つの子ノードが接続する２分木になっており、
前記木構造処理手段は、
前記注目位置に配置された前記注目データの一方に隣接する最大の前記隣接クラスタに対応するノード、または、前記注目データの他方に隣接する最大の前記隣接クラスタに対応するノードを子ノードとする分岐ノードを検索する分岐ノード検索手段と、
前記分岐ノードの子ノードに対応する前記隣接クラスタの中で、前記注目位置に配置された前記注目データとの前記所定の距離尺度による距離が最も近いデータが属する前記隣接クラスタに対応するノードを、前記注目データが属するクラスタに対応するノードの候補である候補ノードとして、前記候補ノードに対応するクラスタに属するデータのうちの隣接するデータどうしの前記所定の距離尺度による距離の最大値を、前記第１の距離として求めるとともに、前記候補ノードに対応するクラスタに属するデータのうちの前記注目データに隣接するデータと前記注目データとの前記所定の距離尺度による距離を、前記第２の距離として求める距離算出手段と、
前記第１と第２の距離の大小関係を判定する判定手段と、
前記判定手段による判定結果に基づいて、前記分岐ノードと前記候補ノードとの間に、前記分岐ノードを親ノードとするとともに前記候補ノードおよび前記注目ノードを子ノードとする前記新たなノードを追加する追加手段と
を有する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記判定手段において、前記第２の距離が、前記第１の距離よりも大きいと判定された場合、
前記追加手段は、前記分岐ノードを親ノードとするとともに前記候補ノードおよび前記注目ノードを子ノードとする前記新たなノードを追加し、
前記判定手段において、前記第２の距離が、前記第１の距離よりも大きくないと判定された場合、
前記候補ノードを新たな分岐ノードとし、かつ前記候補ノードの子ノードを新たな候補ノードとして、
前記距離算出手段が、前記新たな候補ノードに対応するクラスタに属するデータのうちの隣接するデータどうしの前記第１の距離、および、前記新たな候補ノードに対応するクラスタに属するデータのうちの前記注目データに隣接するデータと前記注目データとの前記第２の距離を求め、
前記判定手段が、前記第１と第２の距離の大小関係を判定する
ことを繰り返す
ことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記木構造処理手段は、前記隣接クラスタに対応するノードを、上位階層から下位階層に向かって辿ることにより、前記隣接クラスタに属するデータのうちの隣接するデータどうしの前記第１の距離が、前記隣接クラスタに属するデータのうちの前記注目データに隣接するデータと前記注目データとの前記第２の距離より短い最大のクラスタに対応するノードを検出し、そのノードと前記注目ノードを子ノードとする前記新たなノードを追加する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項７】
複数のデータを、木構造のノードに割り当てて階層化することにより、前記複数のデータを、前記木構造のノードに対応するクラスタにクラスタリングする情報処理方法において、
前記データのメタデータを取得する取得ステップと、
前記メタデータに基づいて一列に並べた前記複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、前記木構造のノードに対応するクラスタのうちの、前記注目位置に配置された前記注目データに隣接する隣接クラスタに属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離、および、前記注目データと、前記隣接クラスタに属するデータのうちの前記注目データに隣接するデータとの前記所定の距離尺度による第２の距離を、前記メタデータに基づいて求め、前記第１および第２の距離に基づいて、前記注目データに割り当てられる注目ノードを子ノードとする新たなノードを、前記木構造に追加する木構造処理ステップと
を含むことを特徴とする情報処理方法。
【請求項８】
複数のデータを、木構造のノードに割り当てて階層化することにより、前記複数のデータを、前記木構造のノードに対応するクラスタにクラスタリングする情報処理を、コンピュータに実行させるプログラムにおいて、
前記データのメタデータを取得する取得ステップと、
前記メタデータに基づいて一列に並べた前記複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、前記木構造のノードに対応するクラスタのうちの、前記注目位置に配置された前記注目データに隣接する隣接クラスタに属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離、および、前記注目データと、前記隣接クラスタに属するデータのうちの前記注目データに隣接するデータとの前記所定の距離尺度による第２の距離を、前記メタデータに基づいて求め、前記第１および第２の距離に基づいて、前記注目データに割り当てられる注目ノードを子ノードとする新たなノードを、前記木構造に追加する木構造処理ステップと
を含むことを特徴とする情報処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、およびプログラムに関し、特に、例えば、ディジタルカメラで撮影された画像データ等のデータをクラスタリングすることにより、所望のデータを容易に探し出すこと等ができるようにする情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
例えば、ディジタルカメラにおいては、撮影された写真としてのディジタル画像データ（以下、適宜、写真データという）を、その写真データの撮影が行われた撮影日時等のメタデータとともに記録するようになっている。
【０００３】
また、ディジタルカメラの普及に伴い、写真データを、コンピュータで管理するための種々の管理用アプリケーションも提供（販売）されている。管理用アプリケーションでは、例えば、写真データが、メタデータに基づき、撮影がされた年、月、日ごとに階層化されてクラスタリングされる。この場合、ユーザは、撮影がされた年、月、日の順に写真データを順次絞り込んで、目的の写真データを探し出すことができる。
【０００４】
さらに、例えば、特許文献１には、写真データを、撮影日時や撮影位置の差分に基づいてグループにクラスタリング（分類）して管理する画像撮影装置が開示されている。
【０００５】
【特許文献１】特開2001-228528号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、ユーザが目的の写真データを容易に探し出すことができるように、写真データをクラスタリングする新たなクラスタリング技術の提案が要請されている。
【０００７】
本発明は、このような状況に鑑みてなされたものであり、新たなクラスタリング技術によって、ユーザが、例えば、所望の写真データ等のデータを容易に探し出すこと等ができるようにするものである。
【課題を解決するための手段】
【０００８】
本発明は、メタデータに基づいて一列に並べた複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、木構造のノードに対応するクラスタのうちの、注目位置に配置された注目データに隣接する隣接クラスタに属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離、および、注目データと、隣接クラスタに属するデータのうちの注目データに隣接するデータとの所定の距離尺度による第２の距離を、メタデータに基づいて求め、第１および第２の距離に基づいて、注目データに割り当てられる注目ノードを子ノードとする新たなノードを、木構造に追加する木構造処理手段／ステップとを含むことを特徴とする。
【０００９】
本発明においては、メタデータに基づいて一列に並べた複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、木構造のノードに対応するクラスタのうちの、注目位置に配置された注目データに隣接する隣接クラスタに属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離、および、注目データと、隣接クラスタに属するデータのうちの注目データに隣接するデータとの所定の距離尺度による第２の距離が、メタデータに基づいて求められる。そして、第１および第２の距離に基づいて、注目データに割り当てられる注目ノードを子ノードとする新たなノードが、木構造に追加される。
【発明の効果】
【００１０】
本発明によれば、データを木構造によって階層的にクラスタリングすることができ、その結果、例えば、ユーザが所望のデータを容易に探し出すこと等が可能となる。
【発明を実施するための最良の形態】
【００１１】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、発明の詳細な説明に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、発明の詳細な説明に記載されていることを確認するためのものである。従って、発明の詳細な説明中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００１２】
請求項１に記載の情報処理装置は、
複数のデータ（例えば、図２の写真データpic1乃至pic7）を、木構造（例えば、図２のクラスタツリー）のノード（例えば、図２のノードN41やN51）に割り当てて階層化することにより、前記複数のデータを、前記木構造のノードに対応するクラスタ（例えば、図２のクラスタC11やC22）にクラスタリングする情報処理装置（例えば、図１の情報処理装置２）において、
前記データのメタデータを取得する取得手段（例えば、図１６のメタデータ読み出し部２０）と、
前記メタデータに基づいて一列に並べた前記複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、前記木構造のノードに対応するクラスタのうちの、前記注目位置に配置された前記注目データに隣接する隣接クラスタ（例えば、図２２のクラスタCl）に属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離（例えば、図２２の距離dq）、および、前記注目データと、前記隣接クラスタに属するデータのうちの前記注目データに隣接するデータとの前記所定の距離尺度による第２の距離（例えば、図２２の距離dn）を、前記メタデータに基づいて求め、前記第１および第２の距離に基づいて、前記注目データに割り当てられる注目ノード（例えば、図２１のノードNnew）を子ノードとする新たなノード（例えば、図２２の新たなノードNin）を、前記木構造に追加する木構造処理手段（例えば、図１６の木構造処理部２２）と
を備えることを特徴とする。
【００１３】
請求項４に記載の情報処理装置は、
前記木構造は、１つのノードに２つの子ノードが接続する２分木になっており、
前記木構造処理手段は、
前記注目位置に配置された前記注目データの一方に隣接する最大の前記隣接クラスタ（例えば、図２１のクラスタCl）に対応するノード（例えば、図２１の左ノードl(Np)）、または、前記注目データの他方に隣接する最大の隣接クラスタ（例えば、図２１のクラスタCr）に対応するノード（例えば、図２１の右ノードr(Np)）を子ノードとする分岐ノード（例えば、図２１の分岐ノードNp）を検索する分岐ノード検索手段（例えば、図１９の分岐ノード検索部３１）と、
前記分岐ノードの子ノードに対応する前記隣接クラスタの中で、前記注目位置に配置された前記注目データとの前記所定の距離尺度による距離が最も近いデータが属する前記隣接クラスタ（例えば、図２２のクラスタCq）に対応するノード（例えば、図２２の候補ノードNq）を、前記注目データが属するクラスタに対応するノードの候補である候補ノードとして、前記候補ノードに対応するクラスタに属するデータのうちの隣接するデータどうしの前記所定の距離尺度による距離の最大値（例えば、図２２の距離dq）を、前記第１の距離として求めるとともに、前記候補ノードに対応するクラスタに属するデータのうちの前記注目データに隣接するデータと前記注目データとの前記所定の距離尺度による距離（例えば、図２２の距離dn）を、前記第２の距離として求める距離算出手段（例えば、図１９の距離算出部４１）と、
前記第１と第２の距離の大小関係を判定する判定手段（例えば、図１９の判定部４２）と、
前記判定手段による判定結果に基づいて、前記分岐ノード（例えば、図２２の分岐ノードNp）と前記候補ノード（例えば、図２２の候補ノードNq）との間に、前記分岐ノードを親ノードとするとともに前記候補ノードおよび前記注目ノードを子ノードとする前記新たなノード（例えば、図２２の新たなノードNin）を追加する追加手段（例えば、図１９の追加部４３）と
を有する
ことを特徴とする。
【００１４】
請求項５に記載の情報処理装置は、
前記判定手段において、前記第２の距離（例えば、図２２の距離dn）が、前記第１の距離（例えば、図２２の距離dq）よりも大きいと判定された場合（例えば、図２２の場合）、
前記追加手段は、前記分岐ノードを親ノードとするとともに前記候補ノードおよび前記注目ノードを子ノードとする前記新たなノード（例えば、図２２の新たなノードNin）を追加し、
前記判定手段において、前記第２の距離（例えば、図２３の距離dn）が、前記第１の距離（例えば、図２３の距離dq）よりも大きくないと判定された場合（例えば、図２３の場合）、
前記候補ノードを新たな分岐ノードとし、かつ前記候補ノードの子ノードを新たな候補ノードとして、
前記距離算出手段が、前記新たな候補ノードに対応するクラスタに属するデータのうちの隣接するデータどうしの前記第１の距離、および、前記新たな候補ノードに対応するクラスタに属するデータのうちの前記注目データに隣接するデータと前記注目データとの前記第２の距離を求め、
前記判定手段が、前記第１と第２の距離の大小関係を判定する
ことを繰り返す
ことを特徴とする。
【００１５】
請求項７に記載の情報処理方法、または請求項８に記載のプログラムは、
複数のデータ（例えば、図２の写真データpic1乃至pic7）を、木構造（例えば、図２のクラスタツリー）のノード（例えば、図２のノードN41やN51）に割り当てて階層化することにより、前記複数のデータを、前記木構造のノードに対応するクラスタ（例えば、図２のクラスタC11やC22）にクラスタリングする情報処理方法、または情報処理をコンピュータに実行させるプログラムにおいて、
前記データのメタデータを取得する取得ステップ（例えば、図１８のステップＳ１１）と、
前記メタデータに基づいて一列に並べた前記複数のデータの並びにおいて、注目している注目データが配置される位置を注目位置として、前記木構造のノードに対応するクラスタのうちの、前記注目位置に配置された前記注目データに隣接する隣接クラスタ（例えば、図２２のクラスタCl）に属するデータのうちの隣接するデータどうしの所定の距離尺度による第１の距離（例えば、図２２の距離dq）、および、前記注目データと、前記隣接クラスタに属するデータのうちの前記注目データに隣接するデータとの前記所定の距離尺度による第２の距離（例えば、図２２の距離dn）を、前記メタデータに基づいて求め、前記第１および第２の距離に基づいて、前記注目データに割り当てられる注目ノード（例えば、図２１のノードNnew）を子ノードとする新たなノード（例えば、図２２の新たなノードNin）を、前記木構造に追加する木構造処理ステップ（例えば、図１８のステップＳ１２）と
を含むことを特徴とする。
【００１６】
以下、図面を参照して、本発明の実施の形態について説明する。
【００１７】
図１は、本発明を適用した情報処理システム（システムとは、複数の装置が論理的に集合した物をいい、各構成の装置が同一筐体中にあるか否かは問わない）の一実施の形態の構成例を示している。
【００１８】
情報処理システムは、カメラ（ディジタル（スチル）カメラ）１と情報処理装置２とから構成されている。
【００１９】
カメラ１は、ユーザの操作に応じて撮影を行い、その撮影の結果得られる写真データを記憶する。また、カメラ１は、写真データのメタデータとして、その写真データの撮影が行われた撮影日時（例えば、年、月、日、時、分、秒を含む）や撮影位置などを含むメタデータも記憶する。さらに、カメラ１は、記憶した写真データとメタデータを、外部に出力（送信）することができるようになっている。
【００２０】
ここで、カメラ１は、例えば、日時を計時する時計を内蔵し、その時計によって計時されている日時に基づき、写真データのメタデータの１つである撮影日時を取得する。また、カメラ１は、例えば、GPS(Global Positioning System)用の衛星からの信号を受信する受信部を内蔵し、その受信部によって受信された信号に基づき、写真データのメタデータの他の１つである撮影位置を取得する。
【００２１】
情報処理装置２は、入力インタフェース１１、データ記憶装置１２、クラスタリング装置１３、クラスタツリー記憶装置１４、表示制御装置１５、表示装置１６、および操作部１７で構成されており、カメラ１を（電気的に）接続することができるようになっている。
【００２２】
入力インタフェース１１は、カメラ１との間で通信をするためのインタフェースとして機能する。即ち、入力インタフェース１１は、カメラ１と情報処理装置２とが、例えば、ケーブルを介して接続されると、カメラ１から、写真データとメタデータを読み出し（取り込み）、データ記憶装置１２に供給する。
【００２３】
データ記憶装置１２は、例えば、ハードディスクや半導体メモリなどで構成され、入力インタフェース１１から供給される写真データとメタデータを記憶する。
【００２４】
クラスタリング装置１３は、データ記憶装置１２に記憶された写真データを、同じくデータ記憶装置１２に記憶されたメタデータに基づき、木構造の後述するクラスタツリーを構成するノードに割り当てて階層化することにより、写真データを、クラスタツリーのノードに対応するクラスタにクラスタリングする。そして、クラスタリング装置１３は、写真データのクラスタリングの結果、即ち、クラスタツリー（の情報）を、クラスタツリー記憶装置１４に供給する。
【００２５】
クラスタツリー記憶装置１４は、クラスタリング装置１３から供給されるクラスタツリーを記憶する。
【００２６】
表示制御装置１５は、クラスタツリー記憶装置１４に記憶されたクラスタツリーに基づき、データ記憶装置１２に記憶された写真データが、いわば階層的に表示されるように、表示装置１６を制御する。
【００２７】
表示装置１６は、例えば、CRT(Cathode Ray Tube)やLCD(Liquid Crystal Display)などであり、表示制御装置１５の制御にしたがって、写真データ等を表示する。
【００２８】
操作部１７は、ユーザによって操作され、その操作に対応する操作信号を、必要なブロックに供給する。例えば、入力インタフェース１１は、操作部１７からの操作信号に応じて、カメラ１からの写真データとメタデータの取り込みを開始する。また、例えば、クラスタリング装置１３は、操作部１７からの操作信号に応じて、データ記憶装置１２に記憶された写真データのクラスタリングを行う。さらに、例えば、表示制御装置１５は、操作部１７からの操作信号に応じて、表示装置１６による写真データの表示を制御する。
【００２９】
以上のように構成される情報処理システムでは、カメラ１と情報処理装置２とが接続され、ユーザが、写真データの取り込みを行うように、操作部１７を操作すると、入力インタフェース１１は、カメラ１から、写真データとメタデータを読み出し、データ記憶装置１２に供給して記憶させる。
【００３０】
クラスタリング装置１３は、データ記憶装置１２に記憶された写真データを、同じくデータ記憶装置１２に記憶されたメタデータに基づき、クラスタツリーを構成するノードに割り当てて階層化することにより、写真データを、クラスタツリーのノードに対応するクラスタにクラスタリングし、そのクラスタリングの結果としてのクラスタツリー（の情報）を、クラスタツリー記憶装置１４に供給して記憶させる。
【００３１】
ここで、クラスタリング装置１３が行うクラスタリングによれば、木構造（階層構造）のクラスタツリーが得られるが、このような木構造のクラスタツリーによる階層的なクラスタリングを、以下、適宜、階層的クラスタリングという。
【００３２】
一方、ユーザが、写真データの表示を行うように、操作部１７を操作すると、表示制御装置１５は、クラスタツリー記憶装置１４に記憶されたクラスタツリーに基づき、データ記憶装置１２に記憶された写真データを、表示装置１６に、階層的に表示させる。
【００３３】
次に、図２は、図１のクラスタリング装置１３が写真データの階層的クラスタリングを行うことにより得られるクラスタツリーの例を示している。
【００３４】
クラスタツリーは、写真データを階層的にクラスタリングする木構造のデータ（情報）であり、クラスタに対応するノードと、ノードどうしを接続するアークとから構成される。
【００３５】
ここで、図２において（クラスタツリーを図示した他の図においても同様）、○印がノードを表し、○印どうしを結ぶ線分がアークを表している。
【００３６】
ノードには、アークによって他のノードを接続することができる。あるノードに接続された、そのノードの階層の１階層だけ下位の階層のノードは、子ノードと呼ばれ、子ノードとアークによって接続された、その子ノードの階層の１階層だけ上位の階層のノードは、親ノードと呼ばれる。
【００３７】
クラスタツリーでは、１つのノードは、２つの子ノードを有することができ（親ノードに、２つの子ノードを接続することができ）、従って、クラスタツリーは、２分木になっている。
【００３８】
そして、クラスタツリーでは、親ノードに接続されていないノード（親ノードが存在しないノード）は、ルートノードと呼ばれ、子ノードが接続されていないノード（子ノードを有しないノード）は、リーフノードと呼ばれる。リーフノードには、写真データが割り当てられる。そして、写真データが割り当てられているリーフノード（としての変数）は、その写真データのメタデータを保持する。
【００３９】
ここで、以下、適宜、クラスタツリーにおいて、ルートノードの階層を、最上位の階層として、第１階層といい、ルートノードの子ノード（ルートノードから辿って１番目のノード）の階層を、第２階層といい、以下、ルートノードから辿ってk番目のノードの階層を、第k+1階層という。
【００４０】
図２のクラスタツリーでは、第１階層のノードであるルートノードN11が、２つの子ノードとして、第２階層のノードN21とN22を有している。ノードN21は、２つの子ノードとして、第３階層のノードN31とN32を有しており、ノードN31は、２つの子ノードとして、第４階層のノードN41とN42を有している。そして、ノードN42は、２つの子ノードとして、第５階層のノードN51とN52を有している。
【００４１】
また、第２階層のノードN22は、２つの子ノードとして、第３階層のノードN33とN34を有しており、ノードN33は、２つの子ノードとして、第４階層のノードN43とN44を有している。
【００４２】
さらに、図２のクラスタツリーでは、第４階層のノードN41、第５階層のノードN51およびN52、第３階層のノードＮ32、第４階層ノードN43およびN44、並びに第３階層のノードN34が、リーフノードとなっている。そして、リーフノードN41，N51，N52，Ｎ32、N43，N44，N34には、写真データpic1，pic2，pic3，pic4，pic5，pic6，pic7が、それぞれ割り当てられている。
【００４３】
ここで、図２において（写真データを図示した他の図においても同様）、□印が写真データを表す。
【００４４】
クラスタツリーのノードは、上述したように、クラスタに対応しており、あるクラスタには、そのクラスタに対応するノードに辿り着くリーフノードに割り当てられている写真データが属する。従って、クラスタツリーの上位階層では、その上位階層のノードに対応するクラスタによって、リーフノードに割り当てられた写真データが、大きな粒度でクラスタリングされる。一方、下位階層では、その下位階層のノードに対応するクラスタによって、リーフノードに割り当てられた写真データが、小さな粒度でクラスタリングされる。
【００４５】
即ち、例えば、図２のクラスタツリーにおいて、第１階層には、ノード（ルートノード）N11のみが存在し、ルートノードN11には、リーフノードN41，N51，N52，Ｎ32、N43，N44，N34のすべてが辿り着く。従って、第１階層では、リーフノードN41，N51，N52，Ｎ32、N43，N44，N34に割り当てられている写真データ、つまり、すべての写真データpic1乃至pic7が、ルートノードN11に対応するクラスタC11にクラスタリングされる。
【００４６】
また、例えば、第２階層には、ノードN21とN22が存在し、ノードN21には、リーフノードN41，N51，N52，Ｎ32が辿り着き、ノードN22には、リーフノードN43，N44，N34が辿り着く。従って、第２階層では、リーフノードN41，N51，N52，Ｎ32にそれぞれ割り当てられている写真データpic1，pic2，pic3，pic4が、ノードN21に対応するクラスタC21にクラスタリングされるとともに、リーフノードN43，N44，N34にそれぞれ割り当てられている写真データpic5，pic6，pic7が、ノードN22に対応するクラスタC22にクラスタリングされる。
【００４７】
ここで、図３に、図２のクラスタツリーによる写真データpic1乃至pic7のクラスタリング結果を示す。
【００４８】
図３の上から１番目は、第１階層でのクラスタリング結果を、図３の上から２番目は、第２階層でのクラスタリング結果を、それぞれ示している。
【００４９】
上述したように、第１階層では、すべての写真データpic1乃至pic7が、ルートノードN11に対応するクラスタC11にクラスタリングされ（図３上から１番目）、第２階層では、写真データpic1乃至pic4が、ノードN21に対応するクラスタC21にクラスタリングされるとともに、写真データpic5乃至pic7が、ノードN22に対応するクラスタC22にクラスタリングされる（図３上から２番目）。
【００５０】
また、第３階層では、図３上から３番目に示すように、第３階層のノードN31，N32，N33，N34のうちのノードN31に辿り着くリーフノードN41，N51，N52にそれぞれ割り当てられている写真データpic1，pic2，pic3が、ノードN31に対応するクラスタC31にクラスタリングされる。さらに、ノードN32に辿り着くリーフノード、つまり、ノードN32自身に割り当てられている写真データpic4が、ノードN32に対応するクラスタC32にクラスタリングされる。また、ノードN33に辿り着くリーフノードN43，N44にそれぞれ割り当てられている写真データpic5，pic6が、ノードN33に対応するクラスタC33にクラスタリングされ、ノードN34に辿り着くリーフノード、つまり、ノードN34自身に割り当てられている写真データpic7が、ノードN34に対応するクラスタC34にクラスタリングされている。
【００５１】
さらに、第４階層では、図３上から４番目に示すように、第４階層のノードN41，N42，N43，N44のうちのノードN41に辿り着くリーフノード、つまり、ノードN41自身に割り当てられている写真データpic1が、ノードN41に対応するクラスタC41にクラスタリングされ、ノードN42に辿り着くリーフノードN51，N52にそれぞれ割り当てられている写真データpic2，pic3が、ノードN42に対応するクラスタC42にクラスタリングされている。また、ノードN43に辿り着くリーフノードであるノードN43自身に割り当てられている写真データpic5が、ノードN43に対応するクラスタC43にクラスタリングされ、ノードN44に辿り着くリーフノードであるノードN44自身に割り当てられている写真データpic6が、ノードN44に対応するクラスタC44にクラスタリングされている。
【００５２】
なお、リーフノードに対応するクラスタは、そのリーフノードの階層から下位の階層に、いわば受け継がれることとする。従って、図１において、第３階層のリーフノードN32に対応するクラスタC32と、リーフノードN34に対応するクラスタC34とは、第４階層に受け継がれ、その結果、第４階層では、リーフノードN32自身に割り当てられている写真データpic4が、リーフノードN32に対応するクラスタC32にクラスタリングされ、リーフノードN34に割り当てられている写真データpic7が、リーフノードN34に対応するクラスタC34にクラスタリングされる。
【００５３】
同様にして、第５階層では、図３上から５番目（１番下）に示すように、リーフノードN41に割り当てられている写真データpic1が、リーフノードN41に対応するクラスタC41に、リーフノードN51に割り当てられている写真データpic2が、リーフノードN51に対応するクラスタC51に、リーフノードN52に割り当てられている写真データpic3が、リーフノードN52に対応するクラスタC52に、リーフノードN32に割り当てられている写真データpic4が、リーフノードN32に対応するクラスタC32に、リーフノードN43に割り当てられている写真データpic5が、リーフノードN43に対応するクラスタC43に、リーフノードN44に割り当てられている写真データpic6が、リーフノードN44に対応するクラスタC44に、リーフノードN34に割り当てられている写真データpic7が、リーフノードN34に対応するクラスタC34に、それぞれクラスタリングされている。
【００５４】
ここで、以上のようなクラスタツリーによるクラスタリング結果によれば、あるノードに対応するクラスタは、そのノードに辿り着く下位階層のノードに対応するクラスタを包含する。即ち、例えば、リーフノードでないノードに対応するクラスタは、そのノードの２つの子ノードそれぞれに対応するクラスタを包含する。従って、クラスタには、大小関係があるということができ、クラスタツリーによるクラスタリング結果において、最大のクラスタは、最も上位の階層（第１階層）のノードに対応するクラスタ、つまり、ルートノードに対応するクラスタとなる。
【００５５】
次に、図４乃至図６を参照して、図１のクラスタリング装置１３が行う階層的クラスタリングの概要について説明する。
【００５６】
一般に、カメラ１で撮影された写真データは、その写真データの撮影日時順（撮影日時の早い順）に整理されることが多い。写真データが撮影日時順に並んでいれば、ユーザは、いわば歴史を追うような間隔で、目的の写真データを探すことができるからである。
【００５７】
そこで、階層的クラスタリングでは、例えば、撮影日時順に一列に並べた複数の写真データの並びが変化しないように、写真データがクラスタリングされる。
【００５８】
即ち、例えば、図４に示すように、左から右に並べた写真データpic1乃至pic7の並びが、撮影日時順（撮影日時の早い順）であるとすると、階層的クラスタリングでは、写真データpic1乃至pic7の並びを維持したまま、写真データpic1乃至pic7をクラスタリングするクラスタツリーが生成される。つまり、階層的クラスタリングでは、写真データpic1乃至pic7の撮影日時の順序関係が逆転するクラスタ（に対応するノードを有するクラスタツリー）は生成されない。
【００５９】
従って、例えば、複数の写真データを、左から右方向に撮影日時順に並べ、その写真データの並びを対象に階層的クラスタリングを行って、クラスタツリーを生成した場合、そのクラスタツリーについては、次式が成り立つ。
【００６０】
t(Nl)<t(Nr)
・・・（１）
【００６１】
ここで、t(N)は、ノード（リーフノード）Nに割り当てられた写真データの撮影日時を表す。また、式（１）において、NlとNrは、いずれも、クラスタツリーのリーフノードを表す。但し、リーフノードNlは、リーフノードNrよりも左側にあるリーフノード（リーフノードNrは、リーフノードNlよりも右側にあるリーフノード）である。
【００６２】
次に、写真データの撮影は、ある場所や、時間に集中して行われることが多い。そして、時間的、または場所的に近い写真データ、つまり、撮影位置が近い写真データや、撮影日時が近い写真データは、同一のクラスタにまとめておく方が、目的の写真を探しやすい。
【００６３】
即ち、図５は、カメラ１で撮影が行われた撮影位置を模式的に示している。
【００６４】
図５では、ユーザは、自宅において、３枚の写真データpic1,pic2,pic3をカメラ１で撮影し、その後、アミューズメントパークに移動して、３枚の写真データpic4,pic5,pic6をカメラ１で撮影している。さらに、ユーザは、アミューズメントパークからレストランに移動し、そのレストランで、４枚の写真データpic7,pic8,pic9,pic10をカメラ１で撮影し、その後、ホテルに移動して、２枚の写真データpic11,pic12を撮影している。
【００６５】
以上のような１２枚の写真データpic1乃至pic12が撮影された場合、これらの写真データpic1乃至pic12は、イベントごとにまとめておく方が、目的の写真を探しやすい。
【００６６】
具体的には、例えば、撮影位置が近い写真データどうし、つまり、自宅で撮影された３枚の写真データpic1乃至pic3、アミューズメントパークで撮影された３枚の写真データpic4乃至pic6、レストランで撮影された４枚の写真データpic7乃至pic10、ホテルで撮影された２枚の写真データpic11およびpic12は、それぞれ、同一のクラスタにまとめておく方が、目的の写真を探しやすい。
【００６７】
また、例えば、撮影日時が近い写真データどうし、即ち、例えば、自宅で撮影された３枚の写真データpic1乃至pic3と、アミューズメントパークで撮影された３枚の写真データpic4乃至pic6とが、同日に撮影され、レストランで撮影された４枚の写真データpic7乃至pic10や、ホテルで撮影された２枚の写真データpic11およびpic12が、別の日に撮影された場合には、同日に撮影された自宅における３枚の写真データpic1乃至pic3と、アミューズメントパークにおける３枚の写真データpic4乃至pic6とは、同一のクラスタにまとめておく方が、目的の写真を探しやすい。
【００６８】
さらに、例えば、自宅で撮影された３枚の写真データpic1乃至pic3のうちの、写真データpic1とpic2との撮影日時や撮影位置が近く、写真データpic3と、写真データpic1およびpic2との撮影日時や撮影位置が離れている場合には、写真データpic1乃至pic3を同一のクラスタにまとめた上で、さらに、撮影日時や撮影位置が近い写真データpic1とpic2とをまとめておく方が、目的の写真を探しやすい。
【００６９】
そこで、階層的クラスタリングでは、写真データの、例えば、時間的、空間的な近さ（遠さ）を表す距離尺度による距離（写真データの時間的、空間的な非類似性を表す非類似度）に基づき、その距離が相対的に近い写真データどうしが同一のクラスタにクラスタリングされる。
【００７０】
即ち、階層的クラスタリングでは、例えば、距離が離れていても、２枚の写真データpic1とpic2しかなければ、写真データpic1とpic2は、同一のクラスタにクラスタリングされる。そして、写真データpic1とpic2に加えて、さらに距離が離れている写真データpic3が追加された場合、写真データpic1とpic2のクラスタはそのままで、写真データpic1とpic2、および写真データpic3が、粒度の大きいクラスタにクラスタリングされる。
【００７１】
ここで、クラスタの粒度とは、所定の距離尺度が定義される写真データの空間におけるクラスタの大きさであり、例えば、クラスタの最も離れた点どうしの距離に対応する。
【００７２】
一方、写真データpic1とpic2に加えて、写真データpic2との距離が写真データpic1よりも近い写真データpic3が追加された場合、距離が相対的に近い写真データpic2とpic3が、同一のクラスタにクラスタリングされる。そして、その写真データpic2とpic3のクラスタはそのままで、写真データpic1、および写真データpic2とpic3が、粒度の大きいクラスタにクラスタリングされる。
【００７３】
以上のように、階層的クラスタリングでは、撮影日時順に並べた写真データの並びを維持しつつ、距離が相対的に近い写真データどうしを、粒度の小さいクラスタにクラスタリングし、距離が相対的に遠い写真データどうしを、粒度の大きいクラスタにクラスタリングする。
【００７４】
階層的クラスタリングでは、撮影日時順に一列に並べた写真データの並びを維持しつつ、距離が相対的に近い写真データを、同一のクラスタにクラスタリングするために、撮影日時順に一列に並べた写真データの隣接する写真データどうしの距離を問題とし、その距離がより近い隣接する写真データどうしを、より粒度の小さいクラスタにクラスタリングする。
【００７５】
その結果、階層的クラスタリングによれば、例えば、図５で説明したように撮影された１２枚の写真データpic1乃至pic12は、例えば、図６に示すようにクラスタリングされる。
【００７６】
即ち、図６において、１２枚の写真データpic1乃至pic12は、撮影日時順に（左から右に）並んでおり、さらに、粒度が最も大きいクラスタであるルートノードN11に対応するクラスタにクラスタリングされている。
【００７７】
また、ルートノードN11に対応するクラスタにクラスタリングされている１２枚の写真データpic1乃至pic12の中で、隣接する写真データpic10とpic11との距離は、他の任意の隣接する写真データどうしの距離よりも遠くなっている。即ち、１２枚の写真データpic1乃至pic12の中で、写真データpic10を含む左側の写真データ（撮影日時が早い写真データ）pic1乃至pic10の並びの任意の隣接する写真データどうしの距離は、写真データpic10とpic11との距離よりも近く、かつ、写真データpic11を含む右側の写真データ（撮影日時が遅い写真データ）pic11とpic12の並びの隣接する写真データpic11とpic12との距離は、写真データpic10とpic11との距離よりも近くなっている。
【００７８】
このため、撮影日時順に並んだ１２枚の写真データpic1乃至pic12の中で、隣接する写真データどうしの距離が相対的に近いpic1乃至pic10が、ルートノードN11に対応するクラスタよりも粒度が小さい、ルートノードN11の一方の子ノードN21に対応するクラスタにクラスタリングされている。同様に、１２枚の写真データpic1乃至pic12の中で、隣接する写真データどうしの距離が相対的に近い写真データpic11およびpic12が、ルートノードN11に対応するクラスタよりも粒度が小さい、ルートノードN11の他方の子ノードN22に対応するクラスタにクラスタリングされている。
【００７９】
そして、ノードN22に対応するクラスタにクラスタリングされている写真データpic11とpic12のうちの写真データpic11は、ノードN22の一方の子ノード（リーフノード）N33に対応するクラスタにクラスタリングされ、写真データpic12は、ノードN22の他方の子ノード（リーフノード）N34に対応するクラスタにクラスタリングされている。
【００８０】
一方、ノードN21に対応するクラスタにクラスタリングされている写真データpic1乃至pic10の中で、写真データpic6を含む左側の写真データpic1乃至pic6の並びの任意の隣接する写真データどうしの距離は、写真データpic6とpic7との距離よりも近く、かつ、写真データpic7を含む右側の写真データ（撮影日時が遅い写真データ）pic7乃至pic10の並びの任意の隣接する写真データどうしの距離は、隣接する写真データpic6とpic7との距離よりも近くなっている。
【００８１】
このため、写真データpic1乃至pic10の中で、隣接する写真データどうしの距離が相対的に近い写真データpic1乃至pic6が、ノードN21に対応するクラスタよりも粒度が小さい、ノードN21の一方の子ノードN31に対応するクラスタにクラスタリングされている。同様に、写真データpic1乃至pic10の中で、隣接する写真データどうしの距離が相対的に近い写真データpic7乃至pic10が、ノードN21に対応するクラスタよりも粒度が小さい、ノードN21の他方の子ノードN32に対応するクラスタにクラスタリングされている。
【００８２】
以下、同様にして、図６では、写真データpic1乃至pic3が、ノードN41に対応するより粒度の小さいクラスタに、写真データpic4乃至pic6が、ノードN42に対応するより粒度の小さいクラスタに、写真データpic7乃至pic9が、ノードN43に対応するより粒度の小さいクラスタに、写真データpic10が、ノード（リーフノード）N44に対応するより粒度の小さいクラスタに、それぞれクラスタリングされている。
【００８３】
さらに、写真データpic1およびpic2が、ノードN51に対応するより粒度の小さいクラスタに、写真データpic3が、ノード（リーフノード）N52に対応するより粒度の小さいクラスタに、写真データpic４およびpic５が、ノードN53に対応するより粒度の小さいクラスタに、写真データpic6が、ノード（リーフノード）N54に対応するより粒度の小さいクラスタに、写真データpic7が、ノード（リーフノード）N55に対応するより粒度の小さいクラスタに、写真データpic8およびpic9が、ノードN56に対応するより粒度の小さいクラスタに、それぞれクラスタリングされている。
【００８４】
そして、写真データpic1は、ノード（リーフノード）N61に対応するより粒度の小さいクラスタに、写真データpic2は、ノード（リーフノード）N62に対応するより粒度の小さいクラスタに、写真データpic4は、ノード（リーフノード）N63に対応するより粒度の小さいクラスタに、写真データpic5は、ノード（リーフノード）N64に対応するより粒度の小さいクラスタに、写真データpic8は、ノード（リーフノード）N65に対応するより粒度の小さいクラスタに、写真データpic9は、ノード（リーフノード）N66に対応するより粒度の小さいクラスタに、それぞれクラスタリングされている。
【００８５】
従って、図６では、例えば、自宅で撮影された３枚の写真データpic1乃至pic3は、ノードN41に対応するクラスタに、アミューズメントパークで撮影された３枚の写真データpic4乃至pic6は、ノードN42に対応するクラスタに、レストランで撮影された４枚の写真データpic7乃至pic10は、ノードN32に対応するクラスタに、ホテルで撮影された２枚の写真データpic11およびpic12は、ノードN22に対応するクラスタに、それぞれクラスタリングされている。
【００８６】
また、例えば、ノードN32に対応するクラスタにクラスタリングされている、レストランで撮影された４枚の写真データpic7乃至pic10のうちの、隣接する写真データどうしの距離が近い３枚の写真データpic7乃至pic9は、ノードN32の子ノードであるノードN43に対応するクラスタにクラスタリングされている。さらに、例えば、ノードN43に対応するクラスタにクラスタリングされている３枚の写真データpic7乃至pic9のうちの、隣接する写真データどうしの距離が近い２枚の写真データpic8およびpic9は、ノードN43の子ノードであるノードN56に対応するクラスタにクラスタリングされている。
【００８７】
ここで、写真データpic#iとpic#jとの時間的、空間的な近さを表す距離尺度としては、例えば、式（２）や式（３）によって距離dpic(i,j)が定義される距離尺度を採用することができる。
【００８８】
dpic(i,j)=α|t(i)-t(j)| + β(|px(i)-px(j)|+|py(i)-py(j)|)+γ|v(i,j)|
・・・（２）
【００８９】
dpic(i,j)=√(α(t(i)-t(j))2 + β((px(i)-px(j))2+(py(i)-py(j))2)+γ(v(i,j))2)
・・・（３）
【００９０】
式（２）および式（３）において、t(i)は、写真データpic#iの撮影日時を表す。また、px(i)とpy(i)は、それぞれ、写真データ#iの撮影位置のx座標とy座標を表す。さらに、v(i,j)は、写真データpic#iが撮影されてから写真データpic#jが撮影されるまでのカメラ１の移動速度を表し、式（４）で求められる。
【００９１】
v(i,j) = √((px(i)-px(j))2 + (py(i)-py(j))2)/(t(j)-t(i))
・・・（４）
【００９２】
なお、式（２）と式（３）において、α，β，γは重み係数であり、適当な値にセットされる。
【００９３】
また、式（２）または式（３）における重み係数α，β，γについては、それらのうちの２以下を0とすることができる。例えば、重み係数αを0とした場合、距離dpic(i,j)としては、写真データpic#iが撮影されてから写真データpic#jが撮影されるまでの時間（時間的な距離）(|t(i)-t(j)|)を加味しない値が求められる。同様に、重み係数βを0とした場合、距離dpic(i,j)としては、写真データpic#iの撮影位置から写真データpic#jの撮影位置までの空間的な距離(√(px(i)-px(j))2+(py(i)-py(j))2))を加味しない値が求められる。さらに、重み係数γを0とした場合、距離dpic(i,j)としては、写真データpic#iが撮影されてから写真データpic#jが撮影されるまでのカメラ１の移動速度(v(i,j))を加味しない値が求められる。
【００９４】
さらに、階層的クラスタリングの結果得られるクラスタツリーのノードに対応するクラスタについて、あるノードNiに対応するクラスタCiと、ノードNiに包含されない他のノード（ノードを、上位階層の方向に辿っていったときにノードNiに辿り着かないノード）Njに対応するクラスタCjとの距離dC(Ni,Nj)を、例えば、式（５）により定義する。
【００９５】
dC(Ni,Nj)= dpic(g,h)
・・・（５）
【００９６】
但し、式（５）において、gとhは、式（６）を満たす写真データを表す。
【００９７】
(g,h)=argmin|t(g)-t(h)|,(g∈Ni,h∈Nj)
・・・（６）
【００９８】
式（６）において、t(g)とt(h)は、それぞれ、写真データpic#gとpic#hの撮影日時を表す。また、g∈Niは、写真データpic#gがノードNiに包含されるノード（ノードを、リーフノードから上位階層の方向に辿っていったときにノードNiに辿り着くノード）に割り当てられていること、つまり、写真データpic#gがノードNiに対応するクラスタCiに属する（クラスタリングされている）写真データであることを表す。同様に、h∈Njは、写真データpic#hがノードNjに対応するクラスタCjに属する写真データであることを表す。さらに、argmin|t(g)-t(h)|は、|t(g)-t(h)|を最小にするgとhを表す。
【００９９】
従って、式（５）によれば、クラスタCiとCjとの距離dC(Ni,Nj)は、クラスタCiに属するいずれかの写真データと、クラスタCjに属するいずれかの写真データとの距離のうちの、撮影日時の差が最小の写真データどうしの距離、つまり、クラスタCiに属する写真データと、クラスタCjに属する写真データとのうちの、例えば、クラスタCiに属する写真データの方が、クラスタCjに属する写真データよりも撮影日時が古い場合には、撮影日時順に並んでいるクラスタCiに属する写真データのうちの、撮影日時が最も新しい写真データpic#gと、同じく撮影日時順に並んでいるクラスタCjに属する写真データのうちの、撮影日時が最も古い写真データpic#hとの距離dpic(g,h)に等しい。
【０１００】
なお、クラスタツリーにおいて、リーフノードに対応するクラスタには、そのリーフノードに割り当てられている写真データだけが属する。従って、ノードNiとNjとの両方がリーフノードである場合には、式（５）の距離dC(Ni,Nj)は、ノードNiに対応するクラスタCiに属する写真データと、ノードNjに対応するクラスタCjに属する写真データとの距離、つまり、リーフノードNiに割り当てられている写真データpic#iと、リーフノードNjに割り当てられている写真データpic#jとの距離dpic(i,j)となる。ここで、以下、適宜、リーフノードNiに割り当てられている写真データpic#iと、リーフノードNjに割り当てられている写真データpic#jとの距離を、写真データpic#iおよびpic#jを用いてdpic(i,j)と表す他、ノードNiおよびNjを用いてdpic(Ni,Nj)とも表す。
【０１０１】
また、ノードNiとNjとのうちの一方がリーフノードであり、他方がリーフノードでないノードである場合、即ち、例えば、ノードNiがリーフノードであり、ノードNjがリーフノードでないノードである場合、式（５）の距離dC(Ni,Nj)は、リーフノードNiに割り当てられた写真データpic#iと、ノードNjに対応するクラスタCjとの距離ということができる。そして、この、写真データpic#iとクラスタCjとの距離dC(Ni,Nj)は、式（５）から、写真データpic#iと、クラスタCjに属する写真データのうちの、写真データpic#iとの撮影日時が最も近い写真データpic#jとの距離dpic(i,j)として求めることができる。
【０１０２】
次に、図７乃至図１５を参照して、階層的クラスタリングによってクラスタツリーが生成されていく手順の概要について説明する。
【０１０３】
階層的クラスタリングでは、新たにクラスタリングしようとする1枚の写真データを、注目データとして注目（選択）し、その注目データに、新たなリーフノードが割り当てられる。
【０１０４】
そして、階層的クラスタリングがされた写真データが存在しない場合、即ち、注目データが、階層的クラスタリングの対象となった最初の写真データである場合、注目データに割り当てられたリーフノードは、クラスタツリーのルートノードとされる。
【０１０５】
具体的には、図７左側に示すように、注目データが、写真データpic1である場合、その注目データpic1に、新たなリーフノードN1が割り当てられ、そのリーフノードN1が、ルートノードとされる。
【０１０６】
そして、図７左側に示したような、写真データpic1が割り当てられたルートノードN1のみからなるクラスタツリーが存在する場合において、新たな写真データpicnewが注目データとされると、階層的クラスタリングでは、クラスタツリーによって既にクラスタリングされている写真データ（クラスタツリーのリーフノードに割り当てられている写真データ）pic1と、注目データpicnewとを、撮影日時順に（左から右に）並べた並びにおいて、注目データpicnewが配置される位置（以下、適宜、注目位置という）が検出される。
【０１０７】
従って、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも遅ければ（新しければ）、図７右側の上側に示すように、写真データpic1の右側の位置が、注目位置として検出される。一方、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも早ければ（古ければ）、図７右側の下側に示すように、写真データpic1の左側の位置が、注目位置として検出される。
【０１０８】
さらに、階層的クラスタリングでは、注目データpicnewに、新たなリーフノードN2が割り当てられ、そのリーフノードN2は、クラスタツリーの注目位置に配置される。即ち、図７右側の上側に示すように、写真データpic1の右側の位置が、注目位置である場合には、写真データpic1に割り当てられたリーフノードN1の右隣の位置に、注目データpicnewに割り当てられたリーフノードN2が配置される。一方、図７右側の下側に示すように、写真データpic1の左側の位置が、注目位置である場合には、写真データpic1に割り当てられたリーフノードN1の左隣の位置に、注目データpicnewに割り当てられたリーフノードN2が配置される。
【０１０９】
そして、写真データpic1が割り当てられているリーフノードN1と、注目データpicnewが割り当てられているリーフノードN2とをそれぞれ子ノードとするノードN3が追加される。その結果、図７右側に示すように、ノードN3をルートノードとし、そのノードN3の子ノードとして、写真データpic1が割り当てられているリーフノードN1と、注目データpicnewが割り当てられているリーフノードN2を有するクラスタツリーが得られる。
【０１１０】
なお、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも遅い場合、図７右側の上側に示したように、注目データpicnewに割り当てられたノードN2は、注目位置としてのノードN1の右側の位置に配置されるので、ノードN1が左側に位置し、ノードN2が右側に位置するクラスタツリーが得られる。
【０１１１】
一方、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも早い場合、図７右側の下側に示したように、注目データpicnewに割り当てられたノードN2は、注目位置としてのノードN1の左側の位置に配置されるので、ノードN1が右側に位置し、ノードN2が左側に位置するクラスタツリーが得られる。
【０１１２】
ここで、クラスタツリーでは、図２で説明したように、リーフノード以外のノードは、２つの子ノードを有する。以下では、クラスタツリーにおいて、リーフノード以外のノードが有する２つの子ノードのうちの左側の子ノードと右側の子ノードを、それぞれ、左ノードと右ノードと呼ぶこととする。
【０１１３】
なお、クラスタツリーにおいて、リーフノードは、撮影日時順に並んだ写真データに割り当てられるので、あるノードの２つの子ノードである左ノードと右ノードに注目した場合、左ノードに包含されるリーフノード（左ノードがリーフノードである場合の、そのリーフノードを含む）に割り当てられている写真データは、いずれも、右ノードに包含されるリーフノードに割り当てられている写真データのいずれよりも撮影日時が早い写真データとなる。逆に、右ノードに包含されるリーフノードに割り当てられている写真データは、いずれも、左ノードに包含されるリーフノードに割り当てられている写真データのいずれよりも撮影日時が遅い写真データとなる。
【０１１４】
次に、図８左から１番目に示すような、撮影日時が早い写真データpic1に割り当てられているノード（リーフノード）N1、撮影日時が遅い写真データpic2に割り当てられているノード（リーフノード）N2、およびそのノードN1とN2をそれぞれ左ノードと右ノードとして有するノード（ルートノード）N3からなるクラスタツリーが存在する場合において、新たな写真データpicnewが注目データとされると、階層的クラスタリングでは、クラスタツリーによって既にクラスタリングされている写真データpic1およびpic2と、注目データpicnewとを、撮影日時順に並べた並びにおいて、注目データpicnewが配置される位置（注目位置）が検出される。
【０１１５】
さらに、階層的クラスタリングでは、注目データpicnewに、新たなリーフノードN4が割り当てられ、そのリーフノードN4は、クラスタツリーの注目位置に配置される。
【０１１６】
例えば、いま、注目データpicnewの撮影日時が、写真データpic2の撮影日時よりも遅ければ、写真データpic2の右側の位置が、注目位置として検出されるので、注目データpicnewに割り当てられた新たなリーフノードN4は、図８左から２番目に示すように、写真データpic2に割り当てられたリーフノードN2の右隣の位置に配置される。
【０１１７】
そして、階層的クラスタリングでは、注目データpicnewに隣接するクラスタ（隣接クラスタ）のうちの最大のクラスタであって、かつ、注目データpicnewとの距離が最小の後述する間近写真データが属するクラスタが、注目データpicnewが属するクラスタの候補となる候補クラスタとして求められる。
【０１１８】
図８左から２番目のクラスタツリーでは、注目データpicnewに隣接するクラスタとしては、ノードN3に対応するクラスタC3と、ノードN2に対応するクラスタC2とがあり、注目データpicnewに隣接するクラスタのうちの最大のクラスタは、ノードN3に対応するクラスタC3だけなので、このクラスタC3が、候補クラスタとして求められる。
【０１１９】
さらに、階層的クラスタリングでは、注目データpicnewと候補クラスタC3に属する写真データのうちの注目データpicnewに隣接する写真データpic2との距離dnが求められるとともに、候補クラスタC3に属する写真データのうちの隣接する写真データどうしの距離の最大値（以下、適宜、最大距離という）dqが求められる。
【０１２０】
ここで、候補クラスタC3に属する写真データのうちの注目データに隣接する写真データは、上述したことから、候補クラスタに属する写真データのうちの、注目データpicnewとの撮影日時が最も近い写真データであり、以下、適宜、間近写真データという。候補クラスタC3の間近写真データは写真データpic2であり、従って、距離dnとしては、注目データpicnewと間近写真データpic2との距離dpic(picnew,pic2)が、式（２）（または式（３））によって求められる。
【０１２１】
また、候補クラスタC3には、写真データpic1とpic2だけが属しているので、最大距離dqとしては、写真データpic1とpic2との距離dpic(pic1,pic2)が、式（２）によって求められる。
【０１２２】
注目データpicnewと候補クラスタC3の間近写真データpic2との距離dnが、候補クラスタC3の最大距離dqより大（または以上）である場合、注目データpicnewを、候補クラスタC3より粒度の大きい、候補クラスタC3とは別のクラスタにクラスタリングするために、その別のクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１２３】
即ち、注目データpicnewを、候補クラスタC3より粒度の大きい、候補クラスタC3とは別のクラスタにクラスタリングするために、図８左から３番目に示すように、クラスタC3に対応するノードN3と、注目データpicnewに割り当てられたリーフノードN4とをそれぞれ子ノードとする新たなノードN5が追加される。
【０１２４】
その結果、図８左から１番目に示したクラスタツリーは、図８左から４番目（右から１番目）に示すように、新たなノードN5をルートノードとし、ノードN3とN4を、それぞれルートノードN5の左ノードと右ノードとし、ノードN1とN2を、それぞれノードN3の左ノードと右ノードとするクラスタツリーに更新される。
【０１２５】
次に、図８左から２番目に示したように、注目データpicnewに割り当てられた新たなリーフノードN4が、写真データpic2に割り当てられたリーフノードN2の右隣の位置に配置された場合において、図９左から１番目に示すように、注目データpicnewと候補クラスタC3の間近写真データpic2との距離dnが、候補クラスタC3の最大距離dq以下（または未満）であるときには、候補クラスタC3に包含させる新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１２６】
即ち、注目データpicnewと候補クラスタC3の間近写真データpic2との距離dnが、候補クラスタC3の最大距離dq以下である場合、注目データpicnewを、候補クラスタC3にクラスタリングするために、その候補クラスタC3に包含させる新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１２７】
具体的には、図９左から２番目に示すように、候補クラスタC3に対応するノードN3と、そのノードN3の２つの子ノードであるノードN1またはN2のうちの、注目データpicnewが割り当てられたリーフノードN4が位置する側のノードN2との間に、そのノードN2と、注目データpicnewが割り当てられたリーフノードN4とをそれぞれ子ノードとする新たなノードN5が追加される。
【０１２８】
その結果、図８左から１番目に示したクラスタツリーは、図９左から３番目（右から１番目）に示すように、ノードN3をルートノードとし、ノードN1とN5を、それぞれルートノードN3の左ノードと右ノードとし、ノードN2とN4が、それぞれノードN5の左ノードと右ノードとなるクラスタツリーに更新される。
【０１２９】
次に、例えば、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも遅く、かつ、写真データpic2の撮影日時より早い場合には、写真データpic1とpic2との間の位置が、注目位置として検出される。従って、この場合、注目データpicnewに割り当てられた新たなリーフノードN4は、図１０左から１番目に示すように、写真データpic1に割り当てられたリーフノードN1と、写真データpic2に割り当てられたリーフノードN2との間の位置に配置される。
【０１３０】
そして、階層的クラスタリングでは、図８で説明したように、注目データpicnewに隣接するクラスタのうちの最大のクラスタであって、かつ、注目データpicnewとの距離が最小の間近写真データが属するクラスタが、注目データpicnewが属するクラスタの候補となる候補クラスタとして求められる。
【０１３１】
図１０左から１番目のクラスタツリーでは、注目データpicnewに隣接するクラスタとしては、注目データpicnewの左右のうちの左隣のノードN1に対応するクラスタC1と、右隣のノードN2に対応するクラスタC2とがあり、注目データpicnewに隣接するクラスタのうちの最大のクラスタは、これらの２つのクラスタC1とC2が存在する。従って、クラスタC1とC2のうちの、注目データpicnewと間近写真データとの距離が短い方が、候補クラスタとされる。
【０１３２】
クラスタC1とC2のうちの、例えば、クラスタC2の間近写真データの方が、クラスタC1の間近写真データよりも、注目データpicnewとの距離が短い場合、クラスタC2が候補クラスタとなる。
【０１３３】
即ち、クラスタC1の間近写真データは写真データpic1であり、クラスタC2の間近写真データは写真データpic2であり、注目データpicnewとpic2との距離が、注目データpicnewとpic1との距離よりも短い場合、クラスタC2が候補クラスタとなる。
【０１３４】
上述したように、階層的クラスタリングでは、注目データpicnewと候補クラスタの間近写真データ（候補クラスタに属する写真データのうちの注目データpicnewに隣接する写真データ）との距離dnが求められるとともに、候補クラスタに属する写真データのうちの隣接する写真データどうしの距離の最大値（最大距離）dqが求められるが、クラスタC2が候補クラスタである場合、クラスタC2に対応するノードN2はリーフノードであるため、クラスタC2に属する写真データは、ノードN2に割り当てられた写真データpic2しか存在しない。即ち、候補クラスタとしてのクラスタC2には、隣接する写真データは存在しない。
【０１３５】
この場合、候補クラスタC2に属する写真データpic2と、注目データpicnewとが属する新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１３６】
即ち、候補クラスタに対応するノードが、リーフノードである場合には、そのリーフノードと、注目データpicnewに割り当てられたリーフノードN4とをそれぞれ子ノードとする新たなノードN5が、クラスタツリーに追加される。
【０１３７】
具体的には、図１０左から２番目に示すように、注目データpicnewが割り当てられたリーフノードN4と、候補クラスタC2に対応するリーフノードN2とをそれぞれ子ノードとする新たなノードN5が、ノードN2とそのノードN2の親ノードであるノードN3との間に、ノードN3の子ノードとする形で、クラスタツリーに追加される。
【０１３８】
その結果、図８左から１番目に示したクラスタツリーは、図１０左から３番目（右から１番目）に示すように、ノードN3をルートノードとし、ノードN1とN5を、それぞれルートノードN3の左ノードと右ノードとし、ノードN4とN2が、それぞれノードN5の左ノードと右ノードとなるクラスタツリーに更新される。
【０１３９】
次に、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも遅く、かつ、写真データpic2の撮影日時より早い場合において、図１１左から１番目に示すように、注目データpicnewに隣接するクラスタC1とC2のうちの、クラスタC1の方が、クラスタC2よりも、注目データpicnewと間近写真データとの距離が短いときには、クラスタC1が候補クラスタとなる。
【０１４０】
即ち、クラスタC1の間近写真データは写真データpic1であり、クラスタC2の間近写真データは写真データpic2であり、注目データpicnewとpic1との距離が、注目データpicnewとpic2との距離よりも短い場合、クラスタC1が候補クラスタとなる。
【０１４１】
クラスタC1に対応するノードN1はリーフノードであり、この場合、図１０で説明したように、候補クラスタC1に属する写真データpic1と、注目データpicnewとが属する新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１４２】
即ち、候補クラスタに対応するノードが、リーフノードである場合には、そのリーフノードと、注目データpicnewに割り当てられたリーフノードN4とをそれぞれ子ノードとする新たなノードN5が、クラスタツリーに追加される。
【０１４３】
具体的には、図１１左から２番目に示すように、注目データpicnewが割り当てられたリーフノードN4と、候補クラスタC1に対応するリーフノードN1とをそれぞれ子ノードとする新たなノードN5が、ノードN1とそのノードN1の親ノードであるノードN3との間に、ノードN3の子ノードとする形で、クラスタツリーに追加される。
【０１４４】
その結果、図８左から１番目に示したクラスタツリーは、図１１左から３番目（右から１番目）に示すように、ノードN3をルートノードとし、ノードN5とN2を、それぞれルートノードN3の左ノードと右ノードとし、ノードN1とN4が、それぞれノードN5の左ノードと右ノードとなるクラスタツリーに更新される。
【０１４５】
次に、例えば、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも早い場合には、写真データpic1の左側の位置が、注目位置として検出される。従って、この場合、注目データpicnewに割り当てられた新たなリーフノードN4は、図１２左から１番目に示すように、写真データpic1に割り当てられたリーフノードN1の左側の位置としての注目位置に配置される。
【０１４６】
そして、階層的クラスタリングでは、上述したように、注目データpicnewに隣接するクラスタのうちの最大のクラスタであって、かつ、注目データpicnewとの距離が最小のクラスタが、注目データpicnewが属するクラスタの候補となる候補クラスタとして求められる。
【０１４７】
図１２左から１番目のクラスタツリーでは、注目データpicnewに隣接するクラスタとしては、ノードN3に対応するクラスタC3と、ノードN1に対応するクラスタC1とがあり、注目データpicnewに隣接するクラスタのうちの最大のクラスタは、ノードN3に対応するクラスタC3だけなので、このクラスタC3が、候補クラスタとして求められる。
【０１４８】
さらに、階層的クラスタリングでは、注目データpicnewと候補クラスタC3の間近写真データである写真データpic1との距離dnが求められるとともに、候補クラスタC3に属する写真データのうちの隣接する写真データどうしの最大距離dq（図１２では、写真データpic1とpic2との距離）が求められる。
【０１４９】
そして、注目データpicnewと候補クラスタC3の間近写真データpic1との距離dnが、候補クラスタC3の最大距離dqより大である場合、図８で説明した場合と同様に、注目データpicnewを、候補クラスタC3より粒度の大きい、候補クラスタC3とは別のクラスタにクラスタリングするために、その別のクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１５０】
即ち、注目データpicnewを、候補クラスタC3より粒度の大きい、候補クラスタC3とは別のクラスタにクラスタリングするために、図１２左から２番目に示すように、クラスタC3に対応するノードN3と、注目データpicnewに割り当てられたリーフノードN4とをそれぞれ子ノードとする新たなノードN5が追加される。
【０１５１】
その結果、図８左から１番目に示したクラスタツリーは、図１２左から３番目（右から１番目）に示すように、新たなノードN5をルートノードとし、ノードN4とN3を、それぞれルートノードN5の左ノードと右ノードとし、ノードN1とN2を、それぞれノードN3の左ノードと右ノードとするクラスタツリーに更新される。
【０１５２】
次に、図１２左から１番目に示したように、注目データpicnewに割り当てられた新たなリーフノードN4が、写真データpic1に割り当てられたリーフノードN1の左隣の位置に配置された場合において、図１３左から１番目に示すように、注目データpicnewと候補クラスタC3の間近写真データpic1との距離dnが、候補クラスタC3の最大距離dq以下であるときには、候補クラスタC3に包含させる新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１５３】
即ち、注目データpicnewと候補クラスタC3の間近写真データpic1との距離dnが、候補クラスタC3の最大距離dq以下である場合、注目データpicnewを、候補クラスタC3にクラスタリングするために、その候補クラスタC3に包含させる新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１５４】
具体的には、図１３左から２番目に示すように、候補クラスタC3に対応するノードN3と、そのノードN3の２つの子ノードであるノードN1またはN2のうちの、注目データpicnewが割り当てられたリーフノードN4が位置する側のノードN1との間に、そのノードN1と、注目データpicnewが割り当てられたリーフノードN4とをそれぞれ子ノードとする新たなノードN5が追加される。
【０１５５】
その結果、図８左から１番目に示したクラスタツリーは、図１３左から３番目（右から１番目）に示すように、ノードN3をルートノードとし、ノードN5とN2を、それぞれルートノードN3の左ノードと右ノードとし、ノードN4とN1が、それぞれノードN5の左ノードと右ノードとなるクラスタツリーに更新される。
【０１５６】
次に、図１４左から１番目に示すような、撮影日時順に（左から右に）並ぶ写真データpic1，pic2，pic3にそれぞれ割り当てられているノード（リーフノード）N1，N2，N3、ノードN2とN3をそれぞれ左ノードと右ノードとして有するノードN4、およびノードN1とノードN4をそれぞれ左ノードと右ノードとして有するノード（ルートノード）N5からなるクラスタツリーが存在する場合において、新たな写真データpicnewが注目データとされると、階層的クラスタリングでは、クラスタツリーによって既にクラスタリングされている写真データpic1乃至pic3と、注目データpicnewとを、撮影日時順に並べた並びにおいて、注目データpicnewが配置される注目位置が検出される。
【０１５７】
さらに、階層的クラスタリングでは、注目データpicnewに、新たなリーフノードN6が割り当てられ、そのリーフノードN6は、クラスタツリーの注目位置に配置される。
【０１５８】
例えば、いま、注目データpicnewの撮影日時が、写真データpic1の撮影日時よりも遅く、かつ、写真データpic2の撮影日時よりも早い場合には、写真データpic1とpic2との間の位置が、注目位置として検出されるので、注目データpicnewに割り当てられた新たなリーフノードN6は、図１４左から２番目に示すように、写真データpic1に割り当てられたリーフノードN1と、写真データpic2に割り当てられたリーフノードN2との間の位置に配置される。
【０１５９】
そして、階層的クラスタリングでは、注目データpicnewに隣接するクラスタのうちの最大のクラスタであって、かつ、注目データpicnewとの距離が最小の間近写真データが属するクラスタが、注目データpicnewが属するクラスタの候補となる候補クラスタとして求められる。
【０１６０】
図１４左から２番目のクラスタツリーでは、注目データpicnewに隣接するクラスタとしては、ノードN1に対応するクラスタC1、ノードN2に対応するクラスタC2、およびノードN4に対応するクラスタC4がある。
【０１６１】
ノードN1，N3，N4のうちの、ノードN1とノードN4は、同一階層のノードであり、ノードN3は、ノードN1の階層およびノードN4の階層よりも下位の階層のノードであるから、注目データpicnewに隣接するクラスタのうちの最大のクラスタとしては、注目データpicnewの左隣のノードN1に対応するクラスタC1と、注目データpicnewの右隣のノードN4に対応するクラスタC4とがある。
【０１６２】
従って、クラスタC1とC4とのうちの、注目データpicnewと間近写真データとの距離が短い方のクラスタが、候補クラスタとなる。なお、図１４において、クラスタC1の間近写真データは、注目データpicnewの左に隣接する写真データpic1であり、クラスタC4の間近写真データは、注目データpicnewの右に隣接する写真データpic2である。
【０１６３】
例えば、クラスタC1とC4とのうちの、クラスタC1の方が、クラスタC4よりも注目データpicnewと間近写真データとの距離が短い場合（クラスタC1の間近写真データpic1と注目データpicnewとの距離が、クラスタC4の間近写真データpic2と注目データpicnewとの距離未満（または以下）である場合）、クラスタC1が、候補クラスタとなる。
【０１６４】
クラスタC1に対応するノードN1はリーフノードであり、この場合、図１０や図１１で説明したのと同様に、候補クラスタC1に属する写真データpic1と、注目データpicnewとが属する新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１６５】
即ち、候補クラスタC1に対応するノードであるリーフノードN1と、注目データpicnewに割り当てられたリーフノードN6とをそれぞれ子ノードとする新たなノードN7が、クラスタツリーに追加される。
【０１６６】
具体的には、図１４左から３番目に示すように、注目データpicnewが割り当てられたリーフノードN6と、候補クラスタC1に対応するリーフノードN1とをそれぞれ子ノードとする新たなノードN7が、ノードN1とその親ノードであるノードN5との間に、ノードN5の子ノードとする形で、クラスタツリーに追加される。
【０１６７】
一方、例えば、クラスタC1とC4とのうちの、クラスタC4の方が、クラスタC1よりも注目データpicnewと間近写真データとの距離が短い場合（クラスタC4の間近写真データpic2と注目データpicnewとの距離が、クラスタC1の間近写真データpic1と注目データpicnewとの距離未満（または以下）である場合）、クラスタC4が、候補クラスタとなる。
【０１６８】
図１４において、候補クラスタであるクラスタC4に対応するノードN4はリーフノードではないので、図９で説明したように、注目データpicnewと候補クラスタC4の間近写真データとの距離dnが求められるとともに、候補クラスタC4に属する写真データのうちの隣接する写真データどうしの最大距離dqが求められる。
【０１６９】
候補クラスタC4の間近写真データは、写真データpic2であり、従って、距離dnは、図１４左から２番目に示すように、注目データpicnewと写真データpic2との距離dpic(picnew,pic2)となる。また、候補クラスタC4には、写真データpic2とpic3だけが属しているので、最大距離dqは、写真データpic2とpic3との距離dpic(pic2,pic3)となる。
【０１７０】
注目データpicnewと候補クラスタC4の間近写真データpic2との距離dnが、候補クラスタC3の最大距離dqより大である場合、図８で説明したのと同様に、注目データpicnewを、候補クラスタC4より粒度の大きい、候補クラスタC4とは別のクラスタにクラスタリングするために、その別のクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１７１】
即ち、注目データpicnewを、候補クラスタC4より粒度の大きい、候補クラスタC4とは別のクラスタにクラスタリングするために、図１４左から３番目に示すように、クラスタC4に対応するノードN4と、注目データpicnewに割り当てられたリーフノードN6とをそれぞれ子ノードとする新たなノードN8が、候補クラスタC4に対応するノードN4とそのノードN4の親ノードであるノードN5との間に、ノードN5の子ノードとする形で、クラスタツリーに追加される。
【０１７２】
また、図１４左から２番目において、注目データpicnewと候補クラスタC4の間近写真データpic2との距離dnが、候補クラスタC4の最大距離dq以下である場合には、候補クラスタC4に包含させる新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１７３】
即ち、注目データpicnewと候補クラスタC4の間近写真データpic2との距離dnが、候補クラスタC4の最大距離dq以下である場合、注目データpicnewを、候補クラスタC4にクラスタリングするために、その候補クラスタC4に包含させる新たなクラスタに対応する新たなノードが、クラスタツリーに追加される。
【０１７４】
具体的には、図１４左から３番目に示すように、候補クラスタC4に対応するノードN4と、そのノードN4の２つの子ノードであるノードN2またはN3のうちの、注目データpicnewが割り当てられたリーフノードN6が位置する側のノードN2との間に、そのノードN2と、注目データpicnewが割り当てられたリーフノードN6とをそれぞれ子ノードとする新たなノードN9が追加される。
【０１７５】
図１５は、図１４左から１番目に示したクラスタツリーに対して、図１４左から３番目に示した新たなノードN7，N8、またはN9が追加されたクラスタツリーそれぞれを示している。
【０１７６】
即ち、図１５上から１番目は、図１４左から１番目に示したクラスタツリーに対して、図１４左から３番目に示した新たなノードN7が追加されたクラスタツリーを示している。
【０１７７】
新たなノードN7は、注目データpicnewが割り当てられたリーフノードN6と、候補クラスタC1に対応するリーフノードN1とをそれぞれ子ノードとし、かつ、ノードN5を親ノードとする形で、クラスタツリーに追加される。
【０１７８】
その結果、図１４左から１番目に示したクラスタツリーは、図１５上から１番目に示すように、ノードN5をルートノードとし、ノードN7とN4を、それぞれルートノードN5の左ノードと右ノードとし、ノードN1とN6を、それぞれノードN7の左ノードと右ノードとし、ノードN2とN3を、それぞれノードN4の左ノードと右ノードとするクラスタツリーに更新される。
【０１７９】
また、図１５上から２番目は、図１４左から１番目に示したクラスタツリーに対して、図１４左から３番目に示した新たなノードN8が追加されたクラスタツリーを示している。
【０１８０】
新たなノードN8は、クラスタC4に対応するノードN4と、注目データpicnewに割り当てられたリーフノードN6とをそれぞれ子ノードとし、かつ、ノードN5を親ノードとする形で、クラスタツリーに追加される。
【０１８１】
その結果、図１４左から１番目に示したクラスタツリーは、図１５上から２番目に示すように、ノードN5をルートノードとし、ノードN1とN8を、それぞれルートノードN5の左ノードと右ノードとし、ノードN6とN4を、それぞれノードN8の左ノードと右ノードとし、ノードN2とN3を、それぞれノードN4の左ノードと右ノードとするクラスタツリーに更新される。
【０１８２】
さらに、図１５上から３番目（下から１番目）は、図１４左から１番目に示したクラスタツリーに対して、図１４左から３番目に示した新たなノードN9が追加されたクラスタツリーを示している。
【０１８３】
新たなノードN9は、候補クラスタC4に対応するノードN4と、ノードN2との間に、そのノードN2と、注目データpicnewが割り当てられたリーフノードN6とをそれぞれ子ノードとする形で、クラスタツリーに追加される。
【０１８４】
その結果、図１４左から１番目に示したクラスタツリーは、図１５上から３番目に示すように、ノードN5をルートノードとし、ノードN1とN4を、それぞれルートノードN5の左ノードと右ノードとし、ノードN9とN3を、それぞれノードN4の左ノードと右ノードとし、ノードN6とN2を、それぞれノードN9の左ノードと右ノードとするクラスタツリーに更新される。
【０１８５】
次に、図１６は、図１のクラスタリング装置１３の構成例を示している。
【０１８６】
クラスタリング装置１３は、メタデータ読み出し部２０、および木構造処理部２２から構成される。
【０１８７】
メタデータ読み出し部２０は、データ記憶装置１２から、注目データpicnewのメタデータを読み出すことにより取得し、木構造処理部２２に供給する。
【０１８８】
ここで、クラスタツリー記憶装置１４に記憶されているクラスタツリーによってクラスタリングされている写真データと、注目データpicnewとを含めた写真データを、階層的クラスタリングの対象とする対象写真データとして、その対象写真データを、メタデータに含まれる撮影日時に基づいて左から右に一列に並べた並びにおいて、注目データpicnewが配置される位置を、注目位置という。
【０１８９】
木構造処理部２２は、クラスタツリー記憶装置１４に記憶されているクラスタツリーのノードに対応するクラスタのうちの注目位置に配置された注目データpicnewに隣接するクラスタ（のうちの候補クラスタ）に属する写真データのうちの間近写真データと、注目データpicnewとの所定の距離尺度による距離（第２の距離）dn、および候補クラスタに属する写真データのうちの隣接する写真データどうしの最大距離（第１の距離）dqを、メタデータに基づいて求め、距離dnおよび最大距離dqに基づいて、注目データpicnewに割り当てられるノードNnew（以下、適宜、注目ノードNnewという）を子ノードとする新たなノードNinを、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加する木構造処理を行う。
【０１９０】
即ち、木構造処理部２２は、図７乃至図１５で説明したように、候補クラスタに属する写真データのうちの、注目データpicnewに隣接する写真データ、つまり、撮影日時が注目データpicnewに最も近い間近写真データを、クラスタツリー記憶装置１４に記憶されているクラスタツリーのリーフノードに保持されているメタデータと、メタデータ読み出し部２０から供給される注目データpicnewのメタデータとに基づいて認識する。さらに、木構造処理部２２は、間近写真データと注目データpicnewのメタデータに含まれる撮影日時と撮影位置に基づき、間近写真データと注目データpicnewとの式（２）（または式（３））による距離dpic()を、距離dnとして求める。同様に、木構造処理部２２は、候補クラスタに属する写真データのメタデータに含まれる撮影日時と撮影位置に基づき、候補クラスタにおける隣接する写真データのどうしの最大距離dqを求める。そして、木構造処理部２２は、距離dnと最大距離dqに基づき、注目データpicnewに割り当てられる注目ノードNnewを子ノードとする新たなノードNinを、クラスタツリー記憶装置１４に記憶されている現在のクラスタツリーに追加することで、新たなクラスタツリーを求め、その新たなクラスタツリーによって、クラスタツリー記憶装置１４の記憶内容を更新する（上書きする）。
【０１９１】
次に、図１７のフローチャートを参照して、図１６のクラスタリング装置１３が行う処理について説明する。
【０１９２】
クラスタリング装置１３では、まず最初に、ステップＳ１において、木構造処理部２２が、クラスタツリーを初期化するかどうかを判定する。
【０１９３】
ステップＳ１において、クラスタツリーを初期化すると判定された場合、即ち、例えば、ユーザが、クラスタツリーを初期化するように、操作部１７を操作した場合、ステップＳ２に進み、木構造処理部２２は、クラスタツリーを初期化し、その初期化の結果得られたクラスタツリーを、クラスタツリー記憶装置１４に記憶させて（上書きして）、ステップＳ３に進む。
【０１９４】
即ち、いま、クラスタツリーのルートノード（を表す変数）を、Nrootと表すとともに、あるノードの左ノードまたは右ノードとなっている子ノード（を表す変数）を、l(N)またはr(N)とそれぞれ表すこととすると、木構造処理部２２は、ルートノードNrootの左l(N)と右ノードr(N)に、ノードが存在しないことを表すNULLをセットする。
【０１９５】
一方、ステップＳ１において、クラスタツリーを初期化しないと判定された場合、即ち、例えば、ユーザが、クラスタツリーを初期化するように、操作部１７を操作しなかった場合、ステップＳ２をスキップして、ステップＳ３に進み、メタデータ読み出し部２０は、データ記憶装置１２に、クラスタツリー記憶装置１４を参照することにより、クラスタツリーによってクラスタリングされていない写真データが記憶されているかどうかを判定する。
【０１９６】
ステップＳ３において、データ記憶装置１２に、クラスタツリーによってクラスタリングされていない写真データが記憶されていると判定された場合、ステップＳ４に進み、メタデータ読み出し部２０は、データ記憶装置１２に記憶されている、クラスタツリーによってクラスタリングされていない写真データのうちの１枚を、注目データpicnewに選択し、ステップＳ５に進む。
【０１９７】
ステップＳ５では、クラスタリング装置１３が、クラスタツリー記憶装置１４に記憶されているクラスタツリーによってクラスタリングされている写真データと、注目データpicnewとを含めた写真データを、階層的クラスタリングの対象とする対象写真データとして、その対象写真データをクラスタリングする新たなクラスタツリーを求め、その新たなクラスタツリーによって、クラスタツリー記憶装置１４の記憶内容を更新するクラスタリング処理が行われ、ステップＳ３に戻る。
【０１９８】
そして、ステップＳ３において、データ記憶装置１２に、クラスタツリーによってクラスタリングされていない写真データが記憶されていないと判定された場合、即ち、データ記憶装置１２に記憶されている写真データすべてが、クラスタツリーによってクラスタリングされている場合、処理を終了する。
【０１９９】
次に、図１８のフローチャートを参照して、図１７のステップＳ５において、図１６のクラスタリング装置１３が行うクラスタリング処理について説明する。
【０２００】
クラスタリング処理では、まず最初に、ステップＳ１１において、メタデータ読み出し部２０は、データ記憶装置１２から、注目データpicnewのメタデータを読み出すことにより取得し、木構造処理部２２に供給して、ステップＳ１２に進む。
【０２０１】
ステップＳ１２では、木構造処理部２２は、クラスタツリー記憶装置１４に記憶されているクラスタツリーによってクラスタリングされている写真データと、注目データpicnewとを含めた写真データを、対象写真データとして、その対象写真データを、メタデータに含まれる撮影日時に基づいて左から右に一列に並べた並び（撮影日時順の対象写真データの並び）において、注目位置に配置された注目データpicnewに隣接するクラスタのうちの候補クラスタの間近写真データと、注目データpicnewとの所定の距離尺度による距離dn、および候補クラスタに属する写真データのうちの隣接する写真データどうしの最大距離dqを、対象写真データのメタデータに基づいて求め、その距離dnおよび最大距離dqに基づいて、注目データpicnewに割り当てられる注目ノードNnewを子ノードとする新たなノードNinを、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加する木構造処理を行って、リターンする（クラスタリング処理を終了する）。
【０２０２】
次に、図１９は、図１８のステップＳ１２の木構造処理を行う図１６の木構造処理部２２の構成例を示している。
【０２０３】
木構造処理部２２は、分岐ノード検索部３１およびノード追加部３２から構成される。
【０２０４】
分岐ノード検索部３１は、メタデータ読み出し部２０から供給される注目データpicnewのメタデータと、クラスタツリー記憶装置１４に記憶されたクラスタツリーとに基づき、撮影日時順の対象写真データの並びにおいて注目位置に配置された注目データpicnewの左右のうちの一方に隣接する最大のクラスタに対応するノード、または、注目データpicnewの他方に隣接する最大のクラスタに対応するノードを子ノードとするノードである分岐ノードを検索する分岐ノード検索処理を行い、その結果得られる分岐ノードを、ノード追加部３２に供給する。
【０２０５】
追加部４３は、距離算出部４１、判定部４２、および追加部４３から構成され、分岐ノード検索部３１から供給される分岐ノードと、メタデータ読み出し部２０から供給される注目データpicnewのメタデータに基づき、注目データpicnewに割り当てられる注目ノードNnewを子ノードとする新たなノードNinを、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加するノード追加処理を行う。
【０２０６】
即ち、距離算出部４１は、分岐ノード検索部３１からの分岐ノードの子ノードに対応するクラスタの中で、注目位置に配置された注目データpicnewと間近写真データとの所定の距離尺度による距離が最も近いクラスタに対応するノードを、新たなノードNinの子ノードの候補である候補ノード、つまり、注目データpicnewが属するクラスタの候補となる候補クラスタに対応するノードである候補ノードとして、その候補ノードに対応する候補クラスタの間近写真データと注目データpicnewとの所定の距離尺度による距離dnと、候補ノードに対応する候補クラスタに属する写真データ（クラスタリングツリーによって既にクラスタリングされている写真データ）のうちの隣接する写真データどうしの所定の距離尺度による距離の最大値である最大距離dqとを求め、判定部４２に供給する。
【０２０７】
判定部４２は、距離算出部４１からの距離dnと最大距離dqとの大小関係、即ち、候補ノードに対応する候補クラスタの間近写真データと注目データとの所定の距離尺度による距離dnと、候補ノードに対応する候補クラスタに属するデータのうちの隣接するデータどうしの最大距離dqとの大小関係を判定し、その判定結果を、追加部４３に供給する。
【０２０８】
追加部４３は、判定部４２からの判定結果に基づいて、現在のクラスタツリー（クラスタツリー記憶装置１４に記憶されているクラスタツリー）における分岐ノードと候補ノードとの間に、分岐ノードを親ノードとするとともに候補ノードおよび注目ノードを子ノードとする新たなノードNinを追加し、これにより、新たなクラスタツリーを生成する。
【０２０９】
即ち、判定部４２において、候補ノードに対応する候補クラスタの間近写真データと注目データpicnewとの距離dnが、候補ノードに対応する候補クラスタに属する写真データのうちの隣接する写真データどうしの最大距離dqよりも大きい（または、以上である）と判定された場合、追加部４３は、分岐ノードを親ノードとし、かつ、候補ノードと注目データpicnewに割り当てられる注目ノードNnewとを子ノードとする新たなノードNinを、現在のクラスタツリーに追加し、これにより、新たなクラスタツリーを生成する。
【０２１０】
一方、判定部４２において、候補ノードに対応する候補クラスタの間近写真データと注目データpicnewとの距離dnが、候補ノードに対応する候補クラスタに属する写真データのうちの隣接する写真データどうしの最大距離dqよりも大きくない（または、以上でない）と判定された場合、候補ノードを新たな分岐ノードとし、かつ候補ノードの子ノードを新たな候補ノードとし、距離算出部４１において、新たな候補ノードに対応する新たな候補クラスタの間近写真データと注目データpicnewとの距離dn、および新たな候補ノードに対応する新たな候補クラスタに属する写真データのうちの隣接する写真データどうしの最大距離dqを求めることと、判定部４２において、距離算出部４１によって求められた距離dnと最大距離dqとの大小関係を判定することとが繰り返される。
【０２１１】
そして、判定部４２において、距離dnが、最大距離dqよりも大きいと判定されると、追加部４３は、上述したように、分岐ノードを親ノードとし、かつ、候補ノードと注目データpicnewに割り当てられる注目ノードNnewとを子ノードとする新たなノードNinを、現在のクラスタツリーに追加し、これにより、新たなクラスタツリーを生成する。
【０２１２】
次に、図２０を参照して、図１９の分岐ノード検索処理部３１が行う、分岐ノードを検索する分岐ノード検索処理について説明する。
【０２１３】
図２０は、クラスタツリー記憶装置１４に記憶されている現在のクラスタツリーの一部を示している。
【０２１４】
ここで、分岐ノードを、Npと表す。この場合、分岐ノードNpが有する２つの子ノードのうちの左側の左ノードは、l(Np)と表され、右側の右ノードは、r(Np)と表される。
【０２１５】
分岐ノードNpは、上述したように、撮影日時順の対象写真データの並びにおいて、注目位置に配置された注目データpicnewの左右のうちの一方に隣接する最大のクラスタに対応するノード、または、注目データpicnewの他方に隣接する最大のクラスタに対応するノードを子ノードとするノードである。
【０２１６】
従って、注目位置に配置された注目データpicnewの左側に隣接する最大のクラスタは、分岐ノードNpの左ノードl(Np)に対応するクラスタClであり、注目位置に配置された注目データpicnewの右側に隣接する最大のクラスタは、分岐ノードNpの右ノードr(Np)に対応するクラスタCrである。
【０２１７】
ところで、クラスタツリーのあるノードNに包含されるノードのうちの最も右側に位置するリーフノードを、Rm(N)と表すとともに、最も左側に位置するリーフノードを、Lm(N)と表すこととすると、分岐ノードNpの左ノードl(Np)に包含されるノードのうちの最も右側に位置するノード（リーフノード）は、Rm(l(Np))と表すことができ、分岐ノードNpの右ノードr(Np)に包含されるノードのうちの最も左側に位置するノード（リーフノード）は、Lm(r(Np))と表すことができる。
【０２１８】
ここで、ノードRm(l(Np))は、分岐ノードNpの左ノードl(Np)に包含されるノードのうちの右端に位置するノード（リーフノード）であるので、以下、適宜、左側右端ノードRm(l(Np))という。同様に、ノードLm(r(Np))は、分岐ノードNpの右ノードr(Np)に包含されるノードのうちの左端に位置するノード（リーフノード）であるので、以下、適宜、右側左端ノードLm(r(Np))という。
【０２１９】
いま、左側右端ノードRm(l(Np))に割り当てられている写真データが写真データpic1であるとすると、注目データpicnewの左側に隣接するクラスタClに属する写真データの中で、最も右側に位置する写真データは、写真データpic1であり、この写真データpic1は、注目データの左側に隣接する。
【０２２０】
同様に、右側左端ノードLm(r(Np))に割り当てられている写真データが写真データpic2であるとすると、注目データpicnewの右側に隣接するクラスタCrに属する写真データの中で、最も左側に位置する写真データは、写真データpic2であり、この写真データpic2は、注目データの右側に隣接する。
【０２２１】
従って、あるリーフノードNに割り当てられている写真データの撮影日時を、t(N)と表すこととすると、左側右端ノードRm(l(Np))に割り当てられている写真データpic1の撮影日時t(Rm(l(Np)))、右側左端ノードLm(r(Np))に割り当てられている写真データpic2の撮影日時t(Lm(r(Np)))、および、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)は、式（７）を満たす。
【０２２２】
t(Rm(l(Np)))＜t(Nnew)＜t(Lm(r(Np)))
・・・（７）
【０２２３】
ここで、以下、説明を簡単にするため、階層的クラスタリングの対象とする対象写真データとなっている写真データの中で、撮影日時が同一の写真データは存在しないこととする。なお、撮影日時が同一の写真データが存在する場合には、式（７）における２つの不等号（＜）のうちのいずれか一方を、等しい場合を含む不等号（≦）とすればよい。
【０２２４】
分岐ノード検索部３１は、現在のクラスタツリーのノードを、ルートノードNrootから下位階層の方向に辿っていき、式（７）を満たすノードNpを検出して、分岐ノードNpとする。
【０２２５】
なお、分岐ノード検索部３１は、左側右端ノードRm(l(Np))に割り当てられている写真データpic1の撮影日時t(Rm(l(Np)))と、右側左端ノードLm(r(Np))に割り当てられている写真データpic2の撮影日時t(Lm(r(Np)))とを、それぞれ、クラスタツリー記憶装置１４に記憶されているクラスタツリー（のリーフノードRm(l(Np))に保持されている写真データpic1のメタデータと、リーフノードLm(r(Np))に保持されている写真データpic2のメタデータ）から認識する。また、分岐ノード検索部３１は、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)を、メタデータ読み出し部２０から供給される注目データpicnewのメタデータから認識する。
【０２２６】
次に、図２１乃至図２６を参照して、図１９のノード追加部３２が行う、注目ノードNnewを子ノードとする新たなノードNinをクラスタツリーに追加するノード追加処理について説明する。
【０２２７】
図２１は、分岐ノード検索部３１が注目データpicnewに対して求めた分岐ノードNpに包含されるノードで構成される、クラスタツリーの一部（部分木）を示している。
【０２２８】
上述したように、階層的クラスタリングでは、撮影日時順に並べた写真データの並びを維持しつつ、写真データをクラスタリングする。従って、写真データに割り当てられたリーフノードの並びも維持されるので、注目データpicnewに割り当てられた注目ノードNnewが、分岐ノードNpの左側右端ノードRm(l(Np))の左側に位置（移動）することはなく、右側左端ノードLm(r(Np))の右側に位置することもない。
【０２２９】
従って、注目ノードNnewが割り当てられた注目データpicnewは、必ず、分岐ノードNpに対応するクラスタに属する。
【０２３０】
また、分岐ノードNpに対応するクラスタは、その子ノードである左ノードl(Np)に対応するクラスタClと、右ノードr(Np)に対応するクラスタCrとを包含し、さらに、左ノードl(Np)の子ノードに対応するクラスタや、右ノードr(Np)の子ノードに対応するクラスタ等を包含する。
【０２３１】
ノード追加処理では、注目データpicnewに割り当てられた注目ノードNnewを子ノードとする新たなノードNinを、分岐ノードNpに包含されるノードのいずれかの子ノードとして追加することにより、分岐ノードNpに対応するクラスタに包含されるクラスタとして、新たなノードNinに対応するクラスタを追加し、これにより、その新たなノードNinに対応するクラスタに、注目データpicnewをクラスタリングする。
【０２３２】
そこで、ノード追加部３２（図１９）では、まず、距離算出部４１が、分岐ノード検索部３１からの分岐ノードNpの子ノードに対応するクラスタ、つまり、左ノードl(Np)に対応するクラスタClと、右ノードr(Np)に対応するクラスタCrとの中で、注目データpicnewと間近写真データとの距離が最も近いクラスタに対応するノードを、新たなノードNinの子ノードの候補である候補ノード、つまり、注目データpicnewが属するクラスタの候補となる候補クラスタに対応するノードである候補ノードとする。
【０２３３】
従って、図２１に示すように、左ノードl(Np)に対応するクラスタClの間近写真データと注目データpicnewとの距離をdlと表すとともに、右ノードr(Np)に対応するクラスタCrの間近写真データと注目データpicnewとの距離をdrと表すこととすると、距離dlが距離dr未満（または、以下）である場合には、クラスタClに対応する左ノードl(Np)が候補ノードとなり、距離dlが距離dr以上（または、より大）である場合には、クラスタCrに対応する右ノードr(Np)が候補ノードとなる。
【０２３４】
ここで、以下、適宜、候補ノードを、Nqと表す。
【０２３５】
また、左ノードl(Np)に対応するクラスタClの間近写真データは、左側右端ノード（リーフノード）Rm(l(Nq))に割り当てられている写真データ（図２１では写真データpic1）となり、右ノードr(Np)に対応するクラスタCrの間近写真データは、右側左端ノード（リーフノード）Lm(r(Nq))に割り当てられている写真データ（図２１では写真データpic2）となる。
【０２３６】
例えば、いま、距離dlが距離drよりも短いとすると、距離算出部４１は、クラスタClに対応する左ノードl(Np)を候補ノードNqとして、図２２左側に示すように、その候補ノードNqに対応する候補クラスタCqの間近写真データと注目データpicnewとの距離dnと、候補ノードNqに対応する候補クラスタCqに属する写真データ（クラスタリングツリーによって既にクラスタリングされている写真データ）のうちの隣接する写真データどうしの距離の最大値である最大距離dqとを求める。
【０２３７】
ここで、いまの場合、候補ノードNqは、分岐ノード検索部３１で得られた分岐ノードNpの左ノードl(Np)である。従って、候補ノードNqに対応するクラスタCqは、分岐ノード検索部３１で得られた分岐ノードNpの左ノードl(Np)に対応するクラスタClであり、さらに、候補クラスタCqの間近写真データと注目データpicnewとの距離dnは、左ノードl(Np)に対応するクラスタClの間近写真データと注目データpicnewとの距離dnに等しい。
【０２３８】
上述したように、距離算出部４１は、候補ノードNqに対応する候補クラスタCqに属する写真データのうちの隣接する写真データどうしの距離の最大値である最大距離dqを求めるが、この最大距離dqは、図２２左側に示すように、候補ノードNqの左ノードl(Nq)に対応するクラスタと、候補ノードNqの右ノードr(Nq)に対応するクラスタとの式（５）により計算される距離dC(l(Nq),r(Nq))、つまり、候補ノードNqの左側右端ノード（リーフノード）Rm(l(Nq))に割り当てられている写真データと、候補ノードNqの右側左端ノード（リーフノード）Lm(r(Nq))に割り当てられている写真データとの距離となる。
【０２３９】
ここで、あるノードNに対応するクラスタに属する写真データのうちの隣接する写真データどうしの距離の最大値（最大距離）が、そのノードNの左側右端ノードRm(l(N))に割り当てられている写真データと、ノードNの右側左端ノードLm(r(N))に割り当てられている写真データとの距離となることについては、後述する。
【０２４０】
以上のようにして求められた距離dnと最大距離dqとの大小関係が、dq＜dn（またはdq≦dn）である場合、図２２右側に示すように、ノード追加部３２の追加部４３は、分岐ノードNpと候補ノードNqとの間に、分岐ノードNpを親ノードとするとともに候補ノードNqおよび注目ノードNnewを子ノードとする新たなノードNinを追加し、これにより、新たなクラスタツリーを生成する。
【０２４１】
ここで、以上のように新たなノードNinが追加されることにより、候補ノードNqと注目ノードNnewとは、新たなノードNinの子ノードとなる。
【０２４２】
そして、新たなノードNinに対応するクラスタCinには、新たなノードNinの１つの子ノードである候補ノードNqに属する写真データと、他の１つの子ノードである注目ノードNnewに属する注目データpicnewとが属する。
【０２４３】
また、候補クラスタCqの間近写真データと注目データpicnewとの距離dnは、候補クラスタCqに属する写真データのうちの、撮影日時が注目データpicnewに最も近い写真データ（注目データpicnewに隣接する写真データ）と、注目データpicnewとの式（２）により計算される距離dpic()であるから、図２２においては、注目データpicnewの左隣の写真データpic1と、注目データpicnewとの距離である。
【０２４４】
そして、距離dnと最大距離dqとの大小関係が、dq＜dn（またはdq≦dn）である場合に、図２２右側に示したように、新たなノードNinが追加されるので、新たなノードNinに対応するクラスタCinに属する写真データのうちの隣接する写真データどうしの距離の最大値（最大距離）は、注目データpicnewの左隣の写真データpic1と、注目データpicnewとの距離となる。
【０２４５】
新たなノードNinから見れば、注目データpicnewの左隣の写真データpic1は、新たなノードNinの左側右端ノードRm(l(Nin))に割り当てられている写真データであり、注目データpicnewは、新たなノードNinの右側左端ノードLm(r(Nin))に割り当てられている写真データであるから、新たなノードNinに対応するクラスタCinに属する写真データのうちの写真データどうしの距離の最大値（最大距離）は、新たなノードNinの左側右端ノードRm(l(Nin))に割り当てられている写真データと、新たなノードNinの右側左端ノードLm(r(Nin))に割り当てられている写真データとの距離となる。
【０２４６】
つまり、上述したように、あるノードNに対応するクラスタに属する写真データのうちの写真データどうしの距離の最大値（最大距離）は、ノードNの左側右端ノードRm(l(N))に割り当てられている写真データと、ノードNの右側左端ノードLm(r(N))に割り当てられている写真データとの距離となる。
【０２４７】
なお、ノードNの左側右端ノードRm(l(N))に割り当てられている写真データは、そのノードNの左ノードl(N)に対応するクラスタに属する写真データの中で、撮影日時が、ノードNの右ノードr(N)に対応するクラスタに属する写真データの撮影日時と最も近い写真である。同様に、ノードNの右側左端ノードLm(r(N))に割り当てられている写真データは、そのノードNの右ノードr(N)に対応するクラスタに属する写真データの中で、撮影日時が、ノードNの左ノードl(N)に対応するクラスタに属する写真データの撮影日時と最も近い写真データである。
【０２４８】
従って、２つのクラスタどうしの距離を、その２つのクラスタにおける撮影日時が最も近い写真どうしの距離として定義する上述の式（５）によれば、ノードNの左側右端ノードRm(l(N))に割り当てられている写真データと、ノードNの右側左端ノードLm(r(N))に割り当てられている写真データとの距離は、ノードNの左ノードl(N)に対応するクラスタと、ノードNの右ノードr(N)に対応するクラスタとの距離に等しい。
【０２４９】
そして、以上から、ノードNに対応するクラスタに属する写真データのうちの写真データどうしの距離の最大値（最大距離）は、ノードNの左ノードl(N)に対応するクラスタと、ノードNの右ノードr(N)に対応するクラスタとの距離に等しい。
【０２５０】
一方、候補ノードNqに対応する候補クラスタCqの間近写真データと注目データpicnewとの距離dnと、候補ノードNqに対応する候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqとの大小関係が、dq≧dn（またはdq＞dn）である場合、図２３に示すように、ノード追加部３２の距離計算部４１は、候補ノードNqを新たな分岐ノードNpとし、かつ候補ノードNqの２つの子ノードのうちの右ノードr(Nq)を新たな候補ノードNqとする、分岐ノードNpおよび候補ノードNqの更新を行う。
【０２５１】
さらに、距離計算部４１は、図２２で説明したように、新たな候補ノードNqに対応する新たな候補クラスタCqの間近写真データと注目データpicnewとの距離dn、および新たな候補ノードNqに対応する新たな候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqを求める、距離dnおよび最大距離dqの算出を行う。
【０２５２】
距離計算部４１は、分岐ノードNpおよび候補ノードNqの更新と、距離dnおよび最大距離dqの算出とを、距離dnと最大距離dqとの大小関係が、dq＜dnとなるまで繰り返す。
【０２５３】
そして、距離dnと最大距離dqとの大小関係が、dq＜dnとなると、図２２で説明したように、追加部４３は、分岐ノードNpと候補ノードNqとの間に、分岐ノードNpを親ノードとするとともに候補ノードNqおよび注目ノードNnewを子ノードとする新たなノードNinを追加し、これにより、新たなクラスタツリーを生成する。
【０２５４】
即ち、例えば、分岐ノードNpおよび候補ノードNqの更新が図２３に示したように行われた後に求められた距離dnと最大距離dqとの大小関係が、dq＜dnとなった場合、図２４に示すように、新たな分岐ノードNpと新たな候補ノードNqとの間に、新たな分岐ノードNpを親ノードとするとともに新たな候補ノードNqおよび注目ノードNnewを子ノードとする新たなノードNinが追加され、これにより、新たなクラスタツリーが生成される。
【０２５５】
従って、ノード追加部３２では、注目位置に配置された注目データpicnewに隣接するクラスタ（候補クラスタ）に対応するノードを、上位階層から下位階層に向かって辿ることにより、注目データpicnewに隣接するクラスタ（候補クラスタ）に属する隣接する写真データどうしの最大距離dqが、注目データに隣接するクラスタ（候補クラスタ）の間近写真データと注目データpicnewとの距離dnより短い最大のクラスタ（候補クラスタ）に対応するノード（候補ノード）を検出し、そのノードと注目ノードNnewを子ノードとする新たなノードNinが追加される。
【０２５６】
なお、図２１に示した、右ノードr(Np)に対応するクラスタCrの間近写真データと注目データpicnewとの距離drが、左ノードl(Np)に対応するクラスタClの間近写真データと注目データpicnewとの距離dlより短い（または、以下である）場合、クラスタCrに対応する右ノードr(Np)を候補ノードNqとして、上述の、クラスタClに対応する左ノードl(Np)を候補ノードNqとした場合と同様の処理が行われる。但し、クラスタCrに対応する右ノードr(Np)を候補ノードNqとして行われる処理は、上述の、クラスタClに対応する左ノードl(Np)を候補ノードNqとして行われる処理の説明の「左」と「右」とを入れ換えた処理となる。
【０２５７】
また、例えば、図２５に示すように、注目データpicnewが、撮影日時順に並んだ写真データの並びの右端に位置する場合、即ち、注目データpicnewの撮影日時が最も新しい場合、注目位置に配置された注目データpicnewの右側に隣接するクラスタは存在せず、注目データpicnewの左側に隣接する最大のクラスタは、ルートノードに対応するクラスタとなる。この場合、ルートノードを左ノードとして有する仮想的なノードを分岐ノードNpとするとともに、ルートノードを候補ノードNqとして、ノード追加処理を行うようにすればよい。
【０２５８】
さらに、同様に、例えば、図２６に示すように、注目データpicnewが、撮影日時順に並んだ写真データの並びの左端に位置する場合、即ち、注目データpicnewの撮影日時が最も古い場合、注目位置に配置された注目データpicnewの左側に隣接するクラスタは存在せず、注目データpicnewの右側に隣接する最大のクラスタは、ルートノードに対応するクラスタとなる。この場合、ルートノードを右ノードとして有する仮想的なノードを分岐ノードNpとするとともに、ルートノードを候補ノードNqとして、ノード追加処理を行うようにすればよい。
【０２５９】
次に、図２７を参照して、図１９の木構造処理部２２が図１８のステップＳ１２で行う木構造処理について説明する。
【０２６０】
木構造処理では、まず最初に、ステップＳ２１において、分岐ノード検索部３１が、メタデータ読み出し部２０から供給される注目データpicnewのメタデータと、クラスタツリー記憶装置１４に記憶されたクラスタツリーとに基づき、分岐ノードを検索する分岐ノード検索処理を行い、その結果得られる分岐ノードを、ノード追加部３２に供給して、ステップＳ２２に進む。
【０２６１】
ステップＳ２２では、ノード追加部３２が、分岐ノード検索部３１から供給される分岐ノードと、メタデータ読み出し部２０から供給される注目データpicnewのメタデータに基づき、注目データpicnewに割り当てられる注目ノードNnewを子ノードとする新たなノードNinを、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加することにより、新たなクラスタツリーを生成するノード追加処理を行って、ステップＳ２３に進む。
【０２６２】
ステップＳ２３では、ノード追加部３２が、ステップＳ２２で生成した新たなクラスタツリーによって、クラスタツリー記憶装置１４に記憶されたクラスタツリーを更新し、リターンする（木構造処理を終了する）。
【０２６３】
次に、図２８を参照して、図１９の木構造処理部２２を構成する分岐ノード検索部３１が図２７のステップＳ２１で行う分岐ノード検索処理について説明する。
【０２６４】
分岐ノード検索部３１は、まず最初に、ステップＳ４１において、現在のクラスタツリー（クラスタツリー記憶装置１４に記憶されているクラスタツリー）のルートノードを、仮の分岐ノードNpとして（分岐ノードNpを表す変数にルートノード（を表す情報）をセットして）、ステップＳ４２に進む。
【０２６５】
ステップＳ４２では、分岐ノード検索部３１は、注目データpicnewにノードを割り当て（注目データpicnewを表すノード（としての変数）を生成し）、その割り当てたノード（注目ノード）に、メタデータ読み出し部２０から供給される注目データpicnewのメタデータを保持させる。
【０２６６】
さらに、ステップＳ４２では、分岐ノード検索部３１は、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)を、その注目ノードNnewが保持しているメタデータから認識するとともに、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))を、その左側右端ノードRm(l(Np))が保持しているメタデータから認識し、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))よりも古いかどうか、即ち、式t(Nnew)＜t(Rm(l(Np)))が満たされるかどうかを判定する。
【０２６７】
ステップＳ４２において、撮影日時t(Nnew)が、撮影日時t(Rm(l(Np)))よりも古いと判定された場合、即ち、図２０に示したように、分岐ノードNpの左側右端ノードRm(l(Np))（に割り当てられた写真データ）は、注目ノードNnew（に割り当てられた注目データpicnew）の左隣に位置しなければならないのにもかかわらず、仮の分岐ノードNpの左側右端ノードRm(l(Np))が、注目ノードNnewの右側に位置する場合、仮の分岐ノードNpは、注目ノードNnew（に割り当てられた注目データpicnew）に対する分岐ノードNpではないので、ステップＳ４３に進み、分岐ノード検索部３１は、仮の分岐ノードNpを、クラスタツリーにおいて左側右端ノードRm(l(Np))がより左側に位置するノードに更新する。
【０２６８】
即ち、ステップＳ４３において、分岐ノード検索部３１は、いま仮の分岐ノードNpとなっているノードの左ノードl(Np)を、新たな仮の分岐ノードNpとする。そして、分岐ノード検索部３１は、ステップＳ４３からステップＳ４１に戻り、以下、同様の処理を繰り返す。
【０２６９】
一方、撮影日時t(Nnew)が、撮影日時t(Rm(l(Np)))よりも古くないと判定された場合、即ち、仮の分岐ノードNpの左側右端ノードRm(l(Np))が、注目ノードNnewの右側に位置しない場合、ステップＳ４４に進み、分岐ノード検索部３１は、仮の分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データの撮影日時t(Lm(r(Np)))を、その右側左端ノードLm(r(Np))が保持しているメタデータから認識し、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データの撮影日時t(Lm(r(Np)))よりも新しいかどうか、即ち、式t(Lm(r(Np)))＜t(Nnew)が満たされるかどうかを判定する。
【０２７０】
ステップＳ４４において、撮影日時t(Nnew)が、撮影日時t(Lm(r(Np)))よりも新しいと判定された場合、即ち、図２０に示したように、分岐ノードNpの右側左端ノードLm(r(Np))（に割り当てられた写真データ）は、注目ノードNnew（に割り当てられた注目データpicnew）の右隣に位置しなければならないのにもかかわらず、仮の分岐ノードNpの右側左端ノードLm(r(Np))が、注目ノードNnewの左側に位置する場合、仮の分岐ノードNpは、注目ノードNnew（に割り当てられた注目データpicnew）に対する分岐ノードNpではないので、ステップＳ４５に進み、分岐ノード検索部３１は、仮の分岐ノードNpを、クラスタツリーにおいて右側左端ノードLm(r(Np))がより右側に位置するノードに更新する。
【０２７１】
即ち、ステップＳ４５において、分岐ノード検索部３１は、いま仮の分岐ノードNpとなっているノードの右ノードr(Np)を、新たな仮の分岐ノードNpとする。そして、分岐ノード検索部３１は、ステップＳ４５からステップＳ４２に戻り、以下、同様の処理を繰り返す。
【０２７２】
一方、ステップＳ４４において、撮影日時t(Nnew)が、撮影日時t(Lm(r(Np)))よりも新しくないと判定された場合、即ち、撮影日時t(Nnew)が、撮影日時t(Rm(l(Np)))よりも古くなく、かつ、撮影日時t(Lm(r(Np)))よりも新しくなく、式（７）を満たす場合、ステップＳ４６に進み、分岐ノード検索部２１は、いま仮の分岐ノードNpとされているノードを、注目ノードNnewに対する分岐ノードNpに確定し、ノード追加部３２に供給してリターンする（分岐ノード検索処理を終了する）。
【０２７３】
次に、図２９のフローチャートを参照して、図１９の木構造処理部２２を構成するノード追加部３２が図２７のステップＳ２２で行うノード追加処理について説明する。
【０２７４】
ノード追加部３２（図１９）では、まず最初に、ステップＳ５１において、距離算出部４１が、分岐ノード検索部３１からの分岐ノードNpと、クラスタツリー記憶装置１４に記憶されたクラスタツリーとに基づき、図２１に示した、分岐ノードNpの左ノードl(Np)に対応するクラスタClの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離（以下、適宜、左クラスタ距離という）dl、および、分岐ノードNpの右ノードr(Np)に対応するクラスタCrの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離（以下、適宜、右クラスタ距離という）drを求め、ステップＳ５２に進む。
【０２７５】
ステップＳ５２において、距離算出部４１は、左クラスタ距離dlが、右クラスタ距離dr未満（または以下）であるかどうかを判定する。
【０２７６】
ステップＳ５２において、左クラスタ距離dlが、右クラスタ距離dr未満であると判定された場合、ステップＳ６１に進み、左クラスタ距離dlが、右クラスタ距離dr未満でないと判定された場合、ステップＳ７１に進む。
【０２７７】
ステップＳ６１では、距離算出部４１は、候補ノードNqを、分岐ノードNpの左ノードl(Np)とし、ステップＳ６２に進む。ステップＳ６２において、距離算出部４１は、候補ノードNqに対応する候補クラスタCqの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離dn、即ち、図２２乃至図２４で説明したように、候補クラスタCqに属する写真データのうちの右端の写真データであり、注目データpicnewの左隣の写真データでもある写真データと注目データpicnewとの距離dnを求め、判定部４２に供給して、ステップＳ６３に進む。
【０２７８】
ステップＳ６３では、距離算出部４１は、候補ノードNqに対応する候補クラスタCqに属する写真データ（クラスタリングツリーによって既にクラスタリングされている写真データ）のうちの隣接する写真データどうしの距離の最大値である最大距離dqを求め、判定部４２に供給して、ステップＳ６４に進む。
【０２７９】
ステップＳ６４では、判定部４２が、距離算出部４１からの、注目データpicnewと候補クラスタCqの間近写真データとの距離dnと、候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqとの大小関係を判定する。
【０２８０】
ステップＳ６４において、注目データpicnewと候補クラスタCqの間近写真データとの距離dnが、候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqより大（または、以上）でないと判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと候補クラスタCqの間近写真データとの距離dnより大（または以上）の距離がある場合、注目データpicnewは、候補クラスタCqに属するので、距離算出部４１は、さらに、注目データpicnewが、候補クラスタCqが包含する粒度の小さいクラスタに属するかどうかを調査するために、ステップＳ６５に進み、分岐ノードNpおよび候補ノードNqを更新する。
【０２８１】
即ち、ステップＳ６５では、距離算出部４１は、候補ノードNqを新たな分岐ノードNpとし、かつ候補ノードNqの２つの子ノードのうちの右ノードr(Nq)を新たな候補ノードNqとする、分岐ノードNpおよび候補ノードNqの更新を行う。
【０２８２】
距離算出部４１は、ステップＳ６５において、分岐ノードNpおよび候補ノードNqの更新を行うと、ステップＳ６２に戻り、以下、同様の処理が繰り返される。
【０２８３】
なお、この場合、ステップＳ６２では、距離算出部４１は、ステップＳ６５での更新後の候補ノードNqに対応する候補クラスタCqの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離dnを求めることになるが、ステップＳ６１で左ノードl(Np)が候補ノードNqとされた場合の、その候補ノードNqに対応する候補クラスタＣqの間近写真データは、注目データpicnewの左隣の写真データであり、分岐ノードNpおよび候補ノードNqの更新が行われても、注目データpicnewの左隣の写真データは変わらない。即ち、距離dnは、注目データpicnewの左隣の写真データと注目データpicnewとの距離であり、注目データpicnewの左隣の写真データは、分岐ノードNpおよび候補ノードNqの更新が行われても変わらないから、距離dnも、分岐ノードNpおよび候補ノードNqの更新が行われても変わらない。
【０２８４】
従って、ある注目データpicnewについて行われる、２回目以降のステップＳ６２の距離dnを求める処理は、スキップすることができる。
【０２８５】
一方、ステップＳ６４において、注目データpicnewと候補クラスタCqの間近写真データとの距離dnが、候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqより大（または、以上）であると判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと候補クラスタCqの間近写真データとの距離dnより大の距離がない場合、注目データpicnewは、いま候補ノードNqとなっているノードに対応するクラスタ（いまの候補クラスタCq）に属しないので、即ち、注目データpicnewは、前回のステップＳ６５で分岐ノードNpおよび候補ノードNqの更新が行われる直前に候補ノードNqとなっていたノードに対応するクラスタには属するが、いま候補ノードNqとなっているノードに対応するクラスタに属しないので、ステップＳ５３に進み、追加部４３は、注目データpicnewが、前回のステップＳ６５で分岐ノードNpおよび候補ノードNqの更新が行われる直前に候補ノードNqとなっていたノードに対応するクラスタには属するが、いま候補ノードNqとなっているノードに対応するクラスタに属しないように、新たなノードNinを追加する。
【０２８６】
即ち、ステップＳ５３では、追加部４３は、現在のクラスタツリーの、分岐ノードNpと候補ノードNqとの間に、分岐ノードNpを親ノードとするとともに候補ノードNqおよび注目ノードNnewを子ノードとする新たなノードNinを追加することにより、新たなクラスタツリーを生成し、リターンする（ノード追加処理を終了する）。
【０２８７】
一方、ステップＳ５２において、左クラスタ距離dlが、右クラスタ距離dr未満でないと判定され、ステップＳ７１に進んだ場合は、距離算出部４１は、候補ノードNqを、分岐ノードNpの右ノードr(Np)とし、ステップＳ７２に進む。ステップＳ７２において、距離算出部４１は、候補ノードNqに対応する候補クラスタCqの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離dnを求め、判定部４２に供給して、ステップＳ７３に進む。
【０２８８】
ここで、ステップＳ７１で右ノードr(Np)が候補ノードNqとされた場合の、その候補ノードNqに対応する候補クラスタCqの間近写真データは、候補クラスタCqに属する写真データのうちの左端の写真データであり、注目データpicnewの右隣の写真データでもある。
【０２８９】
ステップＳ７３では、距離算出部４１は、候補ノードNqに対応する候補クラスタCqに属する写真データ（クラスタリングツリーによって既にクラスタリングされている写真データ）のうちの隣接する写真データどうしの距離の最大値である最大距離dqを求め、判定部４２に供給して、ステップＳ７４に進む。
【０２９０】
ステップＳ７４では、判定部４２が、距離算出部４１からの、注目データpicnewと候補クラスタCqの間近写真データとの距離dnと、候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqとの大小関係を判定する。
【０２９１】
ステップＳ７４において、注目データpicnewと候補クラスタCqの間近写真データとの距離dnが、候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqより大（または、以上）でないと判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと候補クラスタCqの間近写真データとの距離dnより大（または以上）の距離がある場合、注目データpicnewは、候補クラスタCqに属するので、距離算出部４１は、さらに、注目データpicnewが、候補クラスタCqが包含する粒度が小さいクラスタに属するかどうかを調査するために、ステップＳ７５に進み、分岐ノードNpおよび候補ノードNqを更新する。
【０２９２】
即ち、ステップＳ７５では、距離算出部４１は、候補ノードNqを新たな分岐ノードNpとし、かつ候補ノードNqの２つの子ノードのうちの左ノードl(Nq)を新たな候補ノードNqとする、分岐ノードNpおよび候補ノードNqの更新を行う。
【０２９３】
距離算出部４１は、ステップＳ７５において、分岐ノードNpおよび候補ノードNqの更新を行うと、ステップＳ７２に戻り、以下、同様の処理が繰り返される。
【０２９４】
なお、この場合、ステップＳ７２では、距離算出部４１は、ステップＳ７５での更新後の候補ノードNqに対応する候補クラスタCqの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離dnを求めることになるが、ステップＳ７１で右ノードr(Np)が候補ノードNqとされた場合の、その候補ノードNqに対応する候補クラスタCqの間近写真データは、注目データpicnewの右隣の写真データであり、分岐ノードNpおよび候補ノードNqの更新が行われても、注目データpicnewの右隣の写真データは変わらない。即ち、距離dnは、注目データpicnewの右隣の写真データと注目データpicnewとの距離であり、注目データpicnewの右隣の写真データは、分岐ノードNpおよび候補ノードNqの更新が行われても変わらないから、距離dnも、分岐ノードNpおよび候補ノードNqの更新が行われても変わらない。
【０２９５】
従って、ある注目データpicnewについて行われる、２回目以降のステップＳ７２の距離dnを求める処理は、スキップすることができる。
【０２９６】
一方、注目データpicnewとその右隣の写真データ（候補クラスタCqの間近写真データ）との距離dnが、候補クラスタCqに属する写真データのうちの隣接する写真データどうしの最大距離dqより大（または、以上）であると判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewとその右隣の写真データ、つまり、候補クラスタCqの間近写真データとの距離dnより大の距離がない場合、注目データpicnewは、いま候補ノードNqとなっているノードに対応するクラスタ（いまの候補クラスタCq）に属しないので、即ち、注目データpicnewは、前回のステップＳ７５で分岐ノードNpおよび候補ノードNqの更新が行われる直前に候補ノードNqとなっていたノードに対応するクラスタには属するが、いま候補ノードNqとなっているノードに対応するクラスタに属しないので、ステップＳ５３に進み、追加部４３は、注目データpicnewが、前回のステップＳ７５で分岐ノードNpおよび候補ノードNqの更新が行われる直前に候補ノードNqとなっていたノードに対応するクラスタには属するが、いま候補ノードNqとなっているノードに対応するクラスタに属しないように、新たなノードNinを追加する。
【０２９７】
即ち、ステップＳ５３では、追加部４３は、現在のクラスタツリーの、分岐ノードNpと候補ノードNqとの間に、分岐ノードNpを親ノードとするとともに候補ノードNqおよび注目ノードNnewを子ノードとする新たなノードNinを追加することにより、新たなクラスタツリーを生成し、リターンする（ノード追加処理を終了する）。
【０２９８】
次に、図３０乃至図３５のフローチャートを参照して、図１のクラスタリング装置１３が図１７のステップＳ５で行うクラスタリング処理の他の実施の形態について説明する。
【０２９９】
クラスタリング装置１３は、データ記憶装置１２に記憶された注目データpicnewのメタデータを読み出すとともに、注目データpicnewに割り当てる注目ノードを生成する。さらに、クラスタリング装置１３は、注目ノードNnewを表す変数に、注目データpicnewを識別する情報と、データ記憶装置１２に記憶されている注目データpicnewのメタデータを保持させ、ステップＳ１０１において、クラスタツリー記憶装置１４に記憶されている現在のクラスタツリーのノード（リーフノード）に割り当てられている写真データの数を判定する。
【０３００】
ステップＳ１０１において、現在のクラスタツリーのノードに割り当てられている写真データの数が０枚であると判定された場合、即ち、ステップＳ１０２に進み、クラスタリング装置１３は、クラスタツリーのルートノードNrootを、注目ノードNnewとする新たなクラスタツリーを生成し（ルートノードNrootを表す変数に、注目ノードNnewを表す変数の内容をコピーし）、クラスタツリー記憶装置１４に記憶させて（上書きして）、リターンする（クラスタリング処理を終了する）。
【０３０１】
また、ステップＳ１０１において、現在のクラスタツリーのノードに割り当てられている写真データの数が１枚であると判定された場合、即ち、クラスタツリーが、ルートノードNrootだけで構成され、そのルートノードNrootに１枚の写真データが割り当てられているだけの状態になっている場合、ステップＳ１０３に進み、クラスタリング装置１０３は、クラスタツリーのルートノードNrootに割り当てられている写真データの撮影日時t(Nroot)を、ルートノードNrootに保持されているメタデータから認識するとともに、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)を、注目ノードNnewに保持されているメタデータから認識し、ルートノードNrootに割り当てられている写真データの撮影日時t(Nroot)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかを判定する。
【０３０２】
ステップＳ１０３において、ルートノードNrootに割り当てられている写真データの撮影日時t(Nroot)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いと判定された場合、即ち、ルートノードNrootに割り当てられている写真データが、注目データpicnewよりも時間的に前に撮影された写真データである場合、ステップＳ１０４に進み、クラスタリング装置１３は、ルートノードNrootの左ノードl(Nroot)を現在のルートノードNrootとし、かつ、ルートノードNrootの右ノードr(Nroot)を注目ノードNnewとする新たなクラスタツリーを生成し、クラスタツリー記憶装置１４に記憶させて、リターンする。
【０３０３】
また、ステップＳ１０３において、ルートノードNrootに割り当てられている写真データの撮影日時t(Nroot)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古くないと判定された場合、即ち、ルートノードNrootに割り当てられている写真データが、注目データpicnewよりも時間的に後（または同時）に撮影された写真データである場合、ステップＳ１０５に進み、クラスタリング装置１３は、ルートノードNrootの右ノードr(Nroot)を現在のルートノードNrootとし、かつ、ルートノードNrootの左ノードl(Nroot)を注目ノードNnewとする新たなクラスタツリーを生成し、クラスタツリー記憶装置１４に記憶させて、リターンする。
【０３０４】
一方、ステップＳ１０１において、現在のクラスタツリーのノードに割り当てられている写真データの数が２枚以上であると判定された場合、ステップＳ１０６に進み、クラスタリング装置１３は、現在のクラスタツリーのルートノードNrootが包含するノードのうちの右端にあるノードRm(Nroot)（以下、適宜、右端ノードRm(Nroot)という）を求める。
【０３０５】
ここで、ルートノードNrootが包含するノードのうちの右端ノードRm(Nroot)は、ルートノードNrootを引数とする関数Rm(Nroot)を呼び出すことによって求められる。
【０３０６】
ここで、図３１のフローチャートを参照して、クラスタツリーのあるノードNが包含するノードのうちの右端ノードRm(N)を求める、ノードNを引数とする関数Rm(N)の処理を説明する。
【０３０７】
クラスタリング装置１３は、ステップＳ１３１において、クラスタツリーのノードNに対応するクラスタにクラスタリングされている（属する）写真データの数が１枚であるかどうかを判定する。
【０３０８】
ステップＳ１３１において、クラスタツリーのノードNに対応するクラスタにクラスタリングされている写真データの数が１枚でないと判定された場合、即ち、ノードNがリーフノードでない場合、ステップＳ１３２に進み、クラスタリング装置１３は、ノードNを、ノードNの右ノードr(N)に更新して、ステップＳ１３１に戻り、以下、同様の処理を繰り返す。
【０３０９】
そして、ステップＳ１３１において、クラスタツリーのノードNに対応するクラスタにクラスタリングされている写真データの数が１枚であると判定された場合、即ち、ノードNがリーフノードである場合、クラスタリング装置１３は、関数Rm(N)の値（戻り値）として、ノードNを返して処理（関数Rm(N)の処理）を終了する。
【０３１０】
図３０に戻り、クラスタリング装置１３は、上述したように、ステップＳ１０６において、現在のクラスタツリーのルートノードNrootが包含するノードのうちの右端ノードRm(Nroot)、つまり、クラスタツリーの右端のリーフノードRm(Nroot)を求めると、さらに、その右端ノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかを判定する。
【０３１１】
ここで、現在のクラスタツリーのルートノードNrootが包含するノードのうちの右端ノードRm(Nroot)に割り当てられている写真データは、現在のクラスタツリーによってクラスタリングされている写真データの中で最新の写真データである。
【０３１２】
ステップＳ１０６において、右端ノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いと判定された場合、即ち、現在のクラスタツリーによってクラスタリングされている写真データと、注目データpicnewとをあわせた、階層的クラスタリングの対象となる写真データ（対象写真データ）の中で、注目データpicnewが最新の写真データである場合、ステップＳ１０８に進む。
【０３１３】
また、ステップＳ１０６において、右端ノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古くないと判定された場合、即ち、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、現在のクラスタツリーによってクラスタリングされている写真データのうちの最新の写真データの撮影日時t(Rm(Nroot))よりも古い場合、ステップＳ１０７に進み、クラスタリング装置１３は、現在のクラスタツリーのルートノードNrootが包含するノードのうちの左端にあるノードLm(Nroot)（以下、適宜、左端ノードLm(Nroot)という）を求める。
【０３１４】
ここで、ルートノードNrootが包含するノードのうちの左端ノードLm(Nroot)は、ルートノードNrootを引数とする関数Lm(Nroot)を呼び出すことによって求められる。
【０３１５】
ここで、図３２のフローチャートを参照して、クラスタツリーのあるノードNが包含するノードのうちの左端ノードLm(N)を求める、ノードNを引数とする関数Rm(N)の処理を説明する。
【０３１６】
クラスタリング装置１３は、ステップＳ１４１において、クラスタツリーのノードNに対応するクラスタにクラスタリングされている（属する）写真データの数が１枚であるかどうかを判定する。
【０３１７】
ステップＳ１４１において、クラスタツリーのノードNに対応するクラスタにクラスタリングされている写真データの数が１枚でないと判定された場合、即ち、ノードNがリーフノードでない場合、ステップＳ１４２に進み、クラスタリング装置１３は、ノードNを、ノードNの左ノードl(N)に更新して、ステップＳ１４１に戻り、以下、同様の処理を繰り返す。
【０３１８】
そして、ステップＳ１４１において、クラスタツリーのノードNに対応するクラスタにクラスタリングされている写真データの数が１枚であると判定された場合、即ち、ノードNがリーフノードである場合、クラスタリング装置１３は、関数Lm(N)の戻り値として、ノードNを返して処理（関数Lm(N)の処理）を終了する。
【０３１９】
図３０に戻り、クラスタリング装置１３は、ステップＳ１０７において、現在のクラスタツリーのルートノードNrootが包含するノードのうちの左端ノードLm(Nroot)、つまり、クラスタツリーの左端のリーフノードLm(Nroot)を求めると、さらに、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、左端ノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))よりも古いかどうかを判定する。
【０３２０】
ここで、現在のクラスタツリーのルートノードNrootが包含するノードのうちの左端ノードLm(Nroot)に割り当てられている写真データは、現在のクラスタツリーによってクラスタリングされている写真データの中で最も古い写真データである。
【０３２１】
ステップＳ１０７において、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、左端ノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))よりも古いと判定された場合、即ち、現在のクラスタツリーによってクラスタリングされている写真データと、注目データpicnewとをあわせた対象写真データの中で、注目データpicnewが最も古い写真データである場合、ステップＳ１１１に進む。
【０３２２】
また、ステップＳ１０７において、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、左端ノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))よりも古くないと判定された場合、即ち、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、現在のクラスタツリーによってクラスタリングされている写真データのうちの最も古い写真データの撮影日時t(Lm(Nroot))よりも新しい場合、ステップＳ１１２に進む。
【０３２３】
ここで、ステップＳ１０６およびＳ１０７の処理によれば、現在のクラスタツリーによってクラスタリングされている写真データと、注目データpicnewとをあわせた対象写真データを撮影日時順に（左から右に）並べたときに、注目データpicnewが、最左端に配置されるのか、最右端に配置されるのか、または最左端でもなく最右端でもない位置に配置されるのかが判定される。そして、注目データpicnewが、最右端に配置される場合には、ステップＳ１０６からステップＳ１０８に、注目データpicnewが、最左端に配置される場合には、ステップＳ１０７からステップＳ１１１に、注目データpicnewが、最左端でもなく最右端でもない位置に配置される場合には、ステップＳ１０７からステップＳ１１２に、それぞれ進み、以下、後述する処理が行われる。
【０３２４】
即ち、注目データpicnewが、対象写真データの中で最新の写真データであり、対象写真データを撮影日時順に並べた場合に、注目データpicnewが最右端に配置されるときには、ステップＳ１０６からステップＳ１０８に進み、クラスタリング装置１３は、ルートノードNrootと注目ノードNnew（を表す変数）を引数として、関数IRM(Nroot,Nnew)を呼び出し、その戻り値（関数IRM(Nroot,Nnew)の値）を、変数TMPにセットする。
【０３２５】
ここで、関数IRM(Nq,Nnew)は、候補ノードNqと注目ノードNnewとを引数とする関数であり、この関数IRM(Nq,Nnew)によれば、例えば、図２５に示したような、分岐ノードNpの左ノードl(Np)が候補ノードNqとなる場合を対象として、注目ノードNnewを子ノードとする新たなノードNinをクラスタツリーに追加する処理が行われる。
【０３２６】
即ち、図３３は、関数IRM(Nq,Nnew)の処理を説明するフローチャートである。
【０３２７】
まず、ステップＳ１５１において、クラスタリング装置１３は、関数IRM(Nq,Nnew)の引数となっている候補ノードNqを左ノードl(Np)とするノードを分岐ノードNpとして、ステップＳ１５２に進み、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの距離の最大値（最大距離）dqを求める。
【０３２８】
ここで、上述したように、あるノードNに対応するクラスタにクラスタリングされている隣接する写真データどうしの最大距離は、ノードNの左ノードl(N)に対応するクラスタと、ノードNの右ノードr(N)に対応するクラスタとの距離である。さらに、上述したように、あるクラスタCiと他のクラスタCjとの距離は、撮影日時の差が最小の、クラスタCiにクラスタリングされている写真データと、他のクラスタCjにクラスタリングされている写真データとの距離である。
【０３２９】
従って、ノードNに対応するクラスタにクラスタリングされている隣接する写真データどうしの最大距離は、ノードNの左ノードl(N)に対応するクラスタにクラスタリングされている右端の写真データと、ノードNの右ノードr(N)に対応するクラスタにクラスタリングされている左端の写真データとの距離である。
【０３３０】
以上から、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqは、候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))を、式（２）（または式（３））にしたがって計算することにより求めることができる。
【０３３１】
ステップＳ１５２の処理後は、ステップＳ１５３に進み、クラスタリング装置１３は、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnを求める。
【０３３２】
ここで、上述したように、分岐ノードNpの左ノードlL(Np)が候補ノードNqである場合、候補クラスタCqの間近写真データは、注目データpicnewの左隣の写真データである、この写真データは、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データでもある。
【０３３３】
従って、ステップＳ１５３において、候補クラスタCqの間近写真データと注目データpicnewとの距離dnは、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Rm(l(Np)),Nnew)を、式（２）（または式（３））にしたがって計算することにより求めることができる。
【０３３４】
ステップＳ１５３の処理後は、ステップＳ１５４に進み、クラスタリング装置１３は、候補ノードNqに対応する候補クラスタCqの間近写真データと注目データpicnewとの距離dnが、候補ノードNqに対応する候補クラスタCqに属するデータのうちの隣接する写真データどうしの最大距離dqよりも大（または、以上）であるかどうかを判定する。
【０３３５】
ステップＳ１５４において、距離dnが最大距離dqよりも大であると判定された場合、注目データpicnewは、いま候補ノードNqとなっているノードに対応するクラスタ（いまの候補クラスタCq）に属しないので、ステップＳ１５５に進み、クラスタリング装置１３は、左ノードl(Nin)が候補ノードNqとなり、右ノードr(Nin)が注目ノードNnewとなるように、新たなノードNinを、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加し、関数IRM(Nq,Nnew)の戻り値として、新たなノードNinを返して処理（関数IRM(Nq,Nnew)の処理）を終了する。
【０３３６】
また、ステップＳ１５４において、距離dnが最大距離dqよりも大でないと判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データ（注目データpicnewの左隣の写真データ）との距離dnより大（または以上）の距離がある場合、注目データpicnewは、候補クラスタCqに属し、さらに、いまの候補クラスタCqが包含するクラスタに属する可能性があるので、ステップＳ１５６に進み、クラスタリング装置１３は、分岐ノードNpおよび候補ノードNqの更新を行う。
【０３３７】
即ち、クラスタリング装置１３は、ステップＳ１５６において、いまの候補ノードNqを新たな分岐ノードNpとし、かつ候補ノードNqの２つの子ノードのうちの右ノードr(Nq)を新たな候補ノードNqとする。
【０３３８】
ステップＳ１５６の処理後は、ステップＳ１５７に進み、直前のステップＳ１５６での更新後の候補ノードNqに対応する候補クラスタCqに属する写真データの数が１枚であるかどうかを判定する。
【０３３９】
ステップＳ１５７において、候補ノードNqに対応する候補クラスタCqに属する写真データの数が１枚でないと判定された場合、即ち、候補ノードNqがリーフノードでなく、子ノードを有する場合、ステップＳ１５９に進み、クラスタリング装置１３は、直前のステップＳ１５６での更新後の候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqを、ステップＳ１５２の場合と同様にして求め、ステップＳ１６０に進む。
【０３４０】
ステップＳ１６０では、クラスタリング装置１３は、ステップＳ１５４における場合と同様に、候補ノードNqに対応する候補クラスタCqの間近写真データ（注目データpicnewの左隣の写真データ）と注目データpicnewとの距離dnが、候補ノードNqに対応する候補クラスタCqに属するデータのうちの隣接する写真データどうしの最大距離dqよりも大（または、以上）であるかどうかを判定する。
【０３４１】
ステップＳ１６０において、距離dnが最大距離dqよりも大でないと判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データ（注目データpicnewの左隣の写真データ）との距離dnより大（または以上）の距離がある場合、注目データpicnewは、候補クラスタCqに属し、さらに、いまの候補クラスタCqが包含するクラスタに属する可能性があるので、ステップＳ１５６に戻り、以下、同様の処理を繰り返す。
【０３４２】
一方、ステップＳ１５７において、候補ノードNqに対応する候補クラスタCqに属する写真データの数が１枚であると判定されるか、または、ステップＳ１６０において、距離dnが最大距離dqよりも大であると判定された場合、即ち、候補ノードNqがリーフノードであるか、または、注目データpicnewが、いま候補ノードNqとなっているノードに対応するクラスタ（いまの候補クラスタCq）に属しない場合、ステップＳ１５８に進み、クラスタリング装置１３は、左ノードl(Nin)が候補ノードNqとなり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinを、分岐ノードNpの右ノードr(Np)となるように、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加し、関数IRM(Nq,Nnew)の戻り値として、NULLを返して処理（関数IRM(Nq,Nnew)の処理）を終了する。
【０３４３】
図３０に戻り、ステップＳ１０８では、クラスタリング装置１３は、図３３の処理によって得られる関数IRM(Nq,Nnew)の戻り値を、変数TMPにセットして、ステップＳ１０９に進む。
【０３４４】
ステップＳ１０９では、クラスタリング装置１３は、変数TMPがNULL（に等しい）であるかどうかを判定する。ステップＳ１０９において、変数TMPがNULLであると判定された場合、クラスタリング装置１３は処理を終了する。
【０３４５】
また、ステップＳ１０９において、変数TMPがNULLでないと判定された場合、即ち、例えば、図３３の関数IRM(Nq,Nnew)の処理によって、変数TMPに、関数IRM(Nq,Nnew)の戻り値としての新たなノードNinがセットされている場合、ステップＳ１１０に進み、クラスタリング装置１３は、クラスタツリー記憶装置１４に記憶されているクラスタツリーを、ルートノードNrootが、変数TMPにセットされている新たなノードNinとなるように更新して処理を終了する。
【０３４６】
次に、注目データpicnewが、対象写真データの中で最も古い写真データであり、対象写真データを撮影日時順に並べた場合に、注目データpicnewが最左端に配置されるときには、上述したように、図３０において、ステップＳ１０７からステップＳ１１１に進む。ステップＳ１１１では、クラスタリング装置１３は、ルートノードNrootと注目ノードNnew（を表す変数）を引数として、関数ILM(Nroot,Nnew)を呼び出し、その戻り値（関数ILM(Nroot,Nnew)の値）を、変数TMPにセットする。
【０３４７】
ここで、関数ILM(Nq,Nnew)は、候補ノードNqと注目ノードNnewとを引数とする関数であり、この関数ILM(Nq,Nnew)によれば、例えば、図２６に示したような、分岐ノードNpの右ノードr(Np)が候補ノードNqとなる場合を対象として、注目ノードNnewを子ノードとする新たなノードNinをクラスタツリーに追加する処理が行われる。
【０３４８】
即ち、図３４は、関数ILM(Nq,Nnew)の処理を説明するフローチャートである。
【０３４９】
まず、ステップＳ１７１において、クラスタリング装置１３は、関数ILM(Nq,Nnew)の引数となっている候補ノードNqを右ノードr(Np)とするノードを分岐ノードNpとして、ステップＳ１７２に進み、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの距離の最大値（最大距離）dqを、図３３のステップＳ１５２の場合と同様にして求める。
【０３５０】
ステップＳ１７２の処理後は、ステップＳ１７３に進み、クラスタリング装置１３は、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnを求める。
【０３５１】
ここで、上述したように、分岐ノードNpの右ノードr(Np)が候補ノードNqである場合、候補クラスタCqの間近写真データは、候補クラスタCqに属する写真データのうちの、注目データpicnewの右隣の写真データであり、この写真データは、分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データでもある。
【０３５２】
従って、ステップＳ１７３において、候補クラスタCqの間近写真データと注目データpicnewとの距離dnは、分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Lm(r(Np)),Nnew)を、式（２）（または式（３））にしたがって計算することにより求めることができる。
【０３５３】
ステップＳ１７３の処理後は、ステップＳ１７４に進み、クラスタリング装置１３は、候補ノードNqに対応する候補クラスタCqの間近写真データと注目データpicnewとの距離dnが、候補ノードNqに対応する候補クラスタCqに属するデータのうちの隣接する写真データどうしの最大距離dqよりも大（または、以上）であるかどうかを判定する。
【０３５４】
ステップＳ１７４において、距離dnが最大距離dqよりも大であると判定された場合、注目データpicnewは、いま候補ノードNqとなっているノードに対応するクラスタ（いまの候補クラスタCq）に属しないので、ステップＳ１７５に進み、クラスタリング装置１３は、右ノードr(Nin)が候補ノードNqとなり、左ノードl(Nin)が注目ノードNnewとなるように、新たなノードNinを、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加し、関数ILM(Nq,Nnew)の戻り値として、新たなノードNinを返して処理（関数ILM(Nq,Nnew)の処理）を終了する。
【０３５５】
また、ステップＳ１７４において、距離dnが最大距離dqよりも大でないと判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと、分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データ（注目データpicnewの右隣の写真データ）との距離dnより大（または以上）の距離がある場合、注目データpicnewは、候補クラスタCqに属し、さらに、いまの候補クラスタCqが包含するクラスタに属する可能性があるので、ステップＳ１７６に進み、クラスタリング装置１３は、分岐ノードNpおよび候補ノードNqの更新を行う。
【０３５６】
即ち、クラスタリング装置１３は、ステップＳ１７６において、いまの候補ノードNqを新たな分岐ノードNpとし、かつ候補ノードNqの２つの子ノードのうちの左ノードl(Nq)を新たな候補ノードNqとする。
【０３５７】
ステップＳ１７６の処理後は、ステップＳ１７７に進み、直前のステップＳ１７６での更新後の候補ノードNqに対応する候補クラスタCqに属する写真データの数が１枚であるかどうかを判定する。
【０３５８】
ステップＳ１７７において、候補ノードNqに対応する候補クラスタCqに属する写真データの数が１枚でないと判定された場合、即ち、候補ノードNqがリーフノードでなく、子ノードを有する場合、ステップＳ１７９に進み、クラスタリング装置１３は、直前のステップＳ１７６での更新後の候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqを、ステップＳ１７２の場合と同様にして求め、ステップＳ１８０に進む。
【０３５９】
ステップＳ１８０では、クラスタリング装置１３は、ステップＳ１７４における場合と同様に、候補ノードNqに対応する候補クラスタCqの間近写真データ（注目データpicnewの右隣の写真データ）と注目データpicnewとの距離dnが、候補ノードNqに対応する候補クラスタCqに属するデータのうちの隣接する写真データどうしの最大距離dqよりも大（または、以上）であるかどうかを判定する。
【０３６０】
ステップＳ１８０において、距離dnが最大距離dqよりも大でないと判定された場合、即ち、候補クラスタCqに属する隣接する写真データどうしの距離の中に、注目データpicnewと、分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データ（注目データpicnewの右隣の写真データ）との距離dnより大（または以上）の距離がある場合、注目データpicnewは、候補クラスタCqに属し、さらに、いまの候補クラスタCqが包含するクラスタに属する可能性があるので、ステップＳ１７６に戻り、以下、同様の処理を繰り返す。
【０３６１】
一方、ステップＳ１７７において、候補ノードNqに対応する候補クラスタCqに属する写真データの数が１枚であると判定されるか、または、ステップＳ１８０において、距離dnが最大距離dqよりも大であると判定された場合、即ち、候補ノードNqがリーフノードであるか、または、注目データpicnewが、いま候補ノードNqとなっているノードに対応するクラスタ（いまの候補クラスタCq）に属しない場合、ステップＳ１７８に進み、クラスタリング装置１３は、右ノードl(Nin)が候補ノードNqとなり、かつ左ノードl(Nin)が注目ノードNnewとなる新たなノードNinを、分岐ノードNpの左ノードl(Np)となるように、クラスタツリー記憶装置１４に記憶されているクラスタツリーに追加し、関数ILM(Nq,Nnew)の戻り値として、NULLを返して処理（関数ILM(Nq,Nnew)の処理）を終了する。
【０３６２】
図３０に戻り、ステップＳ１１１では、クラスタリング装置１３は、図３４の処理によって得られる関数ILM(Nq,Nnew)の戻り値を、変数TMPにセットして、ステップＳ１０９に進む。
【０３６３】
ステップＳ１０９では、上述したように、クラスタリング装置１３は、変数TMPがNULLであるかどうかを判定し、変数TMPがNULLであると判定した場合、クラスタリング装置１３は処理を終了する。
【０３６４】
また、ステップＳ１０９において、変数TMPがNULLでないと判定された場合、即ち、例えば、図３４の関数ILM(Nq,Nnew)の処理によって、変数TMPに、関数ILM(Nq,Nnew)の戻り値としての新たなノードNinがセットされている場合、ステップＳ１１０に進み、上述したように、クラスタリング装置１３は、クラスタツリー記憶装置１４に記憶されているクラスタツリーを、ルートノードNrootが、変数TMPにセットされている新たなノードNinとなるように更新して処理を終了する。
【０３６５】
次に、注目データpicnewが、対象写真データの中で最も古い写真データではなく、かつ、最新の写真データでもなく、従って、対象写真データを撮影日時順に並べた場合に、最左端でもなく最右端でもない位置に配置されるときには、上述したように、ステップＳ１０７からステップＳ１１２に進む。ステップＳ１１２では、クラスタリング装置１３は、ルートノードNrootと注目ノードNnewを引数として、関数FBN(Nroot,Nnew)を呼び出し、その戻り値（関数FBN(Nroot,Nnew)の値）を、分岐ノードNpとする（分岐ノードNpを表す変数にセットする）。
【０３６６】
ここで、ルートノードNrootと注目ノードNnewとを引数とする関数FBN(Nroot,Nnew)によれば、図２８で説明した分岐ノード検索処理と同様にして、注目ノードNnew（が割り当てられた注目データpicnew）に対する分岐ノードNpを求める処理が行われる。
【０３６７】
即ち、図３５は、関数FBN(Nq,Nnew)の処理を説明するフローチャートである。
【０３６８】
まず最初に、ステップＳ１９１において、クラスタリング装置１３は、クラスタツリー記憶装置１４に記憶されているクラスタツリーのルートノードNrootを、仮の分岐ノードNpとして、ステップＳ１９２に進む。
【０３６９】
ステップＳ１９２では、クラスタリング装置１３は、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)を、その注目ノードNnewが保持しているメタデータから認識するとともに、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))を、その左側右端ノードRm(l(Np))が保持しているメタデータから認識し、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))よりも古いかどうか、即ち、式t(Nnew)＜t(Rm(l(Np)))が満たされるかどうかを判定する。
【０３７０】
ステップＳ１９２において、撮影日時t(Nnew)が、撮影日時t(Rm(l(Np)))よりも古いと判定された場合、即ち、図２０に示したように、分岐ノードNpの左側右端ノードRm(l(Np))（に割り当てられた写真データ）は、注目ノードNnew（に割り当てられた注目データpicnew）の左隣に位置しなければならないのにもかかわらず、仮の分岐ノードNpの左側右端ノードRm(l(Np))が、注目ノードNnewの右側に位置する場合、仮の分岐ノードNpは、注目ノードNnew（に割り当てられた注目データpicnew）に対する分岐ノードNpではないので、ステップＳ１９３に進み、クラスタリング装置１３は、仮の分岐ノードNpを、クラスタツリーにおいて左側右端ノードRm(l(Np))がより左側に位置するノードに更新する。
【０３７１】
即ち、ステップＳ１９３において、クラスタリング装置１３は、いま仮の分岐ノードNpとなっているノードの左ノードl(Np)を、新たな仮の分岐ノードNpとする。そして、クラスタリング装置１３は、ステップＳ１９３からステップＳ１９６に進む。
【０３７２】
一方、撮影日時t(Nnew)が、撮影日時t(Rm(l(Np)))よりも古くないと判定された場合、ステップＳ１９４に進み、クラスタリング装置１３は、仮の分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データの撮影日時t(Lm(r(Np)))を、その右側左端ノードLm(r(Np))が保持しているメタデータから認識し、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データの撮影日時t(Lm(r(Np)))よりも新しいかどうか、即ち、式t(Lm(r(Np)))＜t(Nnew)が満たされるかどうかを判定する。
【０３７３】
ステップＳ１９４において、撮影日時t(Nnew)が、撮影日時t(Lm(r(Np)))よりも新しくないと判定された場合、即ち、撮影日時t(Nnew)が、撮影日時t(Rm(l(Np)))よりも古くなく、かつ、撮影日時t(Lm(r(Np)))よりも新しくなく、式（７）を満たす場合、クラスタリング装置１３は、関数FBN(Nroot,Nnew)の戻り値として、分岐ノードNp（いま仮の分岐ノードNpとされているノードを表す変数）を返して処理を終了する。
【０３７４】
また、ステップＳ１９４において、撮影日時t(Nnew)が、撮影日時t(Lm(r(Np)))よりも新しいと判定された場合、即ち、図２０に示したように、分岐ノードNpの右側左端ノードLm(r(Np))（に割り当てられた写真データ）は、注目ノードNnew（に割り当てられた注目データpicnew）の右隣に位置しなければならないのにもかかわらず、仮の分岐ノードNpの右側左端ノードLm(r(Np))が、注目ノードNnewの左側に位置する場合、仮の分岐ノードNpは、注目ノードNnew（に割り当てられた注目データpicnew）に対する分岐ノードNpではないので、ステップＳ１９５に進み、クラスタリング装置１３は、仮の分岐ノードNpを、クラスタツリーにおいて右側左端ノードLm(r(Np))がより右側に位置するノードに更新する。
【０３７５】
即ち、ステップＳ１９５において、クラスタリング装置１３は、いま仮の分岐ノードNpとなっているノードの右ノードを、新たな仮の分岐ノードNpとする。
【０３７６】
そして、クラスタリング装置１３は、ステップＳ１９５からステップＳ１９６に進み、仮の分岐ノードNpに対応するクラスタに属する（クラスタリングされている）写真データの枚数が１枚より大であるかどうかを判定する。
【０３７７】
ステップＳ１９６において、仮の分岐ノードNpに対応するクラスタに属する写真データの枚数が１枚より大であると判定された場合、即ち、仮の分岐ノードNpがリーフノードでない場合、ステップＳ１９２に戻り、以下、同様の処理が繰り返される。
【０３７８】
また、ステップＳ１９６において、仮の分岐ノードNpに対応するクラスタに属する写真データの枚数が１枚より大でないと判定された場合、即ち、仮の分岐ノードNpがリーフノードである場合、クラスタリング装置１３は、関数FBN(Nroot,Nnew)の戻り値として、分岐ノードNp（いま仮の分岐ノードNpとされているノードを表す変数）を返して処理を終了する。
【０３７９】
図３０に戻り、ステップＳ１１２では、クラスタリング装置１３は、図３５の処理によって得られる関数FBN(Nroot,Nnew)の戻り値を、分岐ノードNpとして（分岐ノードNpを表す変数にセットして）、ステップＳ１１３に進む。
【０３８０】
ステップＳ１１３では、クラスタリング装置１３は、ステップＳ１１２で求められた分岐ノードNpの左ノードl(Np)に対応するクラスタClの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離である左クラスタ距離dl、および、分岐ノードNpの右ノードr(Np)に対応するクラスタCrの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離である右クラスタ距離drを求める。
【０３８１】
ここで、分岐ノードNpの左ノードl(Np)に対応するクラスタClの間近写真データは、分岐ノードNpの左ノードl(Np)に対応するクラスタClに属する写真データのうちの、注目データpicnewとの撮影日時が最も近い写真データである。
【０３８２】
そして、分岐ノードNpの左ノードl(Np)に対応するクラスタClに属する写真データのうちの、注目データpicnewとの撮影日時が最も近い写真データは、クラスタClに属する写真データのうちの最右端の写真データ、即ち、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データ（注目データpicnewの左隣の写真データ）である。
【０３８３】
従って、分岐ノードNpの左ノードl(Np)に対応するクラスタClの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離（左クラスタ距離dl）は、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Rm(l(Np)),Nnew)を、式（２）（または式（３））にしたがって計算することにより求めることができる。
【０３８４】
同様に、分岐ノードNpの右ノードr(Np)に対応するクラスタCrの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離（右クラスタ距離dr）は、分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Lm(r(Np)),Nnew)（＝dpic(Nnew,Lm(r(Np)))）を、式（２）（または式（３））にしたがって計算することにより求めることができる。
【０３８５】
クラスタリング装置１３は、ステップＳ１１３において、以上のようにして、左クラスタ距離dl（＝dpic(Rm(l(Np)),Nnew)）と、右クラスタ距離dr（＝dpic(Nnew,Lm(r(Np)))）とを求めると、さらに、左クラスタ距離dlが、右クラスタ距離drより小（または、以下）であるかどうかを判定する。
【０３８６】
ステップＳ１１３において、左クラスタ距離dlが、右クラスタ距離drより小であると判定された場合、即ち、注目データがpicnewが、分岐ノードNpの左ノードl(Np)の間近写真データに近く、その左ノードl(Np)を候補ノードNqとすべき場合、ステップＳ１１４に進み、クラスタリング装置１３は、分岐ノードNpの左ノードl(Np)を候補ノードＮqとし、その候補ノードNqと、注目ノードNnewを引数として、図３３で説明した関数IRM(l(Np),Nnew)を呼び出して、その戻り値（関数IRM(l(Np),Nnew)の値）を、変数TMPにセットする。
【０３８７】
そして、ステップＳ１１４からＳ１１５に進み、クラスタリング装置１３は、変数TMPがNULLであるかどうかを判定し、変数TMPがNULLであると判定した場合、処理を終了する。
【０３８８】
また、ステップＳ１１５において、変数TMPがNULLでないと判定された場合、即ち、ステップＳ１１４で呼び出された図３３の関数IRM(Nq,Nnew)の処理によって、変数TMPに、関数IRM(Nq,Nnew)の戻り値としての新たなノードNinがセットされている場合、ステップＳ１１６に進み、クラスタリング装置１３は、クラスタツリー記憶装置１４に記憶されているクラスタツリーを、分岐ノードNpの左ノードl(Np)が、変数TMPにセットされている新たなノードNinとなるように更新してリターンする。
【０３８９】
一方、ステップＳ１１３において、左クラスタ距離dlが、右クラスタ距離drより小でないと判定された場合、即ち、注目データpicnewが、分岐ノードNpの右ノードr(Np)の間近写真データに近く、その右ノードr(Np)を候補ノードNqとすべき場合、ステップＳ１１７に進み、クラスタリング装置１３は、分岐ノードNpの右ノードr(Np)を候補ノードＮqとし、その候補ノードNqと、注目ノードNnewを引数として、図３４で説明した関数ILM(r(Np),Nnew)を呼び出して、その戻り値（関数ILM(r(Np),Nnew)の値）を、変数TMPにセットする。
【０３９０】
そして、ステップＳ１１７からＳ１１８に進み、クラスタリング装置１３は、変数TMPがNULLであるかどうかを判定し、変数TMPがNULLであると判定した場合、処理を終了する。
【０３９１】
また、ステップＳ１１８において、変数TMPがNULLでないと判定された場合、即ち、ステップＳ１１７で呼び出された図３４の関数ILM(Nq,Nnew)の処理によって、変数TMPに、関数ILM(Nq,Nnew)の戻り値としての新たなノードNinがセットされている場合、ステップＳ１１９に進み、クラスタリング装置１３は、クラスタツリー記憶装置１４に記憶されているクラスタツリーを、分岐ノードNpの右ノードr(Np)が、変数TMPにセットされている新たなノードNinとなるように更新してリターンする。
【０３９２】
次に、図３６乃至図４２を参照して、クラスタリング装置１３が行う図３０のクラスタリング処理によって生成されるクラスタツリーの具体例について説明する。
【０３９３】
なお、写真データの撮影位置は、ある位置（例えば、カメラ１のユーザの自宅の位置など）を原点とするxy座標系の座標(x,y)で表し、撮影日時は、ある日時を基準として計時された秒数tで表すこととする。ここで、撮影位置(x,y)のx座標とy座標の単位としては、例えばm（メートル）等を採用することができる。
【０３９４】
また、以下、適宜、写真データの撮影位置(x,y)と撮影日時tとをまとめて、撮影情報(x,y,t)という。
【０３９５】
さらに、写真データpic#iとpic#jとの距離dpic(i,j)は、例えば、式（２）によって求めることとする。また、式（２）における重み係数α，β，γとしては、α＝β＝１，γ＝０を採用することとする。従って、写真データpic#iとpic#jとの距離dpic(i,j)は、写真データpic#iとpic#jの撮影情報(x,y,t)を、それぞれ(x1,y1,t1)と(x2,y2,t2)と表すと、式dpic(i,j)=|t1-t2| + |x1-x2|+|y1-y2|で求めることができる。
【０３９６】
図３６は、カメラ１で撮影された写真データの例を示している。
【０３９７】
図３６では、９枚の写真データpic1,pic2,pic3,pic4,pic5,pic6,pic7,pic8,pic9がある。
【０３９８】
なお、図３６においては、写真データpic#i（i=1,2,・・・,9）を□印で表してある。また、□印内の(x,y,t)は、撮影情報を表す。さらに、図３６において、写真データpic#iを表す□印は、その写真データpic#iの撮影位置(x,y)に図示してある。
【０３９９】
図３６において、写真データpic1の撮影位置(x,y)は(0,0)で、撮影日時tは0であり、写真データpic2の撮影位置(x,y)は(0,10)で、撮影日時tは10である。また、写真データpic3の撮影位置(x,y)は(20,10)で、撮影日時tは40であり、写真データpic4の撮影位置(x,y)は(20,20)で、撮影日時tは60である。さらに、写真データpic5の撮影位置(x,y)は(60,20)で、撮影日時tは100であり、写真データpic6の撮影位置(x,y)は(20,40)で、撮影日時tは80である。また、写真データpic7の撮影位置(x,y)は(10,20)で、撮影日時tは70であり、写真データpic8の撮影位置(x,y)は(5,10)で、撮影日時tは20である。さらに、写真データpic9の撮影位置(x,y)は(12,10)で、撮影日時tは20である。
【０４００】
図３７は、図３６に示した９枚の写真データpic1乃至pic9のうちの、例えば、４枚の写真データpic1乃至pic4を、１枚ずつ注目データpicnewとして、図３０のクラスタリング処理を行うことにより得られるクラスタツリーを示している。
【０４０１】
写真データpic1乃至pic4の撮影日時tは、図３６に示したように、それぞれ、0,10,40,60であり、従って、写真データpic1乃至pic4の撮影日時順の並びは、pic1,pic2,pic3,pic4となる。
【０４０２】
そして、図３７のクラスタツリーにおいては、撮影日時順の並びの写真データpic1乃至pic4について、写真データpic1にはノードN1が、写真データpic2にはノードN2が、写真データpic3にはノードN3が、写真データpic4にはノードN4が、それぞれ割り当てられている。また、ノードN1とN2とは、それぞれ、ノードN12の左ノードと右ノードとになっており、ノードN3とN4とは、それぞれ、ノードN34の左ノードと右ノードとになっている。さらに、ノードN12とN34とは、それぞれ、ルートノードであるN1234の左ノードと右ノードとになっている。
【０４０３】
ここで、以下、適宜、写真データpic#iとpic#jとの距離dpic(i,j)を、距離dijと表す。
【０４０４】
図３７に示した、撮影日時順の並びの写真データpic1乃至pic4の隣接する写真データpic#iとpic#(i+1)との距離dijは、以下のようになる。
【０４０５】
即ち、写真データpic1とpic2との距離d12は、|0-0|+|0-10|+|0-10|=20となる。また、写真データpic2とpic3との距離d23は、|0-20|+|10-10|+|10-40|=50となる。さらに、写真データpic3とpic4との距離d34は、|20-20|+|10-20|+|40-60|=30となる。
【０４０６】
次に、図３８を参照して、写真データpic5を注目データpicnewとし、この注目データpicnewと、既にクラスタリングされている写真データpic1乃至pic4とを、対象写真データとして、図３０のクラスタリング処理を行うことにより得られるクラスタツリーを説明する。
【０４０７】
ここで、既にクラスタリングされている写真データpic1乃至pic4の撮影日時tは、上述したように、それぞれ、0,10,40,60である。また、注目データpicnewである写真データpic5の撮影日時tは100である。従って、対象写真データpic1乃至pic5の撮影日時順の並びは、図３８左から１番目に示すように、pic1,pic2,pic3,pic4,pic5となる。
【０４０８】
現在のクラスタツリーのノードに割り当てられている写真データの数は、写真データpic1乃至pic4の４枚であるため、写真データpic5を注目データpicnewとして、図３０のクラスタリング処理が開始されると、ステップＳ１０１からステップＳ１０６に進み、上述したように、現在のクラスタツリーのルートノードNroot（＝Ｎ1234）が包含するノードのうちの右端ノードRm(Nroot)、つまり、クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかが判定される。
【０４０９】
クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic4であり、その写真データpic4の撮影日時tは60である。また、注目データpicnewである写真データpic5の撮影日時tは100である。
【０４１０】
従って、ステップＳ１０６では、現在のクラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))(=60)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=100)よりも古いと判定され、ステップＳ１０８に進み、図３３の関数IRM(Nq,Nnew)が、その引数となっている候補ノードNqにルートノードNroot(=N1234)をセットして呼び出される。
【０４１１】
図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５２において、上述したように、候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０４１２】
いまの場合、候補ノードNqがルートノードN1234であるから、左側右端ノードRm(l(Nq))に割り当てられている写真データは、写真データpic2であり、右側左端ノードLm(r(Nq)に割り当てられている写真データは、写真データpic3である。従って、ステップＳ１５２では、写真データpic2とpic3の距離が、最大距離dqとして求められる。
【０４１３】
ここで、写真データpic2とpic3の距離は、図３７に示したように、50であり、従って、最大距離dqとしては、図３８左から２番目に示すように、50が求められる。
【０４１４】
さらに、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５３において、上述したように、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目データpicnewとの距離が、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnとして求められる。
【０４１５】
いまの場合、候補ノードNqがルートノードN1234であり、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５１において、候補ノードNqを左ノードl(Np)とするノードが分岐ノードNpとされる。この場合、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データは、候補ノードNq(=l(Np))に包含されるノードのうちの右端ノードRm(Nq)に割り当てられている写真データとなり、この写真データは、注目データpicnewの左隣の写真データとなる。
【０４１６】
注目データpicnewである写真データpic5の左隣の写真データは写真データpic4である。そして、写真データpic4の撮影情報(x,y,t)は(20,20,60)であり、写真データpic5の撮影情報(x,y,t)は(60,20,100)であるから、写真データpic4とpic5との距離である、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnは、図３８左から２番目に示すように、|20-60|+|20-20|+|60-100|=80となる。
【０４１７】
以上から、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５４において、距離dn(=80)が、最大距離dq(=50)よりも大であると判定され、ステップＳ１５５に進み、左ノードl(Nin)が候補ノードNqとなり、右ノードr(Nin)が注目ノードNnewとなるように、新たなノードNinが、クラスタツリーに追加される。
【０４１８】
即ち、いまの場合、候補ノードNqはルートノードN1234であるため、図３８左から２番目に示すように、左ノードl(Nin)がルートノードN1234となり、右ノードr(Nin)が注目ノードNnewとなるように、新たなノードNinが、クラスタツリーに追加される。
【０４１９】
そして、図３３の関数IRM(Nq,Nnew)の処理から、図３０のステップＳ１０８にリターンし、ステップＳ１１０において、新たなノードNinがクラスタツリーのルートノードとされる。その結果、図３８左から３番目（右から１番目）に示すような、ルートノードが新たなノードNinとなったクラスタツリーが得られる。
【０４２０】
次に、図３９を参照して、写真データpic6を注目データpicnewとし、注目データpicnewと、既にクラスタリングされている写真データpic1乃至pic4とを、対象写真データとして、図３０のクラスタリング処理を行うことにより得られるクラスタツリーを説明する。
【０４２１】
ここで、既にクラスタリングされている写真データpic1乃至pic4の撮影日時tは、上述したように、それぞれ、0,10,40,60である。また、注目データpicnewである写真データpic6の撮影日時tは80である。従って、対象写真データpic1乃至pic4,pic6の撮影日時順の並びは、図３９左から１番目に示すように、pic1,pic2,pic3,pic4,pic6となる。
【０４２２】
現在のクラスタツリーのノードに割り当てられている写真データの数は、写真データpic1乃至pic4の４枚であるため、写真データpic6を注目データpicnewとして、図３０のクラスタリング処理が開始されると、ステップＳ１０１からステップＳ１０６に進み、上述したように、現在のクラスタツリーのルートノードNroot（＝Ｎ1234）が包含するノードのうちの右端ノードRm(Nroot)、つまり、クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかが判定される。
【０４２３】
クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic4であり、その写真データpic4の撮影日時tは60である。また、注目データpicnewである写真データpic6の撮影日時tは80である。
【０４２４】
従って、ステップＳ１０６では、現在のクラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))(=60)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=80)よりも古いと判定され、ステップＳ１０８に進み、図３３の関数IRM(Nq,Nnew)が、その引数となっている候補ノードNqにルートノードNroot(=N1234)をセットして呼び出される。
【０４２５】
図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５２において、上述したように、候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０４２６】
いまの場合、候補ノードNqがルートノードN1234であるから、左側右端ノードRm(l(Nq))に割り当てられている写真データは、写真データpic2であり、右側左端ノードLm(r(Nq)に割り当てられている写真データは、写真データpic3である。従って、ステップＳ１５２では、写真データpic2とpic3の距離が、最大距離dqとして求められる。
【０４２７】
ここで、写真データpic2とpic3の距離は、図３７に示したように、50であり、従って、最大距離dqとしては、図３９左から２番目の上から１番目に示すように、50が求められる。
【０４２８】
さらに、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５３において、上述したように、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目データpicnewとの距離が、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnとして求められる。
【０４２９】
いまの場合、候補ノードNqがルートノードN1234であり、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５１において、候補ノードNqを左ノードl(Np)とするノードが分岐ノードNpとされる。この場合、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データは、候補ノードNq(=l(Np))に包含されるノードのうちの右端ノードRm(Nq)に割り当てられている写真データとなり、この写真データは、注目データpicnewの左隣の写真データとなる。
【０４３０】
注目データpicnewである写真データpic6の左隣の写真データは写真データpic4である。そして、写真データpic4の撮影情報(x,y,t)は(20,20,60)であり、写真データpic6の撮影情報(x,y,t)は(20,40,80)であるから、写真データpic4とpic6との距離である、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnは、図３９左から２番目に示すように、|20-20|+|20-40|+|60-80|=40となる。
【０４３１】
以上から、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５４において、距離dn(=40)が、最大距離dq(=50)よりも大でないと判定され、ステップＳ１５６に進み、候補ノードNqが新たな分岐ノードNpに、候補ノードNqの右ノードr(Nq)が新たな候補ノードNqに、それぞれ更新される。即ち、いま、候補ノードNqはルートノードN1234であるので、ルートノードN1234が新たな分岐ノードNpとなり、ルートノードN1234の右ノードであるノードN34が新たな候補ノードNqとなる。
【０４３２】
新たな候補ノードNqであるノードN34に対応するクラスタC34には、図３９左から２番目の上から２番目に示すように、２枚の写真データpic3およびpic4が属するので、ステップＳ１５６で、候補ノードNqと分岐ノードNpの更新がされた後は、ステップＳ１５７を介して、ステップＳ１５９に進み、ステップＳ１５２の場合と同様に、新たな候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０４３３】
いまの場合、候補ノードNqがノードN34であるから、左側右端ノードRm(l(Nq))に割り当てられている写真データは、写真データpic3であり、右側左端ノードLm(r(Nq)に割り当てられている写真データは、写真データpic4である。従って、ステップＳ１５９では、写真データpic3とpic4の距離が、最大距離dqとして求められる。
【０４３４】
ここで、写真データpic3とpic4の距離は、図３７に示したように、30であり、従って、最大距離dqとしては、図３９左から２番目の上から２番目に示すように、30が求められる。
【０４３５】
以上のように、ステップＳ１５９において、最大距離dqが求められた後は、ステップＳ１６０において、距離dnと最大距離dqとの大小関係が判定される。いまの場合、距離dnは40であり、最大距離dqは30であるので、ステップＳ１６０では、距離dn(=40)が、最大距離dq(=30)よりも大であると判定され、ステップＳ１５８に進み、左ノードl(Nin)が候補ノードNqとなり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinが、分岐ノードNpの右ノードr(Np)となるように、クラスタツリーに追加される。
【０４３６】
即ち、いまの場合、候補ノードNqはノードN34であり、分岐ノードNpはルートノードN1234であるため、図３９左から２番目の上から２番目に示すように、左ノードl(Nin)がノードN34となり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinが、ルートノードN1234の右ノードr(Np)となるように、クラスタツリーに追加される。
【０４３７】
そして、図３３の関数IRM(Nq,Nnew)の処理から、図３０のステップＳ１０８にリターンし、これにより、図３９左から３番目（右から１番目）に示すような、ルートノードがノードN1234のままのクラスタツリーが得られる。
【０４３８】
次に、図４０を参照して、写真データpic7を注目データpicnewとし、注目データpicnewと、既にクラスタリングされている写真データpic1乃至pic4とを、対象写真データとして、図３０のクラスタリング処理を行うことにより得られるクラスタツリーを説明する。
【０４３９】
ここで、既にクラスタリングされている写真データpic1乃至pic4の撮影日時tは、上述したように、それぞれ、0,10,40,60である。また、注目データpicnewである写真データpic7の撮影日時tは70である。従って、対象写真データpic1乃至pic4,pic7の撮影日時順の並びは、図４０左から１番目に示すように、pic1,pic2,pic3,pic4,pic7となる。
【０４４０】
現在のクラスタツリーのノードに割り当てられている写真データの数は、写真データpic1乃至pic4の４枚であるため、写真データpic7を注目データpicnewとして、図３０のクラスタリング処理が開始されると、ステップＳ１０１からステップＳ１０６に進み、上述したように、現在のクラスタツリーのルートノードNrootが包含するノードのうちの右端ノードRm(Nroot)、つまり、クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかが判定される。
【０４４１】
クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic4であり、その写真データpic4の撮影日時tは60である。また、注目データpicnewである写真データpic7の撮影日時tは70である。
【０４４２】
従って、ステップＳ１０６では、現在のクラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))(=60)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=70)よりも古いと判定され、ステップＳ１０８に進み、図３３の関数IRM(Nq,Nnew)が、その引数となっている候補ノードNqにルートノードNroot(=N1234)をセットして呼び出される。
【０４４３】
図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５２において、上述したように、候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０４４４】
いまの場合、候補ノードNqがルートノードN1234であるから、図４０左から２番目の上から１番目に示すように、図３８や図３９の場合と同様に、写真データpic2とpic3との距離である50が、最大距離dqとして求められる。
【０４４５】
さらに、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５３において、上述したように、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目データpicnewとの距離が、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnとして求められる。
【０４４６】
いまの場合、候補ノードNqがルートノードN1234であり、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５１において、候補ノードNqを左ノードl(Np)とするノードが分岐ノードNpとされる。この場合、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データは、候補ノードNq(=l(Np))に包含されるノードのうちの右端ノードRm(Nq)に割り当てられている写真データとなり、この写真データは、注目データpicnewの左隣の写真データである。
【０４４７】
注目データpicnewである写真データpic7の左隣の写真データは写真データpic4である。そして、写真データpic4の撮影情報(x,y,t)は(20,20,60)であり、写真データpic7の撮影情報(x,y,t)は(10,20,70)であるから、写真データpic4とpic7との距離である、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnは、図４０左から２番目に示すように、|20-10|+|20-20|+|60-70|=20となる。
【０４４８】
以上から、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５４において、距離dn(=20)が、最大距離dq(=50)よりも大でないと判定され、ステップＳ１５６に進み、候補ノードNqが新たな分岐ノードNpに、候補ノードNqの右ノードr(Nq)が新たな候補ノードNqに、それぞれ更新される。即ち、いま、候補ノードNqはルートノードN1234であるので、ルートノードN1234が新たな分岐ノードNpとなり、ルートノードN1234の右ノードであるノードN34が新たな候補ノードNqとなる。
【０４４９】
新たな候補ノードNqであるノードN34に対応するクラスタC34には、図４０左から２番目の上から２番目に示すように、２枚の写真データpic3およびpic4が属するので、ステップＳ１５６で、候補ノードNqと分岐ノードNpの更新がされた後は、ステップＳ１５７を介して、ステップＳ１５９に進み、ステップＳ１５２の場合と同様に、新たな候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０４５０】
いまの場合、候補ノードNqがノードN34であるから、左側右端ノードRm(l(Nq))に割り当てられている写真データは、写真データpic3であり、右側左端ノードLm(r(Nq)に割り当てられている写真データは、写真データpic4である。従って、ステップＳ１５９では、写真データpic3とpic4の距離が、最大距離dqとして求められる。
【０４５１】
ここで、写真データpic3とpic4の距離は、図３７に示したように、30であり、従って、最大距離dqとしては、図４０左から２番目の上から２番目に示すように、30が求められる。
【０４５２】
以上のように、ステップＳ１５９において、最大距離dqが求められた後は、ステップＳ１６０において、距離dnと最大距離dqとの大小関係が判定される。いまの場合、距離dnは20であり、最大距離dqは30であるので、ステップＳ１６０では、距離dn(=20)が、最大距離dq(=30)よりも大でないと判定され、ステップＳ１５６に戻り、上述したように、候補ノードNqが新たな分岐ノードNpに、候補ノードNqの右ノードr(Nq)が新たな候補ノードNqに、それぞれ更新される。
【０４５３】
即ち、いま、候補ノードNqはノードN34であるので、ノードN34が新たな分岐ノードNpとなり、ノードN34の右ノードであるノードN4が新たな候補ノードNqとなる。
【０４５４】
新たな候補ノードNqであるノードN4に対応するクラスタC4には、図４０左から２番目の上から３番目に示すように、１枚の写真データpic4だけが属するので、ステップＳ１５６で、候補ノードNqと分岐ノードNpの更新がされた後は、ステップＳ１５７を介して、ステップＳ１５８に進み、左ノードl(Nin)が候補ノードNqとなり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinが、分岐ノードNpの右ノードr(Np)となるように、クラスタツリーに追加される。
【０４５５】
即ち、いまの場合、候補ノードNqはノードN4であり、分岐ノードNpはノードＮ34であるため、図４０左から２番目の上から３番目に示すように、左ノードl(Nin)がノードN4となり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinが、ノードN34の右ノードr(Np)となるように、クラスタツリーに追加される。
【０４５６】
そして、図３３の関数IRM(Nq,Nnew)の処理から、図３０のステップＳ１０８にリターンし、これにより、図４０左から３番目（右から１番目）に示すような、ルートノードがノードN1234のままのクラスタツリーが得られる。
【０４５７】
次に、図４１を参照して、写真データpic8を注目データpicnewとし、注目データpicnewと、既にクラスタリングされている写真データpic1乃至pic4とを、対象写真データとして、図３０のクラスタリング処理を行うことにより得られるクラスタツリーを説明する。
【０４５８】
ここで、既にクラスタリングされている写真データpic1乃至pic4の撮影日時tは、上述したように、それぞれ、0,10,40,60である。また、注目データpicnewである写真データpic8の撮影日時tは20である。従って、対象写真データpic1乃至pic4,pic8の撮影日時順の並びは、図４１左から１番目に示すように、pic1,pic2,pic8,pic3,pic4となる。
【０４５９】
現在のクラスタツリーのノードに割り当てられている写真データの数は、写真データpic1乃至pic4の４枚であるため、写真データpic8を注目データpicnewとして、図３０のクラスタリング処理が開始されると、ステップＳ１０１からステップＳ１０６に進み、上述したように、現在のクラスタツリーのルートノードNrootが包含するノードのうちの右端ノードRm(Nroot)、つまり、クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかが判定される。
【０４６０】
クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic4であり、その写真データpic4の撮影日時tは60である。また、注目データpicnewである写真データpic8の撮影日時tは20である。
【０４６１】
従って、ステップＳ１０６では、現在のクラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))(=60)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=20)よりも古くないと判定され、ステップＳ１０７に進み、上述したように、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、現在のクラスタツリーのルートノードNrootが包含するノードのうちの左端ノードLm(Nroot)、つまり、クラスタツリーの左端のリーフノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))よりも古いかどうかが判定される。
【０４６２】
クラスタツリーの左端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic1であり、その写真データpic1の撮影日時tは0である。また、注目データpicnewである写真データpic8の撮影日時tは20である。
【０４６３】
従って、ステップＳ１０６では、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=20)が、現在のクラスタツリーの左端のリーフノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))(=0)よりも古くないと判定され、ステップＳ１１２に進み、図３５の関数FBN(Nroot,Nnew)が呼び出される。
【０４６４】
図３５の関数FBN(Nroot,Nnew)の処理では、ステップＳ１９１において、クラスタツリーのルートノードNroot(=N1234)が、仮の分岐ノードNpとされ、ステップＳ１９２において、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))よりも古いかどうか、即ち、式t(Nnew)＜t(Rm(l(Np)))が満たされるかどうかが判定される。
【０４６５】
いまの場合、注目データpicnewである写真データpic8の撮影日時t(Nnew)は20である。また、仮の分岐ノードNpは、ルートノードN1234であるから、その左側右端ノードRm(l(Np))は、ノードN2であり、ノードN2は、写真データpic2が割り当てられている。そして、写真データpic2の撮影日時t(Rm(l(Np)))は、10である。
【０４６６】
従って、ステップＳ１９２では、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=20)が、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))(=10)よりも古くないと判定され、ステップＳ１９４に進み、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データの撮影日時t(Lm(r(Np)))よりも新しいかどうか、即ち、式t(Lm(r(Np)))＜t(Nnew)が満たされるかどうかが判定される。
【０４６７】
いまの場合、仮の分岐ノードNp（ルートノードN1234）の右側左端ノードLm(r(Np))は、ノードN3であり、ノードN3は、写真データpic3に割り当てられている。そして、写真データpic3の撮影日時t(Lm(r(Np)))は、40である。
【０４６８】
従って、ステップＳ１９４では、撮影日時t(Nnew)(=20)が、撮影日時t(Lm(r(Np)))(=40)よりも新しくないと判定され、関数FBN(Nroot,Nnew)の戻り値として、いま仮の分岐ノードNpとなっているルートノードN1234が返される。
【０４６９】
その結果、図３０のステップＳ１１２では、ルートノードN1234が分岐ノードNpとされ、ステップＳ１１３に進み、分岐ノードNpの左ノードl(Np)に対応するクラスタClの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離である左クラスタ距離dl、および、分岐ノードNpの右ノードr(Np)に対応するクラスタCrの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離である右クラスタ距離drの大小関係が判定される。
【０４７０】
ここで、左クラスタ距離dlは、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Rm(l(Np)),Nnew)でもある。
【０４７１】
いまの場合、分岐ノードNpは、ルートノードN1234であるので、左クラスタ距離dlは、ルートノードN1234の左側右端ノードRm(l(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Rm(l(Np)),Nnew)、即ち、写真データpic2と写真データpic8との距離となる。
【０４７２】
写真データpic2の撮影情報(x,y,t)は(0,10,10)であり、写真データpic8の撮影情報(x,y,t)は(5,10,20)であるから、写真データpic2と写真データpic8との距離である左クラスタ距離dlは、|0-5|+|10-10|+|10-20|=15となる。
【０４７３】
また、右クラスタ距離drは、ルートノードN1234の右側左端ノードLm(r(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Lm(r(Np)),Nnew)（＝dpic(Nnew,Lm(r(Np)))）でもあり、従って、写真データpic3と写真データpic8との距離である。
【０４７４】
写真データpic3の撮影情報(x,y,t)は(20,10,40)で、写真データpic8の撮影情報(x,y,t)は(5,10,20)であるから、写真データpic3と写真データpic8との距離である右クラスタ距離drは、|20-5|+|10-10|+|40-20|=35となる。
【０４７５】
従って、図３０のステップＳ１１３では、左クラスタ距離dl(=15)が、右クラスタ距離dr(=35)より小であると判定され、ステップＳ１１４に進み、図３３の関数IRM(Nq,Nnew)が、その引数となっている候補ノードNqに、分岐ノードNp（ルートノードN1234）の左ノードl(Np)、即ち、ノードN12をセットして呼び出される。
【０４７６】
図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５２において、上述したように、候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０４７７】
いまの場合、候補ノードNqがノードN12であるから、左側右端ノードRm(l(Nq))に割り当てられている写真データは、写真データpic1であり、右側左端ノードLm(r(Nq)に割り当てられている写真データは、写真データpic2である。従って、ステップＳ１５２では、写真データpic1とpic2の距離が、最大距離dqとして求められる。
【０４７８】
ここで、写真データpic1とpic2の距離は、図３７に示したように、20であり、従って、最大距離dqとしては、図４１左から２番目に示すように、20が求められる。
【０４７９】
さらに、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５３において、上述したように、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目データpicnewとの距離が、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnとして求められる。
【０４８０】
いまの場合、候補ノードNqがノードN12であり、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５１において、候補ノードNqであるノードN12を左ノードl(Np)とするノード、即ち、ルートノードN1234が分岐ノードNpとされる。この場合、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データは、候補ノードNq(=l(Np))に包含されるノードのうちの右端ノードRm(Nq)に割り当てられている写真データとなり、この写真データは、注目データpicnewの左隣の写真データとなる。
【０４８１】
注目データpicnewである写真データpic8の左隣の写真データは写真データpic2である。そして、写真データpic2の撮影情報(x,y,t)は(0,10,10)であり、写真データpic8の撮影情報(x,y,t)は(5,10,20)であるから、写真データpic2とpic8との距離である、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnは、図４１左から２番目に示すように、|0-5|+|10-10|+|10-20|=15となる。
【０４８２】
以上から、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５４において、距離dn(=15)が、最大距離dq(=20)よりも大でないと判定され、ステップＳ１５６に進み、候補ノードNqが新たな分岐ノードNpに、候補ノードNqの右ノードr(Nq)が新たな候補ノードNqに、それぞれ更新される。即ち、いま、候補ノードNqはノードN12であるので、ノードN12が新たな分岐ノードNpとなり、ノードN12の右ノードであるノードN2が新たな候補ノードNqとなる。
【０４８３】
新たな候補ノードNqであるノードN2に対応するクラスタC2には、図４１左から２番目に示すように、１枚の写真データpic2だけが属するので、ステップＳ１５６で、候補ノードNqと分岐ノードNpの更新がされた後は、ステップＳ１５７を介して、ステップＳ１５８に進み、左ノードl(Nin)が候補ノードNqとなり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinが、分岐ノードNpの右ノードr(Np)となるように、クラスタツリーに追加される。
【０４８４】
即ち、いまの場合、候補ノードNqはノードN2であり、分岐ノードNpはノードN12であるため、図４１左から２番目に示すように、左ノードl(Nin)がノードN2となり、かつ右ノードr(Nin)が注目ノードNnewとなる新たなノードNinが、ノードN12の右ノードr(Np)となるように、クラスタツリーに追加される。
【０４８５】
そして、図３３の関数IRM(Nq,Nnew)の処理から、図３０のステップＳ１０８にリターンし、これにより、図４１左から３番目（右から１番目）に示すような、ルートノードがノードN1234のままのクラスタツリーが得られる。
【０４８６】
次に、図４２を参照して、写真データpic9を注目データpicnewとし、注目データpic9と、既にクラスタリングされている写真データpic1乃至pic4とを、対象写真データとして、図３０のクラスタリング処理を行うことにより得られるクラスタツリーを説明する。
【０４８７】
ここで、既にクラスタリングされている写真データpic1乃至pic4の撮影日時tは、上述したように、それぞれ、0,10,40,60である。また、注目データpicnewである写真データpic9の撮影日時tは20である。従って、対象写真データpic1乃至pic4,pic9の撮影日時順の並びは、図４２左から１番目に示すように、pic1,pic2,pic9,pic3,pic4となる。
【０４８８】
現在のクラスタツリーのノードに割り当てられている写真データの数は、写真データpic1乃至pic4の４枚であるため、写真データpic9を注目データpicnewとして、図３０のクラスタリング処理が開始されると、ステップＳ１０１からステップＳ１０６に進み、上述したように、現在のクラスタツリーのルートノードNrootが包含するノードのうちの右端ノードRm(Nroot)、つまり、クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)よりも古いかどうかが判定される。
【０４８９】
クラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic4であり、その写真データpic4の撮影日時tは60である。また、注目データpicnewである写真データpic9の撮影日時tは20である。
【０４９０】
従って、ステップＳ１０６では、現在のクラスタツリーの右端のリーフノードRm(Nroot)に割り当てられている写真データの撮影日時t(Rm(Nroot))(=60)が、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=20)よりも古くないと判定され、ステップＳ１０７に進み、上述したように、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、現在のクラスタツリーのルートノードNrootが包含するノードのうちの左端ノードLm(Nroot)、つまり、クラスタツリーの左端のリーフノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))よりも古いかどうかが判定される。
【０４９１】
クラスタツリーの左端のリーフノードRm(Nroot)に割り当てられている写真データは、写真データpic1であり、その写真データpic1の撮影日時tは0である。また、注目データpicnewである写真データpic9の撮影日時tは20である。
【０４９２】
従って、ステップＳ１０６では、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=20)が、現在のクラスタツリーの左端のリーフノードLm(Nroot)に割り当てられている写真データの撮影日時t(Lm(Nroot))(=0)よりも古くないと判定され、ステップＳ１１２に進み、図３５の関数FBN(Nroot,Nnew)が呼び出される。
【０４９３】
図３５の関数FBN(Nroot,Nnew)の処理では、ステップＳ１９１において、クラスタツリーのルートノードNroot(=N1234)が、仮の分岐ノードNpとされ、ステップＳ１９２において、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))よりも古いかどうか、即ち、式t(Nnew)＜t(Rm(l(Np)))が満たされるかどうかが判定される。
【０４９４】
いまの場合、注目データpicnewである写真データpic9の撮影日時t(Nnew)は20である。また、仮の分岐ノードNpは、ルートノードN1234であるから、その左側右端ノードRm(l(Np))は、ノードN2であり、ノードN2は、写真データpic2が割り当てられている。そして、写真データpic2の撮影日時t(Rm(l(Np)))は、10である。
【０４９５】
従って、ステップＳ１９２では、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)(=20)が、仮の分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データの撮影日時t(Rm(l(Np)))(=10)よりも古くないと判定され、ステップＳ１９４に進み、注目ノードNnewに割り当てられている注目データpicnewの撮影日時t(Nnew)が、仮の分岐ノードNpの右側左端ノードLm(r(Np))に割り当てられている写真データの撮影日時t(Lm(r(Np)))よりも新しいかどうか、即ち、式t(Lm(r(Np)))＜t(Nnew)が満たされるかどうかが判定される。
【０４９６】
いまの場合、仮の分岐ノードNp（ルートノードN1234）の右側左端ノードLm(r(Np))は、ノードN3であり、ノードN3は、写真データpic3に割り当てられている。そして、写真データpic3の撮影日時t(Lm(r(Np)))は、40である。
【０４９７】
従って、ステップＳ１９４では、撮影日時t(Nnew)(=20)が、撮影日時t(Lm(r(Np)))(=40)よりも新しくないと判定され、関数FBN(Nroot,Nnew)の戻り値として、いま仮の分岐ノードNpとなっているルートノードN1234が返される。
【０４９８】
その結果、図３０のステップＳ１１２では、ルートノードN1234が分岐ノードNpとされ、ステップＳ１１３に進み、分岐ノードNpの左ノードl(Np)に対応するクラスタClの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離である左クラスタ距離dl、および、分岐ノードNpの右ノードr(Np)に対応するクラスタCrの間近写真データと、注目ノードNnewに割り当てられた注目データpicnewとの距離である右クラスタ距離drの大小関係が判定される。
【０４９９】
ここで、左クラスタ距離dlは、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Rm(l(Np)),Nnew)でもある。
【０５００】
いまの場合、分岐ノードNpは、ルートノードN1234であるので、左クラスタ距離dlは、ルートノードN1234の左側右端ノードRm(l(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Rm(l(Np)),Nnew)、即ち、写真データpic2と写真データpic9との距離となる。
【０５０１】
写真データpic2の撮影情報(x,y,t)は(0,10,10)であり、写真データpic9の撮影情報(x,y,t)は(12,10,20)であるから、写真データpic2と写真データpic9との距離である左クラスタ距離dlは、|0-12|+|10-10|+|10-20|=22となる。
【０５０２】
また、右クラスタ距離drは、ルートノードN1234の右側左端ノードLm(r(Np))に割り当てられている写真データと、注目ノードNnewに割り当てられている注目データpicnewとの距離dpic(Lm(r(Np)),Nnew)（＝dpic(Nnew,Lm(r(Np)))）、即ち、写真データpic3と写真データpic9との距離となる。
【０５０３】
写真データpic3の撮影情報(x,y,t)は(20,10,40)で、写真データpic9の撮影情報(x,y,t)は(12,10,20)であるから、写真データpic3と写真データpic9との距離である右クラスタ距離drは、|20-12|+|10-10|+|40-20|=28となる。
【０５０４】
従って、図３０のステップＳ１１３では、左クラスタ距離dl(=22)が、右クラスタ距離dr(=28)より小であると判定され、ステップＳ１１４に進み、図３３の関数IRM(Nq,Nnew)が、その引数となっている候補ノードNqに、分岐ノードNp（ルートノードN1234）の左ノードl(Np)、即ち、ノードN12をセットして呼び出される。
【０５０５】
図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５２において、上述したように、候補ノードNqの左側右端ノードRm(l(Nq))に割り当てられている写真データと、右側左端ノードLm(r(Nq)に割り当てられている写真データとの距離dpic(Rm(l(Nq)),Lm(r(Nq))が、候補ノードNqに対応する候補クラスタCqにクラスタリングされている写真データのうちの隣接する写真データどうしの最大距離dqとして求められる。
【０５０６】
いまの場合、候補ノードNqがノードN12であるから、左側右端ノードRm(l(Nq))に割り当てられている写真データは、写真データpic1であり、右側左端ノードLm(r(Nq)に割り当てられている写真データは、写真データpic2である。従って、ステップＳ１５２では、写真データpic1とpic2の距離が、最大距離dqとして求められる。
【０５０７】
ここで、写真データpic1とpic2の距離は、図３７に示したように、20であり、従って、最大距離dqとしては、図４２左から２番目に示すように、20が求められる。
【０５０８】
さらに、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５３において、上述したように、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データと、注目データpicnewとの距離が、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnとして求められる。
【０５０９】
いまの場合、候補ノードNqがノードN12であり、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５１において、候補ノードNqであるN12を左ノードl(Np)とするノード、即ち、ルートノードN1234が分岐ノードNpとされる。この場合、分岐ノードNpの左側右端ノードRm(l(Np))に割り当てられている写真データは、候補ノードNq(=l(Np))に包含されるノードのうちの右端ノードRm(Nq)に割り当てられている写真データとなり、この写真データは、注目データpicnewの左隣の写真データとなる。
【０５１０】
注目データpicnewである写真データpic9の左隣の写真データは写真データpic2である。そして、写真データpic2の撮影情報(x,y,t)は(0,10,10)であり、写真データpic9の撮影情報(x,y,t)は(12,10,20)であるから、写真データpic2とpic9との距離である、候補クラスタCqの間近写真データと注目ノードNnewに割り当てられている注目データpicnewとの距離dnは、図４２左から２番目に示すように、|0-12|+|10-10|+|10-20|=22となる。
【０５１１】
以上から、図３３の関数IRM(Nq,Nnew)の処理では、ステップＳ１５４において、距離dn(=22)が、最大距離dq(=20)よりも大であると判定され、ステップＳ１５５に進み、左ノードl(Nin)が候補ノードNqとなり、右ノードr(Nin)が注目ノードNnewとなるように、新たなノードNinが、クラスタツリーに追加される。
【０５１２】
即ち、いまの場合、候補ノードNqはノードN12であるため、図４２左から２番目に示すように、左ノードl(Nin)がノードN12となり、右ノードr(Nin)が注目ノードNnewとなるように、新たなノードNinが、クラスタツリーに追加される。
【０５１３】
そして、図３３の関数IRM(Nq,Nnew)の処理から、図３０のステップＳ１１４にリターンし、ステップＳ１１６において、新たなノードNinが、分岐ノードNp、即ち、いまの場合、ルートノードN1234の左ノードl(Np)とされる。その結果、図４２左から３番目（右から１番目）に示すようなクラスタツリーが得られる。
【０５１４】
次に、図４３乃至図４７は、図１の表示装置１６における写真データの表示例を示している。
【０５１５】
例えば、ユーザが、写真データを表示するように、操作部１７を操作すると、表示制御装置１５は、クラスタツリー記憶装置１４に記憶されたクラスタツリーを参照し、そのクラスタツリーに基づいて、写真データのサムネイルを表示する。
【０５１６】
即ち、例えば、図６に示したクラスタツリーが、クラスタツリー記憶装置１４に記憶されているとすると、表示制御装置１５は、例えば、図４３上側に示すように、表示装置１６の表示画面の上半分の領域である親ノード領域１６Ｕに、クラスタツリー（図６）のルートノードN11（を表すシンボル）を表示させる。
【０５１７】
さらに、表示制御装置１５は、表示装置１６の表示画面の下半分の左側の領域である左ノード領域１６Ｌに、親ノード領域１６Ｕに表示されているルートノードN11の左ノードであるノードN21に対応するクラスタに属する写真データpic1乃至pic10のサムネイルを表示させるとともに、表示装置１６の表示画面の下半分の右側の領域である右ノード領域１６Ｒに、親ノード領域１６Ｕに表示されているルートノードN11の右ノードであるノードN22に対応するクラスタに属する写真データpic11およびpic12のサムネイルを表示させる。
【０５１８】
なお、表示制御装置１５は、データ記憶装置１２に記憶されている写真データから、その写真データのサムネイルを生成する。
【０５１９】
操作部１７は、図４３に示すように、上ボタン１７Ｕ、左ボタン１７Ｌ、および右ボタン１７Ｒを有しており、表示装置１６が図４３上側の表示状態になっているときに、ユーザが、例えば、左ノード領域１６Ｌにサムネイルが表示された写真データpic1乃至pic10を指示するように、左ボタン１７Ｌを１回だけ操作すると、表示装置１６の表示状態は、図４３下側に示すようになる。
【０５２０】
即ち、表示制御装置１５は、親ノード領域１６Ｕに、ルートノードN11の左ノードであるノードN21を表示させる。さらに、表示制御装置１５は、左ノード領域１６Ｌに、親ノード領域１６Ｕに表示されているノードN21の左ノードであるノードN31に対応するクラスタに属する写真データpic1乃至pic6のサムネイルを表示させるとともに、右ノード領域１６Ｒに、親ノード領域１６Ｕに表示されているノードN21の右ノードであるノードN32に対応するクラスタに属する写真データpic7乃至pic10のサムネイルを表示させる。
【０５２１】
次に、表示装置１６が図４３下側の表示状態になっているときに、ユーザが、例えば、左ノード領域１６Ｌに表示された写真データpic1乃至pic6を指示するように、左ボタン１７Ｌをさらに１回だけ操作すると、表示装置１６の表示状態は、図４４下側に示すようになる。
【０５２２】
即ち、表示制御装置１５は、親ノード領域１６Ｕに、ノードN21の左ノードであるノードN31を表示させる。さらに、表示制御装置１５は、左ノード領域１６Ｌに、親ノード領域１６Ｕに表示されているノードN31の左ノードであるノードN41に対応するクラスタに属する写真データpic1乃至pic3のサムネイルを表示させるとともに、右ノード領域１６Ｒに、親ノード領域１６Ｕに表示されているノードN31の右ノードであるノードN42に対応するクラスタに属する写真データpic4乃至pic6のサムネイルを表示させる。
【０５２３】
なお、表示装置１６が図４４下側の表示状態になっているときに、ユーザが、例えば、親ノード領域１６Ｕに表示されたノードN31の上の階層を指示するように、上ボタン１７Ｕを１回だけ操作すると、表示装置１６の表示状態は、図４４上側（図４３下側）の状態となる。
【０５２４】
また、表示装置１６が図４４上側の表示状態になっているときに、ユーザが、例えば、右ノード領域１６Ｒに表示された写真データpic7乃至pic10を指示するように、右ボタン１７Ｒを操作すると、表示装置１６の表示状態は、図４５下側に示すようになる。
【０５２５】
即ち、表示制御装置１５は、親ノード領域１６Ｕに、ノードN21の右ノードであるノードN32を表示させる。さらに、表示制御装置１５は、左ノード領域１６Ｌに、親ノード領域１６Ｕに表示されているノードN32の左ノードであるノードN43に対応するクラスタに属する写真データpic7乃至pic9のサムネイルを表示させるとともに、右ノード領域１６Ｒに、親ノード領域１６Ｕに表示されているノードN32の右ノードであるノードN44に対応するクラスタに属する写真データpic10のサムネイルを表示させる。
【０５２６】
なお、表示装置１６が図４５下側の表示状態になっているときに、ユーザが、例えば、親ノード領域１６Ｕに表示されたノードN32の上の階層を指示するように、上ボタン１７Ｕを１回だけ操作すると、表示装置１６の表示状態は、図４５上側の状態となる。
【０５２７】
以上のように、表示装置１６においては、親ノード領域１６Ｕにノード（を表すシンボル）が表示される。さらに、親ノード領域１６Ｕに表示されているノードの左ノードに対応するクラスタに属する写真データのサムネイルが、左ノード領域１６Ｌに表示されるとともに、親ノード領域１６Ｕに表示されているノードの右ノードに対応するクラスタに属する写真データのサムネイルが、右ノード領域１６Ｒに表示される。
【０５２８】
そして、ユーザが、左ボタン１７Ｌを操作した場合、いま親ノード領域１６Ｕに表示されているノードの左ノードが、親ノード領域１６Ｕに表示される。さらに、親ノード領域１６Ｕに表示されているノードの左ノードに対応するクラスタに属する写真データのサムネイルが、左ノード領域１６Ｌに表示されるとともに、親ノード領域１６Ｕに表示されているノードの右ノードに対応するクラスタに属する写真データのサムネイルが、右ノード領域１６Ｒに表示される。
【０５２９】
また、ユーザが、右ボタン１７Ｒを操作した場合、いま親ノード領域１６Ｕに表示されているノードの右ノードが、親ノード領域１６Ｕに表示される。そして、親ノード領域１６Ｕに表示されているノードの左ノードに対応するクラスタに属する写真データのサムネイルが、左ノード領域１６Ｌに表示されるとともに、親ノード領域１６Ｕに表示されているノードの右ノードに対応するクラスタに属する写真データのサムネイルが、右ノード領域１６Ｒに表示される。
【０５３０】
さらに、ユーザが、上ボタン１７Ｕを操作した場合、いま親ノード領域１６Ｕに表示されているノードを子ノードとするノード（親ノード）が、親ノード領域１６Ｕに表示される。そして、親ノード領域１６Ｕに表示されているノードの左ノードに対応するクラスタに属する写真データのサムネイルが、左ノード領域１６Ｌに表示されるとともに、親ノード領域１６Ｕに表示されているノードの右ノードに対応するクラスタに属する写真データのサムネイルが、右ノード領域１６Ｒに表示される。
【０５３１】
従って、ユーザは、操作部１７の上ボタン１７Ｕ、左ボタン１７Ｌ、右ボタン１７Ｒを適宜操作して、所望の写真を容易に見つけ出すことができる。
【０５３２】
なお、図４３乃至図４５では、左ノード領域１６Ｌには、親ノード領域１６Ｕに表示されているノードの左ノードに対応するクラスタに属する写真データすべてのサムネイルを表示し、右ノード領域１６Ｒにも、親ノード領域１６Ｕに表示されているノードの右ノードに対応するクラスタに属する写真データすべてのサムネイルを表示するようにしたが、その他、例えば、図４６や図４７に示すように、左ノード領域１６Ｌには、親ノード領域１６Ｕに表示されているノードの左ノードに対応するクラスタに属する写真データのうちの代表的な写真データだけを表示することができ、右ノード領域１６Ｒにも、親ノード領域１６Ｕに表示されているノードの右ノードに対応するクラスタに属する写真データのうちの代表的な写真データだけを表示するようにすることができる。
【０５３３】
即ち、図４６では、親ノード領域１６ＵにノードN11が表示されている。そして、左ノード領域１６Ｌには、親ノード領域１６Ｕに表示されているノードN11の左ノードN21に対応するクラスタに属する写真データpic1乃至pic10のうちの、例えば、撮影日時が最も古い写真データpic1を、代表的な写真データとして、その写真データpic1だけが表示されている。同様に、右ノード領域１６Ｒには、親ノード領域１６Ｕに表示されているノードN11の右ノードN22に対応するクラスタに属する写真データpic11およびpic12のうちの、撮影日時が最も古い写真データpic11を、代表的な写真データとして、その写真データpic11だけが表示されている。
【０５３４】
また、図４７では、親ノード領域１６ＵにノードN31が表示されている。そして、左ノード領域１６Ｌには、親ノード領域１６Ｕに表示されているノードN31の左ノードN41に対応するクラスタに属する写真データpic1乃至pic3のうちの、撮影日時が最も古い写真データpic1を、代表的な写真データとして、その写真データpic1だけが表示されている。同様に、右ノード領域１６Ｒには、親ノード領域１６Ｕに表示されているノードN31の右ノードN42に対応するクラスタに属する写真データpic4乃至pic6のうちの、撮影日時が最も古い写真データpic4を、代表的な写真データとして、その写真データpic4だけが表示されている。
【０５３５】
なお、図４３乃至図４５のように、サムネイルを表示するか、図４６および図４７のように、代表的な写真データだけを表示するかは、例えば、ユーザが操作部１７を操作することにより設定可能とすることができる。
【０５３６】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０５３７】
そこで、図４８は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０５３８】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク１０５やＲＯＭ１０３に予め記録しておくことができる。
【０５３９】
あるいはまた、プログラムは、フレキシブルディスク、CD-ROM(Compact Disc Read Only Memory)，MO(Magneto Optical)ディスク，DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体１１１に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体１１１は、いわゆるパッケージソフトウエアとして提供することができる。
【０５４０】
なお、プログラムは、上述したようなリムーバブル記録媒体１１１からコンピュータにインストールする他、ダウンロードサイトから、ディジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを、通信部１０８で受信し、内蔵するハードディスク１０５にインストールすることができる。
【０５４１】
コンピュータは、CPU(Central Processing Unit)１０２を内蔵している。CPU１０２には、バス１０１を介して、入出力インタフェース１１０が接続されており、CPU１０２は、入出力インタフェース１１０を介して、ユーザによって、キーボードや、マウス、マイク等で構成される入力部１０７が操作等されることにより指令が入力されると、それにしたがって、ROM(Read Only Memory)１０３に格納されているプログラムを実行する。あるいは、また、CPU１０２は、ハードディスク１０５に格納されているプログラム、衛星若しくはネットワークから転送され、通信部１０８で受信されてハードディスク１０５にインストールされたプログラム、またはドライブ１０９に装着されたリムーバブル記録媒体１１１から読み出されてハードディスク１０５にインストールされたプログラムを、RAM(Random Access Memory)１０４にロードして実行する。これにより、CPU１０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、CPU１０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース１１０を介して、LCD(Liquid Crystal Display)やスピーカ等で構成される出力部１０６から出力、あるいは、通信部１０８から送信、さらには、ハードディスク１０５に記録等させる。
【０５４２】
ここで、本明細書において、コンピュータに各種の処理を行わせるためのプログラムを記述する処理ステップは、必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むものである。
【０５４３】
また、プログラムは、１のコンピュータにより処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０５４４】
以上のように、情報処理装置２（図１）による階層的クラスタリングでは、撮影日時順の写真データの並びを、すべての階層で維持しつつ、写真データをクラスタリングすることができる。
【０５４５】
また、階層的クラスタリングでは、クラスタツリーのノードを、ルートノードから辿っていくことにより、即ち、図３３のステップＳ１５６や図３４のステップＳ１７６で説明したように、分岐ノードNpおよび候補ノードNqを更新していくことにより、注目データpicnewに割り当てられる注目ノードNnewを子ノードとする新たなノードNinを追加するクラスタツリーの位置を決定することができる。
【０５４６】
さらに、階層的クラスタリングでは、撮影日時順の写真データの並びにおける、隣接する写真データどうしの距離だけを求めればよく、隣接しない写真データどうしの距離は求める必要がない。従って、少ない計算量で、写真データをクラスタリングすることができる。
【０５４７】
即ち、データのクラスタリングの方法としては、例えば、最短距離法や、最長距離法、ウォード法などが知られている。最短距離法や、最長距離法、ウォード法によれば、クラスタリングの対象とするデータ（要素）を、距離が最も近いデータどうしをまとめる（併合する）ことによって、階層的なクラスタリングが行われる。
【０５４８】
しかしながら、最短距離法や、最長距離法、ウォード法では、クラスタリングの対象とするデータのすべての組み合わせについて距離を求める必要があり、クラスタリングの対象とするデータがn個であるとすると、n(n-1)/2通りのデータどうしの距離を計算する必要がある。従って、最短距離法や、最長距離法、ウォード法では、クラスタリングの対象となるデータが多くなると、距離の計算量も、個数ｎの２乗に比例して多くなる。
【０５４９】
これに対して、情報処理装置２による階層的クラスタリングでは、撮影日時順の写真データの並びにおける、隣接する写真データどうしの距離だけを求めればよいので、階層的クラスタリングの対象とするデータの性質にも依存するが、例えば、階層的クラスタリングの対象とするデータがランダムなデータであれば、n個のデータに対して、クラスタツリーの高さ（階層の数）は、log2(n)となり、距離の計算量はO(n×log2(n))のオーダとなる。
【０５５０】
なお、本実施の形態では、写真データの階層的クラスタリングにあたり、写真データを撮影日時順に並べるようにしたが、その他、写真データは、例えば、撮影位置にしたがった順番で並べることもできる。即ち、写真データは、例えば、ユーザの自宅の位置などを基準として、撮影位置が、自宅の位置から近い順に並べることが可能である。
【０５５１】
また、本実施の形態では、静止画である写真データを、階層的クラスタリングの対象としたが、写真データの他、例えば、動画が格納された動画ファイルのデータ、その他、ある規則にしたがって並べることができ、かつ、隣接するデータどうしの所定の距離尺度による距離を求めることができるデータを、階層的クラスタリングの対象とすることができる。
【０５５２】
なお、写真データどうしの距離を、式（２）や式（３）に示したように、撮影日時や撮影位置の他、移動速度を加味して求めることにより、写真データを、より適切にクラスタリングすることができる。
【０５５３】
即ち、例えば、いま、重み係数αおよびβを１とするとともに、重み係数γを０とした式（２）によって、写真データpic#iとpic#jとの距離dpic(i,j)を、移動速度を加味せずに求めることとした場合、写真データpic#iを撮影してから、徒歩により、1000秒かけて500mだけ移動した位置で、写真データpic#jを撮影したときの写真データpic#iとpic#jとの距離dpic(i,j)は、1000+500=1500となり、写真データpic#iを撮影してから、自動車により、500秒で1000mだけ移動した位置で、写真データpic#jを撮影したときの写真データpic#iとpic#jとの距離dpic(i,j)は、500+1000=1500となるから、同一になる。
【０５５４】
一方、重み係数γを１とした場合、徒歩で移動して、写真データpic#iとpic#jを撮影したときの写真データpic#iとpic#jとの距離dpic(i,j)は、1000+500+500/1000=1500.5となる。また、自動車で移動して、写真データpic#iとpic#jを撮影したときの写真データpic#iとpic#jとの距離dpic(i,j)は、500+1000+1000/500=1502となる。
【０５５５】
従って、徒歩で移動したときの写真データpic#iとpic#jとの距離dpic(i,j)と、自動車で移動したときの写真データpic#iとpic#jとの距離dpic(i,j)とは、異なる値になり、徒歩で移動したときの写真データpic#iとpic#jとの距離dpic(i,j)の方が、自動車で移動したときの写真データpic#iとpic#jとの距離dpic(i,j)よりも小になる。
【０５５６】
その結果、徒歩で移動したときの写真データpic#iとpic#jの方が、自動車で移動したときの写真データpic#iとpic#jよりも、粒度の小さいクラスタにクラスタリングされやすくなる。
【０５５７】
即ち、移動速度を加味することにより、撮影日時の差（時間的な距離）が同一の写真データどうしは、撮影位置がより近い写真データどうしほど、粒度の小さいクラスタにクラスタリングされやすくなる。また、撮影位置の差（空間的な距離）が同一の写真データどうしは、撮影日時がより近い写真データどうしほど、粒度の小さいクラスタにクラスタリングされやすくなる。
【０５５８】
一般に、人（ユーザ）は、撮影日時の差が同一ならば、撮影位置がより近い写真データどうしをまとめるようにし、撮影位置の差が同一ならば、撮影日時がより近い写真データどうしをまとめるようにすることが多い。従って、移動速度を加味して階層的クラスタリングを行うことにより、人（ユーザ）が行う主観的な分類に即したクラスタリングを行うことができる。
【０５５９】
なお、本実施の形態では、階層的クラスタリングを、カメラ１とは別の装置である情報処理装置２（図１）で行うようにしたが、階層的クラスタリングは、カメラ１内部で行うようにすることが可能である。
【図面の簡単な説明】
【０５６０】
【図１】本発明を適用した情報処理システムの一実施の形態の構成例を示すブロック図である。
【図２】クラスタツリーを示す図である。
【図３】クラスタツリーによるクラスタリング結果を示す図である。
【図４】クラスタツリーを示す図である。
【図５】カメラ１で撮影が行われた撮影位置を示す図である。
【図６】クラスタツリーを示す図である。
【図７】クラスタツリーの生成手順を説明するための図である。
【図８】クラスタツリーの生成手順を説明するための図である。
【図９】クラスタツリーの生成手順を説明するための図である。
【図１０】クラスタツリーの生成手順を説明するための図である。
【図１１】クラスタツリーの生成手順を説明するための図である。
【図１２】クラスタツリーの生成手順を説明するための図である。
【図１３】クラスタツリーの生成手順を説明するための図である。
【図１４】クラスタツリーの生成手順を説明するための図である。
【図１５】クラスタツリーの生成手順を説明するための図である。
【図１６】クラスタリング装置１３の構成例を示すブロック図である。
【図１７】クラスタリング装置１３の処理を説明するフローチャートである。
【図１８】クラスタリング処理を説明するフローチャートである。
【図１９】木構造処理部２２の構成例を示すブロック図である。
【図２０】分岐ノード検索処理を説明するための図である。
【図２１】ノード追加処理を説明するための図である。
【図２２】ノード追加処理を説明するための図である。
【図２３】ノード追加処理を説明するための図である。
【図２４】ノード追加処理を説明するための図である。
【図２５】ノード追加処理を説明するための図である。
【図２６】ノード追加処理を説明するための図である。
【図２７】木構造処理を説明するフローチャートである。
【図２８】分岐ノード検索処理を説明するフローチャートである。
【図２９】ノード追加処理を説明するフローチャートである。
【図３０】クラスタリング処理を説明するフローチャートである。
【図３１】関数Rm(N)の処理を説明するフローチャートである。
【図３２】関数Lm(N)の処理を説明するフローチャートである。
【図３３】関数IRM(Nq,Nnew)の処理を説明するフローチャートである。
【図３４】関数ILM(Nq,Nnew)の処理を説明するフローチャートである。
【図３５】関数FBN(Nq,Nnew)の処理を説明するフローチャートである。
【図３６】カメラ１で撮影された写真データの例を示す図である。
【図３７】クラスタツリーを示す図である。
【図３８】クラスタツリーを示す図である。
【図３９】クラスタツリーを示す図である。
【図４０】クラスタツリーを示す図である。
【図４１】クラスタツリーを示す図である。
【図４２】クラスタツリーを示す図である。
【図４３】クラスタツリーによりクラスタリングされた写真データの表示例を示す図である。
【図４４】クラスタツリーによりクラスタリングされた写真データの表示例を示す図である。
【図４５】クラスタツリーによりクラスタリングされた写真データの表示例を示す図である。
【図４６】クラスタツリーによりクラスタリングされた写真データの表示例を示す図である。
【図４７】クラスタツリーによりクラスタリングされた写真データの表示例を示す図である。
【図４８】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【符号の説明】
【０５６１】
１  カメラ，  ２  情報処理装置，  １１  入力インタフェース，  １２  データ記憶装置，  １３  クラスタリング装置，  １４  クラスタツリー記憶装置，  １５  表示制御装置，  １６  表示装置，  １７  操作部，  ２０  メタデータ読み出し部，  ２２  木構造処理部，  ３１  分岐ノード検索部，  ３２  ノード追加部，  ４１  距離算出部，  ４２  判定部，  ４３  追加部，  １０１  バス，  １０２  CPU，  １０３  ROM，  １０４  RAM，  １０５  ハードディスク，  １０６  出力部，  １０７  入力部，  １０８  通信部，  １０９  ドライブ，  １１０  入出力インタフェース，  １１１  リムーバブル記録媒体
【図１】
2006344005.tif 000003
【図２】
2006344005.tif 000004
【図３】
2006344005.tif 000005
【図４】
2006344005.tif 000006
【図５】
2006344005.tif 000007
【図６】
2006344005.tif 000008
【図７】
2006344005.tif 000009
【図８】
2006344005.tif 000010
【図９】
2006344005.tif 000011
【図１０】
2006344005.tif 000012
【図１１】
2006344005.tif 000013
【図１２】
2006344005.tif 000014
【図１３】
2006344005.tif 000015
【図１４】
2006344005.tif 000016
【図１５】
2006344005.tif 000017
【図１６】
2006344005.tif 000018
【図１７】
2006344005.tif 000019
【図１８】
2006344005.tif 000020
【図１９】
2006344005.tif 000021
【図２０】
2006344005.tif 000022
【図２１】
2006344005.tif 000023
【図２２】
2006344005.tif 000024
【図２３】
2006344005.tif 000025
【図２４】
2006344005.tif 000026
【図２５】
2006344005.tif 000027
【図２６】
2006344005.tif 000028
【図２７】
2006344005.tif 000029
【図２８】
2006344005.tif 000030
【図２９】
2006344005.tif 000031
【図３０】
2006344005.tif 000032
【図３１】
2006344005.tif 000033
【図３２】
2006344005.tif 000034
【図３３】
2006344005.tif 000035
【図３４】
2006344005.tif 000036
【図３５】
2006344005.tif 000037
【図３６】
2006344005.tif 000038
【図３７】
2006344005.tif 000039
【図３８】
2006344005.tif 000040
【図３９】
2006344005.tif 000041
【図４０】
2006344005.tif 000042
【図４１】
2006344005.tif 000043
【図４２】
2006344005.tif 000044
【図４３】
2006344005.tif 000045
【図４４】
2006344005.tif 000046
【図４５】
2006344005.tif 000047
【図４６】
2006344005.tif 000048
【図４７】
2006344005.tif 000049
【図４８】
2006344005.tif 000050