groongaのドキュメントにも位置情報検索について書かれているのですが、情報の更新が追いついていないため情報が不足しています。そこで、ここに現状に合わせたgroongaの位置情報検索についての情報をまとめておきます。なお、ここにまとめた内容もドキュメントに反映させる予定です。

できること

groongaには位置情報を用いた検索機能がついています。位置情報を用いた検索では索引を利用するため、全文検索と同じように高速に検索することができます。ただし、PostGISやMySQLのように¹線や面などもデータとして保持できるというわけではなく、点のみをデータとして保持できます。よって、groongaにできることは以下の通りです。

1. 指定した四角の中に含まれている座標を持つレコードを検索する。

2. 指定した円の中に含まれている座標を持つレコードを検索する。

3. 座標間の距離を計算する。

4. ある座標からの距離が近い順にレコードをソートする。

つまり、以下のようなユースケースにはgroongaの位置情報検索機能を使うことができます。

• 東京ドーム周辺のコンビニを検索する。
• 新宿駅東口から近い順に和菓子屋をソートして表示する。
• 今いる場所の近くにあるラーメン屋をリストアップして、近い順にソートして、今いる位置からの距離も計算する。

一方、以下のようなユースケースでは使えません。

• 杉並区内にある駅を検索する。（1つの四角または1つの円で表現できない領域では検索できない。）
• 湖を点ではなく領域で表現する。（レコードは点としてしか位置情報を持てない。）

文章だけだとピンとこないはずなので、図も用意しました。

まず、以下の図を見てください。黒い点がレコードを表しています。それぞれの操作でレコードがどのように扱われるかを示します。

以下の図は「指定した四角の中に含まれている座標を持つレコードを検索」したところです。赤い四角が「指定した四角」で、赤い点が検索されたレコードです。

以下の図は「指定した円の中に含まれている座標を持つレコードを検索」したところです。赤い円が「指定した円」で、赤い点が検索されたレコードです。

以下の図は「座標間の距離を計算」したところです。赤い点が基準点で、基準点とレコードの座標の間の距離を計算しています。

以下の図は「ある座標からの距離が近い順にレコードをソート」したところです。赤い点が基準点で、基準点からの距離が近い順にレコードを順番に選んでいます。赤い数字が選ばれた順番です。

表現方法

前述の通り、groongaで保持できる位置情報は点だけです。点を格納するカラムは以下のどちらかの型にしなければいけません。

• TokyoGeoPoint: 日本測地系での座標のときに利用する。
• WGS84GeoPoint: 世界測地系（WGS 84のWGSはWorld Geodetic Systemの略）での座標のときに利用する。

どちらの型を用いた場合でも、緯度と経度を格納するという点は変わりません。そのため、どちらの型の値も同じ表現方法を用います。サポートしている表現方法は以下のフォーマットの文字列です。

• "#{緯度}x#{経度}"
• "#{緯度},#{経度}"

緯度・経度は「ミリ秒」または「度」で表現します。ミリ秒表記はあまりなじみがないかもしれませんが、度表記はGoogle Mapsでも使われている表記なので見たことがあるかもしれません。たとえば、東京駅は緯度が35度40分52.975秒、経度が139度45分57.902秒ですが、これは以下のように表現します。

ミリ秒表記:

• 35度40分52.975秒 → ((35 * 60 * 60) + (40 * 60) + 52.975) * 1000 → 128452975
• 139度45分57.902秒 → ((139 * 60 * 60) + (45 * 60) + 57.902) * 1000 → 503157902
• 座標: "128452975x503157902" または "128452975,503157902"

度表記:

• 35度40分52.975秒 → 35 + ((40 + (52.975 / 60.0)) / 60.0) → 35.6813819444444
• 139度45分57.902秒 → 139 + ((45 + (57.902 / 60.0)) / 60.0) → 139.766083888889
• 座標: "35.6813819444444x139.766083888889"または"35.6813819444444,139.766083888889"（これはGoogle Mapsと同じ表記。つまり、Google Mapsで表示した座標情報をそのまま利用できる。）

以下は使用例です。まず、テーブルとカラムを定義します。

