http://web.njit.edu/~rytter/teaching/texts/book.html 少し古い(1994)文字列アルゴリズムの本。

http://www.brics.dk/~gerth/papers/esa06skew.pdf via okamoto7 先生平衡しない二分探索木は、平衡した二分探索木より平均深さが深くて、 そのために平均の枝をたどる数が多く、 探索により長い時間がかかる、というのが伝統的な見解。この論文は、右の子の…

離散値（あるいは有限精度の実数値）の高次元空間を考える。 サイト集合と問い合わせ点が与えられたとき、 問い合わせ点にもっともちかく、サイトのひとつである点を出力せよ。近さはユークリッド距離で定義する。 ただし、他の距離で高速な手法があればその…

http://www.citeulike.org/user/float/article/917508

http://dx.doi.org/10.1016/j.ejor.2005.04.011 range tree というデータ構造を使うと、 K-means clustering が高速にできるというはなしだとおもうけど、 読んでません。

http://www.cse.ucsd.edu/~dasgupta/papers/hier-jcss.ps Algorithmic statistics の Dasgupta 先生らによる。

http://www.cse.ucsd.edu/~dasgupta/algorithms/ 暗号、線形計画や量子アルゴリズムまで含む教科書。 具体例中心という感じなのかな。

http://citeseer.ist.psu.edu/charikar02finding.html 頻度の近似計算？

http://citeseer.ist.psu.edu/bender04insertion.html 未使用領域つき挿入ソートの挿入が、高い確率で O(n log n)

http://scholar.google.com/scholar?hl=en&lr=&cluster=4804964007952417849 Locality Sensitive Hashing 関連。

http://www.cs.princeton.edu/~moses/ Similarity Estimation Techniques from Rounging Algorithmsなど。 近似アルゴリズムの専門家。 Locality Sensitive Hashing は、 2つのオブジェクトのハッシュ値が一致する確率が、 2つのオブジェクトの類似度と同じ…

http://www.math.meiji.ac.jp/~mk/labo/text/ 線形計算とか、関数解析などのノート、というか本に近い。

http://citeseer.ist.psu.edu/735303.html ボトムアップクラスタリングの距離評価に、 Bayesian なモデルによる確率を使う。

http://www.netlib.org/svdpack/ 潜在意味解析 Latent Semantic Analysis に使う 特異値分解 Singular Value Decomposition のパッケージ。 論文相当の User's guide 付き。特異値は非正方行列に対して定義される固有値のようなもので、 A trans(A)の固有値…

http://citeseer.ist.psu.edu/jain99data.html Clustering のサーベイ。

http://www.cs.vu.nl/~dick/pt2ed.html （プログラミング言語を中心にした）構文解析の本。

http://hillbig.cocolog-nifty.com/do/files/2005-12-compind.pdf Suffix Array を使うと、 4NのメモリとO(log N)の時間で検索ができる …というのはもう古い。メモリはCSAでN/2程度、 時間はwavelet tree でO(m)

http://www.dcc.uchile.cl/~gnavarro/eindex.html 自然言語の全文字列索引付けとか、 あいまい検索とか。

http://qwiki.caltech.edu/wiki/complexity_zoo 計算量クラスの一覧。 PTAS(Polynomial-Time Approximation Scheme)

http://www.iba.k.u-tokyo.ac.jp/~iba/cs/

http://www.gatsby.ucl.ac.uk/~zoubin/icml04-tutorial.html ベイズとMCMCのチュートリアル。

http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/index.html 最小カット、スケジューリング、Voronoi図などのデモ。

http://www.research.ibm.com/journal/rd/501/agarwal.html Differential compression arose as part of the string-to-string correction problem [2], finding the minimum cost of representing one string in terms of another. 問題： 差分圧縮：参照フ…

http://citeseer.ist.psu.edu/neal98view.html EM アルゴリズム。1997年の長めの論文。EM の高速化手法。 The EM Algorithm -- an Old Folk-song Sung to a Fast New Tune

http://www.mdl-research.org/reading.html 新しいチュートリアルがあった。 NEW: P.Gr?nwald, A Tutorial introduction to the minimum description length principle. In: Advances in Minimum Description Length: Theory and Applications (edited by P.…

http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf 素数判定が多項式時間。 via Favorite Theorems Recap

http://theory.lcs.mit.edu/~indyk/ 雑音のあるパターンマッチング。 FFTをツールとして、というのが面白そう。

非自然言語データの上で確率的言語モデルを構築し、圧縮する。 単語分割（WX法）とクラス推定を、教師なし学習により行う。まず、単語の最大長 n を与えた上で、 suffix array の一致数（辞書順ソートでの隣接接尾辞の最長共通接頭辞の長さ）の切り替わりを…

Sparse Suffix Tree とは、Krisztian さんの論文[2005-11-02-1]で紹介されている、 単語単位 Suffix Tree のようなもの。 形式的には、文字列と文字列中でのすべての単語の開始位置（区切り記号の位置 -1）が与えられたとき、 単語の開始位置から始まる suff…