アルゴリズム談義 - DO++バイトの人たちとアルゴリズムの話となる。 グラフマイニング。特にGastonについて。 gspanより10倍ぐらい速いらしい。このTech Reportが詳しい 基本的な方針はグラフマイニングで候補部分グラフを少しずつ大きくしていくのだが、そこでもし候補部分グラフがパスや木ならば閉路を含むような複雑なグラフの相同性チェックとかはいらないので簡単なチェックですませてしまおうというQuick Startの方針 skiplistとその拡張について。skiplistはAVLや赤黒木などの平衡木の難しい実装を使わなくても、ランダマイズドアルゴリズムを使うと簡単な実装で平衡木と同じようなことができますよという素敵な話。この方針は木だけでなくほかのいろいろなアルゴリズムに使える。実際にグラフとかへの拡張がすでにやられている。 Cache-Oblivious Algorithmはこの場で初めて聞いた。Re
Christos Faloutsos
http://www.biologie.hu-berlin.de/~gk/events/ibsb2005/
http://www.cse.buffalo.edu/faculty/jianpei/
