海量数据流的最佳算法实战
姓名：苗春雨 学号：16019110036
转载自：http://blog.csdn.net/dev_csdn/article/details/78533168
【嵌牛导读】：摘要：为了高效地分析海量的数据，科学家首先要将大数打破成碎片。作者循序渐进地阐述了一个处理海量数据流的最佳流式算法，算法经过不断改进，是超大规模数据流高性能分析的新算法，以下是译文。
【嵌牛鼻子】：海量数据流的最佳算法
【嵌牛提问】：建立算法所需的策略？
【嵌牛正文】：
原文：Best-Ever Algorithm Found for Huge Streams of Data
翻译：无阻我飞扬
当从消防水带出来的水冲击你的脸部时，很难计量水。从某种意义上说，这正是分析数据流所面临的挑战，数据源源不断地向我们奔流而来，永不停息。如果在Twitter上看一篇篇推文不停闪过，你可能想要暂停一下，以便弄清楚时下的流行话题是什么。话虽这么说，但这行不通，所以需要找到一种方法，以便实时记录主题标签。
执行这种实时计算的计算机程序称为流式算法。因为数据以庞大的量持续不断地出现，流式算法试图记录下重要的数据，同时战略性遗忘其余数据。30多年来，计算机科学家一直致力于构建更好的流式算法。去年秋天，一个研究小组发明了一种近乎完美的算法。
哈佛大学的计算机科学家杰拉尼·尼尔森（Jelani Nelson）表示：“我们开发了一种新算法，从各个标准维度来看，也是最好的算法”，他与丹麦奥胡斯大学的卡斯珀·格林·拉森（Kasper Green Larsen）、哥本哈根大学的迈克尔·托鲁普（Mikkel Thorup）以及东北大学的阮惠（Huy Nguyen）一起提出了这个新算法。
哈佛大学的理论计算机科学家杰拉尼·尼尔森与别人共同开发出了新算法。
图片来源：Yaphet Teklu
这种一流的流式算法的工作原理是，通过记住足够多的数据来告诉你它最常看到的是什么。这表明在数据流分析中固有的折衷实际上似乎并不必要。这也为战略性遗忘的新纪元指明了前进的道路。
流式算法在监视连续不断更新的数据库的任何情况下都是有帮助的。这可能是AT&T持续不断的选项卡数据包或者Google绘制永无止境的搜索查询流程。在这些情况下，流式算法是非常有用的，甚至是必要的，即使没有重新检查或甚至记住你所见过的每一段数据，都有一种方法来回答数据方面的实时问题。
这里有一个简单的例子。假设有一连串的数字，想知道目前为止你所看到的所有数字的总和。这种情况下，很显然不是记住每一个数字，只需要记住一个数字：累计总数。
然而，当想问的关于数据的问题变得更复杂时，这个挑战就更难了。想象一下，假设不是想计算总和，而是想回答以下问题：哪些数字最常出现？看不太出来有什么捷径可以快速给出正确的答案。
这个特殊的谜题被称为“频繁项”（frequent item，或heavy hitter）问题。解决这个难题的第一个算法是在20世纪80年代初由康奈尔大学的大卫·格里斯（David Gries）和得克萨斯大学奥斯汀分校的贾亚德夫·米斯拉（Jayadev Misra）开发的。他们的算法在许多方面是有效的，但却不能处理所谓的“变化检测”。它可以告诉你最常搜索的词语，但是无法告诉哪些词语很流行。以Google为例，它可以将“维基百科”视为一个受欢迎的搜索词语，却发现不了与艾尔玛飓风等重大事件相伴随的热搜。
沃里克大学的计算机科学家格雷厄姆·科尔莫德（Graham Cormode）说：“这是一个编码问题 ——你将信息编码为简洁的摘要，并尝试提取信息，让你恢复最初的内容。”
在接下来的30多年里，科尔莫德和其他计算机科学家改进了Gries和Misra的算法。比如说，一些新的算法能够检测出流行词语，另一些算法能够更精细地定义某个词语怎样才算是频繁词语。所有这些算法都有其弊端，比如牺牲速度以换去准确性，或者牺牲内存消耗来保证可靠性。
这方面的工作大多数依赖索引（index）。想象一下，设若你试图识别频繁的搜索字词。一个办法就是为英语中的每个单词分配一个编号，然后将该编号与跟踪该词搜索了多少次的第二个编号配对起来。也许“aardvark” 以单词编号17被编入索引，并在数据库中显示为（17，9），意思是单词编号为17的单词已被搜索9次。这种方法离将最频繁的项放在手边更近了一步，因为在任何特定时刻，你知道每个单词到底被搜索了多少次。
尽管如此，它还是有缺点的，那就是要花很多的时间用一个算法来梳理英语中成千上万的单词。
但要是字典里只有100个单词，将会怎么样？罗伊·尼尔森说：“遍历字典中的每个单词花不了太长时间。”
可惜，字典里的单词数量实在是太多了。正如新算法的作者发现的那样，除非你可以把大字典分解成更小的字典，并找到一种巧妙的方法把它重新组合起来，否则无计可施。
小数字比大数字容易跟踪。
想象一下，假如你正在监视0到50000000之间的一个数字流（这项任务类似于按照IP地址来记录互联网用户）。可以使用50000000项索引来跟踪这些数字，但是很难处理这么庞大的索引。更好的方法是把每个八位数字视为连接在一起的四个两位数字。
设若看到数字12345678。一种高效记忆的方法是将其分解成四个两位数块：12,34,56,78。然后，可以将每个块发送给计算项目频率的子算法：12发给子算法一，34发给子算法二，56发给子算法三，78发给子算法四。
每个子算法都为它看到的内容建有各自的索引，但由于每个版本都不会看到比两位数大的索引，所以每个索引只是从0到99。
这种分拆的一个重要特点是，如果大数字——12345678 在整个数据流中频繁出现，其两位数字块部分也将频繁出现。如果要求每个子算法识别出最常看到的数字，子算法一会给出12，子算法二将给出34，依此类推。只要在四个短得多的列表中查找频繁项，就能够找到庞大列表中最常见的内容。
图片来源：Lucy Reading-Ikkanda/《Quanta》杂志
尼尔森说：“不是花5000万个时间单位遍历整个宇宙，只是四个算法，花了100个时间单位。”
这种分而治之策略存在的主要问题是，虽然很容易把一个大数字分解成小的数字，但将小数重新组合成大数比较棘手— 很难找出正确的小数来重新组合，从而获得正确的大数。
想象一下，你的数据流通常包含几个数字相同的两个数：12,345,678和12,999,999。两者都从12开始。你的算法将每个大数字分成四个较小的数字，然后将每个小数字发送给子算法。然后你问每个子算法，“哪些数最常看到？”子算法1将会说：“我经常看到数字12.” 一种算法试图识别是哪个八位数字，在这种情况下，经常不知道这些12是属于其中某一个八位数的，还是属于该例中两个不同的八位数的。
尼尔森说：“难就难在搞清楚哪些两位数块与另外哪些两位数块连在一起。”
新算法的作者通过将每个两位数块封装成一个不占用大量内存的小标签来解决这个困境，但是仍然允许算法将两位数的块以正确的方式重新组合在一起。
要查看标签如何工作的简单方法，不妨从12,345,678开始，并将其拆分成两位数块。但这一次，在将每个块发送到其各自的子算法之前，使用一对唯一的标识号封装块，标识号可以将块重新组合在一起。这些标签中的第一个用作块的名称，第二个标签作为环。这样一来，12345678成为：
12, 0, 134, 1, 256, 2, 378, 3, 4
这里，数字12的名称为“0”，并链接到名为“1”的数字。数字34的名称为“1”，并链接到名为“2”的数字，依此类推。
现在，当子算法返回最常见的两位数字块时，12找寻一个标有“1”的数字，从而找到34，然后34找寻一个标有“2”的数字，从而找到56， 56找寻一个标有“3”的数字，从而找到78。
这么一来，可以把两位数字块视为链中的环，并通过这些额外的标记号将这些环连接在一起。
当然许多链的问题在于，其牢固性完全取决于最薄弱的那一环。而这些链几乎可以保证会断掉。
没有一种算法能在每次运行时都完美地运行——即使最好的算法也会在很小的一段时间内失效。在上述的例子中，一个失效可能意味着第二个两位数的块，34，被分配了一个不正确的标签，结果就是当它去找寻它应该连接的块时，它没有找到56所需要的信息。一旦链中的一个环节失败，整个工作就土崩瓦解了。
哥本哈根大学的计算机科学家迈克尔·托鲁普帮助开发了一种防止错误的方法来记住数据。
图片来源：UNIAVISEN.DK
为了避免这个问题，研究人员使用所谓的“扩展图”。在扩展图中，每两个数字块形成一个点。这些点按线连接（遵循上述的标记过程）形成一个聚类。扩展图的一个重要特点是，不只是将每个点与其相邻的块连接起来，而是将每个两个数字块与多个其它块连接起来。以12345678为例，不仅将12与34连接，也与56连接，这样即使12和34之间的链接失败，仍然可以知道12和56属于同一个数字。
扩展图的结果并不总是完美的。有时它无法链接本该链接的两个块，或者会链接不属于一起的两个块。为了克服这个不足，研究人员开发了其算法的最后环节：“聚类保留”子算法，它可以调查扩展图，准确地确定哪些点旨在聚合起来、哪些点不是，即使某几条线丢失、虚假线添加上去也没关系。
托鲁普说：“这确保我可以恢复看起来酷似原始聚类的内容。”
虽然Twitter不会明天就使用这个扩展图，但其底层技术适用于解决极其广泛的计算机科学问题，而不是仅仅用来统计推文。该算法还证明了不需要作出某些牺牲，也即以前在回答频繁项目问题的时候似乎非常必要的牺牲。以前的算法总是放弃一些东西——准确性很高，但很费内存，或者速度很快，但是无法确定哪些频繁项很流行。这个新的算法表明，若有正确的方法来编码大量信息，你最后能够集众者之所长：不仅可以存储频繁项，还可以取回频繁项。
