Axton

软件学报'04 流数据分析与管理综述

· Axton

摘要

流数据的特点是数据持续到达，且速度快、规模宏大；其研究核心是设计高效的单遍数据集扫描算法，在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构——概要数据结构，使得在任何时候都能够根据这个结构迅速获得近似查询结果。

引言

令 \(t\) 表示任一时间戳，\(a_t\) 表示在该时间戳到达的数据，流数据可以表示成\(\{...,a_{t−1},a_t,a_{t+1},...\}\)。

区别于传统应用模型，流数据模型具有以下 4 点共性：

  • 数据实时到达；
  • 数据到达次序独立，不受应用系统所控制；
  • 数据规模宏大且不能预知其最大值；
  • 数据一经处理，除非特意保存，否则不能被再次取出处理，或者再次提取数据代价昂贵。

设计单遍扫描算法(one-pass algorithm)，实时地给出近似查询结果就成为数据流模型下数据处理的目标。

算法的关键在于设计一个远小于数据集规模的结构，从而可以在内存中处理数据。相对于数据流的规模而言，这种名为概要数据结构(synopsis data structure)的规模至多应该是次线性的。即如果流的长度为 \(N\)，则概要数据结构大小不超过 \(O(polylog(N))\)，并且处理流上每一组数据的时间不超过 \(O(polylog(N))\)1

新的流数据处理技术并不保存整个数据集，仅维护一个远小于其规模的概要数据结构，从而能够常驻内存。

  • 流数据处理技术往往包含两部分算法
    • 一部分监控流中的数据，更新概要数据结构；
    • 另一部分响应用户查询请求，返回近似查询结果。

最近几年，流数据处理技术发展很快。一方面，出现了很多流数据模型下的管理系统，即数据流管理系统 (data stream management system,简称 DSMS)，包括斯坦福大学的 STREAM 项目1、施乐公司的Tapestry 项目2、 加州大学伯克力分校的 Telegraph 项目3 4、布朗大学和麻省理工学院合作的Aurora 项目5等等,这些系统针对具体行业背景，给出较全面的数据管理解决方案；另一方面，基于流数据模型的数据挖掘技术也得到了广泛的研究，包括做聚类分析6、决策树分析7 8、密度估计9等等。上述数据流研究的核心就是概要数据结构的设计。

数据流模型根据不同的时序范围可以划分成多种子模型，包括界标模型(landmark model)、滑动窗口模型 (sliding window model)和快照模型(snapshot model)。

基于界标模型的方法

界标模型所要处理的数据范围从一个固定时间戳到当前时间戳。令初始时间戳为 \(s\)，当前时间戳为 \(n\)，则查询范围可以标记为\(\{a_s,...,a_n\}\)

创建基于界标模型的概要数据结构，要求这个结构能够近似模拟这个数据集合的特征。

直方图(Histogram)

直方图技术10 11就是将一个大数据集划分为很多个连续的桶(bucket)，也就是小数据集，每个桶都由一个数字来代表其特征。直方图表示法直观、简洁，能够很好地表示大数据集的轮廓，因此在一些商业数据库中采用。

1. 等宽直方图(Equi-width histogram)

等宽直方图的目标是使各个桶的高度(即桶所含的数据量)比较平均。

维护等宽直方图能够获得数据集的分位点12。

2. 压缩直方图(Compressed histogram)

压缩直方图可以看成是等宽直方图的一个扩充。

在等宽直方图中，各桶所包含的数据量比较接近。如果数据分布比较均匀，等宽直方图能够较好地模拟数据集。但是，一旦数据集中存在某些所占比例特别大的元素(这些元素也被称为热门元素)，等宽直方图表示法就会产生较大的误差。

压缩直方图法单独为那些热门元素创建桶，对其他元素仍然采用维护等宽直方图的方法，因而能够更真实地模拟数据集。

3. V-优化直方图(V-optimal histogram)

V-优化直方图13的目标是使各桶的方差之和最小。

