• 概要・news
• シフトしたプレーン
• 再帰的な分割
• まとめ

シフトしたプレーン

まず非常に単純に、ある粒度においてシフトしたプレーンが境界問題のために 9 地域を探索する問題を回避し得ることを示す。

クリックするとフルサイズの画像が得られます。

	まず起点 O に対して、近傍のポイント情報を検索し、X, Y が共に掛かって欲しい（起点と異なる矩形範囲に含まれているために Y が見逃される、といったことをしたくない）場合を想定する。 この例では O が矩形の端に近いためにそのようなことが生じる。 （なお一般には起点から n Km 以内の範囲でポイントを探す、といったことをすると考えられ、矩形領域はそれを充分カバーする程度に設定された粒度である、という点に注意。）
	このとき、赤枠のような矩形領域に切り取った別のプレーンを用意する。 通常の Geohash の緯度経度からの計算方式に対して、一定のズレを与えてから同一アルゴリズムで計算した結果が赤枠になると考えればよい。 つまりこの場合では O は黒枠を利用せず赤枠のプレーンを利用すれば正しく近傍点を見つける事ができる。 しかしこれでも O が黒枠と赤枠の交点位置に非常に近かった場合はやはりどちらを選んでも見つからないポイントができるだろう。
	そこでこのように 1/3 ずつシフトしたプレーンを用意する。 三枠が皆交差するところはないので、どの地点であってもかならず「境界間近」でないプレーンが存在することになる。 つまり検索方法としては、まずどのプレーンが最も適切か（あるいは順繰りに試して最初に見つかった「ひどい」領域でないプレーン）を選択し、それからただ一度だけ、そのプレーンでの Geohash 文字列の前方探索をすれば良いことになる。 実現するためには 3 プレーン分の Geohash 値、つまり RDB に収めるのであれば従来一カラムで済んでいた Geohash カラムをあと 2 つ追加する必要がある。つまりこれは空間を用意して事前に計算しておくことによって、検索時の探索回数（あるいは条件判断処理の回数）を削減するものと言える。