Google App Engine で地理データ処理
2008 年 8 月 18 日 月曜日今日は、Google App Engine(GAE)の地理データ処理について書きます。GAEによるクラウドマップのAPI化を試みているのですが、その中で多少特殊なテクニックが必要とされる部分がこれでした。
まず目的は、x,y,z (latitude,longitude,elevation)で表される点の集合を地理的な範囲で絞り込むことです。具体的には、xmin<x<xmax, ymin<y<ymax,zmin<zの範囲の中にある点集合を取り出すことです。
普通のデータベースなら何の問題もないのですが、GAEの場合、範囲指定が一つの変数にしか使えないという制約があるので、この絞込みを素直に実行できません。つまり、xmin<x<xmaxのみならいいが、それに加えて, ymin<y<ymaxやzmin<zなど行うことはできないということです。
結論から言うと、xmin<x<xmax, ymin<y<ymaxの絞込みはgeohashと呼ばれるもので、zmin<zの絞込みはListPropertyで行うのがベターだと思います。
■ GAEでgeohashがいいというのはこちらを参考にしました(googleも採用しているそうです→ソース)。geohashは、ある領域を011011111111000001000001などのビット列で表し(それをBase32等でエンコードし)たものです。奇数番目のビット列(0111110000000)がx座標を表し、偶数番目のビット列(101111001001)がy座標を表します。それぞれのビット列の、左端のビットから、全体領域を2分割していったときに左(上)にあるか右(下)にあるかを示し、徐々に細かい粒度の領域を指し示すようになります。図で表すと次のようなものです：
最初の2×2分割を表すのに00,01,10,11というビット列が使われ、次の4×4分割を表すのに、後ろ2ビットが新たに追加されます。
この表現方法でうれしいのは、例えば、011011111111000001000001としたときに最初の01という大まかな領域にあることが分かることです。そして、01の領域の内部を表すには、01≦pt<10とすればいいことです。これにより、x座標の絞込みとy座標の絞込みが同時に行え、GAEの制約を回避することができます。制約がなくても、速度の面から見てこのような方式は有用だろうと思います。
■ さて、geohashでめでたくx,y座標の絞込みはできたのですが、クラウドマップではまだz座標の絞込みをする必要があります。ある高さ以上の点を表示したいというものです。このような絞込みはgeohashのような分割木的な絞込みとは様相が異なります。ここではListPropertyによってその制約を切り抜けました(調査不足で他にこの手の問題を扱っているものが見当たらなかったので確立された方法かどうか分かりません)。
ListPropertyはGAE特有のデータ型で、リストを格納できます。さらに特殊なのは、where句で例えば、list_data = 2とすると[0,1,2]とか[1,2,3,4]など、リストの中にどれか一つ”2″があれば選択されるようになることです。つまり、”In”クエリ的な働きをします。z座標の絞込みはこの特性を利用します。
方法はまず、z座標をn分割します。そして、第1の層にある点をlayer=[0,1,..,n-1]、第2の層にある点をlayer=[1,2,...,n-1]、第３の層にある点をlayer=[2,3,...,n-1]、として格納します。そうすれば、layer=1と指定して第１、第2の層の点を、layer=2と指定して第1、第2、第３の層の点を取り出すことができます。この絞込みは範囲指定でなくイコールなので、geohashの範囲指定と同時に使うことができます。連続的なz座標の絞込みは、この離散的な絞込みの後、GAE本体以外で実行させても問題ないでしょう。
