Redisで地理情報データベース

4292 ワード
地理情報 CoffeeScript JavaScript Redis JavaScript テキストリンク

また、実コードは後回しだ！

なんか、タスクたまってんなー。忙しくって、しかも移動が多くって、メモ用紙に色々書くのが関の山です。あうう。とは言え、やっぱりアウトプットせねば、と思って追記。

Redisで地理情報。方針としては幾つかあって、PostgreSQLみたいに、R木で管理する方法も有る。外接円木でも良いし、ボロノイでも良いよね。「Redisで木構造」みたいなエントリを書いたのは、実はこのあたりが脳内にちらついていたというのもある。とは言え、密度の高いところとすげえ薄いところがある場合、R木とか外接円木とかだと、最近傍を検索しようとすると変にあちこちアクセスしなきゃいけない感じになる（だから、そういう形式だと、PostgreSQLみたいに、「対象点から半径2km以内のエントリを列挙」みたいなクエリにすることになるが、それだと、アプリケーション側での仕事が多くなる傾向にあって使いにくい）のと、木の再構成のコストが読みづらくて、局所的な更新だけだと性能が維持できないという弱点があるので、全部没。あ、木構造をRedisで扱うってのはそれはそれで価値があるので、ちゃんとやるつもりでいるけどね。

地理情報ってのは、ちょっとしたお遊びでも数100万地点を扱うものとして考えた方が良い。そして、クエリにはそれなりのコストがかかるものと覚悟した方が良いので、並列に実行できた方が良い。Redis向きかというと微妙なところだけど、ひとつひとつのクエリが高速で、きめ細かいコントロールが可能なところはRedis向きだ。

で、私のオリジナル、と言えればかっこいいんだけど、探したら、暖めてたネタと似たネタを考えている人がいたので、一応論文を貼っとく。新規ポイントの追加コストも削除コストもちょい高めだけど、更新の局所性は高くて、そこそこ探索の速いアルゴリズムだ。ざっくり言うと、乱択したDB上の地点を最初のpivotにして、前のpivotより目標点よりの近傍を次々選択して、目標点の方向に向かって辿っていく（そして、その途中に密集があった場合は良い感じによけてくれる：なぜ下記のアルゴリズムで「良い感じによけてくれる」かはそのうち説明する）というアルゴリズムだ。3次元までならこのままで実用になるが、4次元以上の場合はさっき貼った論文を見て欲しい（4次元以上だと方向別に近傍を管理するのはあり得ないので、もっと素朴な方法に頼らざるを得ない）

もちろん、方角の算出と距離の算出は、緯度経度で表すときと、ユークリッド平面としてx,yで表すときでは、関数を挿げ替えて実装すべきだろう。

そしてちなみに、ロック方針は、地点毎のReader-Writer-Lockだ。

なかなか良さげだと思うのは、「点Pから方向θを中線として見込む角α以内の最近傍」みたいな探索ができるのよ、これ。（下の仮想コードでは実現してないけどね）

CoffeeScriptでの実装は、ちょいと待ってね。Ingressでごにょごにょしたい人も、ちょっと待ってくれたまえ。

あとは3way-mergeもnode+redisに実装しときたいんだよな……。そっちはちょっと不慣れなので、問題に合わせたオレ流アルゴリズムを産み出すほどの理解度がないので、ちょっと時間がかかりそう。

MAPNAMEなどの大文字は、変数から構築する動的な値

HSET
  'geo:MAPNAME:conf'
    'initial_random_select': 8
    'dist:average': 計算で求める方法を提供するが、強いない

ZSET
  'geo:MAPNAME:x'
    'POINTID': x座標

ZSET
  'geo:MAPNAME:y'
    'POINTID': y座標

HSET
  'geo:MAPNAME:id'
    'POINTNAME': POINTID

HSET
  'geo:MAPNAME:POINTID:position'
    'name': POINTNAME
    'x':
    'y':

