appengine ja night beer talk あらかわ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多次元空間への拡張平面じゃなくて4次元とかでも同じ 4次元の得点空間で、近くの点を探す ≒ 得点が近い人を探す appengine ja night beer talk

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

Presentation on theme: "appengine ja night beer talk あらかわ"— Presentation transcript: