空間索引木を用いた範囲問合せ手法

IPSJ Web Site

Bibliographic Information

Other Title
  • クウカン サクイン ボク オ モチイタ ハンイ トイアワセ シュホウ
  • Distance Range Queries in Spatial Index Tree

Search this article

Abstract

近年，地理情報システムや道路網応用の研究分野で，最短経路問題（SPP），範囲問合せ（DRQ），k最近傍探査問題（kNN）などに有効な空間索引の研究が注目を集めている．我々の先行研究で，ネットワーク上の距離を基準に，道路網データから領域の分割と統合を繰り返して，ボトムアップに構成する空間索引木を提案した．さらに，この空間索引木を用いて最短経路問題を効率的に実行できることを確認した．本稿では，問合せ円を指定する範囲問合せについて議論する．SPPが始点と終点の1対1の計算になるのに対して，DRQは，問合せ点とオブジェクト集合の1対多の計算が必要となる．さらに，先行研究の距離指標のみを用いて問合せ処理を実行すると，オブジェクトが存在すると推定される領域が冗長に見積もられ，空間索引木の刈込みが有効に行えない．これは，距離指標が，母点領域の形状や位置関係を十分に表現できないことに起因する．また，DRQは，グラフ上の問合せ点とオブジェクト集合を用いた問合せであるため，グラフとオブジェクトとの関係を利用しなければ，冗長な領域を計算する必要がある．これらの問題の解決のために，空間の拡がりを示す指標としてMBR（最小外接長方形）を導入し，オブジェクトに関する指標を新たに追加する．MBRは，空間索引木の構成時に付加し，オブジェクト指標については，空間索引木構成後に，様々なオブジェクト種別ごとに，同一の空間索引木に組み込む．これら2つの指標と距離指標の3つの指標を用いた再帰的問合せ手順を新たに提案し，その効果について議論する．提案手法の有効性について確認するため，国土地理院発行の数値地図を利用して，新規追加の指標のサイズと組込み処理時間，距離指標のみを用いたナイーブな手順と提案手法の刈込みの比較，また，参照点埋込み法と提案手法の距離見積りの精度の比較，ならびに，DRQにおいてKriegelらの手法を発展させた階層型参照点埋込み法と提案アルゴリズムの展開数と実行時間の比較を行う．

Recently much attention has been focused on spatial query processing for road networks. In the previous work, the authors have proposed spatial index tree that can be constructed in a bottom-up fashion by generating Network Voronoi Diagram from a given base graph (=road network) using network distance. The tree possesses distance indices for each subregion that work efficiently to prune spatial index tree in processing one-to-one distance-based queries, including Shortest Path Problems (SPP). In this paper, the authors discuss spatial query processing for Distance Range Queries (DRQ). In SPP, distance index is used to extract heuristic path using one-to-one distance computation, while one-to-many distance computation is required for a given query point and target object set for DRQ. Only by use of the distance index, redundant search regions may be extracted from the tree, since distance estimation errors are accumulated regarding the size of generator regions that exist between query point and target objects. This is due to the fact that distance index is not sufficient for DRQ in pruning redundant subregions in the spatial index tree. Further, in DRQ, discussion on spatial relationships of query circles and generator regions become necessary. To cope with these problems, two new indices, namely Minimum Bounding Rectangles (MBR), as spatial extent index, and object index, are introduced in the spatial index tree in the paper. These spatial indexes can be built in the spatial index tree in a bottom up fashion, with preserving inclusion relationships among both generator regions and MBR's, respectively. Also, object indices are utilized to prune redundant subregions in DRQ. Then, using these 3 indices, a new recursive algorithm for DRQ is provided. The algorithm is based on the incremental identification of target subtrees, which corresponds to tree pruning. Numerical evaluations for real map data issued by Geographical Survey Institute, are provided to show effectiveness of the proposed approach, including newly added index size and processing time, and accuracies of distance estimation of our previous work and the proposed framework. Also the proposed algorithm is compared with the extended hierarchical embedding method proposed by Kriegel et al in DRQ.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top