Wheren っていうのを作ってる話

最近 Wheren っていうのを作っていて簡単に言うと GeoHash に時間を縦軸に加えたものです。いつどこを扱うので where + when を足して wheren です。

緯度経度時刻の範囲をハッシュ化出来るので、その３つの範囲で検索する時に、わりと力を発揮してくれるんじゃないかと思います。下にも書いてあるんですけど、割りと狭い範囲で効いてくる感じなのですれ違い通信とかで使えそうかなぁという感じがしています。

前方一致の仕組みはGeoHash同様に入っています。

soh335/p5-Data-Wheren · GitHub
コードはこちら。perlモジュールの書き方がちょっとまだ掴めてないので間違ってたら教えて下さい。

仕組み

GeoHash 自体は Z-order っていうのがベースになっていて、それを３次元に展開してるって事です。

GeoHash はハッシュ化する文字列の長さによって縦と横の長さが交互に変わるんですけど、それだとちょっと考えづらいのでとりあえず今作ってるのは緯度経度に関しては4x4でメッシュを切るようにしてます。

で、縦軸の時間は4つと8つのメッシュで切る２つを用意してあります。

みたいなかんじです。上のものは7Bit、下のものは6Bitという名前をつけてます。ちなみに7Bitのものは一つのボックスが128個に別れてアルファベットとか数字だけじゃ表せないので二文字で１つのレベルを表現するようになっているので注意が必要です。

ちなみにデメリットですが、Z-order なものなので下限上限が必要になります。なので時間も下限上限を作っています。ライブラリ側で指定出来るようになっていますけど、デフォルトはとりあえずUNIXタイムの0秒から2038年問題が起こる秒数までにしてあります。適当にこれは変更出来るので100年後まで使われるサービスとかじゃなければ問題ないかと割りきりました。

使い方

use Data::Wheren::7Bit;

my $wheren = Data::Wheren::7Bit->new;
my $hash = $wheren->encode( $lat, $lon, $epoch_time, $level );
my ($lat, $lon, $epoch_time) = $wheren->decode( $hash );

という感じで使えるので Geo::Hash モジュールと同じように使えます。

ライセンス

GeoHashの拡張みたいなものなので同様にパブリックドメインにしようと考えています。

TODO

今色々mysqlにデータをいれてパフォーマンス取ってるので、そのうちそれも載せます。緯度経度時刻が割りと狭い範囲なら lat, lon, time で検索する場合、geohash、time で検索する場合よりも割りと早い感じです。

後はgeohashが使われてるbigtable辺りでも時刻の範囲を含んだデータを入れる場合は役に立つかもしれませんけど、bigtableに詳しくないのでちょっとよくわからないです。

広くなってくるとハッシュ化した文字列を全部orで繋いで検索する為遅くなるんですけど、時間の上下を調節するのと6Bitと7Bitの選択で割りとどうにかなるのではという気もしていますが、これも後々調べます。

あとテストもまだ書いてないのでそれもやらないとという感じではあります。

いまいち自分でもどう使うといいのかよくわからないので、何か有用に使えそうな事があったら教えてもらいたいです。よろしくお願いします。

追記

テストにこける話

今、Data::Wheren::Base が抽象クラスみたいになっていて、Data::Wheren::7Bit、Data::Wheren::6Bit がそれぞれそれを継承して必要な事だけ書くと後はBaseの方が見てくれるという形にしてるけど、Baseのドキュメントの書き方がよくわからなくて実際に利用される7Bitの方にドキュメントを書いているのでBaseのpodのテストでコケます。
使う側のapiはもう変えることはないと思いますけど、ちょっとそこも悩み中なので何かいい方法とかあったら教えて下さい。