大数据的压缩方法 │ 压缩数据上的聚集算法

本文摘自《大数据算法分析与设计》第5章，有删减。

压缩计算方法是把大数据计算问题转换为小数据计算问题的有效方法。压缩计算方法首先以预处理的方式压缩数据集合，然后直接在压缩数据上无解压地求解大数据计算问题。本章介绍的压缩计算方法是精确计算方法，而基于抽样的计算方法是近似计算方法。当然，如果应用压缩计算方法设计大数据计算问题的近似求解算法，可能会更大幅度地降低大数据计算的时间复杂性。

很多大数据计算问题可以使用压缩计算方法实现亚线性时间精确求解。对于那些使用压缩计算方法很难实现亚线性时间精确求解的大数据计算问题，也可以使用压缩计算方法提高大数据计算问题求解的效率。当问题的输入大数据集合不可压缩或压缩比很低时，压缩计算方法就无能为力了。本章既考虑如何使用压缩计算方法实现亚线性时间算法，也考虑如何使用压缩计算方法最大化大数据计算的效率。

大数据的联机分析是决策支持系统的重要基础。聚集操作是联机分析的重要操作之一。本节介绍基于压缩计算方法的多维数据聚集操作算法的设计与分析。首先讨论聚集问题的定义，然后讨论基于压缩计算的几种聚集算法的设计与分析。

首先讨论通用聚集算法，简记作G-Agg。“通用”意味着算法G-Agg适用于各种情况，无须作任何假定。

1. 算法设计

给定R(D₁,D₂,…,D_k; M)、F=Proj(R, M)、R的压缩结果(c(F), Hd)、和聚集函数Agg，算法G-Agg分为两个阶段，直接在数据集合R的压缩结果(c(F), Hd)上完成R的聚集计算。

第一阶段，转置阶段。该阶段根据聚集属性集合{A₁,A₂,…,A_l}对R的维属性执行转置操作，使得聚集操作得以有效处理。

看图5.4.2给出的例子。R(A, B, C, D; M)是一个4维数据集合，其维属性次序为。如果聚集属性集合为{B, C}，则维属性次序或R(B, C, A, D; M)能够有效支持聚集计算。

2  算法分析

算法的正确性是显然的。这里仅分析算法的时间复杂性和I/O复杂性。在下面的分析中，假设: R(d1,d2,…,dk; M)具有n个元组，每个元组具有常数个字节，R的压缩结果为(c(F), Hd)，c(F)具有N个数据项，c(F)的Header向量Hd具有H个数据项，B是磁盘块或一个内存缓冲区大小。