假设数据集中各个元素的值为 \(v_1,v_2,...,v_n\)，将数据集划分成多桶之后，令 \(b_i\) 表示元素 \(v_i\) 所在桶的平均值。V-优化直方图的目标是使\(∑(v_i-b_i)^2\) 的值最小。

抽样方法(Sampling)

抽样方法也是生成概要数据结构的常用手段。它从数据集中抽取小部分数据代表整个数据集，并根据该样本集合获得查询结果。

  • 抽样方法可以分成均匀抽样(uniform sampling)和偏倚抽样(biased sampling)两种
    • 在均匀抽样方法中，数据集中各元素以相同的概率被选取到样本集合中；
    • 在偏倚抽样方法中，不同元素的入选几率可能不同。
    • 水库抽样方法和精确抽样方法都属于均匀抽样方法，而计数抽样方法则属于偏倚抽样方法。

1. 水库抽样(Reservoir Sampling)

水库抽样方法14单遍扫描数据集，生成均匀抽样集合。令样本集合的容量为 \(S\)，在任一时刻 \(n\)，数据流中的元素都以 \(S/n\) 的概率被选取到样本集合中去。如果样本集合大小超出 \(S\)，则从中随机去除一个样本。可以证明，各元素的入选几率相同。

2. 精确抽样(Concise Sampling)

精确抽样方法15改进了样本集合的表示方法。对于仅出现一次的元素，类似于水库抽样，仍然用元素代码表示；而对于多次出现的元素，则利用结构 \(\left \langle value,count\right \rangle\) 表示，\(value\) 代表元素代码，\(count\) 表示样本集合中该元素的数目。精确抽样方法比水库抽样方法更节约空间。

精确抽样方法通过逐步提高参数 T 的值,实现数据流上的均匀抽样。

3. 计数抽样(Counting Sampling)

计数抽样方法15是精确抽样方法的一个变种。二者的区别在于样本集合溢出时如何处理。在计数抽样算法中，当样本集合溢出时，首先将参数 T 提高到 T′。对于其中的任意一个元素，都是首先以概率 T/T′，之后以概率 1/T′ 判断是否减去 1。一旦该计数器值已经降为 0，或者某一次随机判断之后计数器的值并没有减小，则结束对该元素的操作。计数抽样方法不是均匀抽样方法，但却能有效地获得数据集中的热门元素列表。

小波方法(Wavelet)

小波分析方法是一种通用的数字信号处理技术。类似于傅立叶变换，小波分析根据输入的模拟量，变换成一系列的小波参数，并且少数几个小波参数就拥有大部分能量16。根据这个特性，可以选择少数小波参数，近似还原原始信号。小波分析方法也被应用到数据库领域，例如对高维数据进行降维处理、生成直方图等。小波种类很多，最常见且最简单的是哈尔小波(Haar wavelet)。从而可以估算任一元素的数值或者任一范围之和(range sum)，即某一区间内所有元素之和。

哈希方法(Hash)

定义一组哈希函数，将数据从一个范围映射到另一个范围中去。

1. Bloom Filter 方法

Bloom Filter 方法17自从 1970 年被提出来之后，就广泛应用于网络、数据库、P2P 系统等众多领域。该算法的最大特点是，仅使用一小块远小于数据集数据范围的内存空间表示数据集，并且各个数据仍然能被区分开来。

2. Sketch 方法

Sketch 方法能够解决流上的很多问题，例如，估计数据集的二阶矩大小18、估计数据集自连接的大小19、 获得数据集中热门元素的列表20

3. FM(Flajolet-Martin)方法

