ACM通信
研究突出了
技术视角:数据流处理——当你只看一眼时
数据库和系统社区在开发允许我们存储和查询大量数据的数据库系统方面取得了巨大进展。我的第一台电脑大约花了1000美元;它是一个拥有170KB软盘驱动器的Commodore 64。今天(2009年9月)，我可以用同样的价格配置一个1.7TB的文件服务器。为了应对存储可用性的爆炸式增长，公司正在建造越来越大的数据仓库，我们留下的每一个数字痕迹都被存储在那里，以备日后分析。数据24小时24小时都有，实时的“动态”分析——总能得到答案——正变得势在必行。这时数据流处理就可以派上用场了。
在数据流处理场景中，数据以很高的速度到达，必须使用有限的内存按照接收的顺序进行分析。该领域有两个主要方向:系统方面和算法方面。在系统方面，研究人员开发了数据流处理系统，其工作方式就像颠倒了的数据库系统:在系统中注册长时间运行的查询，数据通过系统进行流处理。创业公司现在出售分析流数据的系统，用于欺诈检测、算法交易和网络监控等领域的解决方案。它们通常提供比传统数据库系统至少数量级的性能改进。
在算法方面，已经有很多关于新颖的单遍算法的研究。这些算法不需要二级索引结构，也不需要昂贵的排序操作。他们是在线的答案查询当前前缀的流是可在任何时间。这些所谓的数据流算法通过交易精确的查询答案和近似的答案来实现这些属性，但是这些近似有可证明的质量保证。
Graham Cormode和Marios Hadjieleftheriou的以下论文概述了在数据流中查找频繁项的重要原语的最新进展。非正式地说，如果一个项的相对频率超过用户定义的阈值，则该项在流的前缀中频繁出现。这个问题的另一种表述只是寻找最常出现的项目。作者提出了一个算法框架，包括以前的工作，并显示了不同方法的彻底实验比较的结果。
这篇论文特别及时，因为其中一些算法已经在使用中(根据作者的说法，那些正在使用的算法不一定是最好的)。例如，在谷歌的分析基础设施中，在mapreduce框架中，存在几个预先打包的“聚合器”，可以一次性收集大量数据集的统计信息。“分位数”聚合，在数据的每个分位数上收集一个值，使用论文中介绍的以前开发的算法，而“顶部”聚合估计数据集中最流行的值，同样使用论文中框架捕获的算法。
在AT&T(作者的家机构)内部，基于信息包头数据的实时分析，目前部署了各种各样的流算法用于网络监控。例如，分位数聚合用于跟踪网络中不同点之间的往返延迟随时间的分布。类似地，重量级聚合用于查找随时间向给定目的地发送最多流量的源。
尽管这篇论文调查了大约30年的研究，但该领域仍有很大进展。此外，找到经常出现的物品只是统计数据之一。实际上，更复杂的查询，如项的频繁组合、挖掘集群或其他统计模型，都需要有质量保证的数据流算法。例如，Yahoo!内容优化展示了如何使用在线构建的时间序列模型来预测基于用户点击流的文章的点击率。
我认为，在应用和新算法方面，我们只触及了表面，我期待着下一个30年的创新。我推荐这篇文章来了解这些年来发展起来的技术类型，并看看算法、统计和数据库的想法是如何在这个问题中结合在一起的。
©2009 acm 0001-0782/09/1000 $10.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.
没有发现记录