留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种Haar小波概要的流数据压缩方法

李水泉 乐阳 李清泉 庄严

李水泉, 乐阳, 李清泉, 庄严. 一种Haar小波概要的流数据压缩方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
引用本文: 李水泉, 乐阳, 李清泉, 庄严. 一种Haar小波概要的流数据压缩方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
LI Shuiquan, YUE Yang, LI Qingquan, ZHUANG Yan. A Streaming Data Compression Method Based on Haar Wavelet Synopses[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
Citation: LI Shuiquan, YUE Yang, LI Qingquan, ZHUANG Yan. A Streaming Data Compression Method Based on Haar Wavelet Synopses[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309

一种Haar小波概要的流数据压缩方法

doi: 10.13203/j.whugis20190309
基金项目: 

国家自然科学基金 41671387

详细信息

A Streaming Data Compression Method Based on Haar Wavelet Synopses

Funds: 

The National Natural Science Foundation of China 41671387

More Information
  • 摘要: 传感器和物联网技术的广泛使用催生了大量流数据。面对海量、连续且实时到达的流数据,其存储、查询以及后续大量数据的连续使用和分析是迫切需要解决的问题, 而流数据压缩是其中一个有效方法。设计了一种数据概要算法,贪心的哈尔小波概要(greedy-Haar-synopses,GH-Synopses),对流数据进行有效的压缩。首先,设计了一种可以实时处理连续数据的概要数据结构; 然后,在Haar小波变换的基础上用一种贪心策略生成尽可能少的概要数据,从而实现有损的流数据实时压缩。相比于现有的Haar小波类数据概要算法,GH-Synopses能够兼顾压缩率和实时性,并能够控制单个数据的误差界限,可以适用更广泛的场景。利用深圳市路段行驶速度数据进行了验证,结果表明,GH-Synopses算法所生成的概要数据数量少,一般压缩率可达到3%~7%,且能高效重构,重构后的每一个数据误差均不会超过设定的误差预值,是一种有效且高效的流数据压缩方法。
  • 图  1  N=3的Haar-N

    Figure  1.  Haar-N Tree with N=3

    图  2  路段W1W2W3一天的行驶速度波动度

    Figure  2.  Road Link Travel Speed Fluctuations of Roads W1, W2, W3

    图  3  概要数据数量

    Figure  3.  Quantity of Synopses Data

    图  4  处理单条路段数据的运行时间

    Figure  4.  Running Time of Processing Single Data

    图  5  处理所有路段数据所需的总运行时间

    Figure  5.  Total Running Time of Processing all Road Data

    图  6  原始数据与重构数据

    Figure  6.  Original Data and Reconstructed Data

    表  1  构建满足Δ的Haar-N

    Table  1.   Construct a Haar-N Tree Satisfying Δ

    层次 x Δ c
    0 $ \left\{\mathrm{9.0, 4.0, 3.9, 3.7}\right\} $ $ \left\{\mathrm{1, 1}, \mathrm{1, 1}\right\} $
    1 $ \left\{\mathrm{6.5, 3.8}\right\} $ $ \left\{\mathrm{1, 0.9}\right\} $ $ \left\{\mathrm{2.5, 0}\right\} $
    2 $ \left\{5.15\right\} $ $ \left\{0.9\right\} $ $ \left\{1.35\right\} $
    3 $ \left\{1.35\right\} $
    下载: 导出CSV

    表  2  为某个元素设定特定误差界限的构建过程

    Table  2.   Setting a Specific Error Bound for an Element

    层次 x Δ c
    0 $ \left\{\mathrm{9.0, 4.0, 3.9, 3.7}\right\} $ $ \left\{\mathrm{1, 1}, \mathrm{0, 1}\right\} $
    1 $ \left\{\mathrm{6.5, 3.8}\right\} $ $ \left\{\mathrm{1, 0}\right\} $ $ \left\{\mathrm{2.5, 0.1}\right\} $
    2 $ \left\{5.15\right\} $ $ \left\{0\right\} $ $ \left\{1.35\right\} $
    3 $ \left\{1.35\right\} $
    下载: 导出CSV

    表  3  S1中各Cj的重构方式

    Table  3.   Reconstruction of Each Cj in S1

    j Pl Pr
    2 0 -2c
    1 +c -c
    3 +2c 0
    下载: 导出CSV

    表  4  重构d0d1d2d3的过程

    Table  4.   Process of Reconstructing d0, d1, d2 and d3

    d 重构过程 结果
    d0 C0 + 1×C1 + 0 = 1 + 2 + 0 3
    d1 C0 + 1×C1 - 0 = 1 + 2 - 0 3
    d2 C0 - 1×C1 + 0×C8 = 1 - 2 + 0 -1
    d3 C0 - 1×C1 + 2×C8 = 1 - 2 - 2×3 -7
    下载: 导出CSV

    表  5  几种Haar小波类概要算法说明

    Table  5.   Description of Several Haar Wavelet ClassSummary Algorithms

    算法 时间复杂度 空间复杂度 概要结构 限制
    F-Shift[2] O(n) O(lgn) Haar
    S+-Shift[2] O(n) O(n) Haar+
    M[4] O($ {\left(\frac{\Delta }{\delta }\right)}^{2}n $) O($ \frac{\Delta }{\delta }\mathrm{l}\mathrm{g}n+n) $ Haar+
    R[3] O$ \left(\frac{{n}^{2}}{\mathrm{l}\mathrm{g}n}\right) $ O(lgn) Haar
    GH-Synopses O(n) O(lgn) Haar-N
    下载: 导出CSV

    表  6  GH-Synopses算法压缩全部路段数据的压缩率

    Table  6.   Compression Ratio of the GH-Synopses for All Road Links

    Δ/(m·s-1) 压缩率/%
    Li=29 Li=210 Li=211 Li=212
    0.5 6.60 6.96 6.54 7.84
    1.0 5.36 5.80 5.06 6.44
    1.5 4.54 4.80 4.82 5.10
    2.0 3.88 4.16 3.64 4.26
    2.5 3.14 3.32 3.02 3.74
    下载: 导出CSV
  • [1] Sudipto G, Boulos H. Wavelet Synopsis for Data Streams: Minimizing Non-euclidean Error[C]//The 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, Chicago, USA, 2005
    [2] Pang Chaoyi, Zhang Qing, Zhou Xiaofang. et al. Computing Unrestricted Synopses Under Maximum Error Bound[J]. Algorithmica, 2013, 65(1), DOI: 10.1007/s00453-011-9571-9
    [3] Muthukrishnan S. Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses[C]//The 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, 2005
    [4] Panagiotis K, Dimitris S, Nikos M. Exploiting Duality in Summarization with Deterministic Guarantees[C]//The 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, USA, 2007
    [5] Minos G, Amit K. Wavelet Synopses for General Error Metrics[J]. ACM Transactions on Database Systems, 2005, 30(4): 888-928 doi:  10.1145/1114244.1114246
    [6] Sudipto G, Boulos H. Approximation Algorithms for Wavelet Transform Coding of Data Streams[J]. IEEE Transactions on Information Theory, 2008, 54(2): 811-830 doi:  10.1109/TIT.2007.913569
    [7] Sudipto G. Space Efficiency in Synopsis Construction Algorithms[C]// The 31st International Conference on very Large Data Bases, Trondheim, Norway, 2005
    [8] Panagiotis K, Nikos M. The Haar+ Tree: A Refined Synopsis Data Structure[C]//IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey, 2007
    [9] Nobuyuki U, Keisuke Y, Masatomo I. 2D Wavelet Transform Data Compression with Error Level Guarantee for Z-Map Models[J]. Journal of Computational Design and Engineering, 2016, 24(2), 238-247
    [10] Shankar K, Elhoseny M. Secure Image Transmission in Wireless Sensor Network Applications Springer International Publishing[M]. Berlin, Germany: Springer International Publishing, 2019
    [11] Oruç Ö, Esen A, Bulut F. A Haar Wavelet Approximation for Two-Dimensional Time Fractional Reaction‍-Subdiffusion Equation[J]. Engineering with Computers, 2019, 35(1): 75-86 doi:  10.1007/s00366-018-0584-8
    [12] Brian B, Shivnath B, Mayur D, et al. Models and Issues in Data Streams Systems[C]//The 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Madison, USA, 2002
    [13] 谢金运, 涂伟, 李清泉, 等. 大规模浮动车流数据并行地图匹配方法[J]. 武汉大学学报·信息科学版, 2017, 42(5): 697-703 doi:  10.13203/j.whugis20140847

    Xie Jinyun, Tu Wei, Li Qingquan, et al. A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 697-703 doi:  10.13203/j.whugis20140847
    [14] 张存保. 基于浮动车的交通信息采集与处理理论及方法研究[D]. 上海: 同济大学, 2006

    Zhang Cunbao. Research on Theory and Method of Traffic Information Collection and Processing Based on Floating Car[D]. Shanghai: Tongji University, 2006
  • [1] 薛帅, 王光霞, 郭建忠, 余文涛, 徐新伟.  顾及最大绝对误差的频率域矢量数据压缩算法 . 武汉大学学报 ● 信息科学版, 2018, 43(9): 1438-1444. doi: 10.13203/j.whugis20160452
    [2] 李春鑫, 彭认灿, 高占胜, 王海波.  一种改进的三维流场数据可视化方法 . 武汉大学学报 ● 信息科学版, 2017, 42(6): 744-748. doi: 10.13203/j.whugis20141000
    [3] 谢金运, 涂伟, 李清泉, 常晓猛, 马承林, 李追日, 黄练.  大规模浮动车流数据并行地图匹配方法 . 武汉大学学报 ● 信息科学版, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
    [4] 黄伟明, 杨建宇, 陈彦清, 张毅, 张睿.  基于扇形筛选法的矢量数据压缩方法 . 武汉大学学报 ● 信息科学版, 2016, 41(4): 487-491. doi: 10.13203/j.whugis20140225
    [5] 周春霞, 邓方慧, 陈一鸣, 王泽民.  利用SAR数据研究南极Grove山地区冰流运动特征 . 武汉大学学报 ● 信息科学版, 2015, 40(11): 1428-1433. doi: 10.13203/j.whugis20150258
    [6] 李坚, 李德仁, 邵振峰.  一种并行计算的流数据Delaunay构网算法 . 武汉大学学报 ● 信息科学版, 2013, 38(7): 794-798.
    [7] 尹晖, 朱锋.  时序数据去噪中的小波策略及评价指标 . 武汉大学学报 ● 信息科学版, 2012, 37(11): 1374-1377.
    [8] 陈亮, 朱长青, 任娜, 朱一姝.  利用小波变换的视频GIS数据数字水印算法 . 武汉大学学报 ● 信息科学版, 2012, 37(10): 1256-1259.
    [9] 任超, 沙磊, 卢献健.  一种改进小波阀值算法的变形监测数据滤波方法 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 873-875.
    [10] 杨静, 李文平, 张健沛.  一种基于SPA的多数据流同异反分析法 . 武汉大学学报 ● 信息科学版, 2011, 36(1): 92-97.
    [11] 杨博雄, 柳林, 秦前清.  基于形态小波的地震数据压缩方法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(7): 785-788.
    [12] 管旭军, 芮国胜, 周旭, 张玉玲.  基于数据压缩的多传感器不敏滤波算法 . 武汉大学学报 ● 信息科学版, 2010, 35(4): 472-476.
    [13] 孙中苗, 翟振和.  航空重力测量数据的小波阈值滤波 . 武汉大学学报 ● 信息科学版, 2009, 34(10): 1222-1225.
    [14] 杨必胜, 李清泉.  基于簇模型的矢量地图数据的高效压缩方法 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 265-268.
    [15] 李清泉, 黄练, 谭文霞.  基于道路特征的海量GPS监控数据压缩方法 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 337-340.
    [16] 王玉海, 朱长青.  基于小波分析的线状要素压缩优化的综合性研究 . 武汉大学学报 ● 信息科学版, 2007, 32(7): 630-632.
    [17] 朱海军, 吴华意, 李德仁.  基于DCT变换的GIS矢量数据压缩技术研究 . 武汉大学学报 ● 信息科学版, 2007, 32(12): 1123-1126.
    [18] 刘春, 吴杭彬.  基于真三维TIN的三维激光扫描数据压缩方法 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 908-911.
    [19] 陈仁喜, 赵忠明, 王殷行.  基于整型小波变换的DEM数据压缩 . 武汉大学学报 ● 信息科学版, 2006, 31(4): 344-347.
    [20] 耿则勋.  基于小波变换的遥感影像保持量测精度的压缩技术研究 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 187-187.
  • 加载中
图(6) / 表(6)
计量
  • 文章访问数:  562
  • HTML全文浏览量:  188
  • PDF下载量:  47
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-12-24
  • 刊出日期:  2021-08-05

一种Haar小波概要的流数据压缩方法

doi: 10.13203/j.whugis20190309
    基金项目:

    国家自然科学基金 41671387

    作者简介:

    李水泉,硕士,主要从事时空大数据分析与挖掘方面的研究。lishuiquan@aliyun.com

    通讯作者: 庄严,博士. E-mail: zhuangyan@whu.edu.cn
  • 中图分类号: P208

摘要: 传感器和物联网技术的广泛使用催生了大量流数据。面对海量、连续且实时到达的流数据,其存储、查询以及后续大量数据的连续使用和分析是迫切需要解决的问题, 而流数据压缩是其中一个有效方法。设计了一种数据概要算法,贪心的哈尔小波概要(greedy-Haar-synopses,GH-Synopses),对流数据进行有效的压缩。首先,设计了一种可以实时处理连续数据的概要数据结构; 然后,在Haar小波变换的基础上用一种贪心策略生成尽可能少的概要数据,从而实现有损的流数据实时压缩。相比于现有的Haar小波类数据概要算法,GH-Synopses能够兼顾压缩率和实时性,并能够控制单个数据的误差界限,可以适用更广泛的场景。利用深圳市路段行驶速度数据进行了验证,结果表明,GH-Synopses算法所生成的概要数据数量少,一般压缩率可达到3%~7%,且能高效重构,重构后的每一个数据误差均不会超过设定的误差预值,是一种有效且高效的流数据压缩方法。

English Abstract

李水泉, 乐阳, 李清泉, 庄严. 一种Haar小波概要的流数据压缩方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
引用本文: 李水泉, 乐阳, 李清泉, 庄严. 一种Haar小波概要的流数据压缩方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
LI Shuiquan, YUE Yang, LI Qingquan, ZHUANG Yan. A Streaming Data Compression Method Based on Haar Wavelet Synopses[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
Citation: LI Shuiquan, YUE Yang, LI Qingquan, ZHUANG Yan. A Streaming Data Compression Method Based on Haar Wavelet Synopses[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1216-1223. doi: 10.13203/j.whugis20190309
  • 随着传感器和物联网技术的迅速发展,大量流数据的产生导致海量、连续且实时到达的流数据的存储、传输、查询和使用等数据管理问题亟待解决。Haar小波概要技术[1]是一种较为有效的压缩方案,如现有的一些Haar小波概要算法F-Shift、S+-Shift[2]R[3]M[4]等,它们均取小部分小波系数作为概要数据,用它们代表整个数据集,从而实现对流数据的高质量压缩,同时,通过这些概要数据又能够高效重构出近似数据。Haar小波概要可以分为有限制的Haar小波概要和无限制的Haar小波概要两大类。有限制的方法在进行Haar小波变换后得到的系数中寻找若干个系数作为概要数据,以实现最小化重构后数据的均方误差[5],或者使用桶绑定(bucket bound,BB)等方法[6-7]控制单个元素的误差;这类方法通常是以不同误差控制条件设计动态规划算法,实现过程较容易,但它们不具有实时性,且受限于固定的系数值,从而造成数据的缩减率相对不高。无限制的方法不受限于固定的系数值,能够实现更高的数据压缩率[8-11],部分算法具有实时性;但是它们往往不能同时兼顾时间复杂度、空间复杂度、实时性和压缩率,如算法M的执行时间与压缩率成反比,算法S+-Shift的时间复杂度低,其空间复杂度为O(n),且不具有实时性。

    针对上述无限制Haar小波概要的缺点,本文提出了一种融合贪心算法的Haar小波概要算法(greedy-Harr-synopses,GH-Synopses),该算法是一种无限制的Haar小波概要算法,与现有同类型的算法相比,在综合时间复杂度、空间复杂度、实时性、数据压缩率以及单个元素的误差控制等方面具有综合优越性。

    • 概要数据结构[12]是用于数据概要算法的一种有用的概念性工具,数据概要算法在流数据下生成概要数据的过程通常就是概要数据结构的构建或更新过程。GH-Synopses算法是基于Haar小波变换的一种数据概要算法,为实现GH-Synopses,需要构建一棵Haar-N树。

    • 不同于将部分到达的数据作“块”处理,GH-Synopses算法是每到达两个数据元素就进行处理,因此,需要构建一种概要数据结构,用于处理连续到达的数据。算法设计了Haar-N树概要数据结构,其中,N表示预先给定的除树的最顶层外,共同定义一个概要数据的树结点的个数。图‍1是一棵N=3的Haar-N树,树中最底层的d0d3矩型框表示先后到达的原始流数据;椭圆虚线内的N个矩型框表示存储Haar小波系数的结点,由Cj($ j\in \left[\mathrm{1, 9}\right] $)表示;Si表示Haar-N树的结点,它包含NCj、最大绝对值误差预值Δi、Haar小波变换产生的平均值xi和小波系数值ci。Haar-N树的核心之一就是寻找Si中合适的Cj作为概要数据,其存储的值就是ciSi中至多有一个Cj可以成为概要数据。大写C表示的是结点,小写c是数值。

      结合Haar-N树相关概要数据定义如下:对于一个构建完成的Si,即Si处于等待构建其父结点的状态时,若Si中存在一个Cj,有Cj > 0,则Cj是概要数据的值,而j就是概要数据的索引,二元组是概要数据(为方便表示,文中均用Cj表示概要数据)。

    • GH-Synopses算法分为3个部分,首先,对流数据集进行实时处理,构建Haar-N树;其次,在Haar小波变换的基础之上,选择部分系数作为概要数据,以控制单个元素的最大绝对值误差;最后,融入一种贪心策略,使生成的概要数据数量更少,即得到更高的数据缩减率。

      Haar小波是GH-Synopses的基础,这与图像压缩领域的Haar小波方法有一些异同之处。相同之处是对每两个数据元素进行Haar小波变换,忽略影响较小的细节值以起到压缩效果;不同之处是图像中常按“Z”型顺序扫描各像素,进行两两数据间的Haar小波变换,但流数据是无限的,图像的方法用于流数据压缩较难达到数据处理实时性的要求。基于Haar-N树,GH-Synopses算法可以实时地从流数据中生成尽可能少的概要数据,算法的误差度量为单个元素,在最大绝对值误差预值范围内,时间复杂度和空间复杂度分别为O(n)和O(lgn)。各部分原理描述如下:

      1) 处理连续到达的数据。算法处理流数据的过程就是构建一棵Haar-N树的过程,从最底层的原始数据di开始,每当到达两个数据$ \left\{\left.{d}_{i}, {{d}_{i}}_{+1}\right|i\mathrm{\%}2=0\right\} $,就构建往上一层的结点Si,等Si的兄弟结点Si+1构建完成后,用SiSi+1构建再往上一层的结点Sj,以此类推。在这个过程中,算法满足实时性的条件。

      2) 构建满足Δ的Haar-N树。当构建结点Si时,首先,对两个元素xlxr(Si的左右孩子结点的x值)进行一次Haar小波变换,得到平均值xi和小波系数ci。然后,按以下两种情形计算xiciΔi(当Si的左右孩子结点为di时,Δidi的最大绝对值误差界限):情形1,[xl-Δlxl+Δl]∩[xr-Δrxr+Δr]≠$ \mathrm{\varnothing } $;情形2,[xl-Δlxl+Δl]∩[xr-Δrxr+Δr]=$ \mathrm{\varnothing } $。

      对于情形1,xlxr在它们各自允许的误差范围内存在交集,即[xl-Δlxl+Δl]∩[xr-Δrxr+Δr]≠$ \mathrm{\varnothing } $,在该交集中的所有数都可以表示xlxr,而误差不会超过原始流数据的误差预值,因此,可以用xi同时表示xlxr,而ci=0。计算方法如下:

      $$ \left\{\begin{array}{l}{c}_{i}=0\mathrm{ }\\ {x}_{i}=\frac{\mathrm{m}\mathrm{i}\mathrm{n}\left({x}_{l}+{\Delta }_{l}, {x}_{r}+{\Delta }_{r}\right)+\mathrm{m}\mathrm{a}\mathrm{x}\left({x}_{l}-{\Delta }_{l}, {x}_{r}-{\Delta }_{r}\right)}{2}\\ {\Delta }_{i}=\frac{\mathrm{m}\mathrm{i}\mathrm{n}\left({x}_{l}+{\Delta }_{l}, {x}_{r}+{\Delta }_{r}\right)-\mathrm{m}\mathrm{a}\mathrm{x}\left({x}_{l}-{\Delta }_{l}, {x}_{r}-{\Delta }_{r}\right)}{2}\end{array}\right. $$ (1)

      式中,min表示取最小值的函数;max表示取最大值的函数。

      对于情形2,xlxr在它们各自允许的误差范围内存在交集,这种情况下找不到一个Δi,能够使得[xi-Δixi+Δi]中任何一个数能够同时表示xlxr,并且不会超出它们的误差界限,因此,当ci$ \ne $0时,才会存在一个有变化范围的xi的集合,使得集合中每个数+ci都可以代表xr,而-ci都可以表示xl。计算方法如下:

      $$ {c}_{i}=\frac{{x}_{l}-{x}_{r}}{2}, {x}_{i}=\frac{{x}_{l}+{x}_{r}}{2}, {\Delta }_{i}=\mathrm{m}\mathrm{i}\mathrm{n}\left({\Delta }_{l}, {\Delta }_{r}\right) $$ (2)

      Δ=1.0为例,假设D=$ \left\{\mathrm{9.0, 4.0, 3.9, 3.7}\right\} $,用该方法构建满足Δ的Haar-N树(N=1)的过程如表 1所示(第0层的xΔc分别表示算法开始前的原始数据D、对应D中每个数据的最大绝对值误差及概要数据)。从表 1中可以看到,大于0的系数有3个,这些系数将作为概要数据存储。

      表 1  构建满足Δ的Haar-N

      Table 1.  Construct a Haar-N Tree Satisfying Δ

      层次 x Δ c
      0 $ \left\{\mathrm{9.0, 4.0, 3.9, 3.7}\right\} $ $ \left\{\mathrm{1, 1}, \mathrm{1, 1}\right\} $
      1 $ \left\{\mathrm{6.5, 3.8}\right\} $ $ \left\{\mathrm{1, 0.9}\right\} $ $ \left\{\mathrm{2.5, 0}\right\} $
      2 $ \left\{5.15\right\} $ $ \left\{0.9\right\} $ $ \left\{1.35\right\} $
      3 $ \left\{1.35\right\} $

      情形1和情形2的区分方法是通过各结点的xi允许的误差值决定的,因此,本节构建满足Δ的Haar-N树的方法可以为某一些原始数据设置特定的Δ。,如设定上述例子中的3.9的Δ=0,其他值的Δ=1,则它的构建过程如表 2所示,其中,结果为大于0的系数有4个。

      表 2  为某个元素设定特定误差界限的构建过程

      Table 2.  Setting a Specific Error Bound for an Element

      层次 x Δ c
      0 $ \left\{\mathrm{9.0, 4.0, 3.9, 3.7}\right\} $ $ \left\{\mathrm{1, 1}, \mathrm{0, 1}\right\} $
      1 $ \left\{\mathrm{6.5, 3.8}\right\} $ $ \left\{\mathrm{1, 0}\right\} $ $ \left\{\mathrm{2.5, 0.1}\right\} $
      2 $ \left\{5.15\right\} $ $ \left\{0\right\} $ $ \left\{1.35\right\} $
      3 $ \left\{1.35\right\} $

      由于每当到达两个数据后,算法就会对前面的数据进行总结,判断是否生成概要数据,所以算法可以处理任意特征的流数据,尤其对于具有局部冗余性的数据可以表现出更好的压缩效果。另外,GH-Synopses算法可以单独为某值域的或某时间段的数据元素设置特殊的最大绝对值误差预值,如对于某些较为敏感的数据,可以单独为其设置较小的最大绝对值误差预值,因此,算法在最大绝对值误差界限下有良好的扩展性。

      3) 融入贪心策略。考虑前面两个部分所述的过程中,变换某些系数值可以使得生成的概要数据数量更少。如令表 1中层次1的平均值6.5变成3.8,即6.5加上增量值-2.7等于3.8,再对$ \left\{\mathrm{3.8, 3.8}\right\} $进行Haar小波变换的差值将是0,减少了局部的概要数据产生。在这个过程中,对一个平均值进行变换需要记录它的增量,为了避免额外存储这个增量,结合Haar-NSi中各个结点不同的重构方式(重构方式详见§1.3),令增量值为k×c(k∈Z),隐藏在Cj中,其中,k与各结点重构方式有关,jk有关(假设k=-1时可以避免下一步产生概要数据,则将c值存储在Cj(j%N=3)中。如对表 1中的x值6.5进行变换,显然k=-‍1时,x+k×c=6.5-1×2.5=4.0最接近3.8,下一步不会产生概要数据,此时,需要将2.5的值存储在C3中才能使重构后的近似数据在误差预值内)。另外,k应当满足k < (N-1)/2,这是因为kN有关,而k可以为负数,所以必须k < (N-1)/2。通过以上方式隐藏了增量值,并且实现了产生局部最少的概要数据。

      根据以上的分析,具体的贪心策略描述为:在构建满足Δ的Haar-N树过程中,对于每一个存在cj > 0的Si,若与它的兄弟结点Si+1满足情形2,那么寻找一个k(|k| < (N-1)/2),使得|k×ci-ci+1|的值最小。因为当|k×ci-ci+1|的值最小时,若有xl=k×cixr=ci+1满足情形1,那么SiSi+1的父结点就不需要生成概要数据,即生成局部最少的概要数据。在这个贪心策略中,任何一个Si的计算只会影响后续构建出的结点S,与之前的状态无关,即没有后效性,因此是安全的策略。

    • 对于具有n个元素的原始数据集D,GH-Synopses算法的空间复杂度主要考虑概要数据集B和概要数据结构Haar-N树两个方面。(1)概要数据集BB是GH-Synopses算法的结果,该结果可通过写入磁盘等方式移出内存不成为GH-Synopses的空间开销,这部分可以忽略不计;(2)概要数据结构Haar-N树:算法的执行过程可认为是构建一棵Haar-N树,其构建过程是对每出现一对左右孩子结点则构建一个父结点,当父结点构建完成后,这对左右孩子结点不再参与计算,这两个结点将被删除。对于n个原始数据元素,Haar-N需要构建的结点为: 前n/2个元素需要1个结点,第n/2+1~3n/4个元素需要1个结点,第3n/4+1~7n/8个元素需要1个结点,以此类推,直至第n-1~n个元素需要1个结点。因此,GH-Synopses的空间复杂度为O‍(lgn)。

      对于时间复杂度,GH-Synopses算法的运行时间为构建各个结点的时间总和。GH-Synopses算法构建结点的过程是通过左右孩子结点进行Haar小波变换得到xΔ值,没有复杂的计算,构建一个结点的开销可当作是常数,总时间开销与构建的结点的总数是线性关系。从Haar-N树中可以看出,对于n个元素的数据集,共需要n/2个最底层的系数结点,n/4个次底层的系数结点,以此类推,直到最顶层只有一个系数结点,需要构建n/2+n/4+…+1=n次,时间复杂度为O(n)。

    • 利用Haar-N树对压缩后数据进行重构。对于Haar-N树中每个Si中包含的Cj,根据CjSi中的位置,有不同的重构方式。通往左子树,重构方式为:

      $$ {P}_{l}=\left\{\begin{array}{l}c, (j-1)\mathrm{\%}N=0\\ c-c\times \frac{j\mathrm{\%}N}{2}, (j-1)\mathrm{\%}N\mathrm{\%}2\ne 0\\ c+c\times \frac{(j-1)\mathrm{\%}N}{2}, (j-1)\mathrm{\%}N\mathrm{\%}2=0\end{array}\right. $$ (3)

      通往右子树,重构方式为:

      $$ {P}_{r}=\left\{\begin{array}{l}-c, (j-1)\mathrm{\%}N=0\\ -c-c\times \frac{j\mathrm{\%}N}{2}, (j-1)\mathrm{\%}N\mathrm{\%}2\ne 0\\ -c+c\times \frac{(j-1)\mathrm{\%}N}{2}, (j-1)\mathrm{\%}N\mathrm{\%}2=0\end{array}\right. $$ (4)

      式中,PlPr分别表示通往左子树和右子树的重构方式;j图 1Cj的下标;cCj的值。

      图  1  N=3的Haar-N

      Figure 1.  Haar-N Tree with N=3

      式(3)和式(4)均基于取模的规则:包含在同一个Si中的N个系数Cj,对于奇数的j,系数c乘以1、2、3‍…;而对于偶数的j,则c乘以-1、-2、-3…。这样的方式具有可扩展性,若N=5时,C4C5仍然适用式(3)和式(4)。当N=3时,通过式(3)和式(4)计算得出的值如表 3所示。

      表 3  S1中各Cj的重构方式

      Table 3.  Reconstruction of Each Cj in S1

      j Pl Pr
      2 0 -2c
      1 +c -c
      3 +2c 0

      概要数据为图 1中的C0C1C8,其中,C0=1,C1=2,C8=3,根据式(3)和式(4)重构d0d1d2d3的过程如表 4所示。d0的重构方式是由上而下将路径上所有能到达d0Si相加,即S0+S1+S2S0只有一个系数C0S0=C0S1中概要数据为C1,由于S1下一步必须通往左子树,到达S2才能最终到达d0,使用式(3),得到Pl‍=C1,相乘的系数为1,S1=1×C1;同样,S2也是通往左子树才能到达d0,采用式(3)得到Pl=2×C8;同理,d1d2d3采用这种方式进行重构。

      表 4  重构d0d1d2d3的过程

      Table 4.  Process of Reconstructing d0, d1, d2 and d3

      d 重构过程 结果
      d0 C0 + 1×C1 + 0 = 1 + 2 + 0 3
      d1 C0 + 1×C1 - 0 = 1 + 2 - 0 3
      d2 C0 - 1×C1 + 0×C8 = 1 - 2 + 0 -1
      d3 C0 - 1×C1 + 2×C8 = 1 - 2 - 2×3 -7
    • 基于数据的可用性,本文选取深圳市2015-01-05—2015-01-30的路段行驶速度数据进行压缩实验。数据首先通过浮动车地图匹配进行处理[13],速度估计模型采用文献[14]。涉及路段共有120 679条,设置速度估计模型的数据采样间隔为2 min,每条路段一天产生720条行驶速度数据,所有路段一天的数据总量为86 888‍ 880条,约700 MB。

      为讨论不同的数据值变化程度对结果的影响,实验选取了有不同交通特征的路段:W1(667 m)、W2(939 m)、W3(262 m),行驶速度波动度W1 < W2 < W3图 2所示,时间为2015年1月5日,采样间隔为2 min。

      图  2  路段W1W2W3一天的行驶速度波动度

      Figure 2.  Road Link Travel Speed Fluctuations of Roads W1, W2, W3

      本实验并没有对交通流数据的空间异质性(交通流的空间异质性是动态变化的)进行专门设计,如果需要针对不同地区设计专用的流数据压缩算法,可以考虑数据的空间相关性和异质性,但是就交通数据而言,其空间相关性和异质性是不稳定的,因此,仅针对不断增长的数据量及数据冗余问题进行算法设计。

      为验证GH-Synopses算法的性能,实验比较了现有几个最大绝对值误差控制条件的Haar小波类概要算法,各算法说明如表 5所示。

      表 5  几种Haar小波类概要算法说明

      Table 5.  Description of Several Haar Wavelet ClassSummary Algorithms

      算法 时间复杂度 空间复杂度 概要结构 限制
      F-Shift[2] O(n) O(lgn) Haar
      S+-Shift[2] O(n) O(n) Haar+
      M[4] O($ {\left(\frac{\Delta }{\delta }\right)}^{2}n $) O($ \frac{\Delta }{\delta }\mathrm{l}\mathrm{g}n+n) $ Haar+
      R[3] O$ \left(\frac{{n}^{2}}{\mathrm{l}\mathrm{g}n}\right) $ O(lgn) Haar
      GH-Synopses O(n) O(lgn) Haar-N
    • 压缩质量(生成的概要数据数量)是衡量GH-Synopses算法有效性主要考虑的指标,实验设置了不同的最大绝对值误差预值Δ,分别统计了GH-Synopses算法生成路段W1W2W3以及所有路段W的概要数据数量,同时,比较了§2.1中提到的其他4种算法,结果分别如图 3(a)~图‍3‍(d)所示,其中,图 3(d)全部路段的路段数量为120 679条。

      图  3  概要数据数量

      Figure 3.  Quantity of Synopses Data

      图 3中的结果表明,无论是哪条路段,在不同的Δ下,S+-Shift总是有最好的结果,GH-Synopses次之,原因是S+-Shift算法先自下而上构建Haar+树存储所包含的原始数据信息,再自上而下地生成概要数据,从而在使用贪心选择判断一个结点是否需要产生概要数据的时候,比GH-Synopses拥有更多的信息,因此,结果往往比GH-Synopses好。但是S+-Shift算法的空间复杂度是O(n),每次只能等数据集达到一定长度后统一处理,不能进行实时处理,而GH-Synopses的空间复杂度是O(lgn),并且可以实时处理流数据。M算法的结果取决于参数值Δ/δ的大小,Δ/δ越大,则得到的概要数据越少;R算法是从有限制的Haar小波系数中做动态规划的选择,由于小波系数值受到限制,没有得到更好的结果。

      $ {\epsilon }_{W} $的计算方法如下:

      $$ {\epsilon }_{W}=2\times \sum\limits_{i}^{W}{Q}_{i}/\sum\limits_{i}^{W}{L}_{i}\times 100\mathrm{\%} $$ (5)

      式中,W表示所有路段的数量;Li表示第i条路段的行驶速度数据集长度;Qi表示生成第i条路段行驶速度的概要数据数量(一个概要数据由数据值和索引值组成,故在压缩率上,Qi需要乘以2)。

      GH-Synopses算法在不同Δ下压缩所有路段的压缩率εW表 6所示。表 6的结果表明,本文方法对路段行驶速度的压缩率在Δ=0.5 m/s时达到6.60%~7.84%,Δ值每增加0.5,压缩率提高约1%。另外,压缩率与数据集长度无关,通过对比不同Δ值下的压缩率可以发现,压缩率εW存在一定波动,但并非随数据集长度增加而降低,如当Δ=0.5 m/s、Li=29Li‍=211时,比Δ=0.5 m/s、Li=210Li‍=212有更好的压缩率。

      表 6  GH-Synopses算法压缩全部路段数据的压缩率

      Table 6.  Compression Ratio of the GH-Synopses for All Road Links

      Δ/(m·s-1) 压缩率/%
      Li=29 Li=210 Li=211 Li=212
      0.5 6.60 6.96 6.54 7.84
      1.0 5.36 5.80 5.06 6.44
      1.5 4.54 4.80 4.82 5.10
      2.0 3.88 4.16 3.64 4.26
      2.5 3.14 3.32 3.02 3.74
    • 在时间效率的验证上,首先,比较了表 5中5种算法处理单条路段数据的运行时间;然后,对比处理所有路段数据的运行时间。

      处理单条路段数据的运行时间对比如图 4所示。由于概要数据生成算法的运行时间只与数据量有关,所以不需要讨论数据值的情况。

      图  4  处理单条路段数据的运行时间

      Figure 4.  Running Time of Processing Single Data

      图 4中可以看出,运行时间由短到长分别为F-Shift、GH-Synopses、S+-Shift、M(δ=0.25)和R算法,前4者在数据量为214下都能保持在0.01 s内。S+-Shift的执行时间接近GH-Synopses,是因为S+-Shift的过程遍历了两遍Haar+树,而GH-Synopses在自底向上构建Haar-N树的过程中,只对生成了概要数据的孩子结点进行了贪心策略的计算,计算量比S+-Shift少。算法M的运行时间由参数δ决定,δ越小,则Δ/δ越大,即需要更多的计算量。R是一种动态规划的算法,其时间复杂度为O‍(n2),运行时间呈指数增长。综上所述,算法F-Shift、GH-Synopses、S+-Shift和M(Δ/δ < 4)均适合用于处理流数据。

      对于处理全部路段的行驶速度数据,实验分别为每一条路段执行GH-Synopses算法,总运行时间是在串行的运行时间下,对各路段行驶速度数据生成概要数据的运行时间之和。处理全部路段的行驶速度数据的执行时间及GH-Synopses运行时间增长趋势图如图 5所示。

      图  5  处理所有路段数据所需的总运行时间

      Figure 5.  Total Running Time of Processing all Road Data

      图 5结果表明,用GH-Synopses算法分别生成各路段行驶速度的概要数据所需要的总运行时间能够跟上数据到达的速度,如对于长度为$ W\times {2}^{13} $的数据集,仅用时35 s左右,且运行时间与数据集大小呈线性趋势,即数据集每增长2倍,运行时间也增长大约2倍。因此,GH-Synopses算法在执行时间上是可靠的。

    • 实验以路段W1产生的行驶速度数据为例(2015年1月5日),分别设置最大绝对值误差预值为1 m/s、1.5 m/s和2 m/s,对GH-Synopses产生的概要数据进行重构,重构后的数据与原始数据的结果如图 6所示。从图 6中可以看出,重构后的每一个数据误差均不会超过设定的误差预值,当误差预值等于1时,重构后的数据与原始数据最为接近,满足最大绝对值误差控制的条件。因此,本文算法所产生的概要数据是可靠的。

      图  6  原始数据与重构数据

      Figure 6.  Original Data and Reconstructed Data

    • 越来越多的传感器产生了大量的流数据,如果不存储这些数据将是巨大的浪费;而存储流数据,日积月累又将产生非常庞大的数据量,给数据的使用效率带来巨大挑战。为解决该问题,本文基于Haar小波概要方法,设计了一种新的流数据概要结构及算法——GH-Synopses。该算法在具备实时性的同时,还具有较高的压缩率和执行时间效率。通过路段行驶速度数据进行验证,结果表明该算法能够高效地压缩路段行驶速度数据。

      研究中发现,在同类型算法中,GH-Synopses算法在压缩质量上并非最好,这主要受限于贪心策略考虑局部最优而不是全局最优,未来可以考虑改进贪心策略。另外,实验结果得出了GH-Synopses算法对于处理波动度小的数据具有相对较好的效果,可以将GH-Synopses算法推广至其他具有显著时空关系的数据中,并考虑时空特征,获得更高效的压缩及重构质量。

参考文献 (14)

目录

    /

    返回文章
    返回