hogemanのちょっといたい話

目次

ニュース

ここは日記帳じゃねえです。
hogemanのコアダンプ
がリアル日記帳です。

書庫

Blog 利用状況

PASSJにでも書いてろって内容だけど...わんくまでやるお!

blogスペース要求しといていい感じに放置状態。ごめんなさい。

今週末の大阪勉強会には一応初参加の予定。知ってる人誰もいないだろうし勉強会のテーマ的にもアウェイ全開っぽいのに懇親会にも登録とかしてるし。まあMなだけなんすけどね。

今日の本題:空気読まずにBlog翻訳
最初のエントリとして SQL Server 2008 空間拡張チームのISAACさんBlogを※未承諾超訳※していってみる。誤訳してたらすまそ。そこはかとなく私自身が書く予定のエントリへのネタフリも兼ねてるわけですが。


空間インデックス パート1 「Why a Spatial Index?」

やあ、きみたち。

もし、僕が空間データベースについて説明してるのをみたことがあるなら、空間インデックスの基本的な動きについての僕の話も聞いてるだろう。ここでの一連のブログ記事でも同じような説明を少し詳しいところまでしていこうとおもう。まずは基本的な話から始めて、だんだんと実際の動きについての話にすすめていくつもりだ。

空間演算に際し、どの空間データベースもだいたい同じような基本的戦略を使っている:(たとえば図形の交差を調べるような)空間演算を処理する場合、実際には二段階に処理をする。一次フィルタと二次フィルタの2段階だ。一次フィルタは粗く絞りこみ、二次フィルタで正確な判断をする。一次フィルタは以下の3つの特性をもってるべき。

  1. 偽の結果を含む。つまり、指定した条件式とマッチしない空間オブジェクトも結果に含めることがある。だが逆に、マッチするはずのものを誤ってふるい落とすことはない。
  2. 偽の結果を含みすぎることはない。(一次フィルタが全然仕事をしないのも意味がないので)
  3. 高速!

具体的に説明する。まず全米の道路網データがあるとしよう。ウィスコンシン州マジソンと重なる道路を取り出したいとする。まず一次フィルタ(雑だけど処理が速い)がウィスコンシン州以外のデータをおおざっぱに枝刈りするわけだ。しかしこの結果セットにはマジソンとは重ならないデータも含まれてしまっている(逆はない)。正確な結果をもとめるためには、この結果セットに対して(二次フィルタで)本来の意味の重なり判定演算を行うという寸法だ。

なんでこんな面倒なことをするかって?そりゃ二次フィルタ(正確な空間演算)が遅いからだよ。複雑な空間演算呼び出しをできる限り排除できたらとても速くなるんだ。もうひとつは、我々はリニアな挙動を望んでいるからだ。ひとつひとつの図形に対していちいち厳密な空間演算してたらそんなの達成できないからね。

よくわからない? 単純に言うと、空間インデックスていうのは一時フィルタのことだよ。

Cheers,
-Isaac

元記事へのリンク:http://blogs.msdn.com/isaac/archive/2007/11/24/spatial-indexing-part-1-why-a-spatial-index.aspx


注:一般的にはここに書いてるような使い方だけでなく一次フィルタで完結するような使い方をするケースもあり。たとえばある地図の表示範囲矩形にPOIを出すためのクエリーをする場合には二次フィルタをかける必要はない。しかしながらどの演算子がどのフィルタを使うかを意識しながらSQLを書く必要がある、というのもどうかと思うが。一次フィルタが余分に取ってくる部分の特性は各空間データベースによって割と違うので見比べると面白いっすよ。

投稿日時 : 2008年2月11日 15:29

Feedback

No comments posted yet.
タイトル  
名前  
Url
コメント