- 2008-01-25 (Fri) 6:27
Cell method
データ領域を包含するセルのサイズを事前に決定する必要があるため、動的なデータベースには不利のようです。
各セルは、そのセル領域と重なる領域の識別子を持ちます。セルを細かく区切れば検索精度は向上しますが、使用するデータ領域が増加します。
Digital MapはCell methodにより読み込む領域を検索していますが、すべてオンメモリでデータ構造を構築しているため、セルのサイズを大きくせざるを得ず、検索精度があまりよくありません。それに加えて数値地図25000には領域の外接長方形のデータしかないのでcell methodの恩恵をあまり受けることができず、地図データの読み込みが遅く、また表示領域以外の領域が読み込まれることが多々あります。
Quad Trees
領域を4分割（2次元）することで木構造を構築します．ディスク上に構築する際には、2分割するよりも高速です．ページングが考慮されていないようです．
k-d trees
ページングが考慮されていないそうです．
R-trees
特徴
- B-Treeを多次元に拡張したデータ構造
- 点検索、範囲検索が可能
- （再編成なしに）動的にデータ構造の変更が可能
- クラスタリングの手法
- すべての組み合わせを調べる手法
- quadratic-cost algorithm :
O(m^2) - linear-cost algorithm :
O(m)
- http://www.db.is.kyushu-u.ac.jp/seminar/20020129/index.html
- http://d.hatena.ne.jp/wanpark/20060510/1147253356
原論文
- R-TREES A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING
(http://www-db.deis.unibo.it/courses/SI2/papers/R3.pdf)
R+-trees
論文
- The R+-Tree: A Dynamic Index for Multi-Dimensional Objects (http://www.informatik.uni-trier.de/~ley/db/conf/vldb/SellisRF87.html)
R*-Tree
- The R*-tree: An Efficient and Robust Access Method for Points and Rectangles (http://www.cs.umd.edu/projects/hpsl/classes/818s-s98/ppt/rtree/)
K-D-B trees
ページングは考慮されているが、点検索しか行えないようです。
Corner stitching
2次元空間データ(≠0)の検索に適しているが、(homegrous primary memory?)を仮定しており、大量のデータをランダムに検索するには効果的でないようです。
原論文
- Corner Stitching: a Data Structuring Technique for VLSI Layout Tools
(http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-114.pdf)
Grid files
空間をグリッドに区切り、グリッドをキーとしたハッシュテーブルを作成します。区切り方によって大きくメモリ効率が変わることと、データの存在する範囲を途中で変更できないこと、次元数が増えるとメモリ効率が極端に落ちてしまうことが問題のようです。
技術動向
OpenGISで空間データベースの検索言語の標準化がすすめられているようです。
参考リンク
- 空間と時間を扱うデータベースに関する覚書
(http://www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html)