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

まとめ

1/3 ずつシフトした Geohash プレーンのアイディアについて説明した。 従来的には起点が矩形領域の端に近い場合に、目標とする距離範囲内にいるにも拘わらず検索できない問題があり、従来的にはこれを（ナイーブには）前後左右斜めの 9 箇所を探索する方法が知られていた。

しかし 1/3 ずつシフトした座標位置（地球全体を 1/3 緯度・経度ともにずらして求める）による Geohash 値によるプレーンを用意することでこの問題を回避できる。 検索時に起点が（端すぎることによる）不適ではない、あるいはもっとも適したプレーン（指定された粒度において中央 1/3 に含まれるプレーンが必ず一つ存在する）を用いることで Geohash 文字列の上位部分一致探索をただ一回だけで済ませる事が出来る。

実際にこれがシステム構築において有益か否かは、MySQL などの処理系が文字列部分一致条件を or で 9 つ列記する事に対して、CPU 処理量では最適プレーンの選定、ディスクおよびメモリ消費（現実にはインデックスはメモリに載り切るか否かで負荷は相当に違う）では Geohash 値のカラムをもう二列用意するといったオーバヘッドとの差し引きと思われるが、筆者はこのあたり全く想像がつかない。

本質的にはデータ量と引き換えに、処理時間を詰めようとする試みなので、まあ地点データのデータ量が爆発した際に有利になるケースがあるかも知れない、程度か。

他にもトレードオフはある。例えば最大矩形領域を世界地図の2倍のサイズから始めなければならないので、32bit で表記する、といった限界設定から生じる最小矩形領域のサイズもやはり倍になってしまう。

ま、素人のその場の思いつきということで、、、バラ色の話があればきっと最初からそうなってるだろうし。