また、実コードは後回しだ！
なんか、タスクたまってんなー。忙しくって、しかも移動が多くって、メモ用紙に色々書くのが関の山です。あうう。とは言え、やっぱりアウトプットせねば、と思って追記。
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点追加アルゴリズムを適用