摘要：为了高效分析海量数据，科学家必须首先将大量数据分解成碎片。作者逐步阐述了一种处理海量数据流的最优流算法。该算法经过不断改进，是一种针对超大规模数据流进行高性能分析的新算法。以下为译文。当消防水带的水喷到您的脸上时，很难计量水量。从某种意义上说，这是分析流向我们的数据流的挑战，永无止境。如果您在Twitter上滚动浏览一条又一条推文，您可能需要停下来弄清楚当前的趋势。话虽这么说，但这是行不通的，因此需要找到一种方法来实时记录主题标签。执行此类实时计算的计算机程序称为流算法。由于数据持续不断地大量涌入，流式算法会尝试记录重要的数据，同时有策略地忘记其余数据。30多年来，计算机科学家一直致力于构建更好的流媒体算法。去年秋天，一组研究人员发明了一种近乎完美的算法。“我们开发了一种新算法，它在每个标准维度上都是最先进的，”与丹麦奥胡斯大学的卡斯合作的哈佛大学计算机科学家JelaniNelson说。KasperGreenLarsen与哥本哈根大学的MikkelThorup和东北大学的HuyNguyen一起提出了新算法。新算法由哈佛大学理论计算机科学家GeraniNelson共同开发。图片来源：YaphetTeklu这种出色的流媒体算法通过记住足够多的数据来告诉您它最常看到的内容。这表明数据流分析中固有的权衡实际上似乎没有必要。它还为战略遗忘的新时代指明了前进的方向。发现趋势流算法在任何情况下都非常有用，只要持续更新的数据库受到监控。它可能是AT&T不断的标签包或谷歌永无止境的搜索查询流。在这些情况下，流式算法非常有用，甚至是必要的，它有办法回答关于数据的实时问题，甚至不需要重新检查甚至记住你见过的每一条数据。这是一个简单的例子。假设您有一个数字序列，并且想知道到目前为止您看到的所有数字的总和。在这种情况下，显然不需要记住每个数字，只需要记住一个数字：累计总数。但是，当您想询问的有关数据的问题变得更加复杂时，这一挑战就会变得更加困难。想象一下，您不想计算总和，而是想回答以下问题：哪些数字最常出现？快速给出正确答案的捷径并不明显。这个特殊的难题被称为“常见项目”（或重击者）问题。解决这个难题的第一个算法是在1980年代初期由康奈尔大学的DavidGries和德克萨斯大学奥斯汀分校的JayadevMisra开发的。他们的算法在很多方面都很有效，但无法处理所谓的“变化检测”。它可以告诉您最常搜索的术语，但不能告诉您哪些是受欢迎的。例如，谷歌可以将“维基百科”视为一个流行的搜索词，但无法找到伴随飓风艾尔玛等重大事件的趋势搜索。华威大学的计算机科学家GrahamCormode说：“这是一个编码问题——你将信息编码成一个简洁的摘要，并尝试提取信息，让你恢复原始内容。在接下来的30多年里，Kermode等计算机科学家对Gries和Misra的算法进行了改进。例如，一些新算法可以检测流行词，而另一些算法可以更精细地定义什么是频繁词。所有这些算法都有其缺点，例如牺牲速度以换取准确性，或者牺牲内存消耗以获得可靠性。该领域的大部分工作都依赖于索引。想象一下，如果您试图识别频繁的搜索词。一种方法是为英语中的每个单词分配一个数字，然后将该数字与一个第二个数字跟踪这个词被搜索了多少次。也许“aardvark”被索引为第17个词，并在数据库中显示为(17,9)，意思是这个词有wordnumber17已被搜索9次。这种方法更接近于将最常用的词条放在手边，因为在任何给定时刻，您都确切知道每个词被搜索了多少次。尽管如此，它的缺点是算法需要花费大量时间来梳理英语中的数千个单词。但是如果字典只有100个单词呢？罗伊·尼尔森说：“把字典里的每一个词都翻一遍不会花太长时间。不幸的是，字典中的单词数量实在是太多了。正如新算法的作者所发现的那样，除非您可以将大词典分解成较小的词典并找到一种巧妙的方法将其重新组合在一起，否则什么都做不了。小数据和小数字比大数字更容易跟踪。想象一下，如果您正在监视0到50000000之间的数字流（类似于按IP地址记录Internet用户的任务）。使用一个50000000条目的索引可以跟踪这些数字，但是很难处理这么大的索引。更好的方法是将每个八位数字视为连接在一起的四个两位数。假设您看到数字12345678。记住它的一种有效方法是将其分解为四个两位数块：12、34、56、78。然后可以将每个块发送到计算项目频率的子算法：12到子算法一,34到子算法二,56到子算法三,78到子算法四.每个子算法都有自己的索引，但由于每个版本都不会看到大于两位数的索引，因此每个索引都只是从0到99。这种拆分的一个重要特征是，如果较大的数字——12345678——在整个数据流中频繁出现，其两位数的块部分也将频繁出现。如果要求每个子算法识别最常见的项，子算法一会给出12，子算法二会给出34，等等。通过简单地在四个更短的列表中查找频繁项，您将能够找到最常见的项巨大清单中的项目。图片来源：LucyReading-Ikkanda/《Quanta》MagazineNielsen说：“与其以5000万个时间单位遍历整个宇宙，不如用4个算法花费100个时间单位。”这种分而治之策略的主要问题是，虽然将大数分解成较小的数字很容易，但将小数位放回一起就比较棘手了——很难找到正确的小数点放回一起以获得正确的数字。大数。想象一下，您的数据流通常包含两个具有多个共同数字的数字：12,345,678和12,999,999。两者都从12开始。您的算法将每个大数分成四个较小的数，然后将每个小数发送给子算法。然后你问每个子算法，“哪些数字最常出现？”子算法1会说，“我经常看到数字12”。一种算法试图识别哪个八位位组是数字，在这种情况下，通常不知道12是属于其中一个八位位组，还是属于两个不同的八位位组。“困难在于弄清楚哪些两位数与哪些其他两位数块链接在一起。“新算法的作者通过将每个两位数的块打包到一个不占用大量内存的小标签中解决了这个难题，但仍然允许算法以正确的方式将两位数的块放回一起.要查看标签这是如何工作的一种简单方法，让我们从12,345,678开始并将其分成两位数的块。但是这次，在将每个块发送到其各自的子算法之前，用一对唯一标识包装这些块numbers，标识号允许将块放回一起。这些标签中的第一个用作块的名称，第二个用作环。这样，12345678变成：这里，数字12的名称为“0”，并链接到名为“1”的数字。数字34的名称为“1”，并链接到名为“2”的数字，依此类推。现在，当子算法返回最常见的两位数块时,12找一个标有“1”的数找到34，然后34找一个标有“2”的数找到56，56找一个number标记为“3”找到78。这样，将两位数的块想象成链中的环，并将这些环与这些额外的标记数字连接在一起。当然，许多链条的问题在于它们的强度取决于最薄弱的环节。而这些锁链几乎是注定会断的。积木没有任何算法在每次运行时都能完美运行——即使是最好的算法也会在很短的时间内失败。在上面的例子中，失败可能意味着第二个两位数的块34被分配了一个错误的标签，结果当它去寻找它应该连接的块时，它没有找到56所需的信息。一旦链条的一个环节出现故障，整个工作就会分崩离析。哥本哈根大学的计算机科学家MichaelTorup帮助开发了一种记忆数据的防错方法。图片来源：UNIAVISEN.DK为了避免这个问题，研究人员使用了所谓的“扩展图”。在展开图中，每两块数字组成一个点。这些点由一条线连接（遵循上述标记过程）以形成一个簇。扩展图的一个重要特征是，不只是每个点，而是将每个两位数块连接到多个其他块。以12345678为例，把12不仅连到34，还要连到56，这样即使12到34之间的数字连不上，仍然可以知道12和56属于同一个数字。扩展图的结果并不总是完美的。有时它无法将两个块链接到它应该链接的位置，或者它链接了两个不属于一起的块。为了克服这个缺点，研究人员开发了他们算法的第一部分：一个“保留簇”的子算法，它调查扩展图以确定哪些点打算聚合，哪些点不打算聚合，即使某些线它不重要的是是否添加了缺失或错误的行。“这确保我可以恢复看起来与原始集群完全一样的东西，”Torup说。虽然Twitter明天不会使用这个扩展图，但底层技术适用于极其广泛的计算机科学问题，而不仅仅是计算推文。该算法还表明，不需要做出以前似乎是回答频繁项目问题所必需的某些牺牲。以前的算法总是会放弃一些东西——准确率高但占用大量内存，或者速度快但无法确定哪些频繁项受欢迎。这种新算法表明，通过正确的方式对大量信息进行编码，您最终可以做到最好：您不仅可以存储频繁出现的项目，还可以检索它们。
