空間を抑える　Sketching and streaming algorithms I & II & IIIの前半：ぱらぱらめくるCrash course "Sublinear Algorithms for Big Datasets"

Sketching and streaming algorithms IのPDF、同 II のPDF、同 III の前半のPDF
いきなり「実例」が始まっている…ということは、要するに「こういう課題設定」なら「こういうsublinear algorithmがありますよ」という(ある意味で雑多な)カタログがsublinear algorithm界の現況であって、その中で、理解しやすい例を教えるのが、良い方法(の少なくとも一つ)ということだろうか
Streamと呼ばれるデータ値が値列として与えられる形式における、中央値の区間推定問題が、その第１例として登場している
Count-min sketchと呼ばれるハッシュテーブル(これは全レコードをなめている)をsublinear化したアルゴリズムが続く。これは"the count–min sketch (CM sketch) is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses hash functions to map events to frequencies, but unlike a hash table uses only sub-linear space, at the expense of overcounting some events due to collisions"である、と：(Count-min sketchはこちら)
Stream dataの処理とは、データを渡されるがままに頭から読んで行って、その都度、保持しておくデータをかいつまんで(「かいつまん」で絵にしたものがスケッチ)ためておく処理方法。これをするにあたって、どれくらいのデータ総量になるかもわからない(かもしれない)ので、常に、かいつまみ情報は使って意味がある状況にしておきたいし、どんどん更新できる(データストリームの速さに対応できる速度で)ことが必要。取り出したい情報がどういうものであって、その精度がどの程度であるかに依存して、その方法の設計は変わるし、事前にデータについて知られている情報も有効活用するように設計するのは、もちろん、あり。
次元を落とせば空間は抑えられる。その一環で、 $L_p-norm$ が出てくる。 $||f||_p = \sum_i (f^p)^{\frac{1}{p}}$ 。疎行列のデータ圧縮にも出てくる。