在许多计算环境中，使用相同的信息过载是一个问题。例如，跟踪其网络应用程序以识别整体网络健康状况和现场异常或行为变化。然而，事件的规模是巨大的，每个网络元素每小时可能有数万个网络事件。虽然该技术允许将监视事件的大小和粒度增加一个数量级，但处理器、内存和磁盘理解这些事件的能力几乎没有增加。即使规模很小，信息量也可能太大而无法方便地存储。为了应对这一挑战，流数据处理模型变得越来越流行。目的不再是捕获、存储和索引每个事件，而是快速处理每个观察以创建当前状态的摘要。处理完成后，事件将被删除并且无法再访问。这样的处理意味着另一种权衡：对世界的描述是近似的而不是精确的，要回答的问题的性质必须事先确定，所以有些问题是无法解决的。然而，以适度的资源极快地处理大量数据的能力可能会突破数据量的极限。因此，流处理技术得到了很多领域的应用，从电信延伸到搜索引擎、社交网络、金融、时间序列分析领域（比如物联网领域）。数据汇总方法更具成本效益，并且涉及算法技巧、系统知识和数学洞察力的组合。具体方法可能是什么？抽样当面对大量相同的信息需要处理时，可能会有完全忽略它的强烈诱惑。一种有点原则性的做法是忽略多数，即从整个数据集中取一个小样本，对这个子集进行计算，然后尝试外推到整个数据集。为了给出一个好的估计，抽样必须是随机的。抽样方法有很多种，最基本的方法是均匀随机抽样。对于大量数据记录，随机选取少量记录作为样本。然后根据样本回答各种问题，例如，估计有多少百分比的客户在特定城市或购买了特定产品。那么，样本应该有多大才能提供好的结论呢？根据标准的统计结果，对于客户记录这样的抽样问题，大小为s的样本的标准误差与1/s成正比。粗略地说，这意味着当从一个样本中估计一个比例时，误差应该看起来像±1/s。因此，查看具有1000个用户投票的民意调查，误差约为3%，即真实答案在样本结果的3%以内，增加样本量将以可预测的方式减少误差，如果A调查与0.3%的误差范围需要联系100,000个用户。二、样本是如何抽取的？简单地获取前s条记录并不能保证是随机的，因此我们需要确保每条记录都有均等的机会被包含在样本中。这可以通过使用标准随机数生成器来选择要包含在样本中的记录来完成。一个常用的技巧是给每条记录附加一个随机数，然后根据这个随机标记对数据进行排序，得到排好序的前s条记录。只要对整个数据集进行排序的成本不高，这种方法就很有效。最后，添加新数据时如何维护样本？一种简单的方法是针对某些选定的p值以概率p挑选每条记录。当一条新记录进来时，随机选择一个介于0和1之间的分数，如果小于p，则将该记录放入样本中。这种方法的问题是我们事先不知道p应该是什么。在前面的分析中，需要固定的样本量s并使用固定的采样率p。这意味着最初元素太少，添加记录时元素太多。这个问题就像一个算法难题，事实上，多年来它一直是技术面试中的常见问题。一种解决方案是随着新记录的到来逐步调整p。保持采样的一种简单而优雅的方法是采用随机标记的思想。为每条记录附加一个随机标记，并将样本定义为具有最小标记值的s条记录。当有新记录到达时，标签值决定是否将新记录添加到样本中并删除旧记录以保持样本大小固定为s。抽样法很常见，应用实例很多。举个简单的例子，在数据库系统中，为了查询规划，通常需要保存一个大关系的样本。在决定如何执行查询时，评估不同的策略可以估计每个步骤可能发生的数据减少量。另一个例子来自数据集成和链接领域，其中一个子问题是测试来自不同表的两列是否可以与同一组实体相关。全面比较列可能很耗时，特别是如果希望测试所有列对的兼容性，相对较小的样本通常足以确定列是否有可能与同一实体相关。抽样方法如此简单通用，为什么还要用其他方法来汇总数据呢？事实证明，抽样对某些问题不起作用。任何需要详细了解数据中个别记录的问题都无法通过抽样方法解决。这样的问题最终需要记录所有的信息，可以通过高度紧凑的编码来解决。一个更复杂的例子是当问题涉及确定数量基数时，在具有许多不同值的数据集中有多少个某种类型的不同值？例如，在特定的客户数据集中有多少个不同的姓氏？使用样本库不会透露此信息。最后，一些可以估计的样本量，但是对于这些量有更好的汇总方法。对于估计特定属性（如居住城市）等频率问题，可以建立一个大小为s的样本集，保证误差为1/s。这是非常强大的采样保证，只有我们在草图中放置更多空间才能得到改善。本文后面介绍的Count-Min图具有此属性。限制之一是必须在设置草图之前指定感兴趣的属性，而示例允许您评估查询中采样的项目的任何记录属性。假设在100万条记录中的1000条样本中，只有900个姓氏出现在抽样的名字中。关于这些名称在其他数据集中的流行程度，您可以得出什么结论？完整数据集中几乎所有其他名称也是唯一的。或者，示例中的每个唯一名称在剩余数据中重复了数十次或数百次。由于样本信息的存在，这两种情况无法区分，导致两种统计方法的置信区间都很大。跟踪有关基数的信息并省略重复项，可以通过诸如HyperLogLog之类的技术来处理，稍后将对此进行处理。布隆过滤器布隆过滤器是一种紧凑的数据结构，充当一组数据项的摘要。任何计算机科学数据结构类型都有“字典”，例如数组、链表、哈希表和许多平衡树及其变体。这些结构的共同特点是可以回答一个项目是否存储在结构中。布隆过滤器也可以回答像这样的成员资格问题，而且空间效率更高。要理解这个过滤器，考虑一个简单的成员资格问题的精确解是有帮助的。假设你想跟踪一百万个可能的记录中的哪一个，并且每个记录都用一个ID标记，那么你可以保留一个百万位数组，用0初始化。每次记录i时只需将数组中的第i位设置为1被看到。相应地，对记录j的查找查询非常简单，只看第j位是1还是0。结构非常紧凑，如果将位数据放在内存中，125KB就足够了。然而，真实的数据很少有这么好的结构。通常，可能有更大的输入集，例如客户的姓名，其中可能的姓名字符串的数量是巨大的。但是，可以通过借用不同的字典结构来调整位数组方法。假设位数组是一个哈希表，哈希函数h将用于将输入空间映射到表的索引范围。也就是说，给定输入i，现在将键i设置为1。当然，我们会注意散列冲突。这里显然有一个权衡，最初，添加额外的哈希函数可以减少误报的机会，但是，随着越来越多的哈希函数被添加，位数组中的1值越来越多，因此更容易发生冲突.可以从数学上分析这种权衡，假设散列函数看起来是完全随机的，并查看任何元素不在集合中的几率。如果n个不同的项目存储在大小为m的布隆过滤器中，并且使用了k个哈希函数，则成员资格查询获得误报结果的机会大约为exp(kln(1exp(kn/m)))。一些简单的分析表明，可以通过选择k=(m/n)ln2来最小化该比率，即对应于滤波器中大约一半的位为1，一半为0。为了实现这一点，过滤器中的位数应该是其中存储的记录数的几倍。一个常见的设置是m=10n和k=7，这意味着误报率低于1%。请注意，压缩超出信息论限制的数据并不神奇，在这些参数下，布隆过滤器每个条目使用大约10位，并且必须使用与存储的不同条目数量成比例的空间。当表示整数值时，这是一个适度的节省，但是当存储具有大描述符（例如任意字符串，如url）的项目时，这是一个相当大的好处。因为，将这些数据存储在哈希表或平衡搜索树等传统结构中，每个项目会消耗数十或数百字节。当误报的结果不会在计算中引入错误，而只是一些额外的工作，并且不会对系统的整体性能产生不利影响时，布隆过滤器最具吸引力。一个很好的例子来自Web浏览场景，如果用户试图访问已知的恶意站点，Web浏览器通常会警告用户。只需根据“恶意”URL的数据库检查URL就可以做到这一点，但需要数据库足够大，以至于将完整的数据库作为浏览器的一部分很难操作，尤其是在移动设备上。相反，数据库的Bloom过滤器编码可以包含在浏览器中，可以检查每个访问的URL。糟糕的结果只是浏览器可能认为一个无辜的网站在黑名单上，为了处理这个问题，浏览器可以联系数据库并检查列表中的完整URL，以远程数据库查找为代价消除误报。布隆过滤器为大多数URL提供所有信息，并为少数URL造成轻微延迟。这比在浏览器中保留数据库副本并为每个URL进行远程查找的解??决方案要好得多，Chrome和Firefox等浏览器采用了这个概念。布隆过滤器于1970年作为一种紧凑存储字典的方式引入，当时内存非常宝贵。随着计算机内存的增长，它似乎不再需要了。但是随着网络的快速发展，Bloomfilters的应用越来越多，很多大型分布式数据库（Google的Bigtable，Apache的Cassandra，HBase）都使用Bloomfilters作为分布式数据块的索引。他们使用过滤器来跟踪数据库的哪些行或列存储在磁盘上，避免对不存在的属性进行磁盘访问。Count-min也许规范数据聚合问题是最不重要的，一个简单的计数器就足够了，每次观察都会增加。计数器必须具有足够的位深度以说明观察到的事件的大小。当存在不同类型的数据项时，对每种类型进行计数的自然方法是为每个项分配一个计数器。然而，当项目类型的数量极大地增长时会遇到困难，为每个项目类型分配一个计数器可能不切实际，并且当计数器的数量超过存储器的容量时，增加相关计数器的时间成本可能变得令人望而却步。例如，社交网络可能希望跟踪记录在外部网站上显示的频率。有数十亿个网页，原则上每个网页都可以链接到一个或多个记录，因此为每个网页分配一个计数器是不可行的。,也是不必要的。很自然地会找到一种更紧凑的方式来对项目计数进行编码，尽管存在失去某些精度的风险。Count-Min也是一种允许这种权衡的数据结构，将大量记录类型编码在一个小数组中。保证大计数将保持相当准确，而小计数可能会出错。Count-Min由一组计数器和一组将数据项映射到数组的哈希函数组成。乍一看，它很像布隆过滤器，但在细节上有显着差异。准确地说，数组被视为一系列行，每个项目通过第一个哈希函数映射到第一行，通过第二个哈希函数映射到第二行，依此类推，递增计数器。请注意，这与布隆过滤器不同，布隆过滤器允许哈希函数映射到重叠范围。对于给定的数据项，Count-min允许估计其计数：检查第一行中第一个哈希函数映射的项目的计数器，以及第二行计数器中第二个哈希函数映射的项目的计数器，等等。每行都有一个计数器，该计数器在项目每次出现时递增。但是，由于预计会发生冲突，因此计数器也可能映射到同一位置的其他项目。给定一组包含所需计数器和噪声的计数器，将这些计数器中的最小值作为估计值。Count-min还实现了输入数据的紧凑表示，但在准确性上有所折衷。使用布隆过滤器，答案是二元的，因此存在误报的可能性；对于Count-Min，答案是频率，因此存在夸大消光的可能性。Count-Min最适合处理轻微的频率膨胀，不适合可能使用布隆过滤器的情况。如果某个数据项的存在与否非常重要，那么Count-Min引入的不确定性将掩盖这种精确度。但是，count-min非常适合跟踪哪些数据项超过给定的流行度阈值。Count-Min更可压缩，其大小可以认为与输入大小无关，而仅取决于所需的精度保证。自诞生以来，Count-Min在跟踪频率统计的系统中得到了广泛的应用，例如内容在不同人群中的流行度、在线视频在不同用户群中的流行度以及通信网络中的流行节点。网络流量的汇总分布可以检测热点，为网络规划决策提供信息，还可以用于检测流行趋势何时发生变化，作为简单的异常检测。HyperLogLog如何跟踪大量可能性中有多少不同的项目？例如，网站可能希望跟踪有多少不同的人看到了特定的广告。在这种情况下，您不想计算同一用户的多次访问。当项目数量不太大时，保留列表或二进制数组是一种自然的解决方案。当可能的项目数变得非常大时，这些方法所需的空间与被跟踪的项目数成正比。可以希望做得更好吗？HyperLogLog承诺更强大，成本仅取决于计算量的对数。当然，还有缩放常数，这意味着所需的空间并不像标示的那么小，但最终的结果往往只需要几千字节的空间，从而在估算数量上具有很高的准确性。HyperLogLog的本质是使用应用于数据项标识符的哈希函数来确定如何更新计数器，以便对重复项进行相同处理。对每个数据项i应用哈希函数g，该函数g以概率2j将数据项映射到j，例如，采用统一二进制扩展中前导零位的数量。然后可以保留一组位标志，指示到目前为止已获得的j的那些值。这里只需要一个对数位，因为只需要那么多不同的j值。HyperLogLog方法仅保留应用哈希函数时看到的j的最大值，进一步减少了位数。这可能与基数有关，为了减少这种变化，使用第二个哈希函数将项目分组，因此相同的项目总是放在同一组中，并保留有关每个组中最大哈希值的信息。每个组产生估计值，这些估计值全部组合以获得总基数的估计值。该方法是对估计进行平均，使用调和平均数来减少这种影响。算法的分析有点技术性，但是算法在实践中被广泛采用和使用，比如Redis。HyperLogLog的一个典型例子是跟踪在线广告的评级。许多网站和不同的广告每天都会发生数万亿次浏览事件。广告商感兴趣的是有多少不同的人接触过内容。收集和传输这些数据并非不可能，只是相当笨拙，尤其是当人们希望执行更高级的查询时（例如计算有多少唯一身份访问者同时看到两个特定广告）。HyperLogLog能够直接回答此类查询，而不是通过搜索整个数据。近似差异计数在Web系统中也被广泛使用，例如Google的广告系统提供了差异计数作为日志数据分析的原语。总结在处理大型、高维数值数据时，人们通常会寻求在保持数据保真度的同时降低维数。假设已经完成了数据操作和建模的艰苦工作，则可以将数据建模为一个巨大的矩阵，其中每一行都是一个样本点，每一列都对数据的一个属性进行编码。一种常见的技术是应用PCA从数据中提取少量“方向”，沿着这些方向，每一行数据都会产生不同的数据表示形式，从而捕获数据集中的大部分变化。它的局限性在于它需要找到协方差矩阵的特征向量，这对于大矩阵变得不可持续。不要寻找“最佳”方向，而是使用（数量稍大的）随机向量。数据矩阵每一行的随机投影可以看作是数据汇总的一个例子。更直接地说，Count-Min可以看作是各种类型的随机投影，它们是加速高维机器学习方法的基础，例如哈希核函数方法。数据汇总的一个目标是允许对任意复杂度的大量数据进行快速近似结果。一些核心的数学运算可以通过数据汇总的思想来解决，比如随机数值线性代数。一个简单的例子是矩阵乘法：给定两个大矩阵A和B，求它们的乘积AB。数据汇总的一种方法是为A的每一行和B的每一列构建降维数据汇总，提供估计。该领域已解决的问题包括回归。输入是一个高维数据集，建模为矩阵A和列向量b，A的每一行是一个数据点，b对应的entry是该行关联的值，目标是找到最小二乘法的回归系数x。这个问题的精确解是可能的，但时间成本与行数相关，而对矩阵A应用数据汇总可以解决低维空间中的问题。对于图，有一些技术可以汇总每个节点的邻接信息，从而可以提取连通性和生成树信息。对于几何数据，解决聚类等问题的输入可以捕获大量的整体结构信息，通过将聚类合并在一起，还可以保留整体点密度分布的良好特征。通常，简单的方法可以提供准确的答案，但需要保留完整的信息。在许多情况下，近似方法可以更快、更节省空间。布隆过滤器有时被认为是“大数据分析”必须掌握的核心技术之一，总的来说，基于快速数据汇总的技术可以提供不同的权衡。
