背景
うん千万あるレコードをGoogle Map上に表示させたいという話があり、単純にピンを貼ると、ブラウザが重くて動かないくなる。
さあ、どうしよう。
やったこと
Elasticsearchの位置検索（Geolocation）を使って、クラスタリングを行い、重心を取得、それをピンとして表示するということをやりました。
Geometric Hashingを使った検索とは
インデックスはWebやってる方は言わずもがなご存じな仕組みだとは思いますが、データの格納箇所をポインタに保存しておくことで、検索を早くするあれですね。
Geometric Hashingを使った検索というのも、インデックスを使う方法なのですが、インデックスを2DのHash Table(geohash grid)に対して貼り付けて、その中にx,y座標を格納しておくことで、速く、座標を取得する技術です。
※Hash Tableのなかにx, y座標を格納することをGeometric Hashingと言います。
絵にするとこのような形で点座標にグリッドを重ね合わせて、
こんな形でポインタを貼ります。
Geometoryに関する仕組みを提供しているものとして有名どころはこの二つかなと。
- MongoDB
- Elasticsearch
この二つから、Geometric Hashingを使える方法を模索していきます。
MongoDB
MongoDBには様々なインデックスの貼り方が提供されてれいるのですが、その中の一つにgeospatial (地理空間)用のインデックス**があります。
種類は3種類。
- 2Dインデックス
- 2DSphereインデックス
- geoHaystackインデックス。
この3つのインデックスが提供されています。
2Dインデックス
以下のコードは、公式 のサンプルコードそのままですが、[数字、数字]もしくは[lng: 数字、lat: 数字]と言う形で座標を登録し、
db.places.save( {
locs : [ [ 55.5 , 42.3 ] ,
[ -74 , 44.74 ] ,
{ lng : 55.5 , lat : 42.3 } ]
} )
locsフィールドに対して、2dというインデックスを貼る関数を実行するだけです。
```js
db.places.createIndex( { "locs": "2d" } )
```
2DSphereインデックス
実は先に話た2Dインデックスというのはレガシーな仕組みで16bitで値が保存されています。
それに対し、2DSphereインデックスは32bitで値が保存されるため、より巨大な座標系を扱う場合は2DSphereを扱うのがいいかと思います。
こちらはlocフィールドに対して以下のような形で座標を登録し、
db.places.insert(
{
loc : { type: "Point", coordinates: [ -73.97, 40.77 ] },
name: "Central Park",
category : "Parks"
}
)
このような形でインデックスを貼ります。
db.places.createIndex( { loc : "2dsphere" } )
値の取得
一定の範囲内の座標を取得したい場合は、$geoWithinを使い、Polygonを利用して範囲指定をして取得します。
db.places.find( { loc :
{ $geoWithin :
{ $geometry :
{ type : "Polygon" ,
coordinates : [ [
[ 0 , 0 ] ,
[ 3 , 6 ] ,
[ 6 , 1 ] ,
[ 0 , 0 ]
] ]
} } } } )
任意の点から近い座標を取得したい場合は、$nearを使います。
db.<collection>.find( { loc :
{ $near :
{ $geometry :
{ type : "Point" ,
coordinates : [ 12 , 34 ] } ,
$maxDistance : 100
} } } )
GeoJson
このlocの値にtypeやらcoordinatesというkeyが入っているのですが、GeoJsonという形式で保存する必要があるため、このような形になっています。
GeoJsonは点情報であれば、
{ type: "Point", coordinates: [ 40, 5 ] }
線情報であれば、
{ type: "LineString", coordinates: [ [ 40, 5 ], [ 41, 6 ] ] }
という形をとります。
Geometory Hashingを行うような形の検索は…行えなさそうですね。
geoHaystackインデックス
そう、これが、追い求めていた検索ができる用のインデックスなのでしょうか…？
以下のような形でデータをmongoにインサートします。
{ _id : 100, pos: { lng : 126.9, lat : 35.2 } , type : "restaurant"}
{ _id : 200, pos: { lng : 127.5, lat : 36.1 } , type : "restaurant"}
{ _id : 300, pos: { lng : 128.0, lat : 36.7 } , type : "national park"}
それのデータに大して、このような形でgeoHatstackインデックスをはることができます。
db.places.createIndex( { pos : "geoHaystack", type : 1 } ,
{ bucketSize : 1 } )
説明を読んでみると、欲しかったのはこれなのですが、
こうなるもよう。200が2つのバケットに入るようです。
これはこれで便利ですが、今回やりたかったものは、もっとMECEな分割がされたものなので、すこし違うようです。
Elasticsearch
Elasticsearchもmongoと同様にgeospatialなインデックスを持つことができ、mongoよりも多様な検索方法が行えます。
どうやら今回の目的のブツもElasticsearchにあるようです。
座標の検索方法は以下の通り、
1. 円形範囲検索（geo_distance）
2. ドーナツ型範囲検索（geo_distance_range）
3. 四角範囲検索（geo_bound_box）
4. 任意の範囲検索（geo_polygon）
1.はmongoで話した$nearの検索と、4.はmongoで話した$geoWithinの検索と同じですね。
そして、目的のブツであるGeometory Hashingが行える検索方法ですが、
geohash_grid Aggregationというまさしく目的の名前が付いた検索方法があるようです。
参考にしたページはこちら
今回はLaravelで実装する必要があったので、
composerでelasticsearchのライブラリをインストール。
composer require elasticsearch/elasticsearch
インデックスの貼り方はこんな感じで、typeにgeo_pointを指定してやることで、geospatialなインデックスを貼ることができます。
// clientを作成
$client = \Elasticsearch\ClientBuilder::create()->setHosts(\Config::get('elasticquent.config.hosts'))->build();
// index作成用のパラメータを作成
$createParams = [
'index' => 'hoge',
'body' => [
'mappings' => [
'properties' => [
'hogeId' => [
'type' => 'keyword',
],
'location' => [
'type' => 'geo_point',
],
'fuga' => [
'type' => 'nested',
],
];,
],
],
];
// indexを作成
$client->indices()->create($createParams);
こそにデータを登録すると、
$params = [
'index' => $index,
'type' => '_doc',
'id' => $id,
'body' => [
'location' => [
'lon' => 132,
'lat' => 36,
]
],
];
$result = $client->index($params);
このような形でgeohash_gridを指定したクエリをなげることで、grid内の座標を取得することができます。
{
"size": 0,
"aggs": {
"1": {
"geohash_grid": {
"field": "location",
"precision": 5
}
}
}
}
また、geohash_grid毎にaggs（集計）させ、かつ、geo_centroidでaggs(集計)することで、grid内の点の重心を得ることもできました。
詳細はまた、時間があるときにここに追加します。