読者です 読者をやめる 読者になる 読者になる

文系プログラマによるTIPSブログ

文系プログラマ脳の私が開発現場で学んだ事やプログラミングのTIPSをまとめています。

【solr】地図検索で超高速にまとめ表示を実現する実装方式【elasticsearch】

solr 位置情報

f:id:treeapps:20140202021002j:plain
一瞬何のことか?と思った方は↑の画像を見て下さい。これです。
位置情報検索を利用して、一定の範囲内に該当するデータが何件あるかをまとめて表示する機能の事です。

この画像ではgoogle map clusterを使った例ですが、clusterを使わず、超高速に位置情報検索を実装する方法を検討してみました。主にsolrとelasticsearchで実現可能かと思います。

google mapを用意する

地図はgoogle mapを使います。
googlemap apiには今表示している地図のboundsを取得する機能があります。
このboundsからnorthEast(北東)とsouthWest(南西)の緯度経度が取得できます。
北東と南西の緯度経度が取れれば、boxの左上・右上・右下・左下の4点の緯度・経度が取得できます

boundsからメッシュを構築する

4点の緯度経度が取れるという事は、メッシュが構築できる事になります。
例えば4点を元に、地図をn分割してみます。
↓こんな感じです。
f:id:treeapps:20140202021732p:plain
見やすいようにマーカー表示してますが、均等なメッシュが構築できています。

メッシュの分割手法

私は算数・数学が苦手なので、以下のように単純な方式しか思いつきません。

まず緯度の大小は、左上(X軸)が大きい値で、左下(X軸)が小さい値になります。
つまり、(左上:緯度 ー 左下:緯度) ÷ n分割 = X軸のメッシュ間距離が求められます。
同様に経度の大小は、右下(Y軸)が大きい値で、左下(Y軸)が小さい値になります。
つまり、(右下:経度 ー 左下:経度) ÷ n分割 = Y軸のメッシュ間距離が求められます。

これでメッシュ間のX軸とY軸の距離が求められたので、後は左上の緯度・経度に、メッシュ間の距離を足していけば、均等にn分割できます。これはサーバサイドでも可能な実装ですね。

本当はもっと高度なやり方があるのかと思いますが、誰にでもできる、凡人にもできる実装方式的にはこんな感じでしょうか。↑のプロットした図はjs側で上記計算式でメッシュ間距離を足し算してプロットしました。

メッシュを1個づつfacetで一括検索する

さあ、各メッシュの4点の緯度・経度は既に解っているので、solrやelasticsearchが得意なfacetで一気に検索しましょう!spatialSearchを使ってもいいし、自前の緯度経度検索でも構いません。1メッシュに対して1facet検索を1回のリクエストで実行し、高速な位置情報検索を魅せつけてやりましょう!

簡単に実装するには、例えば4点の緯度経度を使い、
between 左下(緯度) and 左上(緯度)
and between 左下(経度) and 右下(経度)
という感じで緯度・経度をbetween検索するクエリを、メッシュの数分だけfacet queryとして投げるといいかもしれません。
要は範囲内に含まれるデータを絞り込めれば何でもいいのです。

これで各メッシュ内のデータのヒット件数が取得できたはず。

メッシュの真ん中に件数を表示する

真ん中に表示するのは簡単ですね。
メッシュの緯度の2分の1、経度の2分の1の地点にプロットするだけです。

これをデータが存在する平均位置にプロットしたければ、メッシュ内の緯度経度の平均値を取り、プロットすればできそうですね。その場合、前述のメッシュ検索とは別にプロット位置取得の検索を非同期で投げて取得するといいでしょう。

google mapの表示が検索の始動となる

注意点としては、サーバサイドで検索してからjsで検索済みのデータをプロットする訳ではない点です。
処理フローとしては以下のようになります。

  1. google map表示。
  2. getBoundsでmapの4点を取得。
  3. boundsからnorthEast、southWest取得。
  4. boundsの4点を取得。
  5. メッシュ構築
  6. メッシュをn分割してサーバにリクエスト
  7. 地図をプロット

クライアントサイド側でメッシュを作ってしまうと、サーバサイドへのリクエストパラメータが増えてしまうので、サーバサイド側でメッシュを作るといいと思います。

  1. getBoundsして4点を取得
  2. 4点+縦横のメッシュ分割数パラメータをサーバサイドにリクエスト
  3. サーバサイド側でパラメータを元にメッシュを分割
  4. 分割したメッシュ枚にfacet queryでカウント
  5. プロットする位置+そのポイントの件数をjsonで返す
  6. クライアントサイドでjsonを元にプロットするだけ

というようにすれば、サーバサイドをAPI的に利用できて便利かもしれませんね。

緯度経度を持つデータが用意しにくい!!

以前以下の記事で、住所を元に緯度経度を取得する「ジオコーディング」についての記事を書きました。この記事も以外と人気があったようなので、合わせてご覧下さい。

各種ジオコーディングapiの罠と対処法 - 文系プログラマによるTIPSブログ

雑感

この手法のいいところは、

  • ジオハッシュ等のライブラリに依存しない点。
  • 高度なGeoXXX系を使わないので誰にでも理解できる点。

点です。特にGeoXXX系等の高度なモデルを使えば、より少ないデータでより高度に簡単に検索できる事は知っています。問題なのは、それを理解し保守していける人材が限られる点にあります。「こういうカスタマイズ」をして欲しい、等の要望があった場合、「ライブラリに任せてるので解りませんね」や「内部でやっている処理が難しくて自分には直せそうにありません」、という状況になってしまうのが恐いのですが、それを乗り越えられる人材がいる(居続ける)環境であれば問題有りません。その辺りを考慮し、本記事では「誰にでも理解できて保守・カスタマイズできる手法である」点に重点を置いています。

ちなみにジオハッシュを使う場合、細かくメッシュの分け方を指定しにくい、もしくはできない場合があります。その点この方式は自分でメッシュを構築する必要はありますが、ライブラリの依存無しに実装が可能です。特に、位置情報検索ができないバージョンのsolrを使っている場合にも有効です!!

余談ですが、やっている事はbetween検索とbetween間のデータのcountをしているだけなので、RDBでも実装可能です。countする部分で負荷が掛かってしまいますが、メッシュの数が多くなければギリギリいけるか???と思います。

MarkerClusterer v3 Example
ちなみにgoogle map clusterも大分速い???感じがしますが、データ数が多くなるとどうでしょうね。単純に考えるとjavascriptの算術演算の速度はjavaとは比較にならない程遅いかと思うので、データが少ない時はcluster、多い時は本トピックの方式でいけばよさそうです。

clusterを使ううえで怖いのは、バグや怪しい挙動が有っても追えない・追うのが困難な点にあります。私はclusterを使った事が無いのでどの程度カスタマイズできるか不明ですが、拡張性も不安ですね。

[改訂新版] Apache Solr入門 ~オープンソース全文検索エンジン (Software Design plus)

[改訂新版] Apache Solr入門 ~オープンソース全文検索エンジン (Software Design plus)

Mapion・日本一の地図システムの作り方 (Software Design plus)

Mapion・日本一の地図システムの作り方 (Software Design plus)