algorithm - ~matubara/ChangeLog →移動しました

■ Text algorithms by M. Crochemore and W. Rytter [string][algorithm][book]

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

■ Skewed Binary Search Trees [algorithm][net]

<http://www.brics.dk/~gerth/Papers/esa06skew.pdf>
via okamoto7 先生

平衡しない二分探索木は、平衡した二分探索木より平均深さが深くて、
そのために平均の枝をたどる数が多く、
探索により長い時間がかかる、というのが伝統的な見解。

この論文は、右の子の数と左の子の数を一定比率にした、”一般化平衡二分探索木”のようなものを定義し、
右をたどる時間と左をたどる時間が異なっているとしたときに、最適な子の数の比率が与えられることを示した。

「右にいくのと左にいくのに時間が違うようなことがあるのか」というのが疑問に思われるけれど、
キャッシュミスの比率が違うという説をだし、それを実験的・理論的に示している。

実験設定は、二分探索木を深さ優先探索で線形化（配列化）してやり、
そこにランダムな検索をかける、というもの。

「なんでそれで速くなるんだろうね」「この辺が割と(シーケンシャルな|繰り返しの多い)アクセスをやってるので、キャッシュが効いてるんだと思う」

という議論なら割と自明にキャッシュが効くことが分かるけれど、
このような設定でキャッシュが有効になるのはあまり自明ではない（と思う）し、
標準的な計算モデルにのっとった形で理論的に示し、実験的にも確かめたという点が素晴らしいのではないかと。

↓が分かりやすい。
skewed binary search trees スライド


線形化することのメリットは、今までは、
・平衡していれば、左・右ポインタが不要で必要な領域は1/3
ということだけだったけれど、
これからは、
・平衡から少し偏らせることで、少しだけ速くなるかも
  ただし、左と右が整数比にとれなければ、領域は減らない

■ もっとも近い点を探す [algorithm][ir]

離散値（あるいは有限精度の実数値）の高次元空間を考える。
サイト集合と問い合わせ点が与えられたとき、
問い合わせ点にもっともちかく、サイトのひとつである点を出力せよ。

近さはユークリッド距離で定義する。
ただし、他の距離で高速な手法があればその定義をつかってもいい。

サイト数をN個、次元数をDとすると、
素朴な方法では O(ND) 時間になる。

次元数は1万程度、サイト数は千程度を想定している。
サイト数に関してオーダーNより小さい計算時間が望ましい。

1. 二分探索的な手法
2. 計算幾何で有名な方法があった気がする
3. Z-ordering
4. approximate near neighbor search -- nearest neighbor search を誤差つきにして、誤差内にあるかどうかの決定問題

■ Dynamic programming and board games -- A survey [algorithm][game][net]

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

■ The k-means range algorithm for personalized data clustering in e-commerce [algorithm][net]

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

■ 階層型クラスタリングの性能保証 [algorithm][net]

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

■ Dasgupta, Papadimitriou and Vazirani, "Algorithms" [book][algorithm][net]

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

■ Finding Frequent Items in Data Streams - Charikar, Chen, Farach-Colton (2002) [ir][algorithm][net]

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

■ INSERTION SORT is O(n log n) (ResearchIndex) [algorithm][net]

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

■ Moses Charikar's Home Page [people][math][algorithm][stat][net]

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

この論文では、
数ベクトルのコサイン類似度についてのLSHと
内積が定義されたベクトルのEarth Mover DistanceについてのLSHが構築されている。

これによって得られる近似的な類似度を使って、近似的なNearestNeighbourSearchを高速に行うアルゴリズム

■ Li -- Using Sketches to Estimate Two-way and Multi-way Associations - Google Scholar [math][algorithm][stat][net]

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

■ Bayesian Hierarchical Clustering (2004, ICML) [lm][ir][algorithm][net]

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

■ Katsurada Labo. Text [math][algorithm][book][net]

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

■ SVDPACK [math][algorithm][nlp][net]

<http://www.netlib.org/svdpack/>
潜在意味解析 Latent Semantic Analysis に使う 特異値分解 Singular Value Decomposition のパッケージ。
論文相当の User's guide 付き。

特異値は非正方行列に対して定義される固有値のようなもので、
A trans(A)の固有値の平方根と等しい。
特異値分解は、固有値分解＝直交行列による対角化に対応する。

特異値の大きい方からいくつかだけで特異値分解を近似すると、
次元の圧縮を行うことができる。
そのようなとり方によって、二乗誤差が最小になることが分かっている。

■ Data Clustering -- A Review - Jain, Murty, Flynn (1999) [nlp][algorithm][net]

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

■ Parsing Techniques - Second Edition [algorithm][book][net]

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

■ 岡野原さんによる定数時間検索の解説 [algorithm][net]

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

メモリはCSAでN/2程度、
時間はwavelet tree でO(m)

■ The Personal Page of Gonzalo Navarro [string][people][algorithm][nlp][net]

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

■ Computer Science Special Course (進化計算) [algorithm][net]

<http://www.iba.k.u-tokyo.ac.jp/~iba/CS/>

■ Complexity Zoo - Qwiki [algorithm][net]

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