% groonga -n /tmp/geo-point
> table_create Stations TABLE_HASH_KEY ShortText
[[0,1315881737.57395,0.055109867],true]
> column_create Stations location COLUMN_SCALAR WGS84GeoPoint
[[0,1315881759.65377,0.081054688],true]

データを取り込みます。上記の4パターンすべてを取り込んでいます。

> load --table Stations
> [
> ["_key", "location"],
> ["東京駅（ミリ秒 + x表記）", "128452975x503157902"],
> ["東京駅（ミリ秒 + ,表記）", "128452975,503157902"],
> ["東京駅（度 + x表記）", "35.6813819444444x139.766083888889"],
> ["東京駅（度 + ,表記）", "35.6813819444444,139.766083888889"]
> ]
[[0,1315881767.69242,127.240681505],4]

格納されているデータを確認します。groonga内部では緯度・経度をミリ秒として保持しているため、ミリ秒表記で出力されます。groonga内部でミリ秒として保持しているのは浮動小数点数ではなく整数として処理したいからです。

> select Stations --output_type xml
<?xml version="1.0" encoding="utf-8"?>
<SEGMENTS>
<SEGMENT>
<RESULTPAGE>
<RESULTSET OFFSET="0" LIMIT="4" NHITS="4">
<HIT NO="1">
<FIELD NAME="_id">1</FIELD>
<FIELD NAME="_key">東京駅（ミリ秒 + x表記）</FIELD>
<FIELD NAME="location">128452975x503157902</FIELD>
</HIT>
<HIT NO="2">
<FIELD NAME="_id">2</FIELD>
<FIELD NAME="_key">東京駅（ミリ秒 + ,表記）</FIELD>
<FIELD NAME="location">128452975x503157902</FIELD>
</HIT>
<HIT NO="3">
<FIELD NAME="_id">3</FIELD>
<FIELD NAME="_key">東京駅（度 + x表記）</FIELD>
<FIELD NAME="location">128452974x503157901</FIELD>
</HIT>
<HIT NO="4">
<FIELD NAME="_id">4</FIELD>
<FIELD NAME="_key">東京駅（度 + ,表記）</FIELD>
<FIELD NAME="location">128452974x503157901</FIELD>
</HIT>
</RESULTSET>
</RESULTPAGE>
</SEGMENT>
</SEGMENTS>

>

目視でデータを確認する場合は「--output_type xml」を指定して、XMLとして出力した方が確認しやすいです。

使い方

groongaの位置情報検索機能で利用できる以下のことについてその実現方法を説明します。

1. 指定した四角の中に含まれている座標を持つレコードを検索する。

2. 指定した円の中に含まれている座標を持つレコードを検索する。

3. 座標間の距離を計算する。

4. ある座標からの距離が近い順にレコードをソートする。

説明にあたって、店舗を検索するアプリケーションを考えます。各店舗がそれぞれ1レコードに対応します。

スキーマ定義

まず、店舗を格納する「Shops」テーブルを定義します。今回は説明用なので、各店舗には必要最小限の情報として店舗名と位置情報のみを格納することとします。

table_create Shops TABLE_HASH_KEY ShortText
column_create Shops location COLUMN_SCALAR WGS84GeoPoint

位置情報で高速に検索できるようにインデックスを張ります。

table_create Locations TABLE_PAT_KEY WGS84GeoPoint
column_create Locations shop COLUMN_INDEX Shops location

インデックス用のテーブル「Locations」はパトリシアトライ（TABLE_PAT_KEY）にします。キーの型はインデックス対象のカラム（Shops.location）と同じ型（WGS84GeoPoint）にすることがポイントです。

以下は実際に実行した結果です。

ddl.grn:

table_create Shops TABLE_HASH_KEY ShortText
column_create Shops location COLUMN_SCALAR WGS84GeoPoint

table_create Locations TABLE_PAT_KEY WGS84GeoPoint
column_create Locations shop COLUMN_INDEX Shops location

データベースの作成:

