appengine ja night beer talk あらかわ (@ashigeru) 近くを探す? appengine ja night beer talk あらかわ (@ashigeru)

appengine ja night beer talk - @ashigeru テーマ 座標(x, y)に近い点を探す appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 1次元のレンジスキャン 1つの値を大小関係で並べて順に取り出すだけ 開始地点は選べる (x, y)とかどう見ても2次元座標 appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 方法1: 離散化 座標を一定の幅で区切ってブロックにする 付近のブロックに含まれているか調べる appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 離散化の問題点 濃度によってはダメ 少ない→見つからない, 多い→見つかりすぎる appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 方法2: インメモリフィルタ 2次元目はインメモリで処理する 1次元目は普通にデータストアでやる appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru インメモリフィルタの問題点 個数によってはダメ 1次元目の結果が爆発しているかも appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 空間充填曲線 (x, y)から遠くに向かってスキャンしたい でも1次元のレンジスキャンしかできない 空間を1本の線で埋め尽くせばスキャンできる 空間充填曲線 (Space Filling Curve) appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線 (1) 平面の4点をZで結んでブロックにする むしろN appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線 (2) ブロック4つをさらにZで結んでブロックにする appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線 (3) これを繰り返すと平面状のすべての点を一筆書きできる appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 空間充填曲線のスキャン (1) ある点から前後にスキャンする ただし、Z曲線の上でスキャン appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 空間充填曲線のスキャン (2) 最初のZになければ、ひとつ大きなZで探す appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 空間充填曲線のスキャン (3) 徐々にZを大きくしていけばいつか見つかる 小→大で探すので、近い順に見つかる appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線の作り方 (1) それぞれの次元の値を2進数で書く appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線の作り方 (2) 1ビットずつ取り出して並べ替える appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線の作り方 (3) これだけ appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru 多次元空間への拡張 平面じゃなくて4次元とかでも同じ http://tiling.latest.ashigeru-demo.appspot.com/ http://gist.github.com/398695 4次元の得点空間で、近くの点を探す ≒ 得点が近い人を探す appengine ja night beer talk - @ashigeru

appengine ja night beer talk - @ashigeru Z曲線の問題点 アライメントに左右される 隣のZが意外と遠い なので「一番近いものを探す」というのは難しい 超立方体の構造で探す 1次元だけ極端に値が違ったりすると非常に遠い 次元数が多すぎると使いにくい appengine ja night beer talk - @ashigeru