BD木上での線に沿ったデータ検索

情報処理学会

書誌事項

タイトル別名
  • Data Retrieval along the Line on the BD tree

この論文をさがす

抄録

地理情報処理やグラフィックス、図形処理の分野では空間的な位置関係に依存した図形の検索が重要となる。範囲検索や最近点検索がこの代表例である。一方、この様な検索を効率よく行うためのデータ構造として、階層的な領域分割と木構造による管理を基本としたものが多く提案されている。k-d木、BD木、MD木、R^+木等がこの範疇に属している。本稿では、これらのうちBD木上で「線に沿った検索」を効率よく実行するための検索アルゴリズムについて述べる。線に沿った検索とは、線が検索キーとして与えられ、その「線と交わる全ての図形の検索」、「線から一定距離d以内に存在する図形の検索」、「線の最も近くに存在する図形の検索」等であり、これらは図形情報の検索において重要な形態の1つである。図1は本稿で扱う検索の例を示したものである。ここでは短線分がデータベース化されており、太線で示す線が検索キーとして与えられた場合を示している。BD木の各ノードには下位ノードで管理している図形の外接長方形情報が置かれている。提案方式の基本はこの外接長方形情報と線との関係を調べ、検索対象を効率よくしぼり込むことにある。以下では「線に沿った検索の代表例を3種類取り上げ、その検索アルゴリズムを述べる。

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