% rm -rf /tmp/shops
% mkdir -p /tmp/shops/
% groonga -n /tmp/shops/db < ddl.grn
[[0,1315883158.10711,0.05206624],true]
[[0,1315883158.1593,0.067047364],true]
[[0,1315883158.22642,0.056288895],true]
[[0,1315883158.28277,0.11994776],true]

サンプルデータ

たまたまたいやき屋（+α）のデータがあった²のでそのデータを使います。

shops.grn:

load --table Shops
[
["_key", "location"],
["根津のたいやき", "35.720253,139.762573"],
["たい焼 カタオカ", "35.712521,139.715591"],
["そばたいやき空", "35.683712,139.659088"],
["車", "35.721516,139.706207"],
["広瀬屋", "35.714844,139.685608"],
["さざれ", "35.714653,139.685043"],
["おめで鯛焼き本舗錦糸町東急店", "35.700516,139.817154"],
["尾長屋 錦糸町店", "35.698254,139.81105"],
["たいやき工房白家 阿佐ヶ谷店", "35.705517,139.638611"],
["たいやき本舗 藤家 阿佐ヶ谷店", "35.703938,139.637115"],
["みよし", "35.644539,139.537323"],
["寿々屋 菓子", "35.628922,139.695755"],
["たい焼き / たつみや", "35.665501,139.638657"],
["たい焼き鉄次 大丸東京店", "35.680912,139.76857"],
["吾妻屋", "35.700817,139.647598"],
["ほんま門", "35.722736,139.652573"],
["浪花家", "35.730061,139.796234"],
["代官山たい焼き黒鯛", "35.650345,139.704834"],
["たいやき神田達磨 八重洲店", "35.681461,139.770599"],
["柳屋 たい焼き", "35.685341,139.783981"],
["たい焼き写楽", "35.716969,139.794846"],
["たかね 和菓子", "35.698601,139.560913"],
["たい焼き ちよだ", "35.642601,139.652817"],
["ダ・カーポ", "35.627346,139.727356"],
["松島屋", "35.640556,139.737381"],
["銀座 かずや", "35.673508,139.760895"],
["ふるや古賀音庵 和菓子", "35.680603,139.676071"],
["蜂の家 自由が丘本店", "35.608021,139.668106"],
["薄皮たい焼き あづきちゃん", "35.64151,139.673203"],
["横浜 くりこ庵 浅草店", "35.712013,139.796829"],
["夢ある街のたいやき屋さん戸越銀座店", "35.616199,139.712524"],
["何故屋", "35.609039,139.665833"],
["築地 さのきや", "35.66592,139.770721"],
["しげ田", "35.672626,139.780273"],
["にしみや 甘味処", "35.671825,139.774628"],
["たいやきひいらぎ", "35.647701,139.711517"]
]

データのロード:

% groonga /tmp/shops/db < shops.grn
[[0,1315883204.86313,0.005284274],36]

それでは、サンプルデータが用意できたので実際に使ってみましょう。

指定した四角の中に含まれている座標を持つレコードを検索

明日、あなたは初めて浅草に行くことになりました。初めて行く土地にたいやき屋があるかどうか、気になりますよね。そこで、浅草周辺にあるたいやき屋をgroongaで検索することにしました。

地図を見ると、左上が「35.7185,139.7912」で右下が「35.7065,139.8069」となる四角い範囲の中にたいやき屋があるかどうかを調べれば浅草周辺のたいやき屋を見つけられそうです。

groongaにはgeo_in_rectangle(カラム名, 四角い範囲の左上の座標, 四角い範囲の右下の座標)という関数があり、この関数を--filterオプションに指定すると指定した四角い範囲内にあるレコードをインデックスを使って高速に検索することができます。

% groonga /tmp/shops/db
> select Shops --filter 'geo_in_rectangle(location, "35.7185,139.7912", "35.7065,139.8069")' --output_type xml
<?xml version="1.0" encoding="utf-8"?>
<SEGMENTS>
<SEGMENT>
<RESULTPAGE>
<RESULTSET OFFSET="0" LIMIT="2" NHITS="2">
<HIT NO="1">
<FIELD NAME="_id">30</FIELD>
<FIELD NAME="_key">横浜 くりこ庵 浅草店</FIELD>
<FIELD NAME="location">128563246x503268584</FIELD>
</HIT>
<HIT NO="2">
<FIELD NAME="_id">21</FIELD>
<FIELD NAME="_key">たい焼き写楽</FIELD>
<FIELD NAME="location">128581088x503261445</FIELD>
</HIT>
</RESULTSET>
</RESULTPAGE>
</SEGMENT>
</SEGMENTS>

