串流模型（streaming model）

想像你站在體育場門口，數著並分析一條像河流般、一次一個湧進來的球迷人潮，但你只獲准帶一本小筆記本——小到根本記不下每個人的名字。每個人你只看一次，按順序看，然後他們就走了；你永遠無法回頭再看一眼。串流模型捕捉的正是在這種壓力下的計算：輸入巨大、以「一遍掃過」的序列到來，而你的工作記憶體很小——遠小於資料量，常常只有其大小的多對數（polylog）那麼大。

精確地說，資料是一串項目 x1, x2, ..., xm，你用記憶體 s 一次處理一個，而 s 遠小於 m（想想 s = O((log m)^2) 而 m 是數十億級）。每處理完一個項目，你可以更新你的小摘要，但你不能儲存整串，而且通常只能掃一遍。由於對許多問題的精確回答可證明需要記住太多東西，串流演算法退而求其次，接受近似的、機率性的答案，並使用稱為「草圖（sketch）」的巧妙摘要。反覆出現的招數是：保留一個支援查詢的小型隨機化摘要——例如，要估計你看過多少「相異」項目，你不儲存項目，而是觀察它們的一個基於雜湊的統計量，幾個字組的記憶體就能追蹤它，同時給出不錯的估計。

串流之所以重要，是因為現代資料——網路封包、搜尋查詢、感測器讀數、點擊流——到來的速度與規模超過任何機器所能儲存，所以「全部留著之後再算」根本不可能。這個模型逼出一個尖銳的問題：哪些統計量能在「幾乎沒有記憶體」下被（近似地）算出？答案既出人意料又實用——計數、頻繁項、相異元素、分位數——並支撐著資料庫與網路中的真實系統。誠實的提醒：大多數非平凡的串流結果都是近似且隨機的（在小空間內精確、確定性的答案往往不可能），保證是機率性的（高機率正確，而非確定），而「一遍」是真實的限制——允許多遍能改變可達成的事。