Sublinear algorithm

• 昨日の記事で色々な「大規模データ対策」の一つにsublinear algorithmという、データをスキャンしながら、全部のレコードを眺め渡すことなしに、答えを返す「軽い」方法のことが出てきた
• 調べてみる
• かいつまんで、かつ網羅的に一目でわかるサイトが見つからないので、役に立ちそうなサイトを列挙することから始める
• ここは、Sublinear argorithm関連の2014年度の講義のサイト。基としているのはMITの講義(Sublinear algorithm)とhttp://sublinear-course.wikispaces.com/:title=ハーバードの講義(Big data)]とだとのこと
  • そこが作っているO(n)という進行系の情報発信サイト （SublinearのO表記）
    • そこに置かれている"Sublinear化課題の一覧(PDF)"
      • 基本的な情報抽出・データマイニングの課題があれもこれも（何でも）Sublinear化できないだろうか、と課題として列挙されている
      • 逆に言えば、Sublinear algorithmというのは、「Sublinearにできるかもしれないから、そういうのを作ろう」という『総体』のことなので、"Sublinear 化されているアルゴリズムのすべて"のことがSublinear algorithmとは何かという問いに対する答えらしい
  • 後続の「ぱらぱらめくるシリーズ」をやりながら見えてきたsublinear algorithmsというのは：
    • 大規模データのデータマイニングでは、コンピュータ(のメモリ)を占拠する空間を小さく抑え、意味のあるデータマイニングプロセスのNP問題的な意味での膨大化を抑える(時間を小さく抑える)という、２つの「小さく抑える」アルゴリズムらしい
    • 空間を抑える方法
      • Streamというやり方は、データレコードを読んでは捨てていく、という「データの流れに乗りながら」の処理のこと。『捨てる』ので空間を抑える方法の一つ
      • Sketchというやり方は、微細写真を撮る代わりに、スケッチを描いて概要をとらえる方法。データマイニング自体が、全データレコードから必要な情報を抽出することなので、それでよい。これも部分情報のみを把持するという意味で空間を抑える方法の一つ
    • 時間を抑える方法