【数据库研究前沿】流批一体与增量视图：Materialize、RisingWave、Feldera 的 DBSP 理论
以 IVM 历史、Differential Dataflow、DBSP（Z-set 与线性化）为主线，对比 Materialize、RisingWave、Feldera 的架构取舍，划清与 Flink/Kafka Streams 的能力边界，并附 Python Z-set 最小增量 join demo
streaming 标签归档
共 6 篇文章 · 返回首页
HyperLogLog：用 12KB 统计十亿基数
如何用仅仅 12KB 的内存估计十亿级别的基数？从 Flajolet-Martin 的直觉到 HyperLogLog 的数学证明，概率数据结构的精妙令人叹服。
流式算法总论：亚线性空间的艺术
当数据以每秒百万条的速度涌来，你只能看一遍且内存有限。流式算法用亚线性空间在这个严苛约束下给出令人惊叹的近似答案。
Count-Min Sketch：流式频率估计的瑞士军刀
在无限数据流中统计每个元素的出现频率，精确计数需要无限内存。Count-Min Sketch 用亚线性空间给出有理论保证的近似答案。
水塘抽样：未知大小数据流的公平抽样
面对一个不知道有多长的数据流，如何保证每个元素被等概率选中？水塘抽样用一个优雅的不变量解决了这个看似不可能的问题。
频率估计的理论极限：Space-Saving 与 Misra-Gries
在无限数据流中找出出现频率最高的元素，只用有限内存能做到多精确？从 Misra-Gries 的消消乐到 Space-Saving 的最优实践。