>

浅草周辺には、くりこ庵と写楽があるんですね。それでは、写楽の方に行くことにしましょう。

補足: 実際はブラウザ内の地図表示エリアに表示している範囲にあるレコードを検索するためにgeo_in_rectangle()を使うことが多いでしょう。なぜなら、ほとんどの地図表示エリアは四角だからです。

指定した円の中に含まれている座標を持つレコードを検索

浅草周辺を検索するために四角を指定するのは少し面倒ですね。それよりも、「浅草駅から500m以内にあるたいやき屋」の方がわかりやすいです。

地図を見ると、浅草駅は「35.7119,139.7983」にあります。

groongaにはgeo_in_circle(カラム名, 円の中心の座標, 円の半径)という関数があり、この関数を--filterオプションに指定すると指定した円の範囲内にあるレコードをインデックスを使って高速に検索することができます。

% groonga /tmp/shops/db
> select Shops --filter 'geo_in_circle(location, "35.7119,139.7983", 500)' --output_type xml
<?xml version="1.0" encoding="utf-8"?>
<SEGMENTS>
<SEGMENT>
<RESULTPAGE>
<RESULTSET OFFSET="0" LIMIT="1" NHITS="1">
<HIT NO="1">
<FIELD NAME="_id">30</FIELD>
<FIELD NAME="_key">横浜 くりこ庵 浅草店</FIELD>
<FIELD NAME="location">128563246x503268584</FIELD>
</HIT>
</RESULTSET>
</RESULTPAGE>
</SEGMENT>
</SEGMENTS>

> 

浅草駅の近くには、くりこ庵しかないんですね。それでは、くりこ庵に行くことにしましょう。

座標間の距離を計算

東京駅から2km以内にあるたいやき屋を検索し、それぞれのたいやき屋までの距離も取得しましょう。距離を取得するには_scoreカラムとgeo_distance(カラム名, 基準点の座標)関数を使います。

_scoreカラムは擬似カラムの一種で、検索結果レコードに自動的に追加されているカラムです。通常は検索のヒットスコアを入れるのですが、それ以外の値でも任意の値を入れることができるので、東京駅からの距離を入れることにします。

--scorerオプションを指定することにより_scoreカラムに任意の値を設定できます。ここでgeo_distance()を使い、東京駅からの距離を_scoreカラムに入れます。

実行例（読みやすくするため改行が入っていますが実際は改行を入れてはいけません）:

> select Shops
    --filter 'geo_in_circle(location, "35.68138194,139.766083888889", 2000)'
    --scorer '_score = geo_distance(location, "35.68138194,139.766083888889")'
    --output_columns '_key,_score,*'
    --sortby _score
    --output_type xml
<?xml version="1.0" encoding="utf-8"?>
<SEGMENTS>
<SEGMENT>
<RESULTPAGE>
<RESULTSET OFFSET="0" LIMIT="7" NHITS="7">
<HIT NO="1">
<FIELD NAME="_key">たい焼き鉄次 大丸東京店</FIELD>
<FIELD NAME="_score">230</FIELD>
<FIELD NAME="location">128451283x503166852</FIELD>
</HIT>
<HIT NO="2">
<FIELD NAME="_key">たいやき神田達磨 八重洲店</FIELD>
<FIELD NAME="_score">407</FIELD>
<FIELD NAME="location">128453259x503174156</FIELD>
</HIT>
<HIT NO="3">
<FIELD NAME="_key">銀座 かずや</FIELD>
<FIELD NAME="_score">990</FIELD>
<FIELD NAME="location">128424628x503139222</FIELD>
</HIT>
<HIT NO="4">
<FIELD NAME="_key">にしみや 甘味処</FIELD>
<FIELD NAME="_score">1310</FIELD>
<FIELD NAME="location">128418570x503188660</FIELD>
</HIT>
<HIT NO="5">
<FIELD NAME="_key">しげ田</FIELD>
<FIELD NAME="_score">1606</FIELD>
<FIELD NAME="location">128421453x503208982</FIELD>
</HIT>
<HIT NO="6">
<FIELD NAME="_key">柳屋 たい焼き</FIELD>
<FIELD NAME="_score">1671</FIELD>
<FIELD NAME="location">128467227x503222331</FIELD>
</HIT>
<HIT NO="7">
<FIELD NAME="_key">築地 さのきや</FIELD>
<FIELD NAME="_score">1765</FIELD>
<FIELD NAME="location">128397312x503174595</FIELD>
</HIT>
</RESULTSET>
</RESULTPAGE>
</SEGMENT>
</SEGMENTS>

