Property Testing Reviewという名のウェブサイト！ Testing properties under Lp distances Lp-testing Property testingとdecision Property Testing: Current Research and Surveys (Lecture Notes in Computer Science)作者: Oded Goldreich出版社/メーカ…

Sublinear algorithmに多用されるChernoff boundはランダマイズド・アルゴリズムを用いて確率的にデータマイニングアウトプットをしたときの、そのアウトプットの確度を教えてくれる不等式 それに関する文書はいろいろみつかるけれど、わかりにくかったので…

Sketching and streaming algorithms IのPDF、同 II のPDF、同 III の前半のPDF いきなり「実例」が始まっている…ということは、要するに「こういう課題設定」なら「こういうsublinear algorithmがありますよ」という(ある意味で雑多な)カタログがsublinear …

Markov 不等式 ある確率変数Xの値がt以上になる確率は、Xの期待値をtで割った値以下である # 取りうる値の種類数 n.val <- 10 # 正の確率変数値 v <- sort(runif(n.val)) library(MCMCpack) # 値別の生起確率 p <- rdirichlet(1,rep(1,n.val)) # 期待値 Ex <…

イントロダクションのPDF Big dataを使う例 (1,2,...,n+1)の値のカードがあるときに、バラバラな順番にn枚のカードを見たとする。出ていないカードの値を当てるには、n+1個の値の出た・出ないを全部覚えておく必要はない(覚えておいても良い)。それまでに出…

資料はこちら 構成 イントロダクション Sketching and streaming algorithms I Sketching and streaming algorithms II Sublinear-time algorithms I Sublinear-time algorithms II + Introduction to MapReduce

昨日の記事で色々な「大規模データ対策」の一つにsublinear algorithmという、データをスキャンしながら、全部のレコードを眺め渡すことなしに、答えを返す「軽い」方法のことが出てきた 調べてみる かいつまんで、かつ網羅的に一目でわかるサイトが見つから…

空間と時間とをsublinear化する例のPDF、ビッグデータの検定Lp検定のPDF、グラフ状のデータマイニングの例

Sublinear-time algorithmsのPDF