近くを探す? appengine ja night beer talk あらかわ (@ashigeru) テーマ 座標(x, y)に近い点を探す appengine ja night beer talk - @ashigeru 2 App Engineのクエリの特性 1次元のレンジスキャン 1つの値を大小関係で並べて順に取り出すだけ 開始地点は選べる (x, y)とかどう見ても2次元座標 appengine ja night beer talk - @ashigeru 3 方法1: 離散化 座標を一定の幅で区切ってブロックにす る 付近のブロックに含まれているか調べる appengine ja night beer talk - @ashigeru 4 離散化の問題点 濃度によってはダメ 少ない→見つからない, 多い→見つかりすぎ る appengine ja night beer talk - @ashigeru 5 方法2: インメモリフィルタ 2次元目はインメモリで処理する 1次元目は普通にデータストアでやる appengine ja night beer talk - @ashigeru 6 インメモリフィルタの問題点 個数によってはダメ 1次元目の結果が爆発しているかも appengine ja night beer talk - @ashigeru 7 空間充填曲線 (x, y)から遠くに向かってスキャンしたい でも1次元のレンジスキャンしかできない 空間を1本の線で埋め尽くせばスキャンで きる 空間充填曲線 (Space Filling Curve) appengine ja night beer talk - @ashigeru 8 Z曲線 (1) 平面の4点をZで結んでブロックにする むしろN appengine ja night beer talk - @ashigeru 9 Z曲線 (2) ブロック4つをさらにZで結んでブロック にする appengine ja night beer talk - @ashigeru 10 Z曲線 (3) これを繰り返すと平面状のすべての点を 一筆書きできる appengine ja night beer talk - @ashigeru 11 空間充填曲線のスキャン (1) ある点から前後にスキャンする ただし、Z曲線の上でスキャン appengine ja night beer talk - @ashigeru 12 空間充填曲線のスキャン (2) 最初のZになければ、ひとつ大きなZで探 す appengine ja night beer talk - @ashigeru 13 空間充填曲線のスキャン (3) 徐々にZを大きくしていけばいつか見つか る 小→大で探すので、近い順に見つかる appengine ja night beer talk - @ashigeru 14 Z曲線の作り方 (1) それぞれの次元の値を2進数で書く appengine ja night beer talk - @ashigeru 15 Z曲線の作り方 (2) 1ビットずつ取り出して並べ替える appengine ja night beer talk - @ashigeru 16 Z曲線の作り方 (3) これだけ appengine ja night beer talk - @ashigeru 17 多次元空間への拡張 平面じゃなくて4次元とかでも同じ http://tiling.latest.ashigeru-demo.appspot.com/ http://gist.github.com/398695 4次元の得点空間で、近くの点を探す ≒ 得点が近い人を探す appengine ja night beer talk - @ashigeru 18 Z曲線の問題点 アライメントに左右される 隣のZが意外と遠い なので「一番近いものを探す」というのは難 しい 超立方体の構造で探す 1次元だけ極端に値が違ったりすると非常に遠 い 次元数が多すぎると使いにくい appengine ja night beer talk - @ashigeru 19
© Copyright 2024 ExpyDoc