HSET
  'geo:MAPNAME:POINTID:neighbour'
    'maxdist_neighbours': 下記のdistの最大値
    'n1:id': 近さ１位POINTID
    'n1:dist': 上までの距離の2乗
    'n2:id': 近さ２位POINTID
    'n2:dist': 上までの距離の2乗
      以下同様
    'ne1:{id,dist}':
    'ne2:{id,dist}':
    'e1:{id,dist}':
    'e2:{id,dist}':
    'se1:{id,dist}':
    'se2:{id,dist}':
    's1:{id,dist}':
    's2:{id,dist}':
    'sw1:{id,dist}':
    'sw2:{id,dist}':
    'w1:{id,dist}':
    'w2:{id,dist}':
    'nw1:{id,dist}':
    'nw2:{id,dist}':

ZSET
  'geo:MAPNAME:POINTID:neighboured'
    'POINTID': dist

ユーティリティ：ユニーク名なテンポラリ名を生成

ユーティリティ：最近点登録
　AにBを登録問合せ
　　登録すべきなら
　　　Aのneighbourに登録
　　　押し出されたやつのneighbouredを解除
　　　Bのneighbouredに登録
　　　Aのmaxdist_neighbours更新
　　　更新フラグ
　BにAを登録問合せ
　　登録すべきなら
　　　Bのneighbourに登録
　　　押し出されたやつのneighbouredを解除
　　　Aのneighbouredに登録
　　　Bのmaxdist_neighbours更新
　更新フラグ返却

最近傍検出
　ランダムにxがTxからdist:average以内のgeo:MAPNAME:xからランダムに8点選ぶ
　　総勢で8点未満ならdist:averageの2倍を閾値にして繰り返し
　ランダムにyがTyからdist:average以内のgeo:MAPNAME:yからランダムに8点選ぶ
　　総勢で8点未満ならdist:averageの2倍を閾値にして繰り返し
　上記の計16点とTx,Tyとの距離が最小な要素を、pivotとする。
　pivotに関する処理
　　pivotとTx,Tyとの距離がmaxdist_neighboursよりも遠いとき、
　　　pivotのTx,Ty寄りの、4つの8包囲を対象方角とする。
　　　対象方角の第2要素（ないときは第1要素、それでもなければ解無し）とTx,Tyとの距離算出
　　　上記の最小値がpivotとTx,Tyとの距離より小さければ、
　　　　その最小値を持つ要素をpivotにして繰り返し◆◆◆
　　　上記の最小値がpivotとTx,Tyとの距離より小さければ、
　　　　対象方角の第1要素とTx,Tyとの距離算出
　　　　上記の最小値がpivotとTx,Tyとの距離より小さければ、
　　　　　その最小値を持つ要素をpivotにして繰り返し◆◆◆
　　　　上記の最小値がpivotとTx,Tyとの距離より大きければ、
　　　　　pivotが解◆◆◆
　　pivotとTx,Tyとの距離がmaxdist_neighboursよりも近いとき、
　　　対象方角の第2要素からはじめて、第1要素まで、走査しつつTx,Tyとの距離算出
　　　上記の距離がpivotとTx,Tyとの距離より小さければ、
　　　　その点をpivotにして繰り返し◆◆◆
　　　上記の距離がpivotとTx,Tyとの距離より大きければ
　　　　イテレーション
　　　最後まで走査し終えたら、
　　　　pivotが解◆◆◆

1点追加
　ユニークなテンポラリ名を生成し、「候補」「予約」「処理済」の3つのSETを生成
　追加点の最近傍を検出し、候補に登録
　2回繰り返し
　　候補と追加点の距離算出
　　候補のneighbourを走査し、候補でも処理済でなければ予約に登録
　　候補のneighbouredを走査し、候補でも処理済でなければ予約に登録
　　候補を最近点登録
　　候補を処理済に登録（結果付き）
　　予約を候補に格上げ
　候補と追加点の距離算出
　候補を最近点登録
　候補を処理済に登録（結果付き）

1点削除
　削除点のneighbouredを走査し、削除点のneighbourを候補として置き換える

全点分析（地理データベース初期化）
　x,yの最大最小4件ずつ（計高々8点を選択し、相互に最近点登録する。
　あとは、xの小さい順に、1点追加アルゴリズムを適用
Leetcode 27:要素の除去(最も詳細な解決策!!)
C++Prime:関数