2013-01-09 ウェーブレット木の世界
- 講演メモ
計算量がデータサイズに対して線形より大きかったら
並列化はほとんど意味がない。
n^3 なら 10000台並べても 10倍にしかならない
→
1. ちゃんとしたアルゴリズム、データ構造、分析手法を使う。
2. それから分散並列化
完備辞書は n+O(n) bit をもちいて rank,select を O(1)時間で実現出来る。
ウェーブレット木
全部入りの根から、代償に応じて二分木に分ける。
そのとき、０、１を右左に対応させて各ノードにラベルを付ける。
ウェーブレット木の高さは log Σ でいいのかな？
「値方向と添え字方向でソートされているデータ構造だ。」
「機械学習、近傍探索さえよければ何でも解けちゃいますね。」
実数値データは、順位空間へ変換する。
異なりがないようにする。
二次元データは、x を固定して、yの値の列とする。
→ 三次元は苦手(方法は存在するけどきれいじゃない)
グラフへの利用
頂点リストをすべてつなげて文字列を作る。
各頂点リストがどこから始まっているかは完備辞書で記録。
ウェーブレット行列 (去年の夏くらいに出た)
ウェーブレット木の問題点は、値の範囲が大きいときにサイズが大きくなってしまう。
1bit目が0であるものを左に、1であるものを右に。
2bit目が0であるものを左に、1であるものを右に。(高速フーリエ変換のシャッフルに似ている)
ウェーブレット木と同じ接点があるが位置は交差している。
完備辞書 rsdic 秒間100万クエリ可能。
fmindex++
グラフの類似検索 gwt
データが加わった場合どうなるか？
ウェーブレット木の場合、末尾に追加された場合は簡単。
現実的に完備辞書の動的更新も可能になってきている。ただ遅くなる。
バイオの方ではBWTはアライメントの標準ツールになっている。
google 日本語入力は簡潔データ構造を作っている。
LOUS
「ディスクに置かなければならない場合は、できるだけアクセスしない方がいいので、
分岐数を増やして深さを減らしてアクセスを減らせばできると思う。」
