https://shogo82148.github.io/blog/2017/03/28/database-gis/
「サーバーで付近の情報を通知するサービスのつくり方」 という、Geohashを使って近傍検索を実現する記事をみつけました。 最近Redisに関する記事を書いた関係で、 この記事をみて「GeohashはRedisと一緒に使うともっと便利だよ！」と思わず宣伝したくなったのですが、 MySQL5.7でInnoDBに空間インデックス(Spatial Index)のサポートが入ったので 「MySQLでももっと簡単にできるのでは？」と思い、 RedisやMySQLを含めたいろんなDBで近傍検索を実現する方法を調べてみました。
以前、スマートフォンのセンサを活用して花火の打ち上げ場所を推定するアプリを作った関係で、 地球上での距離計算の実装も気になったので、それについても調査してみました。
Geohash（ジオハッシュ） は緯度・経度を短い文字列に変換する方法です。 距離が近い2地点のGeohashは似たような文字列になるという特徴があります(一部例外あり)。 この特徴を利用すると、文字列検索だけで近傍検索が実現できます。
地球は完全な球体ではなく、回転楕円体であることが知られています。 地球の形がわからないと緯度・経度などを決められないので、 地球楕円体が定義されています。 近似方法によっていくつか種類があるのですが、GPSなどで使われているWGS84がよく使われているようです。
国土地理院が提供している測量計算サイトでは 距離と方位角の計算を使って緯度・経度から距離を計算できます。 回転楕円体上の距離の厳密解は求められない(要出典)ので、 数値計算によって求めることになります。 計算式を見て分かる通り非常に複雑なので、なんらかの近似をしている実装がほとんどです。
Redisでは3.2からGEO関連の機能をサポートしています。 ソート済みセットにGeohashを組み合わせて実現しています。
簡単に試してみました。データは以下の記事から拝借したものを使用します。
GEOADDでデータ挿入です。 ちなみにデータを削除するGEODELは用意されていないとのこと。 中身はソート済みセットなので、ZREMでいいんですね。
$ cat command.txt
GEOADD geotable 139.777254 35.713768 上野駅 139.774029 35.711846 西郷隆盛像
GEOADD geotable 139.774744 35.712737 上野の森美術館 139.770872 35.712351 不忍池弁財天
GEOADD geotable 139.775696 35.716293 野口英世博士像 139.775803 35.715420 国立西洋美術館
GEOADD geotable 139.776544 35.716319 国立科学博物館 139.772776 35.717186 東京都美術館
GEOADD geotable 139.776462 35.718883 東京国立博物館 139.794547 35.715280 花やしき
GEOADD geotable 139.792692 35.710635 雷門
$ redis-cli < command.txt
(integer) 2
(integer) 2
(integer) 2
(integer) 2
(integer) 2
(integer) 1
GEOHASHで各地点のGeohashを取得できます。
$ redis-cli
127.0.0.1:6379> GEOHASH geotable 上野駅 西郷隆盛像 上野の森美術館
1) "xn77htqxy10"
2) "xn77hthkdf0"
3) "xn77htkcg80"