我是如何爱上随机流算法的

在当今的数据经济中，产生的数据量呈指数级增长。最好的估计表明 每天至少产生 2.5 万亿字节的数据 （那是 2.5，后面是惊人的 18 个零！） 参考 .这一步伐只会随着物联网 (IoT) 的发展而加快。

我们如何更有效地表示和建模这种数据流入（流）是关键。数据结构在实现这一目标方面发挥着关键作用，可以大致分为确定性和概率性。

确定性数据结构：

• 大多数典型的数据结构本质上是确定性的。
• 从一个空结构和一系列具有特定键值的插入、查找和删除操作开始，生成的结构将始终完全相同

概率数据结构：

• 在过去的十年中，人们对概率或随机算法和数据结构产生了浓厚的兴趣
• 在概率数据结构中，相同的操作序列通常不会产生相同的结构，这取决于操作过程中产生的随机位序列

随机流算法使用概率数据结构，这是捕获和建模无限的传入流数据集的好方法。

正式的问题定义

给定连续的数据流 D 和一个函数 F， 将数据压缩成数据结构（ DS ) 以允许计算 F 刚刚给出的数据结构。

示例用例：

功能 F： 数数 的数量 清楚的 在德国的 Sound Cloud 上播放的歌曲。

数据流 ：从移动和网络应用程序流式传输的事件和活动。

数据结构 DS： 以压缩形式表示流数据的数据结构（以千字节为单位：））→ HLL（Hyper Log Log）是 DS 之一。

我把自己介绍给了 计数不同 在处理每分钟来自 Wi-Fi 传感器的数百万个传入请求时的流式算法 HLL（Hyper Log Log）。我将在下一篇博客中介绍 HLL。

流的两个关键维度是它的长度 米 和宇宙大小 n 从中绘制流元素。目标是在子空间中处理和建模流 小号 ， 自从 米 和 n 很大 **** 和 **** 趋于无穷大，流式算法的关键要求是使 小号 在 m 和 n 中尽可能小，理想情况下是次线性的。 s = o(min{m, n})

X- Data VS Y- Memory

要实现的圣杯是对数复杂度 O(log(m)+log(n)) 在 p 越过溪流，在哪里 p = 1 - >（一次通过意味着 - 只看到一次数据）

流式算法的另一个非常重要的属性是 可合并性 ，这意味着可以合并多个流模型。我将讨论分布式系统的可合并性概念。

概率 DS 的各种其他应用

谷歌趋势： https://trends.google.com/trends/?geo=DE 使用 重击手 数据结构为我们提供搜索趋势。

许多数据库（例如 REDIS）在内部使用类似的数据结构 Count Min： https://redis.com/blog/count-min-sketch-the-art-and-science-of-estimating-stuff/

随机算法简史

随机算法明确使用随机性来找到目标函数的最优值或优化本身具有随机性的目标函数。

Photo by 爱德华多·苏亚雷斯 on 不飞溅

功能 : A 柜台 C

用例 : 今天我的路由器路由了多少包？

函数支持的操作：

询问 : 返回数字 C

增量 : 将 C 增加 1

简单的解决方案 : 将 C 以 K 位存储在内存中 (log2(C) +1)

挑战： 我们可以将 C 存储在小于 K 位数字的内存中吗？

显而易见的答案是否定的！

NSA 的计算机科学家 Robert H Morris 提出了一种将 C 存储在小于 K 位的内存中的随机方法。

莫里斯的天真想法：

1. 初始化 X = 0
2. 每当 C 增加时，掷硬币（硬币是 p0.5 的公平硬币）
3. 如果硬币只落在正面，则增加 X
4. 我们期望将 X 增加 0.5 倍。

0.5 C = X — — -> C = 2X

X 是 C 的一半，因此与 C 相比，X 可以以更少的位数存储。

缺点 ：

1. 最多我们只节省 1 位
2. 对于较小的 C 值，误差非常高

复杂的莫里斯方法：

我们不掷一枚硬币，但我们掷出多枚硬币并仅在所有硬币都是正面时才增加 X。

我们可以证明 C = (2^X — 1)

参考参考文献中的归纳证明：来自剑桥大学 Nelson 教授的演讲

X = log2 C

如果 C 是 k 位长，则 X 是 log k 位

以上解决了以对数位数表示的缺点。

如果我们用 (1/2^x) = (0.5)^x 增加 X，我们将有很高的方差，相反，如果 X 以概率 (0.99)^x 增加，而用 1^x 增加，那么它是天真的增量，没有方差。

错误 ：

期望(C) = 100(1.01^x — 1)

logk + log (1/e) 数字而不是 ķ 最多方差为的数字 (1+e) .

上述提出的算法得出的结论是，只要稍微牺牲精度，我们就可以在对数尺度上实现内存和速度。

流式算法广泛用于解决以下问题：

1. 计算计数不同
2. 计算分位数、排名、直方图
3. 计算频繁项（Heavy Hitters）
4. 设置操作
5. 采样

我将在连续的博客中讨论每个问题。

我们#Dilax 使用类似的数据结构和算法来摄取和处理大量流式 WiFi 数据。

笔记：

正确的概率数据结构允许您在数据集（数据流）中仅保留部分信息，以换取降低的准确性。当然，在许多情况下（例如银行账户），降低准确性是不可接受的。

但是对于向网站用户推荐电影或展示广告来说，一个相对罕见的错误的成本很低，并且可以节省大量空间。

如果您对处理大量数据和应用高级算法感兴趣，请查看我们的职业页面： https://dilax.com/en/careers ， 我们正在招聘。

参考：

1. https://www.sketchingbigdata.org/fall17/lec/lec1.pdf
2. https://redis.com/blog/count-min-sketch-the-art-and-science-of-estimating-stuff/

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/30256/11501208