>

鉄次が一番近いですね。

ある座標からの距離が近い順にレコードをソート

前の例では_scoreに入れた東京駅からの距離でソートしていましたが、このときはインデックスを使いません。インデックスを使ってソートする場合は--sortbyにgeo_distance()関数を指定します。ただし、--sortby内では緯度・経度の区切りに「,」は使えないことに注意してください。--sortbyでgeo_distance()を使うときは、「"#{緯度},#{経度}"」ではなく「"#{緯度}x#{経度}"」というように緯度・経度の区切りには「x」を使ってください。

• ×: --filter 'geo_distance(location, "35.68138194,139.766083888889")'
• ○: --filter 'geo_distance(location, "35.68138194x139.766083888889")'

実行例（読みやすくするため改行が入っていますが実際は改行を入れてはいけません）:

> select Shops
    --filter 'geo_in_circle(location, "35.68138194,139.766083888889", 2000)'
    --sortby 'geo_distance(location, "35.68138194x139.766083888889")'
    --output_type xml
<?xml version="1.0" encoding="utf-8"?>
<SEGMENTS>
<SEGMENT>
<RESULTPAGE>
<RESULTSET OFFSET="0" LIMIT="7" NHITS="7">
<HIT NO="1">
<FIELD NAME="_key">たい焼き鉄次 大丸東京店</FIELD>
<FIELD NAME="location">128451283x503166852</FIELD>
</HIT>
<HIT NO="2">
<FIELD NAME="_key">たいやき神田達磨 八重洲店</FIELD>
<FIELD NAME="location">128453259x503174156</FIELD>
</HIT>
<HIT NO="3">
<FIELD NAME="_key">銀座 かずや</FIELD>
<FIELD NAME="location">128424628x503139222</FIELD>
</HIT>
<HIT NO="4">
<FIELD NAME="_key">にしみや 甘味処</FIELD>
<FIELD NAME="location">128418570x503188660</FIELD>
</HIT>
<HIT NO="5">
<FIELD NAME="_key">しげ田</FIELD>
<FIELD NAME="location">128421453x503208982</FIELD>
</HIT>
<HIT NO="6">
<FIELD NAME="_key">柳屋 たい焼き</FIELD>
<FIELD NAME="location">128467227x503222331</FIELD>
</HIT>
<HIT NO="7">
<FIELD NAME="_key">築地 さのきや</FIELD>
<FIELD NAME="location">128397312x503174595</FIELD>
</HIT>
</RESULTSET>
</RESULTPAGE>
</SEGMENT>
</SEGMENTS>

>

インデックスを使わない場合と同じ結果になっていますね。

データ構造

ここまではユーザ向けの説明でしたが、ここからは実装の説明になります。

groongaでは位置情報を高速に検索するために、GeoHashと同じ考え方で緯度経度をエンコードしてパトリシアトライに格納しています。同じ考え方というのは、緯度と経度の情報を交互に含んだバイト列としてエンコードするという点です。

例えば、東京駅はミリ秒表記では「128452975x503157902」になります。groongaは内部では緯度・経度をミリ秒としてデータを持っていて、それぞれ32bit整数として保持しています。東京駅のデータは2進数で表すと以下のようになります。

