地図・GIS・位置特定に関する連載の4日目のエントリーです。最初はブラウザの座標を取得するAPIとか、IPアドレスから場所を推定するGeoIPを使って、近い場所の人を探すサービスでも作ってみようかと思っていました。Quad-Treeみたいなゲームでよくある座標系を収めるデータ構造を使って、近くのメンバーを探す機能とかを作ろうと思っていましたが、ふと「座標系をそのまま格納して検索できるデータベースとかありそうだな」と思って調べたところRedisがヒットして横道にそれてしまったのでそのまま横道を突き進んでみました。

Redisは2010年ぐらいに有志でドキュメント翻訳したりしたりして、チョットワカル程度でしたが、久々にドキュメントを見ていたら座標情報を保持したり検索したりするコマンドが増えていました。その辺りを少し調べてみました。

Redisのジオメトリ機能

Redisのジオメトリ関係のコマンドは10個ほどあります。

GEOADD: 座標つきでメンバーを登録
GEODIST: 登録したメンバーの距離を計測
GEOPOS: 登録したメンバーの座標を取得

メインの検索機能はこちら

GEOSEARCH: 指定の座標/メンバーから範囲内（矩形、もしくは半径）のメンバー一覧を返す

メインの検索機能を便利にするメソッドはこちら

GEOSEARCHSTORE: GEOSEARCHの結果をsorted setに保存
GEORADIUS: GEOSEARCHの座標→半径計算特化版。STOREも可能。
GEORADIUS_RO: GEOSEARCHの座標→半径計算特化版。STOREなし。
GEORADIUSBYMEMBER: GEOSEARCHのメンバー→半径計算特化版。STOREも可能。
GEORADIUSBYMEMBER_RO: GEOSEARCHのメンバー→半径計算特化版。STOREも可能。

なお、これらはネイティブなデータ構造になっているわけではなく、次のコマンドを使ってGeoHashというキーを生成し、sorted setに格納されています。登録したメンバーの一覧を取得や、メンバーの数の取得、メンバーの削除はsorted setのコマンドをそのまま使うことになっています。

GEOHASH: 緯度・経度をgeohashというアルゴリズムでハッシュキー化します。

Redisのドキュメントから持ってきたサンプルは以下の通りです。

このサンプルのSicilyというのはsorted setの名前です。地球の座標系、火星の座標系など、複数のスペースを分けて使います。GEOADDは複数の要素を一括で入れられて、緯度・経度・キーをセットで入れます。GEODISTは登録したメンバー同士の距離を返す機能で、GEORADIUSは特定の座標から一定距離内のメンバー一覧を返しています。

redis:6379> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2
redis:6379> GEODIST Sicily Palermo Catania
"166274.1516"
redis:6379> GEORADIUS Sicily 15 37 100 km
1) "Catania"
redis:6379> GEORADIUS Sicily 15 37 200 km
1) "Palermo"
2) "Catania"

GeoHash

このジオメトリ機能の肝はGeoHashです。パブリックドメインなアルゴリズムです。たとえば、13.361389 38.115556という座標はsqc8b49rny0というキーになります。

Redisは経度としては±180度、緯度は±85.05112878度までをサポートしています。北極点、南極点から555kmの範囲は表現できなそうですね。

GeoHashは長さが長くなればなるほど精度があがって細かい座標も表現できるというモデルになっています。sqc8b49rny0の末尾の文字列を削ってもだいたい同じ位置になるが、丸められてしまう、みたいな欠損してもvalidな面白いデータ構造になっています。

GeoHashの各文字はbase32にエンコードされた数値です。1文字で5ビットあります。奇数文字列目は3ビットの経度＋2ビットの緯度、偶数文字列目は2ビットの経度＋3ビットの緯度で表現されます。Redisは11文字の文字列で表現されるので、55ビットと思いきや、内部的には52ビットとなるようです。なので、おそらく、緯度・経度ともに26ビットの精度になると思われます。本来のGeoHashはRedisと違って緯度は±90度なので、ちょっと計算は違うかもしれませんが、Wikipediaの計算をもとにすると、誤差は30cm程度。十分な精度ですね。

