空間データの検索方法
空間データというのは、具体的には「点」「線」「多角形」といった図形のデータのことだ。ナビゲーションシステムで言えば、地図上の道路は「線」のデータとして、コンビニやレストランなどの小さい建物は「点」データとして、公園のように広い面積をもつ施設は「多角形」のデータとして表現されている。こういった「図形」のデータに対して検索するときは、普通のデータベースで検索する時とは少し違う検索方法（クエリ）が使われる。よく使われるものは以下の四種類。
- 物体クエリ (Object Query)
- 地点クエリ (Point Query)
- 範囲クエリ (Range Query)
- 近傍クエリ (Nearest-Neighbor Query)
空間インデックスは、主に Range Query と Nearest-Neighbor Query を高速に処理することを目的に作られる。なお「〜クエリ 」という日本語は、イメージしやすいように私が勝手に当てたもので、学会などでの一般的な言い方ではないことをことわっておく。
物体クエリ (Object Query)
探したい施設の名前や電話番号を検索ワードとして与えて、その施設の場所を見つけるというクエリ（検索方法）のこと。ナビで行きたい場所を検索するときには、このクエリがよく使われていると思う。
このクエリは、検索ワードは「施設の名前」だったり「電話番号」だったりするので、空間データ特有の「位置の情報」を全く使わず処理できる。なので、一次元のデータを検索するときと同じインデックスを使って検索できる。そういう意味では、空間データ特有の検索方法ではない。
地点クエリ (Point Query)
位置の情報を検索ワードとして与えて、その位置にある図形、もしくはその位置を含んでいる図形を見つけるクエリのこと。これは、住所を情報として入れて、その住所の地点にある建物や施設を見つけるという形で使われる。
範囲クエリ (Range Query)
何らかの図形を検索ワードとして与えて、その図形に含まれる、あるいはその図形と重なりのある図形を見つけるクエリのこと。これは例えば、不完全な住所情報（例えば「京都市左京区」までとか」を使って、その範囲にある施設を探すといった用途に使われる。この他、3D のアクションゲームやシューティングゲームで「弾がいま当たっている物」を見つけるという、いわゆる「当たり判定」の処理もこれにあたる。
近傍クエリ (Nearest-Neighbor Query)
位置の情報を検索ワードとして与えて、そこから最も「近くに」ある施設などを探すクエリのこと。ナビゲーションシステムでは、今いる場所から一番近いコンビニやレストランを探すという用途に使われている。このクエリは、空間データ特有の「距離」の情報を使わないと処理できないことから、通常のデータベースでのクエリの処理方法をそのまま使うことがむずかしい。
さらに、地図のデータで以外でも、このクエリはよく使われる。例えば、画像検索や音声検索、Webページの検索といった「完全に一致してないけど、それに近いもの」を探すときにも威力を発揮する。こうした検索をする場合は、音声や画像のデータを予め多次元のデータ（特徴ベクトルということもある）に変換しておき、変換された多次元のデータを検索するという形で行われる。
なお、このクエリは一般に「近い方から k 個探す」クエリという意味で k-Nearest-Neighbor Query (kNN) と呼ばれることが多い。k=1 なら「一番近い」ものを探すことになる。
