とりあえず読了。
(ref. [2007-09-13-2])

■徳山豪 / オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ 5 数理技法編)


私の場合こういう教科書は「読了した」といっても「ざっと目を通した」レベルで、証明とかは「あとで理解する」とタグ付けし飛ばし飛ばしなのです。「本の内容の理解」とはほど遠いのです。

第4章の冒頭にこんな記述が。

読み方としては、まずは数式や証明の詳細はスキップして全体のストーリーとアルゴリズムの設計の手法を眺めて、その後で解析の部分の数式をチェックするというのがお奨めである。

ということで、難しいところは「あとで読む」！
今月、来月いっぱいはちょこちょこ見直すことになるかと。

そんなわけですが、アルゴリズムの詳細以外に関しての自分用インデックスだけ載せておきます。一番興味を持って読んだ6章の分のみだけど。

第6章　ストリームアルゴリズム
- オンラインアルゴリズム：過去の履歴はすべて記録しておける。
- ストリームアルゴリズム：過去の履歴は記録できない。
- そろばんでの計算術はストリームアルゴリズムそのもの。
- 誤り許容カウント法(lossy count method)。省メモリで高頻度のものをカウント。これは使える。
- チェビシェフ(Chebyshev)の定理によるランダムサンプリング。省メモリで種類数をカウント。
- スライド窓モデル(sliding window model)・時間窓モデル(time window model)。有効期限切れ最大値問題に使う。マキシマ(maxima)というデータ構造を使う（この問題では時間最新順と値最大順の両方を満たす）。
- マルチパス・ストリームアルゴリズムは本書では対象外だけど少しだけ紹介ということで Apriori アルゴリズムが解説されていた。現場でバリバリ使えそうだ。