ちなみに、これらは地球上の座標として表現されているので、Redisで火星の座標系とかを表現しようとすると、補正が必要ですね。

ベンチマーク

Redis 7.0.3、Go 1.18.4、ドライバとしてgithub.com/go-redis/redis/v9を使って、M2 MacBook Airでベンチマークを取ってみました。RedisのドキュメントにはO(N+log(M)) (Nは検索範囲のバウンディングボックスの中のメンバー数、Mはその図形の中のメンバー数)とドキュメントにはあるのですが、実際にかかる時間の肌感覚を知りたかったので。コードは次のところにあります。

https://gist.github.com/shibukawa/2cf8fc518d58f5031619798d3d43ceb7

要素数は以下の通りで、関東の範囲(東経139-141, 北緯35-37)にランダムにメンバーを登録して、検索をかけてみました。要素数は以下のケースで検証してみました。

1000: (関東のマクドナルドの店舗数の1377と同じぐらいのオーダー
10000: (関東の郵便局数の4627と関東のコンビニの店舗数20779の間ぐらいのオーダー
100000: (関東の信号の数の59188よりもちょっと多いオーダー)

ちなみに、100000件データを入れても、Redisの消費メモリは16MB程度、Redisが生成したファイルが1.2MB程度で想像よりも遥かに少ないです。

結果は以下の通りで、このぐらいの検索だと誤差の範囲ぐらいですね、というか本当かよ？と思うぐらいの高パフォーマンス。一番最後のやつで40件近くヒットしていて、動作上は肌感覚的に間違ってなさそうな結果は出ています。要素数が増えても、検索対象を賢く絞ってパフォーマンスが落ちないような工夫がされていそうです。

要素数	検索条件	時間
1000	1辺1kmの矩形	24μs
1000	半径1kmの円	22μs
1000	1辺2kmの矩形	23μs
1000	半径2kmの円	23μs
10000	1辺1kmの矩形	23μs
10000	半径1kmの円	24μs
10000	1辺2kmの矩形	24μs
10000	半径2kmの円	27μs
100000	1辺1kmの矩形	26μs
100000	半径1kmの円	33μs
100000	1辺2kmの矩形	33μs
100000	半径2kmの円	52μs

GeoHashがすごいのは、文字列長さによって精度が変わることと、1次元にマッピングしていること。つまり、探したい座標と範囲が分かれば先頭一致で要素が絞れます。2次元を1次元で表現する方法は昔考えたことがあるものの、なかなか思いつかなかったのですが、コンピューターサイエンスの勝利というか、久々に胸が熱くなるものを見つけました。あらかじめQuadTreeの深さとかパラメータを調整する必要もないですしね。LOUDSみたいなデータ構造との相性も良いですしね。夢が広がります。

まとめ

こちらの機能としてはウェブサービスを作る時とかに便利に使えそうですよね。座標はブラウザの機能とか使えば簡単にとれます。Redis側にあらかじめいろんな場所情報を入れてあげて、ブラウザから取得した座標を投げ込めば簡単に近隣のスポットを探す、というサービスが作れそうです。

https://developer.mozilla.org/en-US/docs/Web/API/Geolocation_API

navigator.geolocation. getCurrentPosition((pos: GeolocationPosition) => {
    console.log(pos.coords);
    // {latitude: 35.0, longitude: 135.0, altitude: null}
});

SQLiteでマスターを配布するような感じで、Redisも読み込み専用で使ってあげるとかも面白い気がします。ビジネス利用がいろいろ考えられますね。

今回はRedisを調べただけですが、座標周りのロジックにはいろいろあります。

IPアドレスから座標を推定するGeoIP
場所から座標を調べるジオロケーション
座標から場所を調べる逆ジオロケーション

人間にわかりやすいコード体系やら機械にわかりやすいコード体系、それぞれの変換など、「場所」の世界は奥深いですね。これらを組み合わせると場所を使った面白いサービスが作れそうです。

次は塚本さんの住所情報から経路を探索する”そこそこ”な方法です。