何番目のビットか	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
緯度（128452975）	0	0	0	0	0	1	1	1	1	0	1	0	1	0	0	0
経度（503157902）	0	0	0	1	1	1	0	1	1	1	1	1	1	1	0	1
何番目のビットか	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
緯度（128452975）	0	0	0	0	1	0	0	1	0	1	1	0	1	1	1	1
経度（503157902）	1	0	0	1	0	1	0	0	1	0	0	0	1	1	1	0

この緯度・経度データをエンコードして1つのビット列にし、それをパトリシアトライのキーとします。このとき、緯度のビットと経度のビットを交互に使います。

何番目のビットか	0	1	2	3	4	5	6	7	8	9	10	11	12	13	...
エンコードされた緯度・経度データ	0	0	0	0	0	0	0	1	0	1	1	1	1	0	...
緯度の何番目のビットか	0		1		2		3		4		5		6		...
緯度（128452975）	0		0		0		0		0		1		1		...
経度の何番目のビットか		0		1		2		3		4		5		6	...
経度（503157902）		0		0		0		1		1		1		0	...

こうすることにより、先頭の方から2ビットずつデータを読んでいけば緯度情報と経度情報を両方読み込むことができるデータ構造になります。さらに、先頭の方がより粗い位置情報（より広い範囲を表す情報）となっているので、先頭からデータを読み込むことにより徐々に範囲を絞り込んでいけます。

検索方法

では、このデータ構造を使ってどのように効率よく検索するかを説明します。

以下の図は先頭の2ビットだけを読んだ状態の図です。

先頭の2ビットが「00」の場合は右上の赤い範囲を表します。つまり、赤い範囲にあるレコードを検索したい場合は先頭の2ビットが「00」のレコードを検索すればよいことになります。

さらに2ビット読んで先頭の4ビットまで使うことにしたのが以下の図です。

先頭の4ビットが「0000」であれば、右上の範囲の中のさらに左下の赤い範囲にあることがわかります。

このようにして先頭から2ビット単位でデータを読み込むことによりレコードを絞り込むことができます。先頭ビットでレコードを絞り込んでいく部分はパトリシアトライの前方一致検索機能を使います。そのため、位置情報のインデックス用のテーブルはパトリシアトライである必要があります。

geo_in_rectangle()を使った検索

geo_in_rectangle()がどのように検索しているかを説明します。

geo_in_rectangle()は、まず，指定された四角よりも少しだけ大きい範囲を選びます。例えば、黒塗りの四角が指定された場合は赤い縁になっている2つの範囲を選びます。このとき、できるだけ小さい範囲を選ぶようにがんばります。

次に、範囲の中にあるレコードを取り出し、指定された四角の中に本当にレコードが含まれているかを確認します。範囲を少し大きめにとっているため、このチェックをしないと、指定された四角に入っていない（けど近くにある）レコードも検索結果に含めてしまう可能性があるためです。

geo_in_circle()を使った検索

geo_in_circle()も、形が四角ではなく円であるというだけでやっていることはgeo_in_rectangle()とほとんど同じです。違うのはどうやって検索対象とする範囲を選ぶかという部分だけです。

まず、指定された円よりも少しだけ大きい範囲を選びます。例なので、実際の処理よりも大雑把に説明します。以下の図のように黒塗りの円が指定された場合は赤い縁になっている9つの範囲を選びます³。このとき、できるだけ小さい範囲を選ぶようにがんばります。

次に、範囲の中にあるレコードを取り出し、指定された円の中に本当にレコードが含まれているかを確認します。これはgeo_in_rectangle()でもやっている処理と同じです。

まとめ

groongaのドキュメントの位置情報検索についての情報が不足しているため、現状に合わせた内容をまとめました。ここにまとめた内容は後でgroongaのドキュメントに反映させる予定です。

1. このあたりに興味のある人はOpen Geospatial Consortiumのサイトもみるとよいでしょう。 ↩

2. 元々はgroonga本体のテスト用に用意したデータです。 ↩

3. 実際はもっと細かく範囲を分割して、検索範囲をもっと小さくします ↩