(57)【要約】【課題】課題複数種類の特徴量からなる高次元空間の探索において、各々の特徴量に異なる重み付けが動的に与えられる場合の多次元空間データ探索方法を提供する。【解決手段】データベースに格納されるマルチメディアデータを組織する複数の多次元空間データ木構造において、重み付けが大きい多次元空間データ木構造を優先して探索し、リーフノードに関する悲観的距離を用いて、アクセス済みノードに関する楽観的距離を対象とした枝刈戦略を実施し、最近傍リーフノードを確定することにより、ノードアクセス数を抑えることで探索性能の向上を実現する。【選択図】  図１
2004348426.tif 000002
【特許請求の範囲】
【請求項１】
データベースに格納されるマルチメディアデータを複数の多次元空間データ木構造に格納したものについて、
重み付けが強い多次元空間データ木構造を優先して探索し、
リーフノードに関して、リーフノードまでアクセスしていない次元が存在する場合に、その次元に関してリーフノードがとり得る最大距離を算出し、
アクセス済みのノードに関して、リーフノードまでアクセスしていない次元が存在する場合に、その次元に関してリーフノードがとり得る最小距離を算出し、前記最大距離と最小距離とを用いて枝刈戦略を実施することを特徴とする多次元空間データ探索方法。
【請求項２】
前記請求項１に記載の多次元空間データ探索方法において、
前記枝刈戦略の際に、他のノードの枝刈に成功したリーフノードに、枝刈した他ノードのインデックス情報を保持し、そのリーフノードが最近傍ノードであることが確定した際に、保持していたインデックス情報を探索対象空間に戻すことにより、次の最近傍ノードを探索することを特徴とする多次元空間データ探索方法。
【請求項３】
【数３】
2004348426.tif 000040
のように表される多次元空間データ木構造において、
アクセス済ノンリーフノード選定手段により、すべてのアクセス済ノンリーフノードついて
【数４】
2004348426.tif 000041
により数値を算出し、算出される数値が最小のものを次にアクセスするノンリーフノードとして選定し、選定したノンリーフノードにアクセスする第１ステップと、
アクセス済ノンリーフノード選定手段により、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、有していない場合には第１ステップに戻ることを決定し、有している場合には第３ステップに進むことを決定する第２ステップと、
枝刈手段により、アクセス済リーフノードについて
【数５】
2004348426.tif 000042
により問い合わせ点との最大距離を算出し、
アクセス済ノンリーフノードについて
【数６】
2004348426.tif 000043
により問い合わせ点との最小距離を算出し、前記最大距離と最小距離とを用いて枝刈戦略を行い、アクセス済リーフノードの最大距離よりもアクセス済ノンリーフノードの最小距離が大きい場合に、そのノンリーフノードは枝刈の対象となり、アクセス済ノンリーフノード集合を保持しているアクセス済リストから削除して第４ステップに進むことを決定し、また前記技刈戦略が行われなかった場合、若しくは前記枝刈リスト中で最も小さい距離を持つアクセス済ノンリーフノードよりも、小さい距離を持つそのアクセス済リーフノードと同じ多次元空間データ木に所属するアクセス済ノンリーフノードが存在すると判断した場合は、第１ステップに戻ることを決定する第３ステップと、
最近傍判定手段により、前記枝刈戦略により選定された最近傍候補ノードについては前記最大距離をそのまま用い、枝刈戦略リスト中の最近傍候補ノード以外の全アクセス済リーフノードについては
【数７】
2004348426.tif 000044
により最小距離を算出し、これらの最大距離と最小距離とを比較し、最近傍候補ノードの最大距離が最も小さい場合に、この最近傍候補ノードが最近傍の多次元空間データであることを確定する第４ステップと、からなることを特徴とする多次元空間データ探索方法。
【請求項４】
前記請求項３に記載の多次元空間データ探索方法において、
前記枝刈手段により、前記第３ステップでアクセス済リーフノードに枝刈されたノードを、前記アクセス済リーフノードに保持し、
前記最近傍判定手段により、前記第４ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする多次元空間データ探索方法。
【請求項５】
【数３】
2004348426.tif 000045
のように表される多次元空間データ木構造において、
アクセス済ノンリーフノード選定手段により、すべてのアクセス済ノンリーフノードについて
【数４】
2004348426.tif 000046
により数値を算出し、算出される数値が最小のものを次にアクセスするノンリーフノードとして選定し、選定したノンリーフノードにアクセスする第１ステップと、
アクセス済ノンリーフノード選定手段により、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、有していない場合には第１ステップに戻ることを決定し、有している場合には第３ステップに進むことを決定する第２ステップと、
枝刈手段により、アクセス済リーフノードについて
【数５】
2004348426.tif 000047
により問い合わせ点との最大距離を算出し、
アクセス済ノンリーフノードについて
【数６】
2004348426.tif 000048
により問い合わせ点との最小距離を算出し、距離の値が小さい順に整列させ、最も小さい距離を有するものがリーフノードである場合には後述の第５ステップに進むことを決定し、最も小さい距離を有するものがノンリーフノードである場合には、アクセス済リーフノードの最大距離よりも大きい最小距離を有するアクセス済ノンリーフノードを枝刈し、アクセス済ノンリーフノード集合を保持しているアクセス済リストから削除してから後述の第４ステップに進むことを決定する、第３ステップと、
枝刈手段により、アクセスできるノンリーフノードが無い多次元空間データ木の有無を判断し、有ると判断した場合は後述の第５ステップに進むことを決定し、無いと判断した場合は第１ステップに戻ることを決定する第４ステップと、
最近傍判定手段により、前記最大距離が最も小さいリーフノードについては前記最大距離をそのまま用い、それ以外のリーフノードについては
【数７】
2004348426.tif 000049
により最小距離を算出し、これらの最大距離と最小距離とを比較し、前記最大距離が最も小さい場合に、この最大距離を有するリーフノードが最近傍の多次元空間データであることを確定する第５ステップと、からなることを特徴とする多次元空間データ探索方法。
【請求項６】
前記請求項５に記載の多次元空間データ探索方法において、
前記枝刈手段により、前記第３ステップでアクセス済リーフノードに枝刈されたノードを、前記アクセス済リーフノードに保持し、
前記最近傍判定手段により、前記第５ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする多次元空間データ探索方法。
【請求項７】
多次元空間データの最近傍探索において、
アクセス済ノンリーフノード選定手段により、各特徴量のルートノードにアクセスする第１ステップと、
アクセス済ノンリーフノード選定手段により、アクセスしたノードに関する子ノードをアクセス済リストに挿入する第２ステップと、
アクセス済ノンリーフノード選定手段により、アクセス済リストのノンリーフノードについて
【数３】
2004348426.tif 000050
により算出される値をアクセス済リストに格納する第３ステップと、
アクセス済ノンリーフノード選定手段により、前記アクセス済リストから
【数４】
2004348426.tif 000051
により算出される値が、最も小さいものを次にアクセスするノンリーフノードとして選定する第４ステップと、
アクセス済ノンリーフノード選定手段により、選定したノンリーフノードにアクセスする第５ステップと、
アクセス済ノンリーフノード選定手段により、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、リーフノードを有していない場合には第１ステップに戻ることを決定し、リーフノードを有している場合には次のステップに進むことを決定する第６ステップと、
枝刈手段により、アクセス済リーフノードについて
【数５】
2004348426.tif 000052
により問い合わせ点との最大距離を算出し、枝刈戦略リストに挿入する第７ステップと、
枝刈手段により、アクセス済リストに格納されているノンリーフノードについて
【数６】
2004348426.tif 000053
により問い合わせ点との最小距離を算出し、枝刈戦略リストに挿入する第８ステップと、
枝刈手段により、前記枝刈戦略リスト中の各ノードを距離の値が小さい順に整列させる第９ステップと、
枝刈手段により、最も小さい距離の値を有するノードがリーフノードであるかを判断し、リーフノードであると判断した場合には後段の第１３ステップに進むことを決定し、リーフノードではないと判断した場合には次の第１１ステップに進むことを決定する第１０ステップと、
枝刈手段により、前記枝刈戦略リスト中のリーフノードより大きい距離を持つノンリーフノードを枝刈し、アクセス済リストから削除する第１１ステップと、枝刈手段により、アクセスできるノンリーフノードが無い多次元空間データ木が有るかを判断し、無いと判断した場合には第２ステップに戻ることを決定し、有ると判断した場合には次の第１３ステップに進むことを決定する第１２ステップと、
最近傍判定手段により、前記最大距離が最も小さいリーフノードについては前記最大距離をそのまま用い、それ以外のリーフノードについては
【数７】
2004348426.tif 000054
により最小距離を算出し、これらの最大距離と最小距離とを比較し、前記最大距離が最も小さい場合に、この最大距離を有するリーフノードが最近傍の多次元空間データであることを確定する第１３ステップと、からなることを特徴とする多次元空間データ探索方法。
【請求項８】
前記請求項７に記載の多次元空間データ探索方法において、
前記枝刈手段により、前記第１１ステップでリーフノードに枝刈されたノードを、前記リーフノードに保持し、
前記最近傍判定手段により、前記第１３ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする多次元空間データ探索方法。
【請求項９】
検索情報を入力する入力手段と、
【数３】
2004348426.tif 000055
のように表される多次元空間データ木構造を有するデータベースと、
すべてのアクセス済ノンリーフノードについて
【数４】
2004348426.tif 000056
により数値を算出し、算出される数値が最小のものを次にアクセスするノンリーフノードとして選定し、選定したノンリーフノードにアクセスする第１ステップと、
アクセスしたノンリーフノードがリーフノードを有しているかを判断し、有していない場合には第１ステップに戻ることを決定し、有している場合には第３ステップに進むことを決定する第２ステップと、を実行するアクセス済ノンリーフノード選定手段と、
アクセスしたノンリーフノードがリーフノードを有している場合に、アクセス済リーフノードについて
【数５】
2004348426.tif 000057
により問い合わせ点との最大距離を算出し、
アクセス済ノンリーフノードについて
【数６】
2004348426.tif 000058
により問い合わせ点との最小距離を算出し、距離の値が小さい順に整列させ、最も小さい距離を有するものがリーフノードである場合には後述の第５ステップに進むことを決定し、最も小さい距離を有するものがノンリーフノードである場合には、アクセス済リーフノードの最大距離よりも大きい最小距離を有するアクセス済ノンリーフノードを枝刈し、アクセス済ノンリーフノード集合を保持しているアクセス済リストから削除してから後述の第４ステップに進むことを決定する、第３ステップと、
アクセスできるノンリーフノードが無い多次元空間データ木の有無を判断し、有ると判断した場合は後述の第５ステップに進むことを決定し、無いと判断した場合は第１ステップに戻ることを決定する第４ステップと、を実行する枝刈手段と、
前記最大距離が最も小さいリーフノードについては前記最大距離をそのまま用い、それ以外のリーフノードについては
【数７】
2004348426.tif 000059
により最小距離を算出し、これらの最大距離と最小距離とを比較し、前記最大距離が最も小さい場合に、この最大距離を有するリーフノードが最近傍の多次元空間データであることを確定する第５ステップを実行する最近傍判定手段と、
前記最近傍多次元空間データを出力するデータ出力手段と、からなることを特徴とする多次元空間データ探索装置。
【請求項１０】
前記請求項９に記載の多次元空間データ探索装置において、前記枝刈手段は、前記第３ステップでアクセス済リーフノードに枝刈されたノードを、前記アクセス済リーフノードに保持し、
前記最近傍判定手段は、前記第５ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする多次元空間データ探索装置。
【請求項１１】
検索情報を入力する入力手段と、
【数３】
2004348426.tif 000060
のように表される多次元空間データ木構造を有するデータベースと、
各特徴量のルートノードにアクセスする第１ステップと、
アクセスしたノードに関する子ノードをアクセス済リストに挿入する第２ステップと、
アクセス済リストのノンリーフノードについて
【数３】
2004348426.tif 000061
により算出される値をアクセス済リストに格納する第３ステップと、
前記アクセス済リストから
【数４】
2004348426.tif 000062
により算出される値が、最も小さいものを次にアクセスするノンリーフノードとして選定する第４ステップと、
選定したノンリーフノードにアクセスする第５ステップと、
アクセスしたノンリーフノードがリーフノードを有しているかを判断し、リーフノードを有していない場合には第１ステップに戻ることを決定し、リーフノードを有している場合には次のステップに進むことを決定する第６ステップと、を実行するアクセス済ノンリーフノード選定手段と、
アクセス済リーフノードについて
【数５】
2004348426.tif 000063
により問い合わせ点との最大距離を算出し、枝刈戦略リストに挿入する第７ステップと、
アクセス済リストに格納されているノンリーフノードについて
【数６】
2004348426.tif 000064
により問い合わせ点との最小距離を算出し、枝刈戦略リストに挿入する第８ステップと、
前記枝刈戦略リスト中の各ノードを距離の値が小さい順に整列させる第９ステップと、
最も小さい距離の値を有するノードがリーフノードであるかを判断し、リーフノードであると判断した場合には後段の第１３ステップに進むことを決定し、リーフノードではないと判断した場合には次の第１１ステップに進むことを決定する第１０ステップと、
前記枝刈戦略リスト中のリーフノードより大きい距離を持つノンリーフノードを枝刈し、アクセス済リストから削除する第１１ステップと、
アクセスできるノンリーフノードが無い多次元空間データ木が有るかを判断し、無いと判断した場合には第２ステップに戻ることを決定し、有ると判断した場合には次の第１３ステップに進むことを決定する第１２ステップと、を実行する枝刈手段と、
前記最大距離が最も小さいリーフノードについては前記最大距離をそのまま用い、それ以外のリーフノードについては
【数７】
2004348426.tif 000065
により最小距離を算出し、これらの最大距離と最小距離とを比較し、前記最大距離が最も小さい場合に、この最大距離を有するリーフノードが最近傍の多次元空間データであることを確定する第１３ステップを実行する最近傍判定手段と、
前記最近傍多次元空間データを出力するデータ出力手段と、からなることを特徴とする多次元空間データ探索装置。
【請求項１２】
前記請求項１１に記載の多次元空間データ探索装置において、
前記枝刈手段は、前記第１１ステップでリーフノードに枝刈されたノードを、前記リーフノードに保持し、
前記最近傍判定手段は、前記第１３ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする多次元空間データ探索装置。
【請求項１３】
上記の請求項１乃至１２のいずれか１項に記載の多次元空間データ探索方法または多次元空間データ探索装置を、コンピュータプログラムで記載してそれを実行可能にしたことを特徴とするプログラム。
【請求項１４】
上記の請求項１乃至１２のいずれか１項に記載の多次元空間データ探索方法または多次元空間データ探索装置を、コンピュータで実行可能に記載したプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベースに格納される多次元空間データの探索技術に関し、特に多次元空間探索における、多次元空間データ探索方法、多次元空間データ探索装置、多次元空間データ探索プログラム、および多次元空間データ探索プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
従来の空間アクセス法の中で、高次元空間の探索に有用な手法としてＲ−ｔｒｅｅとその派生手法がある（以下、Ｒ−ｔｒｅｅファミリーと呼ぶ。）。Ｒ−ｔｒｅｅファミリーには、Ｒ−ｔｒｅｅ、Ｒ＊−ｔｒｅｅ、Ｈｉｌｂｅｒｔ  Ｒ−ｔｒｅｅ、ＳＳ−ｔｒｅｅ、ＳＲ−ｔｒｅｅなどがあり、いずれもデータオブジェクトは最小包囲領域、つまり最小包囲矩形（ＭＢＲ；Ｍｉｎｉｍｕｍ  Ｂｏｕｎｄｉｎｇ  Ｒｅｃｔａｎｇｌｅ）もしくは最小包囲球（ＭＢＳ；Ｍｉｎｉｍｕｍ  Ｂｏｕｎｄｉｎｇ  Ｓｐｈｅｒｅ）に包囲され、更に階層構造をなしている。多次元空間データ木は、下記の数式１のような構造を有する。
【０００３】
【数１】
2004348426.tif 000003
【０００４】
ここで、εはノードに格納されているエントリ数である。Ｓは、ε個の子ノードのＭＢＲを表現したものである。またｃｈｉｌｄ−ｎｏｄｅｉによって子ノードにアクセスすることができる。ｌｅａｆ＿Ｎｏｄｅの中にはｎ種類の多次元空間データＦｊ（ｊ＝１、・・・・、ｎ）がそれぞれ格納されている。データオブジェクトをあるアルゴリズムに従って、クラスタリングしＭＢＲを定義した上で木構造を構築していく手段については、それぞれのＲ−ｔｒｅｅファミリーによって異なる。
【０００５】
【発明が解決しようとする課題】
上述した従来手法では、多次元空間データ木構造を、固定された重み付けの下で構築する必要がある。多次元空間データ木構造を構築する行程は検索を行う行程よりも処理時間が長いことが一般的であり、重み付き多次元空間データ探索において重み付けが動的に変化する場合、その都度その重み付けの下で多次元空間データ木構造を構築した上で、検索を行ってく方法は現実的ではない。また、重み付けのバリエーション毎に多次元空間データ木構造をあらかじめ構築しておく方法では、無数にある重み付けのバリエーションに対応できない。
【０００６】
現在のところ、従来手法では、ある固定された重み付けの下で構築された木構造を用いて、動的に変化する多次元空間データ探索を行っており、計算量が多く、結果的に処理時間が長くなってしまうことがある。
【０００７】
例として、図１１のような２次元のデータ空間上の問い合わせ点Ｑとの最近傍点を求める問題について説明する。問い合わせ点Ｑから距離の近いノンリーフノード（図１１ではＲ１およびＲ２にあたる）からアクセスしていき、その後、その子ノードの中で距離の近いノードをアクセスしていく。従来手法であると、Ｒ１およびＲ２とＱとの距離が等しいため、Ｒ１およびＲ２の子ノードにアクセスしていき、それぞれの距離を計算しながら枝刈戦略を実施していくことになる。しかし、この２つの次元ｘおよびｙの間に１：０の重み付けがなされた場合を考えると、ｙ次元の数値は距離に反映されないため、Ｒ１内の子ノードのみアクセスすればよいが、従来手法では２つの次元ｘおよびｙの間の重み付けが１：１であることを前提として木構造が構成されているため、どのような重み付けが与えられたとしても、Ｒ１およびＲ２の子ノードにアクセスしていき、枝刈戦略を実施していくことになる。このことは、無駄な計算を実施していることになり、結果的に処理時間が長くなってしまう。
【０００８】
このように、上述した従来の探索処理においては、ｎ個の特徴ベクトルに重み付けが変更される場合でも、あらかじめ固定的に決められた重み付けの下に多次元空間データ木構造を構築しなくてはならないため、結果的に効率的な探索を行うことができない。
【０００９】
重み付き多次元データの問い合わせ点Ｑとの最近傍距離は下記の数式２のように表される。
【００１０】
【数２】
2004348426.tif 000004
【００１１】
各多次元空間データｅｊ（ｊ  ＝  １、・・・・、ｎ）に付与される重みｗｅｉｇｈｔｊ（ｊ  ＝  １、・・・・、ｎ）の間に大きな差がある場合は、重み付けを考慮した探索方法が有効となる。あらかじめ重みが不変であるならば、重み付けをした多次元空間データを用いて多次元空間データ木構造を構築すればよいが、類似画像検索など、色相、彩度、明度、テクスチャ等さまざまな特徴量に与える重み付けを多次元空間データ探索を行うたびに動的に変更するような使い方をするシステムでは計算量が多くなってしまい、効率的な探索ができない場合が生じてしまう。
【００１２】
例えば類似画像検索では、検索対象となる画像の色相、彩度、明度、テクスチャ、形状等様々な特徴量を抽出し、多次元空間データ木構造を構築するが、実際に類似画像検索を行う場合は、色味が似ている画像の検索や模様が似ている画像の検索が要求されるなど、抽出した特徴量に重み付けをつけて検索されることが一般的であるシステムが存在する。
【００１３】
本発明は、重み付けが与えられる単位毎に多次元特徴ベクトルを格納する多次元空間データ木構造を構築し、各特徴量に与えられた重み付けを加味して効率的な探索を行うことができる、多次元空間データ探索方法、多次元空間データ探索装置、多次元空間データ探索プログラム、および多次元空間データ探索プログラムを記録した記録媒体を提供することにある。
【００１４】
【課題を解決するための手段】
そこで前記課題を解決するために、請求項１に記載の多次元空間データ探索方法は、データベースに格納されるマルチメディアデータを複数の多次元空間データ木構造に格納したものについて、重み付けが強い多次元空間データ木構造を優先して探索し、リーフノードに関して、リーフノードまでアクセスしていない次元が存在する場合に、その次元に関してリーフノードがとり得る最大距離（悲観的距離）を算出し、アクセス済みのノードに関して、リーフノードまでアクセスしていない次元が存在する場合に、その次元に関してリーフノードがとり得る最小距離（楽観的距離）を算出し、前記最大距離（悲観的距離）と最小距離（楽観的距離）とを用いて枝刈戦略を実施することを特徴とする。
【００１５】
また、請求項２に記載の多次元空間データ探索方法、は前記請求項１に記載の多次元空間データ探索方法において、前記枝刈戦略の際に、他のノードの枝刈に成功したリーフノードに、枝刈した他ノードのインデックス情報を保持し、そのリーフノードが最近傍ノードであることが確定した際に、保持していたインデックス情報を探索対象空間に戻すことにより、次の最近傍ノードを探索することを特徴とする。
【００１６】
また、請求項３に記載の多次元空間データ探索方法は、
【００１７】
【数３】
2004348426.tif 000005
【００１８】
のように表される多次元空間データ木構造において、アクセス済ノンリーフノード選定手段により、すべてのアクセス済ノンリーフノードついて
【００１９】
【数４】
2004348426.tif 000006
【００２０】
により数値を算出し、算出される数値が最小のものを次にアクセスするノンリーフノードとして選定し、選定したノンリーフノードにアクセスする第１ステップと、アクセス済ノンリーフノード選定手段により、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、有していない場合には第１ステップに戻ることを決定し、有している場合には第３ステップに進むことを決定する第２ステップと、枝刈手段により、アクセス済リーフノードについて
【００２１】
【数５】
2004348426.tif 000007
【００２２】
により問い合わせ点との最大距離を算出し、アクセス済ノンリーフノードについて
【００２３】
【数６】
2004348426.tif 000008
【００２４】
により問い合わせ点との最小距離を算出し、前記最大距離と最小距離とを用いて枝刈戦略を行い、アクセス済リーフノードの最大距離よりもアクセス済ノンリーフノードの最小距離が大きい場合に、そのノンリーフノードは枝刈の対象となり、アクセス済ノンリーフノード集合を保持しているアクセス済リストから削除して第４ステップに進むことを決定し、また前記技刈戦略が行われなかった場合、若しくは前記枝刈リスト中で最も小さい距離を持つアクセス済ノンリーフノードよりも、小さい距離を持つそのアクセス済リーフノードと同じ多次元空間データ木に所属するアクセス済ノンリーフノードが存在すると判断した場合は、第１ステップに戻ることを決定する第３ステップと、最近傍判定手段により、前記枝刈戦略により選定された最近傍候補ノードについては前記最大距離をそのまま用い、枝刈戦略リスト中の最近傍候補ノード以外の全アクセス済リーフノードについては
【００２５】
【数７】
2004348426.tif 000009
【００２６】
により最小距離を算出し、これらの最大距離と最小距離とを比較し、最近傍候補ノードの最大距離が最も小さい場合に、この最近傍候補ノードが最近傍の多次元空間データであることを確定する第４ステップと、からなることを特徴とする。
【００２７】
また、請求項４に記載の多次元空間データ探索方法は、前記請求項３に記載の多次元空間データ探索方法において、前記枝刈手段により、前記第３ステップでアクセス済リーフノードに枝刈されたノードを、前記アクセス済リーフノードに保持し、前記最近傍判定手段により、前記第４ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする。
【００２８】
また、請求項５に記載の多次元空間データ探索方法は、
【００２９】
【数３】
2004348426.tif 000010
【００３０】
のように表される多次元空間データ木構造において、アクセス済ノンリーフノード選定手段により、すべてのアクセス済ノンリーフノードについて
【００３１】
【数４】
2004348426.tif 000011
【００３２】
により数値を算出し、算出される数値が最小のものを次にアクセスするノンリーフノードとして選定し、選定したノンリーフノードにアクセスする第１ステップと、アクセス済ノンリーフノード選定手段により、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、有していない場合には第１ステップに戻ることを決定し、有している場合には第３ステップに進むことを決定する第２ステップと、枝刈手段により、アクセス済リーフノードについて
【００３３】
【数５】
2004348426.tif 000012
【００３４】
により問い合わせ点との最大距離を算出し、アクセス済ノンリーフノードについて
【００３５】
【数６】
2004348426.tif 000013
【００３６】
により問い合わせ点との最小距離を算出し、距離の値が小さい順に整列させ、最も小さい距離を有するものがリーフノードである場合には後述の第５ステップに進むことを決定し、最も小さい距離を有するものがノンリーフノードである場合には、アクセス済リーフノードの最大距離よりも大きい最小距離を有するアクセス済ノンリーフノードを枝刈し、アクセス済ノンリーフノード集合を保持しているアクセス済リストから削除してから後述の第４ステップに進ことを決定する、第３ステップと、枝刈手段により、アクセスできるノンリーフノードが無い多次元空間データ木の有無を判断し、有ると判断した場合は後述の第５ステップに進むことを決定し、無いと判断した場合は第１ステップに戻ることを決定する第４ステップと、最近傍判定手段により、前記最大距離が最も小さいリーフノードについては前記最大距離をそのまま用い、それ以外のリーフノードについては
【００３７】
【数７】
2004348426.tif 000014
【００３８】
により最小距離を算出し、これらの最大距離と最小距離とを比較し、前記最大距離が最も小さい場合に、この最大距離を有するリーフノードが最近傍の多次元空間データであることを確定する第５ステップと、からなることを特徴とする。
【００３９】
また、請求項６に記載の多次元空間データ探索方法は、前記請求項５に記載の多次元空間データ探索方法において、前記枝刈手段により、前記第３ステップでアクセス済リーフノードに枝刈されたノードを、前記アクセス済リーフノードに保持し、前記最近傍判定手段により、前記第５ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする。
【００４０】
また、請求項７に記載の多次元空間データ探索方法は、多次元空間データの最近傍探索において、アクセス済ノンリーフノード選定手段により、各特徴量のルートノードにアクセスする第１ステップと、アクセス済ノンリーフノード選定手段により、アクセスしたノードに関する子ノードをアクセス済リストに挿入する第２ステップと、アクセス済ノンリーフノード選定手段により、アクセス済リストのノンリーフノードについて
【００４１】
【数３】
2004348426.tif 000015
【００４２】
により算出される値をアクセス済リストに格納する第３ステップと、アクセス済ノンリーフノード選定手段により、前記アクセス済リストから
【００４３】
【数４】
2004348426.tif 000016
【００４４】
により算出される値が、最も小さいものを次にアクセスするノンリーフノードとして選定する第４ステップと、アクセス済ノンリーフノード選定手段により、選定したノンリーフノードにアクセスする第５ステップと、アクセス済ノンリーフノード選定手段により、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、リーフノードを有していない場合には第１ステップに戻ることを決定し、リーフノードを有している場合には次のステップに進むことを決定する第６ステップと、枝刈手段により、アクセス済リーフノードについて
【００４５】
【数５】
2004348426.tif 000017
【００４６】
により問い合わせ点との最大距離を算出し、枝刈戦略リストに挿入する第７ステップと、枝刈手段により、アクセス済リストに格納されているノンリーフノードについて
【００４７】
【数６】
2004348426.tif 000018
【００４８】
により問い合わせ点との最小距離を算出し、枝刈戦略リストに挿入する第８ステップと、枝刈手段により、前記枝刈戦略リスト中の各ノードを距離の値が小さい順に整列させる第９ステップと、枝刈手段により、最も小さい距離の値を有するノードがリーフノードであるかを判断し、リーフノードであると判断した場合には後段の第１３ステップに進むことを決定し、リーフノードではないと判断した場合には次の第１１ステップに進むことを決定する第１０ステップと、枝刈手段により、前記枝刈戦略リスト中のリーフノードより大きい距離を持つノンリーフノードを枝刈し、アクセス済リストから削除する第１１ステップと、枝刈手段により、アクセスできるノンリーフノードが無い多次元空間データ木が有るかを判断し、無いと判断した場合には第２ステップに戻ることを決定し、有ると判断した場合には次の第１３ステップに進むことを決定する第１２ステップと、最近傍判定手段により、前記最大距離が最も小さいリーフノードについては前記最大距離をそのまま用い、それ以外のリーフノードについては
【００４９】
【数７】
2004348426.tif 000019
【００５０】
により最小距離を算出し、これらの最大距離と最小距離とを比較し、前記最大距離が最も小さい場合に、この最大距離を有するリーフノードが最近傍の多次元空間データであることを確定する第１３ステップと、からなることを特徴とする。
【００５１】
また、請求項８に記載の多次元空間データ探索方法は、前記請求項７に記載の多次元空間データ探索方法において、前記枝刈手段により、前記第１１ステップでリーフノードに枝刈されたノードを、前記リーフノードに保持し、前記最近傍判定手段により、前記第１３ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする。
【００５２】
また、請求項９に記載の多次元空間データ探索装置は、検索情報を入力する入力手段と、
【００５３】
【数３】
2004348426.tif 000020
【００５４】
のように表される多次元空間データ木構造を有するデータベースと、すべてのアクセス済ノンリーフノードについて
【００５５】
【数４】
2004348426.tif 000021
【００５６】
により数値を算出し、算出される数値が最小のものを次にアクセスするノンリーフノードとして選定し、選定したノンリーフノードにアクセスする第１ステップと、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、有していない場合には第１ステップに戻ることを決定し、有している場合には第３ステップに進むことを決定する第２ステップと、を実行するアクセス済ノンリーフノード選定手段と、アクセスしたノンリーフノードがリーフノードを有している場合に、アクセス済リーフノードについて
【００５７】
【数５】
2004348426.tif 000022
【００５８】
により問い合わせ点との最大距離（悲観的距離）を算出し、アクセス済ノンリーフノードについて
【００５９】
【数６】
2004348426.tif 000023
【００６０】
により問い合わせ点との最小距離（楽観的距離）を算出し、距離の値が小さい順に整列させ、最も小さい距離を有するものがリーフノードである場合には後述の第５ステップに進むことを決定し、最も小さい距離を有するものがノンリーフノードである場合には、アクセス済リーフノードの最大距離（悲観的距離）よりも大きい最小距離（楽観的距離）を有するアクセス済ノンリーフノードを枝刈し、アクセス済ノンリーフノード集合を保持しているアクセス済リストから削除してから後述の第４ステップに進むことを決定する、第３ステップと、アクセスできるノンリーフノードが無い多次元空間データ木の有無を判断し、有ると判断した場合は後述の第５ステップに進むことを決定し、無いと判断した場合は第１ステップに戻ることを決定する第４ステップと、を実行する枝刈手段と、前記最大距離（悲観的距離）が最も小さいリーフノードについては前記最大距離（悲観的距離）をそのまま用い、それ以外のリーフノードについては
【００６１】
【数７】
2004348426.tif 000024
【００６２】
により最小距離（楽観的距離）を算出し、これらの最大距離（悲観的距離）と最小距離（楽観的距離）とを比較し、前記最大距離（悲観的距離）が最も小さい場合に、この最大距離（悲観的距離）を有するリーフノードが最近傍の多次元空間データであることを確定する第５ステップを実行する最近傍判定手段と、前記最近傍多次元空間データを出力するデータ出力手段と、からなることを特徴とする。
【００６３】
また、請求項１０に記載の多次元空間データ探索装置は、前記請求項９に記載の多次元空間データ探索装置において、前記枝刈手段は、前記第３ステップでアクセス済リーフノードに枝刈されたノードを、前記アクセス済リーフノードに保持し、前記最近傍判定手段は、前記第５ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする。
【００６４】
また、請求項１１に記載の多次元空間データ探索装置は、検索情報を入力する入力手段と、
【００６５】
【数３】
2004348426.tif 000025
【００６６】
のように表される多次元空間データ木構造を有するデータベースと、各特徴量のルートノードにアクセスする第１ステップと、アクセスしたノードに関する子ノードをアクセス済リストに挿入する第２ステップと、アクセス済リストのノンリーフノードについて
【００６７】
【数３】
2004348426.tif 000026
【００６８】
により算出される値をアクセス済リストに格納する第３ステップと、前記アクセス済リストから
【００６９】
【数４】
2004348426.tif 000027
【００７０】
により算出される値が、最も小さいものを次にアクセスするノンリーフノードとして選定する第４ステップと、選定したノンリーフノードにアクセスする第５ステップと、アクセスしたノンリーフノードがリーフノードを有しているかを判断し、リーフノードを有していない場合には第１ステップに戻ることを決定し、リーフノードを有している場合には次のステップに進むことを決定する第６ステップと、を実行するアクセス済ノンリーフノード選定手段と、アクセス済リーフノードについて
【００７１】
【数５】
2004348426.tif 000028
【００７２】
により問い合わせ点との最大距離（悲観的距離）を算出し、枝刈戦略リストに挿入する第７ステップと、アクセス済リストに格納されているノンリーフノードについて
【００７３】
【数６】
2004348426.tif 000029
【００７４】
により問い合わせ点との最小距離（楽観的距離）を算出し、枝刈戦略リストに挿入する第８ステップと、前記枝刈戦略リスト中の各ノードを距離の値が小さい順に整列させる第９ステップと、最も小さい距離の値を有するノードがリーフノードであるかを判断し、リーフノードであると判断した場合には後段の第１３ステップに進むことを決定し、リーフノードではないと判断した場合には次の第１１ステップに進むことを決定する第１０ステップと、前記枝刈戦略リスト中のリーフノードより大きい距離を持つノンリーフノードを枝刈し、アクセス済リストから削除する第１１ステップと、アクセスできるノンリーフノードが無い多次元空間データ木が有るかを判断し、無いと判断した場合には第２ステップに戻ることを決定し、有ると判断した場合には次の第１３ステップに進むことを決定する第１２ステップと、を実行する枝刈手段と、
前記最大距離（悲観的距離）が最も小さいリーフノードについては前記最大距離（悲観的距離）をそのまま用い、それ以外のリーフノードについては
【００７５】
【数７】
2004348426.tif 000030
【００７６】
により最小距離（楽観的距離）を算出し、これらの最大距離（悲観的距離）と最小距離（楽観的距離）とを比較し、前記最大距離（悲観的距離）が最も小さい場合に、この最大距離（悲観的距離）を有するリーフノードが最近傍の多次元空間データであることを確定する第１３ステップを実行する最近傍判定手段と、前記最近傍多次元空間データを出力するデータ出力手段と、からなることを特徴とする。
【００７７】
また、請求項１２に記載の多次元空間データ探索装置は、前記請求項１１に記載の多次元空間データ探索装置において、前記枝刈手段は、前記第１１ステップでリーフノードに枝刈されたノードを、前記リーフノードに保持し、前記最近傍判定手段は、前記第１３ステップで最近傍多次元空間データが確定した場合に、前記最近傍多次元空間データであるリーフノードが保持しているノードを探索対象に戻してから、さらに多次元空間データ探索を行うことを特徴とする。
【００７８】
また、請求項１３に記載のプログラムは、上記の請求項１乃至１２のいずれか１項に記載の多次元空間データ探索方法または多次元空間データ探索装置を、コンピュータプログラムで記載してそれを実行可能にしたことを特徴とする。
【００７９】
また、請求項１４に記載の記録媒体は、上記の請求項１乃至１２のいずれか１項に記載の多次元空間データ探索方法または多次元空間データ探索装置を、コンピュータで実行可能に記載したプログラムを記録したことを特徴とする。
【００８０】
請求項１，３，５，７，９，１１に記載の本発明にあっては、ｎ種類からなる多次元特徴ベクトルを、Ｒ−ｔｒｅｅファミリー等における多次元空間データ木構造及び多次元空間データ更新方法を用いて、それぞれ独立した多次元空間データ木構造として格納する。多次元空間データ木構造は下記の数式３のように表される。
【００８１】
【数３】
2004348426.tif 000031
【００８２】
ここで、εはノードに格納されているエントリ数である。Ｓは、ε個の子ノードのＭＢＲを表現したものである。またｃｈｉｌｄ−ｎｏｄｅｉによって子ノードにアクセスすることができる。ｌｅａｆ＿Ｎｏｄｅｊの中には、ｎ種類の多次元空間データＦｊ（ｊ  ＝  １、・・・・、ｎ）がそれぞれ格納されている。数式３はそれぞれ独立したｎ種類の多次元空間データ木構造を示している。そして、ノードにアクセスする順番を、下記の数式４に示される数値により決定し、最もその数値が少ないものから順にアクセスしていく。
【００８３】
【数４】
2004348426.tif 000032
【００８４】
ここで、Ｑは問合せ点であり、ｍｉｎ  ｄｉｓｔ（Ｑ，ｎｏｎ＿ｌｅａｆ＿Ｎｏｄｅｉ）は、問合せ点Ｑとｎｏｎ＿ｌｅａｆ＿Ｎｏｄｅｉとの最小距離を表している。またｗｅｉｇｈｔｉは多次元空間データ木構造ｉにつけられた重みである。このアクセス順の決定方法によって、重み付けが大きく且つ問合せ点との距離が小さい多次元特徴ベクトルの木構造を優先的に走査していくことが可能となる。
【００８５】
アクセスを進めていくと、やがてリーフノードが現れるが下記の数式５で定義する数値（以下、悲観的距離）により、またノンリーフノードについては下記の数式６で定義する数値（以下、楽観的距離）により枝刈戦略を行う。
【００８６】
【数５】
2004348426.tif 000033
【００８７】
ここで、ｃｕｒ＿ａｃｃ＿ｎｏｎ＿ｌｅａｆ＿Ｎｏｄｅｉは現在アクセスしているノンリーフノードの集合を表しており、数式５はアクセス済みのリーフノードについては、問合せ点との距離をそのまま採用し、リーフノードに到達していない場合については、問合せ点との距離が最大となりえる場合での距離を採用し重み付け距離を計算するものである。
【００８８】
【数６】
2004348426.tif 000034
【００８９】
ここで、ｃｕｒ＿ａｃｃ＿Ｎｏｄｅｉは現在アクセスしている全てのノードの集合を表しており、数式６はアクセス済みのリーフノードについては、問合せ点との距離をそのまま採用し、リーフノードに到達していない場合については、問合せ点との距離が最小となりえる場合での距離を採用し重み付け距離を計算するものである。
【００９０】
また下記の数式７は、最近傍判定過程において、楽観的距離を計算する数式である。
【００９１】
【数７】
2004348426.tif 000035
【００９２】
ここで、ｃｕｒ＿ａｃｃ＿ｎｏｎｌｅａｆ＿Ｎｏｄｅｉは現在アクセスしている全てのノンリーフノードの集合を表しており、数式７はアクセス済のリーフノードについては、問い合わせ点との距離をそのまま採用し、リーフノードに到達していない場合については、問い合わせ点との距離が最小となりえる場合での距離を採用し、重み付け距離を計算するものである。
【００９３】
悲観的距離と楽観的距離とを比較し、あるリーフノードに関する悲観的距離があるノードに対する楽観的距離よりも小さい場合は、未アクセスのノードが含まれていても、そのリーフノードの方が、あるノードに含まれるリーフノードよりも近傍であることが保証できる。
【００９４】
請求項２，４，６，８，１０，１２の本発明にあたっては、問合せ点Ｑとの距離が小さい上位ｋ件の点を求める問題について、請求項１，３，５，７，９，１１の多次元空間データ探索方法によって最近傍点を確定した後も、継続して問合せ点Ｑとの距離が次に小さい点を効率的に探索する方法を提供するものである。
つまり、請求項１，３，５，７，９，１１のリーフノードの悲観的距離と他ノードの楽観的距離とを比較し枝刈を行った際に、枝刈によって探索対象から外れたノードのインデックス情報を枝刈に成功したリーフノードに保持しておき、最近傍が決定した段階で、最近傍リーフノードが保持していたノードを探索対象集合に戻すようにする。
【００９５】
【発明の実施の形態】
以下、本発明の実施形態を図面に基づいて説明する。
【００９６】
図１に示すように、多次元空間データの最近傍探索は大きく３つのプロセスをとる。一つ目は、アクセス済ノンリーフノード集合の中から、次のステップでどのノンリーフノードにアクセスするかを決定するアクセス済ノンリーフノード選定過程（Ｓ１０）。二つ目は、アクセス済リーフノードに関する悲観的距離と、アクセス済ノンリーフノードに関する楽観的距離とを用いて枝刈を行う枝刈過程（Ｓ２０）。三つ目は、アクセス済リーフノードが最近傍ベクトルであるかを判定する最近傍判定過程（Ｓ３０）である。
【００９７】
図１０は本発明の多次元空間データ探索を行う装置の構成図である。図１０に示すように、該装置は、入力手段１、アクセス済ノンリーフノード選定手段２、枝刈手段３、最近傍判定手段４、データ出力手段５、およびデータベース６から構成される。なお、アクセス済ノンリーフノード選定過程（Ｓ１０）はアクセス済ノンリーフノード選定手段２により実行され、枝刈過程（Ｓ２０）は枝刈手段３により実行され、最近傍判定過程（Ｓ３０）は最近傍判定手段４により実行される。また、データベース６には、探索対象であるマルチメディアデータを組織する複数の多次元空間データ木構造が格納されている。
【００９８】
アクセス済ノンリーフノード選定過程（Ｓ１０）においては、前記数式４で示した評価関数により次にアクセスするノンリーフノードを選定する。この過程ではアクセス済ノンリーフノードと間い合わせ点との最短距離および前記数式４による評価値を保持しておく「アクセス済リスト」データ構造が用いられる。アクセス済リストには、ｎ種類の多次元空間データに関するノンリーフノードを格納する。  アクセス済リストに保持されているノンリーフノード全てに対して、前記数式４により示した評価関数により得られる数値を算出し、この数値が最小のものを次にアクセスするノンリーフノードとして選定する。この操作により、重み付けが大きく且つ問い合わせ点との距離が近いノンリーフノードが選定されることになる。このことは、最近傍点が含まれる可能性の高いノンリーフノードを優先してアクセスしていることになる。アクセス済ノンリーフノード選定過程（Ｓ１０）を進めていくと、やがてリーフノードにアクセスすることとなる。
【００９９】
枝刈過程（Ｓ２０）においては、アクセス済リーフノードについて前記数式５で示される問い合わせ点との悲観的距離と、アクセス済ノンリーフノードについて前記数式６で示される問い合わせ点との楽観的距離とを用いて枝刈戦略を行う。アクセス済リーフノードの悲観的距離よりもアクセス済ノンリーフノードの楽観的距離が大きい場合、そのノンリーフノードは枝刈の対象となりアクセス済ノンリーフノード集合を保持しているアクセス済リストから削除する。
【０１００】
また、請求項２，４，６，８，１０，１２については、各ノードに枝刈したリーフノードを保持しておく「枝刈リスト」データ構造を用い、あるアクセス済リーフノードに枝刈されたノードをこのアクセス済リーフノードの枝刈リストに保持する。
【０１０１】
この過程では、全アクセス済リーフノードについては、悲観的距離が計算され、全アクセス済ノンリーフノードについては、楽観的距離が計算され、これら全てを距離の小さい順に整列させることによって、容易に枝刈が可能である。この各ノードの楽観的距離および悲観的距離を保持しておく「枝刈戦略リスト」データ構造を用い、距離の小さい順に整列させ枝刈を行う。この枝刈戦略リストを距離の小さい順に整列した後、アクセス済リーフノードが最小値をとる、またはそのアクセス済リーフノードが所属する多次元空間データ木が全てアクセス済であった場合に、このアクセス済リーフノードが最近傍候補ノードとなり、次の最近傍判定過程（Ｓ３０）に進む。また、技刈が行われなかった場合や、枝刈戦略リスト中で最も小さい距離を持つアクセス済ノンリーフノードよりも、小さい距離を持つそのアクセス済リーフノードと同じ多次元空間データ木に所属するアクセス済ノンリーフノードが存在する場合については、アクセス済ノンリーフノード選定過程（Ｓ１０）に戻り、次にアクセスするノンリーフノードを選定する。
【０１０２】
最近傍判定過程（Ｓ３０）においては、枝刈戦略リストの中で、最も小さい距離のアクセス済リーフノードもしくは、所属する多次元空間データ木が全てアクセス済であるようなアクセス済リーフノードの中で距離が最小のものが、その他のアクセス済リーフノードよりも距離が小さいかを判定する。
【０１０３】
この過程では、枝刈戦略リストにより選定された最近傍候補ノードについては悲観的距離が計算され、枝刈戦略リスト中の最近傍候補ノード以外の全アクセス済リーフノードについては前記数式７による楽観的距離が計算され、これらの距離を比較した結果、最近傍候補ノードの悲観的距離が最も小さい場合に、この最近傍候補ノードが最近傍の多次元空間データであることが確定する。
【０１０４】
また、請求項２，４，６，８，１０，１２については、最近傍の多次元空間データであることが確定したノードに関する枝刈リストに保持されている枝刈されたノンリーフノードおよびリーフノードをそれぞれ、アクセス済リスト、枝刈戦略リストに再挿入し、最近傍探索を繰り返し行う。
【０１０５】
アクセス済ノンリーフノード選定過程（Ｓ１０）、枝刈過程（Ｓ２０）、最近傍判定過程（Ｓ３０）のフローチャートをそれぞれ、図２、図３に示す。
【０１０６】
ここで、最近傍探索方法の例を図４、および図５に示す例を用いて説明する。
例えば、２種類の特徴ベクトルＡとＢが存在し、それぞれはａ次元、ｂ次元の特徴ベクトルであるとする。そして問い合わせ点ＱＡ、ＱＢとの重み付き最近傍を求めることが目的であるとする。このとき、特徴ベクトルＡおよびＢへの重み付けをそれぞれＷＡ、ＷＢとする。また、特徴ベクトルＡおよびＢが図４に示すような多次元空間データ木構造で格納されているものとする。各特徴ベクトルの多次元空間データを多次元空間データ木構造に格納する方法については、Ｒ−ｔｒｅｅファミリー等の従来技術を用いればよいが、ここではＲ−ｔｒｅｅで多次元空間データ木構造が構成されているとする。また、多次元空間Ａ、Ｂ内のノードと問い合わせ点Ｑとの距離は図５に示すものとする。
【０１０７】
まず始めに、特徴空間ベクトル木のルートノードからアクセスする。図４に示すように、ルートノードには下記のＲα、Ｒβ、Ｒγ、Ｒδがあり、それらをアクセス済リストに挿入し、それぞれの前記数式４による評価関数による値を算出し、最も小さいものを選定する（アクセス済ノンリーフノード選定過程）。前記数式４による計算を下記の表１に示す。
【０１０８】
【表１】
2004348426.tif 000036
【０１０９】
図６にアクセス済リストを示す。評価関数による値から、Ｒαが最も小さいため、Ｒαをアクセスするノードとして選出する。次に、Ｒαをアクセスすると、図４に示すように、リーフノードとしてＲ３，Ｒ６，Ｒ７が存在する。これらはリーフノードであるため、これらの悲観的距離、および現在アクセス済ノンリーフノードに挿入されているノードに関する楽観的距離を計算した上で、枝刈戦略リストに挿入し、枝刈を行う。これらの計算を下記の表２に示す。
【０１１０】
【表２】
2004348426.tif 000037
【０１１１】
枝刈戦略リストは図７のようになり、枝刈は特に行われなかったため、アクセス済ノンリーフノードから次にアクセスするノードを選定する。アクセス済リストは図８に示すようになり、Ｒβが選定され、Ｒβにアクセスすると、図４に示すように、リーフノードＲ４、Ｒ５が存在する。
【０１１２】
これらはリーフノードであるため、これらの悲観的距離および現在アクセス済ノンリーフノードに挿入されているノードに関する楽観的距離を計算した上で、枝刈戦略リストに挿入し。枝刈を行う。これらの計算を下記の表３に示す。
【０１１３】
【表３】
2004348426.tif 000038
【０１１４】
枝刈戦略リストは、図９に示すようになり、リーフノード（Ｒ６，Ｒ５，Ｒ３，Ｒ４，Ｒ７）の悲観的距離よりも、ノンリーフノード（Ｒδ、Ｒγ）の楽観的距離の方が小さいため、ここでも枝刈は行われない。
【０１１５】
この時点で、特徴空間ベクトルＡについては、全てアクセスが終了しており、図３のＳ３６０の評価により、これ以上アクセスするノードがないため、現時点までにアクセスしたリーフノードの情報を用いて最近傍判定過程へと進む。
【０１１６】
ここで、枝刈戦略リストにより選定された最近傍候補ノードＲ６についての悲観的距離の計算、および枝刈戦略リスト中の最近傍候補ノード以外の全アクセス済リーフノードについての前記数式７による楽観的距離の計算を下記の表４に示す。
【０１１７】
【表４】
2004348426.tif 000039
【０１１８】
この結果、Ｒ６の悲観的距離が、残りの全てのリーフノードの楽観的距離より小さいため、Ｒ６が最近傍ノードということが決定する。
【０１１９】
請求項２，４，６，８，１０，１２については、この場合、Ｒ６によって、Ｒ５，Ｒ３，Ｒ４，Ｒ７が枝刈されるため、Ｒ６の枝刈リストにこれらの４つのノードが保持されることとなるが、Ｒ６は最近傍ノードであるため、Ｒ６が枝刈リストに保持していたノードは全て、全過程において値が参照されることとなる。そして、引き続き２番目に近いデータを探すために、同様の処理が行われる。
【０１２０】
本発明は、重み付けが与えられる単位に多次元特徴ベクトルを格納する多次元空間データ木構造を分け、各特徴量に与えられた重み付けを加味して効率的な探索を行う、多次元空間データ探索方法と前記方法を実施するプログラムとプログラムを記録した記録媒体とを提供することにある。上記の例では、多次元空間Ａのノードが専らアクセスされており、重み付けの大きい多次元空間が優先的にアクセスされることが分かる。
【０１２１】
なお、本発明は図１０に示したシステムの一部又は全部の処理機能をプログラムとして構成してコンピュータを用いて実現すること、あるいは図２、３で示した処理手順をプログラムとして構成してコンピュータに実行させることができる。また、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、フレキシブルディスク、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることが可能であり、また、インターネットのような通信ネットワークを介して配布したりすることが可能である。
【０１２２】
【発明の効果】
以上説明したように、本発明によれば、重み付けが与えられる単位に多次元特徴ベクトルを格納する多次元空間データ木構造を分け、各特徴量に与えられた重み付けを加味して多次元空間データ探索を行うことで、動的な重み付けの変化に対応ができ、少ないノードアクセスでオブジェクトを検出することが可能となり、結果として計算量が減り、探索性能の向上を実現することができる。また、本発明は多次元空間データとして表現される画像、映像、音声、文書等を対象とする広範囲な情報検索に適用可能である。
【図面の簡単な説明】
【図１】多次元空間データの最近傍点探索プロセスのフローチャート。
【図２】アクセス済ノンリーフノード選定過程のフローチャート。
【図３】枝刈過程のフローチャート。
【図４】多次元空間データ木構造の例を示す構成図。
【図５】問い合わせ点Ｑとの距離および重み付けの例を示す関係図。
【図６】アクセス済リストの例を示す関係図。
【図７】枝刈戦略リストの例を示す関係図。
【図８】アクセス済リストの例を示す関係図。
【図９】枝刈戦略リストの例を示す関係図。
【図１０】多次元空間データ探索装置の構成図。
【図１１】２次元のデータ空間上の問い合わせ点Ｑとの最近傍点を求める問題の例を示す構成図。
【符号の説明】
１…入力手段
２…アクセス済ノンリーフノード選定手段
３…枝刈手段
４…最近傍判定手段
５…データ出力手段
６…データベース
【図１】
2004348426.tif 000066
【図２】
2004348426.tif 000067
【図３】
2004348426.tif 000068
【図４】
2004348426.tif 000069
【図５】
2004348426.tif 000070
【図６】
2004348426.tif 000071
【図７】
2004348426.tif 000072
【図８】
2004348426.tif 000073
【図９】
2004348426.tif 000074
【図１０】
2004348426.tif 000075
【図１１】
2004348426.tif 000076