FM 方法21是求解数据集中不相同元素的个数(即 \(F_0\)的有力手段。它所采用的哈希函数(least significant 1 bit,简称 LSB)将一个大小为 \(M\) 的数据集映射到范围\([0..logM−1]\)中去，且映射到 \(i\) 的概率是 \(1/2^{i+1}\)。假设不相同元素的个数是 \(D\)，且哈希函数独立随机，则恰有 \(D/2^{i+1}\) 个不同元素映射到 \(i\)。这个性质可以用于估计 \(D\) 的值。

基于滑动窗口模型的方法

假设窗口的大小是 \(W\), 在任一时间点 \(n\), 滑动窗口模型的查询范围是\(\{a_{max(0,n−W+1)},...,a_n\}\)。时间点\(max(0,n−W+1)\)之前的数据全部忽略不计。

指数直方图(Exponential Histogram)

指数直方图22技术是最早用来生成基于滑动窗口模型的概要数据结构的方法。传统的直方图技术将数据集划分成多个桶，相邻桶的元素值连续。而指数直方图则是按照元素的到达次序构建桶。桶的容量按照不同级别呈指数递增，从小到大分别是 1,2,4,8,…各个级别桶的个数均不超过一个预定义的门槛值。每“看到”流中的一个 元素，视应用需求就决定是否创建一个最低级别的桶。

指数直方图仅维护还未过期的桶，一旦最“旧”的桶所有元素都过期了，就删除该桶，释放其所占空间。

指数直方图能够解决滑动窗口模型下的很多问题，例如基本计数(basic counting)问题、求和问题22、方差问题23等。

基本窗口(Basic Window)

基本窗口技术24将大小为 \(W\) 的窗口按照时间次序划分成 \(k\) 个等宽的子窗口，称为基本窗口，每个基本窗口包含 \(W/k\) 个元素,且由一个小结构表示基本窗口的特征。

如果窗口所包含的元素均已过期，则删除表征这个基本窗口的小结构。用户可以基于这些未过期的小结构得到查询结果。

链式抽样(Chain-Sampling)

链式抽样方法25能够获得在滑动窗口上均匀抽样的样本集合。

应用例子

  • 在流上挖掘热门元素。根据用户定义的门槛参数 \(s\in (0,1)\)，输出在整个数据流中所占比重大于 \(s\) 的所有元素。很多应用需要用到这个信息。例如，网络路由器需要监控比例特别高的 IP 包，防止 DOS 攻击；对于决策支持系统而言，了解数据集中哪些元素关系密切也非常重要。
  • 在流上挖掘分位点。令集合大小是 \(N\)，参数\(\phi \in (0,1)\)，分位点元素就是数据集排序之后第\(\phi N\) 位置的元素。分位点是数据集合的一个重要统计量。获得分位点有助于优化查询计划，提高数据库系统的性能。

虽然数据流算法只能返回近似查询结果，但是大部分算法都能将其误差限制在一个预定义的小范围之内。

  • 在理论上保证误差范围的算法又可以分为确定性算法和非确定性算法两种
    • 确定性算法所得到的查询结果在任何情况下都是可信的
    • 非确定性算法只能保证结论正确的概率很高，给定足够的空间，其概率值可以接近于 1

  1. Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues in data streams. In: Popa L, ed. Proc. of the 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Madison: ACM Press, 2002. 1~16. ↩︎ ↩︎

  2. Terry D, Goldberg D, Nichols D, Oki B. Continuous queries over append-only databases. SIGMOD Record, 1992,21(2):321~330. ↩︎

  3. Avnur R, Hellerstein J. Eddies: Continuously adaptive query processing. In: Chen W, Naughton JF, Bernstein PA, eds. Proc. of the 2000 ACM SIGMOD Int’l Conf. on Management of Data. Dallas: ACM Press, 2000. 261~272. ↩︎

  4. Hellerstein J, Franklin M, Ch andrasekaran S, D eshpande A, Hildrum K, Madden S, Rama n V, Shah MA. Adaptive query processing: Technology in evolution. IEEE Data Engineering Bulletin, 2000,23(2):7~18. ↩︎

  5. Carney D, Cetinternel U, Cherniack M, Convey C, Lee S, Seidman G, Stonebraker M, Tatbul N, Zdonik S. Monitoring streams——A new class of DBMS applications. Technical Report, CS-02-01, Providence: Department of Computer Science, Brown University, 2002. ↩︎

  6. Guha S, Mishra N, Motwani R, O’Callaghan L. Clustering data streams. In: Blum A, ed. The 41st Annual Symp. on Foundations of Computer Science, FOCS 2000. Redondo Beach: IEEE Computer Society, 2000. 359~366. ↩︎

  7. Domingos P, Hulten G. Mining high-speed data streams. In: Ramakrishnan R, Stolfo S, Pregibon D, eds. Proc. of the 6th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Boston: ACM Press, 2000. 71~80. ↩︎

  8. Domingos P, Hulten G, Spencer L. Mining time-changing data streams. In: Provost F, Srikant R, eds. Proc. of the 7th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. San Francisco: ACM Press, 2001. 97~106. ↩︎

  9. Zhou A, Cai Z, Wei L, Qian W. M-Kernel merging: Towards density estimation over data streams. In: Cha SK, Yoshikawa M, eds. The 8th Int’l Conf. on Database Systems for Advanced Applications (DASFAA 2003). Kyoto: IEEE Computer Society, 2003. 285~292. ↩︎

  10. Kooi R P. The optimization of queries in relational databases [Ph.D. Thesis]. Cleveland: Case Western Reserve University, 1980. ↩︎

  11. Piatetsky-Shapiro G, Connell C. Accurate estimation of the number of tuples satisfying a condition. SIGMOD Record, 1984,14(2): 256~276. ↩︎

  12. Greenwald M, Khanna S. Space-Efficient online computation of quantile summaries. In: Proc. of the 2001 ACM SIGMOD Int’l Conf. on Management of Data. Santa Barbara: ACM Press, 2001. 58~66. ↩︎

  13. Ioannidis Y, Poosala V. Balancing histogram optimality and practicality for query result size estimation. SIGMOD Record, 1995, 24(2):233~244. ↩︎

  14. Vitte r JS. Random sampling with a reservoir. ACM Trans. on Mathematical Software, 1985,11(1):37~57. ↩︎

  15. Gibbons PB, Matias Y. New sampling-based summary statistics for improving approximate query answers. In: Haas LM, Tiwary A, eds. SIGMOD 1998, Proc. of the ACM SIGMOD Int’l Conf. on Management of Data. Seattle: ACM Press, 1998. 331~342. ↩︎ ↩︎

  16. Jawerth B , Sweldens W. An overview of wavelet based multiresolution analyses. SIAM Review, 1994,36(3):377~412. ↩︎

  17. Bloom B. Space/time tradeoffs in hash coding with allowable errors. Communications of the ACM, 1970,13(7):422~426. ↩︎

  18. Alon N, Matias Y, Szegedy M. The space complexity of approximating the frequency moments. In: Miller G, ed. Proc. of the 28th Annual ACM Symp. on the Theory of Computing. Philadelphia: ACM Press, 1996. 20~29. ↩︎

  19. Alon N, Gibbons PB, Matias Y, Szegedy M. Tracking join and self-join sizes in limited storage. In: Proc. of the 18th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Philadelphia: ACM Press, 1999. 10~20. ↩︎

  20. Charika r M, Chen K, Farach-Colton M. Finding frequent items in data streams. Theoretical Computer Science, 2004,312(1):3~15. ↩︎

  21. Flajolet P, Martin GN. Probabilistic counting algorithms for data base applications. Journal of Computer and Systems Sciences, 1992,31(2):182~209. ↩︎

  22. Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. In: Eppstein D, ed. Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms. San Francisco: ACM/SIAM, 2002. 635~644. ↩︎ ↩︎

  23. Babcock B, Datar M, Motwani R, O’Callaghan L. Maintaining variance and k-Medians over data stream windows. In: Neven F, ed. Proc. of the 22nd ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. San Diego: ACM Press, 2003. 234~243. ↩︎

  24. Zhu Y, Shasha D. StatStream: Statistical monitoring of thousands of data streams in real time. In: Bernstein P, Ioannidis Y, Ramakrishnan R, eds. Proc. of the 28th Int’l Conf. on Very Large Data Bases. Hong Kong: Morgan Kaufmann, 2002. 358~369. ↩︎

  25. Babcock B, Datar M, Motwani R. Sampling from a moving window over streaming data. In: Eppstein D, ed. Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms. San Francisco: ACM/SIAM, 2002. 633~634. ↩︎