# 流式算法总论：数据流模型、频率矩下界与线性 sketch

DevFeed: [流式算法总论：数据流模型、频率矩下界与线性 sketch](<https://devfeed.tech/articles/sketch-60359.md>)

Original publisher: [Read original article](<https://quant67.com/post/algorithms/36-streaming-algorithms/streaming-algorithms.html>)

Author: Liao Tonglang

Published: 2025-07-15T00:00:00Z

Content type: article

Language: zh

Sources: [土法炼钢 - 系统与基础设施](<https://devfeed.tech/sources/source-4.md>)

Topics: [Time Series](<https://devfeed.tech/topics/time-series.md>), [Temporal data](<https://devfeed.tech/topics/temporal-data.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [ams-sketch](<https://devfeed.tech/tags/ams-sketch.md>), [c](<https://devfeed.tech/tags/c.md>), [communication-complexity](<https://devfeed.tech/tags/communication-complexity.md>), [count](<https://devfeed.tech/tags/count.md>), [count-min-sketch](<https://devfeed.tech/tags/count-min-sketch.md>), [events](<https://devfeed.tech/tags/events.md>), [frequency-moments](<https://devfeed.tech/tags/frequency-moments.md>), [hyperloglog](<https://devfeed.tech/tags/hyperloglog.md>), [i](<https://devfeed.tech/tags/i.md>), [ieee](<https://devfeed.tech/tags/ieee.md>), [linear-sketch](<https://devfeed.tech/tags/linear-sketch.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [mergeable-summaries](<https://devfeed.tech/tags/mergeable-summaries.md>), [minhash](<https://devfeed.tech/tags/minhash.md>), [misra-gries](<https://devfeed.tech/tags/misra-gries.md>), [sketch](<https://devfeed.tech/tags/sketch.md>), [space-saving](<https://devfeed.tech/tags/space-saving.md>), [streaming](<https://devfeed.tech/tags/streaming.md>), [t-digest](<https://devfeed.tech/tags/t-digest.md>), [time-series](<https://devfeed.tech/tags/time-series.md>), [turnstile](<https://devfeed.tech/tags/turnstile.md>)

## AI overview

This article introduces streaming algorithms through the data-stream model, explaining frequency-moment space lower bounds, linear sketch mergeability and deletion support, and the role of randomness and approximation. It also traces the progression from Morris counters to AMS and related sketches, with an empirical discussion of AMS F2 error.

## Source excerpt

一遍扫描、内存远小于数据时能算什么：梳理三种流模型、Morris 到 AMS 与 Indyk 的谱系、通信复杂度下界，实测 AMS F2 sketch 误差随计数器数的变化，说明线性 sketch 为何可合并、可删除，并把本系列 30 到 35 篇串成路线图。