PDF数据概要
近似方法通常更快且更有效率。
Graham Cormode
您是否曾感到被无休止的信息流淹没？似乎新邮件和短信的狂轰滥炸需要持续关注，还有电话要接听，文章要阅读，以及敲门声要回应。将这些碎片拼凑起来以追踪重要信息可能是一项真正的挑战。
同样的信息过载也是许多计算环境中关注的问题。例如，电信公司希望跟踪其网络上的活动，以识别整体网络健康状况并发现异常或行为变化。然而，事件发生的规模是巨大的：每个网络元素每小时发生数百万次网络事件。虽然新技术使得被监控事件的规模和粒度能够以数量级增加，但计算元件（处理器、内存和磁盘）理解这些事件的能力却几乎没有增加。即使在小规模上，信息量也可能太大，无法存储在资源匮乏的环境中（例如，嵌入式设备），或无法方便地保存在快速存储中。
为了应对这一挑战，流数据处理模型越来越受欢迎。其目的不再是捕获、存储和索引每一个细微的事件，而是快速处理每个观察结果，以便创建当前状态的摘要。在处理之后，事件被丢弃，不再可访问。保留的摘要通常被称为数据的概要（sketch）。
应对庞大的信息规模意味着需要做出妥协：对世界的描述是近似的而不是精确的；要回答的查询的性质必须提前确定，而不是事后；并且一些问题现在是无法解决的。然而，以适度的资源以惊人的速度处理大量数据的能力，可以弥补这些限制。
因此，流式方法已被许多领域采用，最初是电信领域，后来扩展到搜索引擎、社交网络、金融和时间序列分析。这些想法也正在传统方法使用的领域中找到应用，但在这些领域中，粗略的概要方法更具成本效益。概要的成功应用涉及算法技巧、系统技术和数学洞察力的结合，并在这些领域中的每一个领域都带来了新的研究贡献。
本文介绍了概要背后的思想，重点是算法创新。它在抽象层面上描述了一些算法发展，然后介绍了将它们付诸实践所需的步骤，并附带示例。本文还探讨了四个新颖的算法思想，并讨论了一些新兴领域。
简单采样
当面对大量信息需要处理时，可能会强烈地想要完全忽略它。一种稍微更合乎原则的方法是只忽略大部分——也就是说，从完整数据集中抽取少量示例，对这个子集执行计算，然后尝试推断到完整数据集。为了给出良好的估计，示例必须是随机选择的。这就是采样的领域。
采样有很多变体，但本文使用最基本的：均匀随机采样。考虑大量的客户记录集合。随机选择少量记录即可提供样本。然后，仅通过查看样本即可准确回答各种问题：例如，估计有多少比例的客户居住在某个城市或购买了某种产品。
方法
为了充实这一点，让我们填补一些空白。首先，样本应该有多大才能提供好的答案？根据标准统计结果，对于客户记录示例中的问题，大小为s的样本的标准误差与1/√s成正比。粗略地说，这意味着在从样本中估计比例时，误差预计看起来像±1/√s。因此，查看1,000名选民子集的投票意向会产生一个民意调查，其误差约为百分之三——提供高度的信心（但不是确定性），即真实答案在样本结果的百分之三以内，假设样本是随机抽取的，并且参与者诚实地回答。增加样本的大小会导致误差以可预测的，尽管昂贵的方式减少：将民意调查的误差幅度降低到0.3%将需要联系100,000名选民。
其次，应该如何抽取样本？简单地取前s条记录并不能保证是随机的；数据中可能存在聚类。您需要确保每条记录都有相同的机会被包含在样本中。这可以通过使用标准随机数生成器来选择哪些记录包含在样本中来实现。一个常见的技巧是为每条记录附加一个随机数，然后根据这个随机标签对数据进行排序，并取排序后的前s条记录。这很好用，只要对完整数据集进行排序的成本不太高。
最后，当新项目到达时，您如何维护样本？一种简单的方法是以概率p选择每条记录，对于某个选定的p值。当新记录到达时，选择一个介于0和1之间的随机分数，如果它小于p，则将记录放入样本中。这种方法的问题在于您事先不知道p应该是什么。在之前的分析中，需要固定的样本大小s，而使用固定的采样率p意味着最初元素太少，但随着更多记录的到来，元素又太多了。
以这种方式呈现，这个问题具有算法难题的外观，实际上这在多年的技术面试中是一个常见问题。人们可以想出巧妙的解决方案，随着新记录的到来逐步调整p。维护样本的一种简单而优雅的方法是调整随机标签的思想。为每条记录附加一个随机标签，并将样本定义为标签值最小的s条记录。随着新记录的到来，标签值决定是否将新记录添加到样本中（并删除一个旧项目以保持样本大小固定为s）。
讨论和应用
采样方法非常普遍，以至于有很多例子可以考虑。一个简单的例子是在数据库系统中。数据库管理系统通常会保留大型关系的样本，以用于查询规划。在确定如何执行查询时，评估不同的策略可以提供对每个步骤可能发生多少数据减少的估计，当然，存在一些不确定性。另一个例子来自数据集成和链接领域，其中的一个子问题是测试来自不同表的两列是否可以与同一组实体相关。完整地比较列可能非常耗时，特别是当您想要测试所有列对的兼容性时。比较一个小样本通常足以确定列是否有可能与相同的实体相关。
关于采样的理论和实践，特别是围绕尝试优先采样更重要元素的方案，以减少从样本中估计的误差，已经写了整本书。有关计算视角的良好调查，请参阅海量数据的概要：样本、直方图、小波和概要。11
鉴于采样的简单性和通用性，为什么还需要任何其他方法来汇总数据？事实证明，采样并不适合某些问题。任何需要详细了解数据中单个记录的问题都无法通过采样来回答。例如，如果您想知道某个特定的人是否在您的客户中，那么样本会让您不确定。如果客户不在样本中，您不知道是因为该人不在数据中，还是因为他或她碰巧没有被采样。像这样的问题最终需要记录所有存在信息，并通过高度紧凑的编码（例如布隆过滤器，在下一节中描述）来回答。
一个更复杂的例子是当问题涉及确定数量的基数时：在具有许多不同值的数据集中，某种类型的不同值有多少个？例如，在特定的客户数据集中有多少个不同的姓氏？使用样本无法揭示此信息。假设在100万条记录的样本大小为1,000的样本中，在采样的姓名中只有900个姓氏出现过一次。您能得出关于这些姓名在其余数据集中的受欢迎程度的什么结论？可能是完整数据集中的几乎每个其他姓名也是唯一的。或者可能是样本中每个唯一的姓名在其余数据中重复出现数十次或数百次。使用采样信息，无法区分这两种情况，这导致这些统计数据的置信区间非常大。跟踪关于基数的信息，并省略重复项，可以通过诸如HyperLogLog之类的技术来解决，稍后会介绍。
最后，有些量样本可以估计，但存在更好的专用概要。回想一下，大小为s的样本的标准误差是1/√s。对于诸如估计特定属性（例如居住城市）的频率之类的问题，您可以构建大小为s的概要，以便其保证的误差与1/s成正比。这比采样保证要强得多，并且仅在我们为概要分配更多空间s时才有所改善。本文稍后描述的Count-Min概要具有此属性。一个限制是，感兴趣的属性必须在设置概要之前指定，而样本允许您评估样本项的任何记录属性的查询。
由于其灵活性，采样是构建大型数据集概要的一种强大而自然的方法。有很多不同的采样方法，旨在最大程度地利用样本，或针对样本可能用于回答的不同类型的查询。11下一节将提供有关不太灵活的方法的更多信息，这些方法解决了采样的某些局限性。
使用布隆过滤器汇总集合
布隆过滤器是一种紧凑的数据结构，用于汇总一组项目。任何计算机科学数据结构课程都充斥着“字典”数据结构的示例，例如数组、链表、哈希表以及平衡树结构的许多深奥变体。这些结构的共同特征是它们都可以回答“成员资格问题”，形式为：某个项目是否存储在结构中？布隆过滤器也可以响应此类成员资格问题。但是，该结构给出的答案要么是“该项目肯定没有被存储”，要么是“该项目可能已被存储”。这种对项目状态引入不确定性（可以认为引入了潜在的误报）使得过滤器可以使用比其精确的相对结构小得多的空间量。过滤器也不允许列出已放入其中的项目。相反，您只能针对特定项目提出成员资格问题。
方法
为了理解过滤器，思考成员资格问题的简单精确解决方案是有帮助的。假设您想要跟踪您已经看到的一百万个可能项目中的哪些项目，并且每个项目都方便地标有其ID号（介于一百万和一百万之间的整数）。然后，您可以保留一个包含100万位的数组，全部初始化为0。每次您看到项目i时，只需将数组中的第i位设置为1。项目j的查找查询也相应地很简单：只需查看位j是1还是0。该结构非常紧凑：如果您将这些位打包到内存中，则125 KB就足够了。
但是，真实数据很少有如此好的结构。通常，您可能有更大的可能输入集——再次考虑客户姓名，其中可能的姓名字符串的数量是巨大的。您仍然可以通过借鉴不同的字典结构来调整您的位数组方法。想象一下，位数组是一个哈希表：您将使用哈希函数h将输入空间映射到表的索引范围。也就是说，给定输入i，您现在将位h(i)设置为1。当然，现在您必须担心哈希冲突，其中多个条目可能映射到相同的位。传统的哈希表可以处理这个问题，因为您可以保留关于表中条目的信息。但是，如果您坚持自己的想法，并且只在位数组中保留位，则会导致误报：如果您查找项目i，则可能是条目h(i)设置为1，但i尚未见过；相反，存在某个项目j被见过，其中h(i) = h(j)。
您可以在坚持使用位数组的同时修复此问题吗？不能完全修复，但您可以使其不太可能发生。与其仅使用单个哈希函数对每个项目i进行一次哈希处理，不如使用k个哈希函数h1, h2, ... hk的集合，并依次使用每个哈希函数映射i。所有对应于h1(i), h2(i) ... hk(i) 的位都被设置为1。现在要测试j的成员资格，请检查它哈希到的所有条目，如果其中任何一个为0，则说否。
这里显然存在一个权衡：最初，添加额外的哈希函数会降低误报的可能性，因为需要更多的事情“出错”才能给出错误的答案。但是，随着添加的哈希函数越来越多，位数组中填充的1值越来越多，因此冲突的可能性也更大。可以对这种权衡进行数学分析，并找到最小化误报机会的最佳点。分析的工作原理是假设哈希函数看起来完全是随机的（这在实践中是一个合理的假设），并通过查看集合中任意元素未被报告为存在的机会。
如果n个不同的项目存储在大小为m的布隆过滤器中，并且使用了k个哈希函数，则应该收到否定答案的成员资格查询产生误报的机会大约为exp(k ln(1 exp(kn/m)))。4虽然短期内对这个表达式进行广泛研究可能没有回报，但一些简单的分析表明，通过选择k = (m/n) ln 2可以将此速率最小化。这对应于过滤器中大约一半的位为1，一半为0的情况。
为了使之有效，过滤器中的位数应为您期望存储在其中的项目数的某个倍数。一个常见的设置是m = 10n和k = 7，这意味着误报率低于百分之一。请注意，这里没有可以压缩数据超出信息论极限的魔力：在这些参数下，布隆过滤器每个项目使用大约10位，并且必须使用与存储的不同项目数成正比的空间。当表示整数值时，这节省了适度的空间，但是当存储的项目具有大量描述时（例如，任意字符串，如URL），这是一个相当大的好处。将它们存储在传统结构（如哈希表或平衡搜索树）中，每个项目将消耗数十或数百个字节。图1显示了一个简单的示例，其中项目i通过k = 3个哈希函数映射到大小为m = 12的过滤器，并且这些条目被设置为1。
讨论和应用
需要仔细处理误报的可能性。当误报的后果不是在计算中引入错误，而是导致一些额外的工作，而这些工作不会对系统的整体性能产生不利影响时，布隆过滤器最具有吸引力。一个很好的例子来自浏览网络的背景。现在，Web浏览器通常会在用户尝试访问已知托管恶意软件的站点时向用户发出警告。这是通过针对“坏”URL数据库检查URL来完成的。数据库足够大，URL也足够长，以至于将完整数据库作为浏览器的一部分保留会很笨拙，尤其是在移动设备上。
相反，可以将数据库的布隆过滤器编码包含在浏览器中，并且可以针对它检查访问的每个URL。误报的后果是浏览器可能认为一个无辜的站点在坏列表中。为了处理这个问题，浏览器可以联系数据库权威机构并检查完整URL是否在列表中。因此，误报被消除，但代价是远程数据库查找。
请注意布隆过滤器的效果：它为大多数URL发出全部清除信号，并且仅对一小部分（或当访问坏URL时）产生轻微的延迟。这比在浏览器中保留数据库副本的解决方案以及对访问的每个URL执行远程查找的解决方案都更可取。诸如Chrome和Firefox之类的浏览器已采用此概念。当前版本的Chrome使用基于更直接地编码哈希URL列表的布隆过滤器的变体，因为本地副本不必动态更新，并且可以节省更多空间。
布隆过滤器于1970年被引入，作为在空间非常宝贵时存储字典的一种紧凑方法。3随着计算机内存的增长，似乎不再需要过滤器了。但是，随着Web的快速增长，自本世纪初以来，已经为过滤器设计了许多应用程序。4这些应用程序中的许多应用程序都具有上述示例的味道：过滤器为查找查询提供了快速答案，并且可以在权威参考中对肯定答案进行双重检查。
布隆过滤器已被广泛用于避免在缓存中存储不受欢迎的项目。这强制执行了仅当项目以前被看到时才将其添加到缓存的规则。布隆过滤器用于紧凑地表示已看到的项目集。误报的后果是，一小部分罕见项目也可能存储在缓存中，这与规则的字面意思相矛盾。许多大型分布式数据库（Google的Bigtable，Apache的Cassandra和HBase）使用布隆过滤器作为分布式数据块的索引。它们使用过滤器来跟踪数据库的哪些行或列存储在磁盘上，从而避免了对不存在的属性进行（昂贵的）磁盘访问。
使用Count-Min概要进行计数
也许规范的数据汇总问题是最简单的：要计算已观察到的某种类型的项目数，您不需要保留每个项目。相反，一个简单的计数器就足够了，每次观察都会递增。计数器必须具有足够的位深度才能应对观察到的事件量级。当事件数量变得非常巨大时，可以使用诸如Robert Morris的近似计数器之类的想法，以更少的位提供这样的计数器12（概要的另一个示例）。
当存在不同类型的项目，并且您想要对每种类型进行计数时，自然的方法是为每个项目分配一个计数器。但是，当项目类型的数量变得巨大时，您会遇到困难。为每种项目类型分配计数器可能不切实际。即使是这样，当计数器的数量超过快速内存的容量时，递增相关计数器的时间成本可能会变得太高。例如，诸如Twitter之类的社交网络可能希望跟踪通过外部网站显示推文的观看次数。有数十亿个网页，每个网页原则上都可以链接到一个或多个推文，因此为每个推文分配计数器是不可行且不必要的。相反，自然而然地寻找一种更紧凑的方式来编码项目的计数，可能带有一些可容忍的保真度损失。
Count-Min概要是一种数据结构，可以实现这种权衡。它在一个小型数组中编码了潜在的大量项目类型。保证是大型计数将被相当准确地保留，而小型计数可能会产生更大的（相对）误差。这意味着它适用于您对分布的头部感兴趣的应用，而不太适用于其尾部。
方法
乍一看，概要看起来很像布隆过滤器，因为它涉及使用数组和一组哈希函数。但是，细节上存在显着差异。概要由计数器数组和一组将项目映射到数组中的哈希函数形成。更准确地说，数组被视为一系列行，并且每个项目通过第一个哈希函数映射到第一行，通过第二个哈希函数映射到第二行，依此类推（请注意，这与布隆过滤器形成对比，布隆过滤器允许哈希函数映射到重叠的范围）。通过将项目依次映射到每一行（通过相应的哈希函数）并递增其映射到的计数器来处理项目。
给定一个项目，概要允许估计其计数。这遵循与处理更新类似的轮廓：检查第一行中项目被第一个哈希函数映射到的计数器，以及第二行中项目被第二个哈希映射到的计数器，依此类推。每一行都有一个计数器，该计数器已通过该项目的每次出现而递增。但是，该计数器也可能被映射到同一位置的其他项目的出现而递增，因为预计会发生冲突。给定包含所需计数以及噪声的计数器集合，对所需项目的真实计数的最佳猜测是将这些计数器中的最小值作为您的估计。
图2显示了更新过程：项目i通过哈希函数hj映射到每一行j中的一个条目，并将c的更新添加到每个条目。它也可以看作是对查询过程进行建模：对同一项目i的查询将导致探测相同的位置集，并将最小值作为答案返回。
讨论和应用
与布隆过滤器一样，概要实现了输入的紧凑表示，并在准确性方面进行了权衡。两者都提供了一些不满意答案的可能性。对于布隆过滤器，答案是二进制的，因此存在误报响应的一些机会；对于Count-Min概要，答案是频率，因此存在答案被夸大的一些机会。
起初可能令人惊讶的是，获得的估计非常好。从数学上讲，可以证明返回的估计值很有可能接近正确的值。估计的质量取决于概要中的行数（每增加一行，坏估计的概率减半）和列数（列数加倍，估计中噪声的规模减半）。这些保证来自哈希函数的随机选择，并且不依赖于正在汇总的数据分布中的任何结构或模式。对于大小为s的概要，误差与1/s成正比。如前所述，这比采样的情况有所改进，在采样中，相应的行为与1/√s成正比。
正如布隆过滤器最适合于可以容忍和减轻误报的情况一样，Count-Min概要最适合于处理频率的轻微膨胀。这意味着，特别是，它们不适用于可能使用布隆过滤器的情况：如果项目是否已被看到很重要，那么Count-Min概要引入的不确定性将掩盖这种精度的水平。但是，概要非常适合跟踪哪些项目超过给定的受欢迎程度阈值。特别是，虽然布隆过滤器的大小必须与它表示的输入大小保持成比例，但Count-Min概要可以更具压缩性：它的大小可以被认为与输入大小无关，而仅取决于所需的准确性保证（即，为了实现目标精度ε，固定与1/ε成正比的概要大小s，该大小在处理数据过程中不会变化）。
之前提到的Twitter场景就是一个很好的例子。跟踪推文在不同网站的每次出现中所获得的观看次数，会产生大量数据，难以管理。此外，在这种应用中存在一些不确定性似乎是可以接受的：夸大一个网站对一条推文的受欢迎程度的后果是最小的。为每条推文使用概要仅消耗比推文和相关元数据略多的空间，并且可以跟踪哪些场所最吸引该推文的关注。因此，大约一千字节的空间足以跟踪来自不同位置的观看百分比，误差小于一个百分点，例如。
自从十多年前引入以来，7 Count-Min概要已在跟踪频率统计的系统中找到应用，例如不同组内容（例如，不同用户集中的在线视频）的受欢迎程度，或通信网络中节点的热门目的地。概要用于电信网络中，在电信网络中，沿着链路传递的数据量是巨大的，并且永远不会存储。汇总网络流量分布可以检测热点，从而为网络规划决策提供信息，并允许检测和调试配置错误和洪泛。6由于概要紧凑地编码了频率分布，因此它也可以用于检测何时发生受欢迎程度的变化，作为异常检测的一个简单示例。
使用HyperLogLog计数不同项目
另一个基本问题是跟踪在大量可能性中已经看到了多少不同的项目。例如，Web发布者可能想要跟踪有多少不同的人接触过特定广告。在这种情况下，您不希望将同一查看者计算多次。当可能的项目数量不是太大时，保留列表或二进制数组是一种自然解决方案。随着可能的项目数量变得非常大，这些方法所需的空间与跟踪的项目数量成正比。切换到近似方法（如布隆过滤器）意味着空间仍然与不同项目的数量成正比，尽管常数得到了改进。
您能希望做得更好吗？如果您只是计算了项目总数，而没有删除重复项，那么一个简单的计数器就足够了，使用的位数与遇到的项目数的对数成正比。如果只有一种方法可以知道哪些项目是新的，并且只计算这些项目，那么您就可以实现此成本。
HLL（HyperLogLog）算法承诺了更强大的功能：成本只需要取决于计算数量的对数的对数。当然，有一些缩放常数意味着所需的空间并不像这可能暗示的那样小，但最终结果是，可以使用几千字节的空间以高精度（例如，高达百分之一或百分之二的误差）来估计数量。
方法
此方法的本质是使用应用于项目标识符的哈希函数来确定如何更新计数器，以便将重复项目同等对待。布隆过滤器具有类似的属性：尝试插入已在布隆过滤器中表示的项目意味着将许多已经记录为1的值的位设置为1。一种方法是保留布隆过滤器并查看最终的1和0密度，以估计所表示的不同项目的数量（考虑到哈希函数下的冲突）。这仍然需要与项目数量成正比的空间，并且是早期解决此问题的方法的基础。15
为了打破这种线性关系，需要一种不同的构建二进制计数器的方法。您可以不为每个项目将计数器加1，而是以二分之一的概率加1，以四分之一的概率加2，以八分之一的概率加4，依此类推。这种随机性的使用降低了计数器的可靠性，但是您可以检查预期计数是否与遇到的项目真实数量相对应。当使用哈希函数时，这更有意义。将哈希函数g应用于每个项目i，并具有相同的分布：g以概率2−j将项目映射到j（例如，通过取统一哈希值的二进制扩展中前导零位的数量）。然后，您可以保留一组位，指示到目前为止已看到的j值。这是早期Flajolet-Martin方法跟踪不同项目数量的本质。8这里需要对数数量的位，因为预计只有这么多不同的j值。
HLL方法通过仅保留应用哈希函数时已看到的最高j值来进一步减少位数。这可能与基数相关，尽管变化很大，例如，可能只看到一个项目，该项目恰好哈希到一个很大的值。为了减少这种变化，使用第二个哈希函数将项目划分为组（因此，同一项目始终放置在同一组中），并保留有关每个组中最大哈希的信息。每个组产生对局部基数的估计；所有这些组合起来以获得对总基数的估计。
首先要做的努力是取估计值的平均值，但这仍然允许一个大的估计值扭曲结果；相反，使用调和平均值来减少这种影响。通过哈希到s个单独的组，标准误差与1/√s成正比。图3显示了一个小例子。该图显示了一个小的示例HLL概要，其中包含s = 3个组。考虑五个不同的项目a, b, c, d, e及其相关的哈希值。由此，获得以下数组
| 3 | 2 | 1 |
该估计值是通过将 2 提升为数组中每个条目的幂，并计算这些值的倒数之和而获得的，在本例中得到 1/8 + 1/4 + 1/2 = 7/8。最终的估计值是通过将 αss2 乘以该总和的倒数来计算的。这里，αs 是一个取决于 s 的比例常数。α3 = 0.5305，因此得到的估计值为 5.46，接近真值 5。
该算法的分析相当技术性，但证明在于部署：该算法已被广泛采用并应用于实践中。
讨论和应用
HLL 的一个应用示例是在线广告的观看人数跟踪。在许多网站和不同的广告中，每天可能会发生数万亿次的观看事件。广告商对“独立用户数”感兴趣：有多少不同的用户（或者更确切地说，是浏览设备）接触过该内容。收集和整理这些数据并非不可行，而是非常繁琐，特别是如果希望进行更高级的查询（例如，计算有多少独立用户同时看到了两个特定的广告）。使用 HyperLogLog 草图可以直接通过组合两个草图而不是遍历完整数据来回答这种查询。草图已用于此目的，其中使用随机性带来的少量不确定性与其他误差来源（如数据丢失或测量失败）相当。
近似去重计数也广泛应用于网络规模系统的幕后。例如，谷歌的 Sawzall 系统提供了各种草图，包括去重计数，作为日志数据分析的原语。13 谷歌工程师描述了为确保 HLL 在所有可能的基数范围内都具有高精度而进行的一些实现修改。10
去重计数的最后一个有趣的应用是在社交网络分析的背景下。2016 年，Facebook 着手测试其社交网络中的“六度分隔”理论。Facebook 友谊图非常庞大（超过十亿个节点和数千亿条边），为每个用户维护关于长距离连接分布的详细信息是不可行的。本质上，问题是为每个用户计算他们在距离 1、2、3 等处有多少朋友。这本应是一个简单的图探索问题，但距离 2 的一些朋友可以通过多条路径（通过不同的共同朋友）到达。因此，去重计数用于生成关于可达性的准确统计数据，而无需重复计数，并提供准确的距离分布（Facebook 图中估计的分隔度数为 3.57）。2
高级草图技术
粗略地说，本文描述的四个草图示例涵盖了当前数据摘要模型的绝大多数实际应用。然而，毫不奇怪的是，存在大量关于这些想法的新应用和变体的研究。就在眼前的是大量新的数据摘要技术，这些技术正处于实际应用的风口浪尖。本节提到了一些看起来最有希望的方向。
用于降维的草图技术
在处理大型高维数值数据时，通常会寻求在保持数据保真度的同时降低维度。假设数据整理和建模的繁重工作已经完成，并且可以将数据建模为一个巨大的矩阵，其中每一行是一个示例点，每一列编码数据的一个属性。一种常见的技术是应用 PCA（主成分分析）从数据中提取少量“方向”。将数据的每一行沿着这些方向投影，可以得到数据的不同表示，从而捕获数据集的大部分变化。
PCA 的一个局限性在于，找到方向需要大量的工作。它需要找到协方差矩阵的特征向量，这对于大型矩阵来说很快变得难以维持。随机投影的竞争方法认为，与其找到“最佳”方向，不如使用（稍微多一些的）随机向量就足够了。选择适量的随机方向可以捕获相当数量的变化，同时需要的计算量要少得多。
数据矩阵的每一行的随机投影可以被视为数据草图的一个示例。更直接地说，随机投影与前面描述的草图之间存在密切的联系。Count-Min 草图可以被视为某种随机投影；此外，用于降维的随机投影的最佳构造看起来很像 Count-Min 草图，但有一些变化（例如，将矩阵的每一列随机乘以 -1 或 1）。这是加速高维机器学习方法的基础，例如 Hash Kernels 方法。14
随机数值线性代数
草图技术的一个宏伟目标是允许通过草图近似且快速地回答对大量数据进行的任意复杂数学运算。虽然这个目标看起来还很遥远，并且由于一些不可能的结果而可能不可行，但许多核心数学运算可以使用草图技术来解决，这引出了随机数值线性代数的概念。一个简单的例子是矩阵乘法：给定两个大型矩阵 A 和 B，您想要找到它们的乘积 AB。使用草图技术的一种方法是构建 A 的每一行和 B 的每一列的降维草图。组合每一对草图可以为乘积的每个条目提供估计值。与其他示例类似，小答案无法很好地保留，但可以准确找到大条目。
在这个领域中已解决的其他问题包括回归。这里的输入是一个高维数据集，建模为矩阵 A 和列向量 b：A 的每一行是一个数据点，b 的对应条目是与该行关联的值。目标是找到回归系数 x，使 ‖Ax-b‖2 最小化。这个问题的精确解是可能的，但就作为行数的函数的时间而言，成本很高。相反，将草图技术应用于矩阵 A 可以在较低维度的草图空间中解决问题。5 David Woodruff 提供了对该领域最新技术的全面数学调查。16
丰富数据：图和几何
到目前为止，草图技术的应用可以被视为总结可能被认为是高维向量或矩阵的数据。这些数学抽象概括了大量情况，但是，越来越需要更丰富的数据模型——例如，对社交网络中的链接进行建模（最好将其视为图），或测量移动用户的移动模式（最好将其视为平面或 3D 中的点）。草图技术也已应用于此。
对于图，有一些技术可以总结每个节点的邻接信息，以便可以提取连通性和生成树信息。1 这些方法提供了一个令人惊讶的数学见解，即可以压缩大量边数据，同时保留关于图结构的基本信息。这些技术尚未在实践中得到广泛应用，可能是因为编码大小的开销很高。
对于几何数据，人们对解决诸如聚类等问题非常感兴趣。9 这里的关键思想是，输入的一部分聚类可以捕获大量的整体结构信息，通过将聚类合并在一起（聚类聚类），您可以保留整体点密度分布的良好图像。
您为什么要关心？
本文的目的是介绍一些最新的技术，这些技术为数据分析和操作中经常出现的一些一般性问题提供了近似答案。在所有情况下，简单的替代方法都可以提供精确的答案，但代价是保留完整的信息。然而，此处显示的示例说明，在许多情况下，近似方法可以更快且更节省空间。这些方法的使用正在增长。Bloom 过滤器有时被称为“大数据专家”必须掌握的核心技术之一。至少，重要的是要了解草图技术，以测试声称以某种方式解决问题是唯一选择的说法。通常，快速的基于草图的近似技术可以提供不同的权衡。
参考文献
1. Ahn, K. J., Guha, S., McGregor, A. 2012. Analyzing graph structure via linear measurements. In -SIAM Symposium on Discrete Algorithms.
2. Bhagat, S., Burke, M., Diuk, C., Filiz, I. O., Edunov, S. 2016. Three and a half degrees of separation. Facebook Research; https://research.fb.com/three-and-a-half-degrees-of-separation/.
3. Bloom, B. 1970. Space/time trade-offs in hash coding with allowable errors. Communications of the 13(7): 422-426.
4. Broder, M., Mitzenmacher, A. 2005. Network applications of Bloom filters: a survey. Internet Mathematics 1(4): 485-509.
5. Clarkson, K. L., Woodruff, D. P. 2013. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing: 81-90.
6. Cormode, G., Korn, F., Muthukrishnan, S., Johnson, T., Spatscheck, O., Srivastava, D. 2004. Holistic UDAFs at streaming speeds. In SIGMOD International Conference on Management of Data: 35-46.
7. Cormode, G., Muthukrishnan, S. 2005. An improved data stream summary: the Count-Min sketch and its applications. Journal of Algorithms 55(1): 58-75.
8. Flajolet, P., Martin, G. N. 1985. Probabilistic counting. In IEEE Conference on Foundations of Computer Science: 76-82. Journal version in Journal of Computer and System Sciences 31: 182-209.
9. Guha, S., Mishra, N., Motwani, R., O'Callaghan, L. 2000. Clustering data streams. In IEEE Conference on Foundations of Computer Science.
10. Heule, S., Nunkesser, M., Hall, A. 2013. HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. In International Conference on Extending Database Technology.
11. Jermaine, C. 2012. Sampling techniques for massive data. In Synopses for massive data: samples, histograms, wavelets and sketches, ed. G. Cormode, M. Garofalakis, P. Haas, and C. Jermaine. Foundations and Trends in Databases 4(1-3). NOW Publishers.
12. Morris, R. 1977. Counting large numbers of events in small registers. Communications of the 21(10): 840-842.
13. Pike, R., Dorward, S., Griesemer, R., Quinlan, S. 2005. Interpreting the data: parallel analysis with Sawzall. Dynamic Grids and Worldwide Computing 13(4): 277-298.
14. Weinberger, K. Q., Dasgupta, A., Langford, J., Smola, A. J., Attenberg, J. 2009. Feature hashing for large-scale multitask learning. In International Conference on Machine Learning.
15. Whang, K. Y., Vander-Zanden, B. T., Taylor, H. M. 1990. A linear-time probabilistic counting algorithm for database applications. Transactions on Database Systems 15(2): 208.
16. Woodruff, D. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science 10(1-2): 1-157.
相关文章
它可能有效
概率算法在我们周围无处不在。它们不仅可以接受，而且一些程序员实际上还在寻找使用它们的机会。
Tyler McMullen, Fastly
https://queue.org.cn/detail.cfm?id=2855183
工程师统计学
将统计技术应用于运营数据
Heinrich Hartmann
https://queue.org.cn/detail.cfm?id=2903468
Graham Cormode 是英国华威大学的计算机科学教授。此前，他曾在贝尔实验室和 AT&T 从事数据管理算法的研究。他因其在数据分析方面的工作获得了 2017 年亚当斯奖。
版权所有 © 2017 归所有者/作者所有。出版权已许可给 。
最初发表于 Queue vol. 15, no. 2—
在 数字图书馆 中评论本文
更多相关文章
Qian Li, Peter Kraft - 事务和无服务器是天作之合
数据库支持的应用程序是无服务器计算的一个令人兴奋的新领域。通过紧密集成应用程序执行和数据管理，事务性无服务器平台实现了许多在现有无服务器平台或基于服务器的部署中不可能实现的新功能。
Pat Helland - 任何其他名称的身份
新兴的系统和协议都在收紧和放松我们对身份的概念，这很好！它们使完成工作变得更容易。REST、IoT、大数据和机器学习都围绕着刻意保持灵活且有时含糊不清的身份概念。身份概念是我们分布式系统的基本机制的基础，包括互换性、幂等性和不变性。
Raymond Blum, Betsy Beyer - 实现数字永恒
当今的信息时代正在为世界所依赖的数据创造新的用途和新的管理方式。世界正在远离熟悉的物理文物，转向更接近信息本质的新表示手段。我们需要流程来确保知识的完整性和可访问性，以保证历史将被知晓和真实。
Heinrich Hartmann - 工程师统计学
现代 IT 系统从网络设备、操作系统、应用程序和其他组件收集越来越多的数据。需要分析这些数据，以获得关于用户体验和业务绩效的重要信息。例如，需要检测故障、测量服务质量，并预测未来几天和几个月的资源使用情况。
© 保留所有权利。