"点削除が行われたノードにおいてアンダーフローが発生しているか否かを判定し、アンダーフローが発生している場合には、アンダーフローが発生しているノードの情報を得る判定手段と、前記アンダーフローが発生しているノードの中心座標QからカレントノードのセルCまでの最短距離及び許容誤差係数εにより定まる調整可能な値が、最近傍ノード候補リストに格納されている距離より小さいか否かを判定することにより最近傍ノードを決定し、当該最近傍ノードの情報を得る検索手段と、アンダーフローが発生しているノードと、前記検索手段より得られた最近傍ノードとの間で点若しくはセルの授受を行う授受手段とを有する、アンダーフロー処理装置。前記定まる値は下記の式で定められる、請求項1に記載のアンダーフロー処理装置。値=1ε×中心座標QからセルCまでの最短距離アンダーフローが発生しているノードの中心座標QとカレントノードのセルCとの距離により定まる調整可能な値と、アンダーフローが発生しているノードと最近傍ノード候補との最短距離とを比較して、前者の方が小さければ前記カレントノードの子ノードをカレントノードにし、一方前者のほうが大きければ、前記カレントノードの親ノードをカレントノードにし、アンダーフローが発生しているノードとカレントノードの深さが等しくなったときは、当該カレントノードを新たな最近傍ノード候補にし、カレントノードが根ノードに到達したら、最近傍ノード候補のうち2番目に近いノードを授受先ノードとするアンダーフロー処理方法。前記定まる値は下記の式で定められることを特徴とする、請求項3に記載のアンダーフロー処理方法。定まる値=1ε×中心座標QからセルCまでの最短距離上述したように、削除処理の実行速度と削除後の木の検索速度とがトレードオフの関係となり、木の検索効率か削除速度のどちらを優先したいかによって、選びたいアルゴリズムが異なる。従来の技術では、検索効率を優先したアルゴリズム、削除速度を優先したアルゴリズムを別々に実装する必要があった。検索対象のノード数は、両極端な場合しか選べず、ノード数を中間とする場合にはチューニングが必要である。一般的には、実データへの登録や検索の回数が多く、削除回数が少ない場合は、木の検索効率を優先した方が良いが、そのような要求にこたえる技術は提案されていなかった。本実施の形態は、近似近傍検索誤差許容係数εを用いることで、削除速度と木の検索速度のトレードオフを調整可能なアンダーフロー時の多次元インデックスの処理技術を提供することを目的とする。一の実施の形態によれば、アンダーフロー処理装置は、判定手段と、検索手段と、授受手段を有している。判定手段は、点削除が行われたノードにおいてアンダーフローが発生しているか否かを判定し、アンダーフローが発生している場合には、アンダーフローが発生しているノードの情報を得る。検索手段は、前記アンダーフローが発生しているノードの中心座標QからカレントノードのセルCまでの最短距離及び許容誤差係数εにより定まる調整可能な値が、最近傍ノード候補リストに格納されている距離より小さいか否かを判定することにより最近傍ノードを決定し、当該最近傍ノードの情報を得る。授受手段は、アンダーフローが発生しているノードと、前記検索手段より得られた最近傍ノードとの間で点若しくはセルの授受を行う。別の実施の形態によれば、アンダーフロー処理方法が提案される。このアンダーフロー処理方法は、アンダーフローが発生しているノードの中心座標QとカレントノードのセルCとの距離により定まる調整可能な値と、アンダーフローが発生しているノードと最近傍ノード候補との最短距離とを比較して、前者の方が小さければ前記カレントノードの子ノードをカレントノードにし、一方前者のほうが大きければ、前記カレントノードの親ノードをカレントノードにし、アンダーフローが発生しているノードとカレントノードの深さが等しくなったときは、当該カレントノードを新たな最近傍ノード候補にし、カレントノードが根ノードに到達したら、最近傍ノード候補のうち2番目に近いノードを授受先ノードとする。0.定義本明細書中で用いられる用語の定義を述べる。0.1.バランス木バランス木とは、どの葉ノードからみても、根までの距離が等しい木をいう。なお、1ノード内のセルや点の個数には、上限値Mと下限値mが存在する。0.2.アンダーフローアンダーフローとは、ノードからセルや点を削除した後、そのノード内のセルや点の個数が下限値mを下回った状態をいう。0.3.k最近傍検索k最近傍検索とは、クエリとなる点からの最短距離が近い順にk個検索することをいう。なお、k最近傍検索はk-NNとも表記する。0.4.近似近傍検索近似近傍検索とは、誤差許容係数ε≧0を含めたk最近傍検索をいう。εの値が大きいほど高速だが検索誤差も大きい。1.実施の形態1.1.実施の形態の特徴本発明の実施の形態であるアンダーフロー処理装置、並びにアンダーフロー処理方法の特徴について説明する。本実施の形態では、アンダーフローを起こしたノード以下、UFノードと称すの最近傍ノードを探索し、その探索結果として得られた最近傍ノードからデータを移すことにより、アンダーフロー状態を解消させる。UFノードの最近傍ノードを探索する手法として、本実施の形態では近似近傍探索を用いることで高速化を図る。これは、近似近傍探索において用いる許容誤差係数εを大きくするほど、検索対象のノード数を減少させることができるためである。図1に許容誤差係数εを用いた探索領域と、許容誤差係数εを用いない探索領域を比較する図を示す。点QはUFノードの中心座標である。中心座標Qの近傍に最近傍候補ノード900が存在する。ノード900には点として探索を行い、それにより探索領域を狭め、他のノードが候補にならないようにすることができる。1.1.実施の形態の概要次に、本実施の形態の概要について説明する。図2はある多次元空間を示す図、図3は図2に示した多次元空間を木構造で示した図である。木構造は根ノード800、中間ノード810A、810B、葉ノード820C,820D,820E,820Fを有している。根ノード800はセル800-1.800-2を有しており、セル800-1は中間ノード810Aを指し、セル800-2は中間ノード810Bを指している。中間ノード810Aはセル810A-1,810A-2を有しており、中間ノード810Bはセル810B-1,810B-2を有している。セル810A-1,810A-2はそれぞれ葉ノード820C,820Dを指している。セル810B-1,810B-2はそれぞれ葉ノード820E,820Fを指している。葉ノード820C,820D,820E,820Fはそれぞれ点840を有しているに到達した場合には、そのノードが最近傍ノード候補となりうるかどうかを判定し、判定結果に応じて用意しておいた最近傍ノード候補リストを更新する。その後、ルートを逆にたどり探索を継続する。中間ノードにおいては通過したセル以外のセルは、候補となっているセルよりも遠いのでそのセルより下の階層を探索する必要がなく省略できる。図3では、×印を付したセル810A-2,810B-2のセルが指す葉ノード820D、820Fについては探索を省略することができるようになり、処理の高速化を図ることができる。1.2.アンダーフロー処理装置1の構成例以下、図面を参照して本発明の実施の形態に係るアンダーフロー処理装置1を説明する。本発明の一実施形態であるアンダーフロー処理装置1は、多次元インデックスにおいてセルや点を削除したのちにそのノード内のセルや点の個数が下限値を下回った状態であるアンダーフローが生じた場合、バランスを調整する処理を実行する装置である。なお、本実施の形態が扱う多次元インデックスは以下の条件を満たしていることが好ましい。1多次元インデックスがSRtreeなどのバランス木であること2点の登録/削除を動的に行うアルゴリズムを備えていること。ここで、動的とは、1点ずつ挿入/削除するたびに木のバランスを整えることを意味する。アンダーフロー処理装置1は、演算処理装置CPU、主メモリRAM、読出し専用メモリROM、入出力装置I/O、必要な場合にはハードディスク装置等の外部記憶装置を具備している情報処理装置、或いはそのような情報処理装置を含む装置であって、例えばコンピュータ、携帯電話機、HDレコーダ、家電製品などである。アンダーフロー処理装置1の前記ROM、若しくはハードディスク装置などにアンダーフロー処理を実行するためのプログラム、アプリケーション、あるいはモジュールが記憶されており、このプログラムを主メモリ上に載せ、CPUがこれを実行することによりアンダーフロー処理装置1が実現される。1.1.アンダーフロー処理装置1の構成例次に、アンダーフロー処理装置1の構成例について説明する。図4は、アンダーフロー処理装置1の構成例を示す機能ブロック図である。なお、アンダーフロー処理装置1が図4に示した構成要素それぞれに相当する部品、ユニット、ハードウエアを有することを意味するものではない。アンダーフロー処理装置1は、木の情報格納部10と、この木の情報格納部10に接続された点削除部20、アンダーフロー処理部30、及びセル調整部100とを有している。葉ノード判定部はさらに点削除部20に接続されている。アンダーフロー処理部30は点削除部20及びセル調整部100に接続されている。アンダーフロー処理部30は、アンダーフロー判定部40、根ノード処理部50、授受先ノード検索部60、授受部70を有している。アンダーフロー判定部40は、前述の点削除部20に接続されているとともに、根ノード処理部50、授受先ノード検索部60、並びに授受部70に接続されている。授受部70は点授受部80及びセル授受部90を有している。授受部70はさらに前述のセル調整部100に接続されている。以下に、上記各構成要素の機能について説明する。なお、以下の説明において接続されているとは、配線通信線などを介して物理的に接続されている場合のみでなく、構成要素間でデータ命令コードなどの情報のやり取りが可能な状態であることを広く含む。1木の情報格納部木の情報格納部10は、木の深さ、セルや点の上限下限値、ノード、セル、点などの木全体に関する情報を格納する機能を有する。木の情報格納部10は、必要に応じて都度、木の情報を各構成要素とやり取りする機能を有する。2点削除部点削除部20は、削除点を特定する情報、及びk-最近傍検索のためのパラメータεを含むユーザ指定情報を取得し、この削除点を含む葉ノードを木の情報格納部10から取得し、この葉ノードから削除点を削除する機能を有する。3アンダーフロー判定部アンダーフロー判定部40は、点削除部20から点削除が行われた葉ノードを受け取り、この葉ノードにおいてアンダーフローが発生しているか否かを判定し、アンダーフローが発生している場合には、アンダーフローが発生している葉ノードの情報を授受先ノード検索部60に渡す機能を有する。なおアンダーフロー判定部40は本発明の判定手段に相当する。また、アンダーフロー判定部40は、後述する授受部70から親ノードの情報を取得し、その親ノードについてアンダーフローの有無の判定を行う機能を有する。アンダーフローを起こしたノードが根ノードの場合には、後述する根ノード処理部50に根ノード用処理を実行させる。4授受先ノード検索部授受先ノード検索部60は、アンダーフローしたノードの最近傍ノードを検索し、検索の結果得られた最近傍ノードの情報を出力する機能を有する。なお授受先ノード検索部60は本発明の検索手段に相当する。図5は、授受先ノード検索部60の構成例を示した機能ブロック図である。上述の授受先ノード検索部60は、カレントノード変更部61と、ノード分岐リスト作成部62と、最近傍ノード候補リスト更新部63とを有している。カレントノード変更部61は、木の情報格納部10に接続されているとともに、ノード分岐リスト作成部62と、最近傍ノード候補リスト更新部63にも接続されている。また、カレントノード変更部61は前述のアンダーフロー判定部40にも接続されている。以下、各構成要素の説明をする。4-1カレントノード変更部カレントノード変更部61は、木の情報格納部10より木の情報を取得する。この木の情報は、カレントノード内の全セルの情報である。カレントノード変更部61は、取得した木の情報をノード分岐リストに作成部62に渡し、カレントノードの分岐リストL_Nを作成させ、分岐リストL_Nを取得する。次に、カレントノード変更部61は、最近傍ノード候補リスト更新部63から最近傍ノード候補リストNNを取得する。この最近傍ノード候補リストNNはアンダーフローしたノードの中心座標Qからカレントノードまでの距離は、最近傍ノード候補リストNNに格納されている候補の距離より近いかどうかの判定のために必要なためである。次に、カレントノード変更部61は、アンダーフローしたノードとカレントノードのセルとの距離と、最近傍ノード候補リストNNの距離とを比較して、前者の方が近ければアンダーフローしたノードの高さに等しくなるまで、どんどん木を降りていくカレントノードを子ノードに変更する。アンダーフローしたノードとカレントノードとの距離のほうが遠ければ、木を降りない枝刈り。アンダーフローしたノードとカレントノードの高さが等しくなったときは、カレントノード変更部61は、最近傍ノード候補リストNNの中の距離と比較して、より近ければ、当該カレントノードを新たな最近傍ノード候補にするように、最近傍ノード候補リストNを更新する。前述の分岐リストL_N内の全てのセルを比較し終わったら、カレントノードを親ノードに戻す。カレントノードが根ノードに到達したら授受先ノードの探索を終了する。4-2ノード分岐リスト作成部ノード分岐リスト作成部62は、カレントノード指定ノード内のセルを格納した分岐リストL_Nを作成する。4-3最近傍ノード候補リスト更新部最近傍ノード候補リスト更新部63は、最近傍ノード候補リストNNを有しており、、当該リストNNに格納されている最近傍ノード候補より近いノードが見つかると、当該より近いノードを最近傍ノード候補として格納するように、当該リストNNを更新する機能を有する。最近傍ノード候補リスト更新部63は、最後に2番目に近いノードを、相手先ノード授受先ノードとして出力する1番目はアンダーフローしたノードそのものとなるため。図4に戻り、アンダーフロー処理装置1の構成要素の説明を続ける。5授受部授受部70は、アンダーフローしたノードと、授受先ノード検索部60の検索の結果得られた最近傍ノードとの間で点若しくはセルの授受を行わせる処理を実行する機能を有する。授受部は点の授受を処理する点授受部80と、セルの授受を処理するセル授受部90とからなる。なお授受部70は本発明の授受手段に相当する。6セル調整部セル調整部100は、授受部70による授受の処理に関与したセルの大きさを取得し、調整する機能を有する。7根ノード処理部根ノード処理部50は、アンダーフローしたノードが根ノードの場合、後述する根ノード用処理を実行する機能を有する。以上で、アンダーフロー処理装置1の構成例の説明を終了する。2.アンダーフロー処理装置の動作例以下、アンダーフロー処理装置1の動作例を説明する。アンダーフロー処理装置1はアンダーフロー処理を主たる動作として実行する装置である。本実施の形態では、アンダーフロー処理はメイン処理及びメイン処理中のサブ処理である根ノード用処理で構成される。図6は、アンダーフロー処理装置1の主たる動作であるメイン処理を示したフローチャートである。このメイン処理はアンダーフロー処理におけるメイン処理でもある。まず、ユーザはアンダーフロー処理装置1にアンダーフロー処理を行う他に必要なデータを入力する。必要なデータとは、以下のものである。1削除点を示す情報2許容誤差係数ε≧0上記データの入力を受け付けたアンダーフロー処理装置1、より詳しくは点削除部20は、木の情報格納部10に格納されたデータを参照して、削除するデータを格納している葉ノードを見つけるS110。さらに、アンダーフロー処理装置1、より詳しくは点削除部20は、上記葉ノードをカレントノードに設定しS120、カレントノードから削除点に相当するデータを削除するS130。次に、アンダーフロー処理装置1、より詳しくはアンダーフロー判定部40は、カレントノードがアンダーフローしているか否かを判定するS140。カレントノードがアンダーフローしていないと判定した場合S140、Noは、アンダーフロー処理装置1、より詳しくはアンダーフロー判定部40は、アンダーフロー処理を終了する。一方、カレントノードがアンダーフローしていると判定した場合S140,Yesは、アンダーフロー処理装置1、より詳しくはアンダーフロー判定部40はカレントノードが根ノードでないか否かを判定するS150。カレントノードが根ノードであると判定した場合S150、No、アンダーフロー判定部40は根ノード処理部50に根ノード用処理を実行させるS160。根ノード用処理が終了するとアンダーフロー処理装置1はそのままアンダーフロー処理メイン処理を終了する。以下に根ノード用処理の具体例について説明する。図7は、根ノード用処理の例を示したフローチャートである。まず、根ノード処理部50は、根ノードのセル数が1個であるか否かを判定するS310。根ノードのセル数が1個でない場合S310、Noは、根ノード処理部50は根ノード用処理をそのまま終了する。一方、根ノードのセル数が1個である場合S310,Yes、根ノード処理部50は根ノードの子ノードが葉ノードであるか否かを判定するS320。子ノードが葉ノードであると判定した場合S310、Yes、根ノード処理部50は根ノード用処理をそのまま終了する。一方、子ノードが葉ノードでないと判定した場合S310,No、根ノード処理部50はその子ノードを新たな根ノードに設定する。次に、根ノード処理部50はその根ノードのセルの大きさを調整するS340。以上で、根ノード処理部50は根ノード用処理を完了する。図6に戻り、アンダーフロー処理メイン処理の説明を続ける。カレントノードが根ノードではないと判定した場合には、アンダーフロー判定部40は、アンダーフローを起こしたノードの最近傍ノードを得るように、授受先ノード検索部60に授受先ノード探索処理を実行させるS170。この探索により得られた最近傍ノードは、アンダーフローを起こしたノードに点又はセルを渡すノードである、授受先ノードとなる。授受先ノード探索処理の内容ついては後述する。授受先ノード探索処理の終了後、授受先ノード探索部60、は、授受先ノードから点又はセルを受け取っても授受先ノードにおいてアンダーフローが起こらないか否かを判定するS180。アンダーフローは起こらないと判定した場合S180、Yes、授受先ノード探索部60、は、探索の結果得られた、アンダーフローを起こしたノードの最近傍ノードである授受先ノードを示す情報を授受部70に渡すS190。授受部70は、授受先ノードのデータをアンダーフローを起こしたノードのデータに移す処理である授受処理を実行し、データを移す処理の後、セル調整部90がセルの大きさを調整する処理を実行し、その後アンダーフロー処理メイン処理を終了する。一方、授受先ノードにおいてアンダーフローが起こると判定した場合S180、No、授受部70は授受先ノードのデータ点又はセルをすべてアンダーフローを起こしたノードに移すように、木の情報格納部10に格納された木の情報を変更させるS200。この場合授受先ノードは消滅することとなる。次に、授受部70はアンダーフロー判定部40に、消滅した授受先ノードの親ノードについてアンダーフローを起こしているか否かを判定させる。アンダーフロー判定部40は、授受先ノードの親ノードをカレントノードに設定しS210、先に述べたところと同様にカレントノードがアンダーフローを起こしているか否かを判定しS140、以下同様にS140以降の処理が続けられる。以上で、メイン処理の説明を終了する。次に、前述した授受先ノード探索処理S170を説明する。図8は、授受先ノード探索処理の一例を示したフローチャートである。以下、図8を参照しながら処理内容を説明する。まず、授受先ノード探索部60、より詳しくはカレントノード変更部61は、ユーザ指定情報上述した削除点、εを点削除部20、アンダーフロー判定部40から取得しておく。次に、授受先ノード探索部60、より詳しくはカレントノード変更部61は初期化処理を実行するS410。初期化処理の具体的な一例をあげると以下の内容である。1アンダーフローしたノードの中心座標をQとする。2アンダーフローしたノードの深さをDとする3許容誤差係数をεとする4カレントノードNを根ノードに設定する5カレントノードの深さd=0に設定する6最近傍ノード候補リストNNにノードIDと距離を格納できる領域を2個分用意する。7NNの距離は無限大∞に初期化する8カレントノードN内のすべてのセルを格納する一時的なリストを分岐リストL_Nとする初期化処理S410後、授受先ノード探索部60、より詳しくはカレントノード変更部61は、ノード分岐リスト作成部62に、カレントノードN内のセルを、中心座標Qとの距離が近い順に並べて、カレントノードNの分岐リストL_Nに格納させるS420。次に、授受先ノード探索部60、より詳しくはカレントノード変更部61は分岐リストL_Nにセルが入っているか否かを判定するS430。分岐リストL_Nにセルが入っていないと判定した場合S430,No、授受先ノード探索部60、より詳しくはカレントノード変更部61はカレントノードNが根ノードか否かを判定するS440。カレントノードNが根ノードであると判定した場合S440、Yes、授受先ノード探索部60は、最近傍ノード候補リストNNに2番目に格納されているノードを授受先ノードと決定しS450、授受先ノード探索処理を終了する。一方、カレントノードNが根ノードでないと判定した場合S440,No、授受先ノード探索部60、はカレントノードNを現在のカレントノードの親ノードに変更し、カレントノードの深さdから1だけ減じてS460、先のステップS430に戻り、授受先ノード検索処理をさらに続行する。ステップS430の説明に戻る。ステップS430においてリストLにセルが入っていると判定した場合S430,Yes、授受先ノード探索部60、より詳しくはカレントノード変更部61はリストLからセルを1個取り出すS470。取り出されるセルとして、分岐リストL_N中、中心座標Qに最も近いものが選択される。、以下、そのセルをセルCと呼ぶものとする。授受先ノード探索部60、より詳しくはカレントノード変更部61は、中心座標QからセルCまでの最短距離と許容誤差係数εにより定まる値が最近傍ノード候補リストNNに格納されている距離より小さい近いか否かを判定するS480。但し、中心座標QがセルCの内部に含まれている場合、QからCまでの最短距離は0とする。前記定まる値は以下の式により算出される値である。値=1ε×中心座標QからセルCまでの最短距離但し、ε>0これにより、近似近傍探索ANNによる枝刈りを行うことができることになる。前記定まる値が最近傍ノード候補リストNNに格納されている距離より小くない近くないと判定した場合S480,No、授受先ノード探索部60は前述のステップS440に移行する。一方、前記値が最近傍ノード候補リストNNに格納されている距離より小さい近いと判定した場合S480、Yes、授受先ノード探索部60は分岐リストL_NをセルCが指すノードのセルのリストに書き換え、且つ、深さdの値を1加算するS490。次に、授受先ノード探索部60はカレントノードの深さdとアンダーフローしたノードの深さDがd=Dとなったか否かを判定するS500。d=Dとなっていないと判定した場合S500,No、授受先ノード探索部60は前述のステップS420に戻り、新たなカレントノードNについての分岐リストL_Nを生成し、ステップS430移行の処理を実行する。。一方、d=Dとなっていると判定した場合S500、Yes、授受先ノード探索部60は、最近傍ノード候補リスト更新部63に、最短距離がセルCまでの最短距離より大きいノードに代えて、最近傍ノード候補リストNNにカレントノードNを示すノードIDと中心座標QからセルCまでの最短距離とを格納させS510、最近傍ノード候補リストNNの更新を実行する。その後前述のステップS460に進み、授受先ノード探索処理をさらに続行する。以上で授受先ノード探索処理の説明を終了し、アンダーフロー処理装置の動作例の説明を完了する。3.本実施の形態の利点本実施の形態によれば、近似近傍検索誤差許容係数εを用いることで、削除速度と木の検索速度のトレードオフを調整できる。すなわち、ε=0のときは全てのノードが対象となり、εの値を大きくすると、遠くにあるノードを探索する手間が省ける枝刈り。"