Geohashでインデックスしたデータ構造

cocoraでは、現在位置の近くでの発言を高速に探索する必要がありました。
また、cocoraではプラットフォームとしてGoogle App Engineを用いましたが、DBからの検索はただでさえ時間がかかる上、複数のプロパティに対する範囲検索ができないという特徴があります。

そこで、Geohashをキーとしたマップ(辞書)型のpython用クラスライブラリを作りました(geohashtree)。
このデータ構造の特徴は、k-NN探索を効率的に行うことが出来るという点です。
このライブラリはGitHubに置いてあります。
以下、データ構造の説明です。

Geohashは、緯度経度を文字列で表現する手法で、xとyのビットが交互に続く構造となっています。
これはモートン順序と解釈することができ、また、kd木との類似性を見出すことができます。
geohashtreeでは、エッジをGeohashの各ビットの01に対応させて一意に判別できるように(葉ノードに)データを格納します。
計算量は、追加、探索、削除、そしてNN探索(最近傍探索)が実質的にO(logN)なはずです。(最悪はO(N)ですが)