(57)【要約】【課題】削除速度と木の検索速度のトレードオフを調整可能なアンダーフロー時の多次元インデックスの処理技術を提供する。【解決手段】判定手段は、点削除が行われたノードにおいてアンダーフローが発生しているか否かを判定し、発生している場合には、発生しているノードの情報を得る。検索手段は、前記アンダーフローが発生しているノードの中心座標ＱからカレントノードのセルＣまでの最短距離及び許容誤差係数εにより定まる調整可能な値が、最近傍ノード候補リストに格納されている距離より小さいか否かを判定することにより最近傍ノードを決定し、当該最近傍ノードの情報を得る。授受手段は、アンダーフローが発生しているノードと、前記検索手段より得られた最近傍ノードとの間で点若しくはセルの授受を行う。【選択図】図４
2012155579.tif 000002
【特許請求の範囲】
【請求項１】
点削除が行われたノードにおいてアンダーフローが発生しているか否かを判定し、アンダーフローが発生している場合には、アンダーフローが発生しているノードの情報を得る判定手段と、
前記アンダーフローが発生しているノードの中心座標ＱからカレントノードのセルＣまでの最短距離及び許容誤差係数εにより定まる調整可能な値が、最近傍ノード候補リストに格納されている距離より小さいか否かを判定することにより最近傍ノードを決定し、当該最近傍ノードの情報を得る検索手段と、
アンダーフローが発生しているノードと、前記検索手段より得られた最近傍ノードとの間で点若しくはセルの授受を行う授受手段と
を有する、アンダーフロー処理装置。
【請求項２】
前記定まる値は下記の式で定められる、請求項1に記載のアンダーフロー処理装置。
値＝（１＋ε）×（中心座標ＱからセルＣまでの最短距離）
【請求項３】
アンダーフローが発生しているノードの中心座標ＱとカレントノードのセルＣとの距離により定まる調整可能な値と、アンダーフローが発生しているノードと最近傍ノード候補との最短距離とを比較して、前者の方が小さければ前記カレントノードの子ノードをカレントノードにし、一方前者のほうが大きければ、前記カレントノードの親ノードをカレントノードにし、
アンダーフローが発生しているノードとカレントノードの深さが等しくなったときは、当該カレントノードを新たな最近傍ノード候補にし、
カレントノードが根ノードに到達したら、最近傍ノード候補のうち２番目に近いノードを授受先ノードとする
アンダーフロー処理方法。
【請求項４】
前記定まる値は下記の式で定められることを特徴とする、請求項３に記載のアンダーフロー処理方法。
定まる値＝（１＋ε）×（中心座標ＱからセルＣまでの最短距離）
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載の実施の形態は、アンダーフロー処理装置並びにアンダーフロー処理方法に関する。
【背景技術】
【０００２】
データベースやファイルシステムなどの大量の情報を高速に検索等する技術の一つとして、バランス木（B-Tree；Balanced  Tree)が用いられることが少なくない。バランス木を用いたデータベースやファイルシステムの場合でも、不要となった個々のデータは適宜削除し、最新の状態に保たれる必要がある。この場合、バランス木の葉ノードから削除するデータに相当する点を削除することとなる。
【０００３】
葉ノードから点を削除後、アンダーフローが起こった場合、バランス木では都度バランスを整える必要がある。バランスを整えるには、他のノードからいくつか点をもらってくるか、もしくは全て渡すことが行われる。この場合、点を削除したノードのなるべく近くのノードから点をやりとりすると、木のクラスタリング効率が劣化せず、検索精度が維持される（もしくは高くなる）。ただし、削除処理の実行速度と、削除後の木の検索速度はトレードオフの関係となり、時間をかけてなるべく近くのノードを探すか、時間をかけずにまずまず近いノードを探すか、で処理方法は異なってくる。実データの種類（点の分散度合い）や、削除後の処理内容、優先したい速度などで、バランスを整える方法は最適な方法が都度異なる。
【０００４】
従来の削除技術として、以下のものが提案されている
（１）多次元インデックスにおける点削除後、ノードにアンダーフローが起こったら、影響を受ける点は全て木から取り除きキューに一時保存し、木を整えたあとで、キューの点を1個ずつ挿入していく技術（非特許文献１）。この技術では、木のバランスが保たれるため検索速度への影響は最も少ないが、影響を受ける点は全て挿入（場合によっては再挿入も）しなくてはならないため、削除そのものにかかる所要時間が大きい。
【０００５】
（２）また、子ノードの最大Hilbert値を持つR-treeでの削除アルゴリズムが提案されている（非特許文献２）。この技術では、アンダーフローしたノードは他のノードと点／セルの授受を行う。この技術は、検索速度への影響は上述の（１）の技術より大きいが、削除処理が高速に行える他のノードの決定方法については言及はない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】"R-trees: a dynamic index structure for spatial searching"; A. Guttman. Proc. ACM SIGMOD, pp. 47-57, 1984.
【非特許文献２】"Hilbert R-tree: An Improved R-tree using fractals", In Proc. of the 20th VLDB Conf, 1994, pp.500-509
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したように、削除処理の実行速度と削除後の木の検索速度とがトレードオフの関係となり、木の検索効率か削除速度のどちらを優先したいかによって、選びたいアルゴリズムが異なる。
【０００８】
従来の技術では、検索効率を優先したアルゴリズム、削除速度を優先したアルゴリズムを別々に実装する必要があった。検索対象のノード数は、両極端な場合しか選べず、ノード数を中間とする場合にはチューニングが必要である。一般的には、実データへの登録や検索の回数が多く、削除回数が少ない場合は、木の検索効率を優先した方が良いが、そのような要求にこたえる技術は提案されていなかった。
【０００９】
本実施の形態は、近似近傍検索（誤差許容係数ε）を用いることで、削除速度と木の検索速度のトレードオフを調整可能なアンダーフロー時の多次元インデックスの処理技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
一の実施の形態によれば、アンダーフロー処理装置は、判定手段と、検索手段と、授受手段を有している。判定手段は、点削除が行われたノードにおいてアンダーフローが発生しているか否かを判定し、アンダーフローが発生している場合には、アンダーフローが発生しているノードの情報を得る。検索手段は、前記アンダーフローが発生しているノードの中心座標ＱからカレントノードのセルＣまでの最短距離及び許容誤差係数εにより定まる調整可能な値が、最近傍ノード候補リストに格納されている距離より小さいか否かを判定することにより最近傍ノードを決定し、当該最近傍ノードの情報を得る。授受手段は、アンダーフローが発生しているノードと、前記検索手段より得られた最近傍ノードとの間で点若しくはセルの授受を行う。
【００１１】
別の実施の形態によれば、アンダーフロー処理方法が提案される。このアンダーフロー処理方法は、アンダーフローが発生しているノードの中心座標ＱとカレントノードのセルＣとの距離により定まる調整可能な値と、アンダーフローが発生しているノードと最近傍ノード候補との最短距離とを比較して、前者の方が小さければ前記カレントノードの子ノードをカレントノードにし、一方前者のほうが大きければ、前記カレントノードの親ノードをカレントノードにし、アンダーフローが発生しているノードとカレントノードの深さが等しくなったときは、当該カレントノードを新たな最近傍ノード候補にし、カレントノードが根ノードに到達したら、最近傍ノード候補のうち２番目に近いノードを授受先ノードとする。
【図面の簡単な説明】
【００１２】
【図１】許容誤差係数εを用いた探索領域と、許容誤差係数εを用いない探索領域を比較する図
【図２】ある多次元空間を示す図
【図３】図２に示した多次元空間を木構造で示した図
【図４】アンダーフロー処理装置の構成例を示す機能ブロック図
【図５】授受先ノード検索部の構成例を示した機能ブロック図
【図６】アンダーフロー処理装置の主たる動作であるメイン処理を示したフローチャート
【図７】根ノード用処理の例を示したフローチャート
【図８】授受先ノード探索処理の一例を示したフローチャート
【発明を実施するための形態】
【００１３】
[０．定義]
本明細書中で用いられる用語の定義を述べる。
[０．１．バランス木]
「バランス木」とは、どの葉ノードからみても、根までの距離が等しい木をいう。なお、１ノード内のセルや点の個数には、上限値Ｍと下限値ｍ(ただし、ｍ≧M/2)が存在する。
[０．２．アンダーフロー]
「アンダーフロー」とは、ノードからセルや点を削除した後、そのノード内のセルや点の個数が下限値ｍを下回った状態をいう。
[０．３．k-最近傍検索]
「k-最近傍検索」とは、クエリとなる点からの最短距離が近い順にk個検索することをいう。なお、k-最近傍検索はｋ−ＮＮとも表記する。
[０．４．近似近傍検索]
「近似近傍検索」とは、誤差許容係数ε（≧0）を含めたk-最近傍検索をいう。εの値が大きいほど高速だが検索誤差も大きい。
【００１４】
[１．実施の形態]
[１．１．実施の形態の特徴]
本発明の実施の形態であるアンダーフロー処理装置、並びにアンダーフロー処理方法の特徴について説明する。
【００１５】
本実施の形態では、アンダーフローを起こしたノード（以下、ＵＦノードと称す）の最近傍ノードを探索し、その探索結果として得られた最近傍ノードからデータを移すことにより、アンダーフロー状態を解消させる。
【００１６】
ＵＦノードの最近傍ノードを探索する手法として、本実施の形態では近似近傍探索を用いることで高速化を図る。これは、近似近傍探索において用いる許容誤差係数εを大きくするほど、検索対象のノード数を減少させることができるためである。
【００１７】
図１に許容誤差係数εを用いた探索領域と、許容誤差係数εを用いない探索領域を比較する図を示す。点ＱはＵＦノードの中心座標である。中心座標Ｑの近傍に最近傍候補ノード９００が存在する。ノード９００には点(データ）９０１が複数存在する（図中では黒点でしめし、代表して一つにのみ参照符号を付した）。このノード９００が最近傍ノードであれば、点９０１のいずれかをＵＦノードに移すこととなる。
【００１８】
ここで、許容誤差係数εを用いない探索領域９０２の半径をｒとすると、許容誤差係数εを用いた探索領域９０３の半径をｒ／(1＋ε)として探索を行い、それにより探索領域を狭め、他のノードが候補にならないようにすることができる。
【００１９】
[１．１．実施の形態の概要]
次に、本実施の形態の概要について説明する。図２はある多次元空間を示す図、図３は図２に示した多次元空間を木構造で示した図である。
【００２０】
木構造は根ノード８００、中間ノード８１０Ａ、８１０Ｂ、葉ノード８２０Ｃ，８２０Ｄ，８２０Ｅ，８２０Ｆを有している。根ノード８００はセル８００−１．８００−２を有しており、セル８００−１は中間ノード８１０Ａを指し、セル８００−２は中間ノード８１０Ｂを指している。
【００２１】
中間ノード８１０Ａはセル８１０Ａ−１，８１０Ａ−２を有しており、中間ノード８１０Ｂはセル８１０Ｂ−１，８１０Ｂ−２を有している。セル８１０Ａ−１，８１０Ａ−２はそれぞれ葉ノード８２０Ｃ，８２０Ｄを指している。セル８１０Ｂ−１，８１０Ｂ−２はそれぞれ葉ノード８２０Ｅ，８２０Ｆを指している。
【００２２】
葉ノード８２０Ｃ，８２０Ｄ，８２０Ｅ，８２０Ｆはそれぞれ点(データ)８４０を有している(図中黒丸でしめし、代表して一つにのみ参照符号を付す）。なお、葉ノード８２０Ｃは、点削除によりアンダーフローを起こしているものとする。
【００２３】
上記図２、図３に示した例における本実施の形態の最近傍ノード探索処理の概要を以下に述べる。まず、カレントノードを根ノード８００とする。つぎに、アンダーフローを起こしたノード（葉ノード８２０Ｃ）により近いセルが指すノードをたどって下の階層のノードを探索する。下の階層へ辿った際通過したノードのセルを覚えておく。
【００２４】
このように下層への探索を行い、アンダーフローを起こしたノードと同じ階層（深さ)に到達した場合には、そのノードが最近傍ノード候補となりうるかどうかを判定し、判定結果に応じて用意しておいた最近傍ノード候補リストを更新する。
【００２５】
その後、ルートを逆にたどり探索を継続する。中間ノードにおいては通過したセル以外のセルは、候補となっているセルよりも遠いのでそのセルより下の階層を探索する必要がなく省略できる。図３では、×印を付したセル８１０Ａ−２，８１０Ｂ−２のセルが指す葉ノード８２０Ｄ、８２０Ｆについては探索を省略することができるようになり、処理の高速化を図ることができる。
【００２６】
[１．２．アンダーフロー処理装置１の構成例]
以下、図面を参照して本発明の実施の形態に係るアンダーフロー処理装置１を説明する。
本発明の一実施形態であるアンダーフロー処理装置１は、多次元インデックスにおいてセルや点を削除したのちにそのノード内のセルや点の個数が下限値を下回った状態であるアンダーフローが生じた場合、バランスを調整する処理を実行する装置である。
【００２７】
なお、本実施の形態が扱う多次元インデックスは以下の条件を満たしていることが好ましい。  
（１）多次元インデックスがSR-treeなどのバランス木であること
（２）点(データ)の登録／削除を動的に行うアルゴリズムを備えていること。
ここで、「動的」とは、１点ずつ挿入／削除するたびに木のバランスを整えることを意味する。
【００２８】
アンダーフロー処理装置１は、演算処理装置（ＣＰＵ）、主メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、入出力装置（Ｉ／Ｏ）、必要な場合にはハードディスク装置等の外部記憶装置を具備している情報処理装置、或いはそのような情報処理装置を含む装置であって、例えばコンピュータ、携帯電話機、ＨＤレコーダ、家電製品などである。アンダーフロー処理装置１の前記ＲＯＭ、若しくはハードディスク装置などにアンダーフロー処理を実行するためのプログラム、アプリケーション、あるいはモジュールが記憶されており、このプログラムを主メモリ上に載せ、ＣＰＵがこれを実行することによりアンダーフロー処理装置１が実現される。
【００２９】
[１．１．アンダーフロー処理装置１の構成例]
次に、アンダーフロー処理装置１の構成例について説明する。図４は、アンダーフロー処理装置１の構成例を示す機能ブロック図である。なお、アンダーフロー処理装置１が図４に示した構成要素それぞれに相当する部品、ユニット、ハードウエアを有することを意味するものではない。
【００３０】
アンダーフロー処理装置１は、木の情報格納部１０と、この木の情報格納部１０に接続された点削除部２０、アンダーフロー処理部３０、及びセル調整部１００とを有している。葉ノード判定部はさらに点削除部２０に接続されている。アンダーフロー処理部３０は点削除部２０及びセル調整部１００に接続されている。
【００３１】
アンダーフロー処理部３０は、アンダーフロー判定部４０、根ノード処理部５０、授受先ノード検索部６０、授受部７０を有している。アンダーフロー判定部４０は、前述の点削除部２０に接続されているとともに、根ノード処理部５０、授受先ノード検索部６０、並びに授受部７０に接続されている。
【００３２】
授受部７０は点授受部８０及びセル授受部９０を有している。授受部７０はさらに前述のセル調整部１００に接続されている。
【００３３】
以下に、上記各構成要素の機能について説明する。なお、以下の説明において「接続されている」とは、配線・通信線などを介して物理的に接続されている場合のみでなく、構成要素間でデータ・命令・コードなどの情報のやり取りが可能な状態であることを広く含む。
【００３４】
（１）木の情報格納部
木の情報格納部１０は、木の深さ、セルや点の上限・下限値、ノード、セル、点などの木全体に関する情報を格納する機能を有する。木の情報格納部１０は、必要に応じて都度、木の情報を各構成要素とやり取りする機能を有する。
【００３５】
（２）点削除部
点削除部２０は、削除点を特定する情報、及びｋ−最近傍検索のためのパラメータ（ε）を含むユーザ指定情報を取得し、この削除点を含む葉ノードを木の情報格納部１０から取得し、この葉ノードから削除点を削除する機能を有する。
【００３６】
（３）アンダーフロー判定部
アンダーフロー判定部４０は、点削除部２０から点削除が行われた葉ノードを受け取り、この葉ノードにおいてアンダーフローが発生しているか否かを判定し、アンダーフローが発生している場合には、アンダーフローが発生している葉ノードの情報を授受先ノード検索部６０に渡す機能を有する。なおアンダーフロー判定部４０は本発明の判定手段に相当する。
【００３７】
また、アンダーフロー判定部４０は、後述する授受部７０から親ノードの情報を取得し、その親ノードについてアンダーフローの有無の判定を行う機能を有する。アンダーフローを起こしたノードが根ノードの場合には、後述する根ノード処理部５０に根ノード用処理を実行させる。
【００３８】
（４）授受先ノード検索部
授受先ノード検索部６０は、アンダーフローしたノードの最近傍ノードを検索し、検索の結果得られた最近傍ノードの情報を出力する機能を有する。なお授受先ノード検索部６０は本発明の検索手段に相当する。
【００３９】
図５は、授受先ノード検索部６０の構成例を示した機能ブロック図である。上述の授受先ノード検索部６０は、カレントノード変更部６１と、ノード分岐リスト作成部６２と、最近傍ノード候補リスト更新部６３とを有している。カレントノード変更部６１は、木の情報格納部１０に接続されているとともに、ノード分岐リスト作成部６２と、最近傍ノード候補リスト更新部６３にも接続されている。また、カレントノード変更部６１は前述のアンダーフロー判定部４０にも接続されている。
【００４０】
以下、各構成要素の説明をする。  
【００４１】
（４−１）カレントノード変更部
カレントノード変更部６１は、木の情報格納部１０より木の情報を取得する。この木の情報は、カレントノード内の全セルの情報である。
カレントノード変更部６１は、取得した木の情報をノード分岐リストに作成部６２に渡し、カレントノードの分岐リストＬ＿Ｎを作成させ、分岐リストＬ＿Ｎを取得する。次に、カレントノード変更部６１は、最近傍ノード候補リスト更新部６３から最近傍ノード候補リストＮＮを取得する。この最近傍ノード候補リストＮＮは「アンダーフローしたノードの中心座標Ｑからカレントノードまでの距離は、最近傍ノード候補リストＮＮに格納されている候補の距離より近い」かどうかの判定のために必要なためである。
【００４２】
次に、カレントノード変更部６１は、アンダーフローしたノードとカレントノードのセルとの距離と、最近傍ノード候補リストＮＮの距離とを比較して、前者の方が近ければアンダーフローしたノードの高さに等しくなるまで、どんどん木を降りていく（カレントノードを子ノードに変更する）。アンダーフローしたノードとカレントノードとの距離のほうが遠ければ、木を降りない（枝刈り）。アンダーフローしたノードとカレントノードの高さが等しくなったときは、カレントノード変更部６１は、最近傍ノード候補リストＮＮの中の距離と比較して、より近ければ、当該カレントノードを新たな最近傍ノード候補にするように、最近傍ノード候補リストＮを更新する。前述の分岐リストＬ＿Ｎ内の全てのセルを比較し終わったら、カレントノードを親ノードに戻す。カレントノードが根ノードに到達したら授受先ノードの探索を終了する。
【００４３】
（４−２）ノード分岐リスト作成部  
ノード分岐リスト作成部６２は、カレントノード（指定ノード）内のセルを格納した分岐リストＬ＿Ｎを作成する。
【００４４】
（４−３）最近傍ノード候補リスト更新部
最近傍ノード候補リスト更新部６３は、最近傍ノード候補リストＮＮを有しており、、当該リストＮＮに格納されている最近傍ノード候補より近いノードが見つかると、当該より近いノードを最近傍ノード候補として格納するように、当該リストＮＮを更新する機能を有する。最近傍ノード候補リスト更新部６３は、最後に２番目に近いノードを、相手先ノード（授受先ノード）として出力する（1番目はアンダーフローしたノードそのものとなるため）。
図４に戻り、アンダーフロー処理装置１の構成要素の説明を続ける。  
【００４５】
（５）授受部  
授受部７０は、アンダーフローしたノードと、授受先ノード検索部６０の検索の結果得られた最近傍ノードとの間で点若しくはセルの授受を行わせる処理を実行する機能を有する。授受部は点の授受を処理する点授受部８０と、セルの授受を処理するセル授受部９０とからなる。なお授受部７０は本発明の授受手段に相当する。
【００４６】
（６）セル調整部  
セル調整部１００は、授受部７０による授受の処理に関与したセルの大きさを取得し、調整する機能を有する。
【００４７】
（７）根ノード処理部
根ノード処理部５０は、アンダーフローしたノードが根ノードの場合、後述する根ノード用処理を実行する機能を有する。
以上で、アンダーフロー処理装置１の構成例の説明を終了する。
【００４８】
[２．アンダーフロー処理装置の動作例]
以下、アンダーフロー処理装置１の動作例を説明する。アンダーフロー処理装置１はアンダーフロー処理を主たる動作として実行する装置である。本実施の形態では、アンダーフロー処理はメイン処理及びメイン処理中のサブ処理である根ノード用処理で構成される。
【００４９】
図６は、アンダーフロー処理装置１の主たる動作であるメイン処理を示したフローチャートである。このメイン処理はアンダーフロー処理におけるメイン処理でもある。
【００５０】
まず、ユーザはアンダーフロー処理装置１にアンダーフロー処理を行う他に必要なデータを入力する。必要なデータとは、以下のものである。
【００５１】
（１）削除点を示す情報
（２）許容誤差係数ε（≧０）
【００５２】
上記データの入力を受け付けたアンダーフロー処理装置１、より詳しくは点削除部２０は、木の情報格納部１０に格納されたデータを参照して、削除するデータを格納している葉ノードを見つける（Ｓ１１０）。さらに、アンダーフロー処理装置１、より詳しくは点削除部２０は、上記葉ノードをカレントノードに設定し（Ｓ１２０）、カレントノードから削除点に相当するデータを削除する（Ｓ１３０）。
【００５３】
次に、アンダーフロー処理装置１、より詳しくはアンダーフロー判定部４０は、カレントノードがアンダーフローしているか否かを判定する（Ｓ１４０）。
【００５４】
カレントノードがアンダーフローしていないと判定した場合（Ｓ１４０、Ｎｏ）は、アンダーフロー処理装置１、より詳しくはアンダーフロー判定部４０は、アンダーフロー処理を終了する。
【００５５】
一方、カレントノードがアンダーフローしていると判定した場合（Ｓ１４０，Ｙｅｓ）は、アンダーフロー処理装置１、より詳しくはアンダーフロー判定部４０はカレントノードが根ノードでないか否かを判定する（Ｓ１５０）。カレントノードが根ノードであると判定した場合（Ｓ１５０、Ｎｏ）、アンダーフロー判定部４０は根ノード処理部５０に根ノード用処理を実行させる（Ｓ１６０）。根ノード用処理が終了するとアンダーフロー処理装置１はそのままアンダーフロー処理（メイン処理）を終了する。
【００５６】
以下に根ノード用処理の具体例について説明する。図７は、根ノード用処理の例を示したフローチャートである。まず、根ノード処理部５０は、根ノードのセル数が1個であるか否かを判定する（Ｓ３１０）。根ノードのセル数が１個でない場合（Ｓ３１０、Ｎｏ）は、根ノード処理部５０は根ノード用処理をそのまま終了する。
【００５７】
一方、根ノードのセル数が1個である場合（Ｓ３１０，Ｙｅｓ）、根ノード処理部５０は根ノードの子ノードが葉ノードであるか否かを判定する（Ｓ３２０）。子ノードが葉ノードであると判定した場合（Ｓ３１０、Ｙｅｓ）、根ノード処理部５０は根ノード用処理をそのまま終了する。一方、子ノードが葉ノードでないと判定した場合（Ｓ３１０，Ｎｏ）、根ノード処理部５０はその子ノードを新たな根ノードに設定する。次に、根ノード処理部５０はその根ノードのセルの大きさを調整する（Ｓ３４０）。以上で、根ノード処理部５０は根ノード用処理を完了する。
【００５８】
図６に戻り、アンダーフロー処理（メイン処理）の説明を続ける。  
カレントノードが根ノードではないと判定した場合には、アンダーフロー判定部４０は、アンダーフローを起こしたノードの最近傍ノードを得るように、授受先ノード検索部６０に授受先ノード探索処理を実行させる（Ｓ１７０）。この探索により得られた最近傍ノードは、アンダーフローを起こしたノードに点又はセルを渡すノードである、授受先ノードとなる。授受先ノード探索処理の内容ついては後述する。
【００５９】
授受先ノード探索処理の終了後、授受先ノード探索部６０、は、授受先ノードから点又はセルを受け取っても授受先ノードにおいてアンダーフローが起こらないか否かを判定する（Ｓ１８０）。アンダーフローは起こらないと判定した場合（Ｓ１８０、Ｙｅｓ）、授受先ノード探索部６０、は、探索の結果得られた、アンダーフローを起こしたノードの最近傍ノードである授受先ノードを示す情報を授受部７０に渡す（Ｓ１９０）。授受部７０は、授受先ノードのデータをアンダーフローを起こしたノードのデータに移す処理である授受処理を実行し、データを移す処理の後、セル調整部９０がセルの大きさを調整する処理を実行し、その後アンダーフロー処理（メイン処理）を終了する。
【００６０】
一方、授受先ノードにおいてアンダーフローが起こると判定した場合（Ｓ１８０、Ｎｏ）、授受部７０は授受先ノードのデータ（点又はセル）をすべてアンダーフローを起こしたノードに移すように、木の情報格納部１０に格納された木の情報を変更させる（Ｓ２００）。この場合授受先ノードは消滅することとなる。次に、授受部７０はアンダーフロー判定部４０に、消滅した授受先ノードの親ノードについてアンダーフローを起こしているか否かを判定させる。アンダーフロー判定部４０は、授受先ノードの親ノードをカレントノードに設定し（Ｓ２１０）、先に述べたところと同様にカレントノードがアンダーフローを起こしているか否かを判定し（Ｓ１４０）、以下同様にＳ１４０以降の処理が続けられる。
【００６１】
以上で、メイン処理の説明を終了する。  
次に、前述した授受先ノード探索処理（Ｓ１７０）を説明する。図８は、授受先ノード探索処理の一例を示したフローチャートである。以下、図８を参照しながら処理内容を説明する。まず、授受先ノード探索部６０、より詳しくはカレントノード変更部６１は、ユーザ指定情報(上述した削除点、ε）を点削除部２０、アンダーフロー判定部４０から取得しておく。
【００６２】
次に、授受先ノード探索部６０、より詳しくはカレントノード変更部６１は初期化処理を実行する（Ｓ４１０）。初期化処理の具体的な一例をあげると以下の内容である。
【００６３】
（１）アンダーフローしたノードの中心座標をＱとする。
（２）アンダーフローしたノードの深さをＤとする
（３）許容誤差係数をεとする
（４）カレントノードＮを根ノードに設定する
（５）カレントノードの深さｄ＝０に設定する
（６）最近傍ノード候補リストＮＮにノードＩＤと距離を格納できる領域を２個分用意する。
（７）ＮＮの距離は無限大∞に初期化する
（８）カレントノードＮ内のすべてのセルを格納する一時的なリストを分岐リストＬ＿Ｎとする
【００６４】
初期化処理（Ｓ４１０）後、授受先ノード探索部６０、より詳しくはカレントノード変更部６１は、ノード分岐リスト作成部６２に、カレントノードＮ内のセルを、中心座標Ｑとの距離が近い順に並べて、カレントノードＮの分岐リストＬ＿Ｎに格納させる（Ｓ４２０）。
【００６５】
次に、授受先ノード探索部６０、より詳しくはカレントノード変更部６１は分岐リストＬ＿Ｎにセルが入っているか否かを判定する（Ｓ４３０）。分岐リストＬ＿Ｎにセルが入っていないと判定した場合（Ｓ４３０，Ｎｏ）、授受先ノード探索部６０、より詳しくはカレントノード変更部６１はカレントノードＮが根ノードか否かを判定する（Ｓ４４０）。カレントノードＮが根ノードであると判定した場合（Ｓ４４０、Ｙｅｓ）、授受先ノード探索部６０は、最近傍ノード候補リストＮＮに2番目に格納されているノードを授受先ノードと決定し（Ｓ４５０）、授受先ノード探索処理を終了する。一方、カレントノードＮが根ノードでないと判定した場合（Ｓ４４０，Ｎｏ）、授受先ノード探索部６０、はカレントノードＮを現在のカレントノードの親ノードに変更し、カレントノードの深さｄから１だけ減じて（Ｓ４６０）、先のステップＳ４３０に戻り、授受先ノード検索処理をさらに続行する。
【００６６】
ステップＳ４３０の説明に戻る。ステップＳ４３０においてリストＬにセルが入っていると判定した場合（Ｓ４３０，Ｙｅｓ）、授受先ノード探索部６０、より詳しくはカレントノード変更部６１はリストＬからセルを１個取り出す（Ｓ４７０）。取り出されるセルとして、分岐リストＬ＿Ｎ中、中心座標Ｑに最も近いものが選択される。、以下、そのセルをセルＣと呼ぶものとする。
【００６７】
授受先ノード探索部６０、より詳しくはカレントノード変更部６１は、中心座標ＱからセルＣまでの最短距離と許容誤差係数εにより定まる値が最近傍ノード候補リストＮＮに格納されている距離より小さい（近い）か否かを判定する（Ｓ４８０）。但し、中心座標ＱがセルＣの内部に含まれている場合、ＱからＣまでの最短距離は０とする。前記定まる値は以下の式により算出される値である。
値＝（１＋ε）×（中心座標ＱからセルＣまでの最短距離）
但し、ε＞０
これにより、近似近傍探索ＡＮＮによる枝刈りを行うことができることになる。
【００６８】
前記定まる値が最近傍ノード候補リストＮＮに格納されている距離より小くない（近くない）と判定した場合（Ｓ４８０，Ｎｏ）、授受先ノード探索部６０は前述のステップＳ４４０に移行する。
【００６９】
一方、前記値が最近傍ノード候補リストＮＮに格納されている距離より小さい（近い）と判定した場合（Ｓ４８０、Ｙｅｓ）、授受先ノード探索部６０は分岐リストＬ＿ＮをセルＣが指すノードのセルのリストに書き換え、且つ、深さｄの値を１加算する（Ｓ４９０）。
【００７０】
次に、授受先ノード探索部６０はカレントノードの深さｄとアンダーフローしたノードの深さＤがｄ＝Ｄとなったか否かを判定する（Ｓ５００）。
【００７１】
ｄ＝Ｄとなっていないと判定した場合（Ｓ５００，Ｎｏ）、授受先ノード探索部６０は前述のステップＳ４２０に戻り、新たなカレントノードＮについての分岐リストＬ＿Ｎを生成し、ステップＳ４３０移行の処理を実行する。。一方、ｄ＝Ｄとなっていると判定した場合（Ｓ５００、Ｙｅｓ）、授受先ノード探索部６０は、最近傍ノード候補リスト更新部６３に、最短距離がセルＣまでの最短距離より大きいノードに代えて、最近傍ノード候補リストＮＮにカレントノードＮを示すノードＩＤと中心座標ＱからセルＣまでの最短距離とを格納させ（Ｓ５１０）、最近傍ノード候補リストＮＮの更新を実行する。その後前述のステップＳ４６０に進み、授受先ノード探索処理をさらに続行する。
以上で授受先ノード探索処理の説明を終了し、アンダーフロー処理装置の動作例の説明を完了する。
【００７２】
[３．本実施の形態の利点]
本実施の形態によれば、近似近傍検索（誤差許容係数ε）を用いることで、削除速度と木の検索速度のトレードオフを調整できる。すなわち、ε＝0のときは全てのノードが対象となり、εの値を大きくすると、遠くにあるノードを探索する手間が省ける（枝刈り）。
【符号の説明】
【００７３】
１…アンダーフロー処理装置；  １０…木の情報格納部；  ２０…点削除部；  ３０…アンダーフロー処理部；  ４０…アンダーフロー判定部；  ５０…根ノード処理部；  ６０…授受先ノード検索部；  ７０…授受部；  ８０…点授受部；  ９０…セル授受部；  １００…セル調整部
【図１】
2012155579.tif 000003
【図２】
2012155579.tif 000004
【図３】
2012155579.tif 000005
【図４】
2012155579.tif 000006
【図５】
2012155579.tif 000007
【図６】
2012155579.tif 000008
【図７】
2012155579.tif 000009
【図８】
2012155579.tif 000010