时间序列数据压缩算法简述

本文简单介绍了时间序列压缩任务的来源,压缩算法的分类,并对常见压缩算法的优缺点进行了简介,爱码士们快来一探究竟呀!

引言

时间序列数据是在许多应用程序和领域中生成的一种基本数据类型,例如金融、医疗保健、交通和智慧城市[1]。时间序列分析对于各种任务至关重要,包括异常检测、预测、分类和聚类等。然而,时间序列数据的庞大数量和复杂性可能对高效存储、检索和处理带来重大挑战[2]。

相比于传统的关系型数据库,时间序列数据库天生是为了时间序列数据处理而生。关系数据库往往采用传统的B+树存储结构以及行式存储的方式。这种存储结构的设计方案往往适合读多写少的场景,来提高数据查询性能,用以减少磁盘或者网络 I/O。

然而,在这种设计上,由于绝大部分设计和资源都是为了读取数据,在每插入一条新记录时,都要同步更新相应的存储结构。数据库往往还要先找到所要插入的数据位于B+ 树中的哪个节点,存储页面中的哪一个页,查看相应的键是不是已经存在等等,这都会大量增加插入操作的时间开销。因此,以目前时间序列数据库开源社区使用最为广泛的InfluxDB[3]为例,其采用了基于LSM树的存储结构,并对此进行了一些特异性优化开发,使得数据库写入的能力提高很多倍。

随着时间的推移,早期产生的数据所具有的价值会越来越低,对于时间序列数据库的应用场景之一监控场景来说,用户更可能仅仅关注当前时刻或近期内数据库的状态参数,而较早产生的数据会因时间积累越来越多且仅有较低概率会被查询。因此有必要对早期的数据进行一定程度的压缩,同时考虑到该类型数据查询价值较低,在提高压缩比的同时又能够尽可能保留原始数据的一些特征便成为了一个重要的问题。这样可以更好地对数据库资源合理规划、缓解数据库管理数据的压力,降本增效,更好的为数据的存储和查询赋能。

为了应对这些挑战,越来越需要专门的算法和数据结构来压缩并索引时间序列数据。数据压缩算法主要在数据压缩比、数据解压缩速度、数据压缩精度这几方面做权衡,指导了时间序列数据压缩的各种技术的发展。

数据压缩算法分类

对于时间序列数据,有几种常用的压缩算法。可以根据压缩再解压后是否丢失精度问题,将压缩算法分为两类:分别是无损压缩算法和有损压缩算法。

无损压缩算法的特点是压缩前后数据的完整性保持不变,即压缩后的数据可以完全恢复到压缩前的原始数据。常见的无损压缩算法包括:

  • 基于差分编码的算法[7,8]:差分编码算法通过计算相邻时间点之间的差异来压缩时间序列数据,减少冗余信息的存储。
  • 基于霍夫曼编码的算法[9,10]:使用变长编码,高频数据用较短的代码表示,而低频数据用较长的代码表示。

有损压缩算法通过去除一些冗余信息来达到较高的压缩率,但压缩后的数据不能完全恢复到原始数据,可能存在一定程度的误差。常见的有损压缩算法包括:

  • 基于小波变换的算法[11,12]:小波变换可以将时间序列数据分解成多个频率子带,提取时间序列数据的主要特征,然后通过编码对这些特征进行压缩。
  • 基于离散余弦变换的算法:离散余弦变换可以将时间序列数据转换为频域信号,通过保留高频分量和抑制低频分量实现压缩。

广泛应用的压缩算法简介

  • Gorilla[13]是一种基于二进制元组编码的时间序列数据压缩算法。它的优点包括高压缩率、高压缩速度和较低的存储要求,但由于需要大缓冲区,可能会受到内存限制的影响。
  • LZ4[14]是一种通用数据压缩算法,也可用于时间序列数据压缩。其优点包括压缩速度快、压缩延迟低、压缩比好,但在一些特殊的时间序列数据分布中,可能会出现压缩性能不佳的情况。
  • Zstandard[15]是一种基于LZ77算法的压缩算法,适用于一般的压缩解压任务, 也可以用于时间序列数据的压缩。其优点是压缩比高,解压延迟低,压缩速度可调,但压缩时间可能较长。
  • Snappy[16]是一种快速压缩算法,适用于各种类型的数据,包括时间序列数据。其优点包括压缩速度高、压缩延迟低、压缩比可靠,但压缩比相对较低。
  • LFZip[17]是一种基于分段和拟合算法的时间序列数据压缩算法,具有良好的压缩比和速度。它的缺点是不能处理异常值和噪声,需要调整一些参数以适应 同的数据分布。
  • Chimp[18]是一种基于采样的时间序列数据压缩算法,具有高压缩比和速度,可以动态适应不同的数据分布。它的缺点是需要足够的采样频率来保证压缩精度,并且处理异常值的能力较弱。
  • Sprintz[19]是一种简单有效的无损数据压缩算法。其主要优点包括压缩比高、速度快、复杂度低。但是Sprintz算法对数据相关性的依赖度很高,需要额外的一些位来存储差异,导致存储量相对较低。

在 CnosDB 中应用压缩算法

在 CnosDB 中,可以在创建数据库时对特定的属性指定压缩方法,CnosDB 中支持的压缩方法包括:

  • Delta
  • Gzip
  • Bzip
  • Gorilla
  • Snappy
  • Zstd
  • Zlib
  • BitPack
  • SDT
  • DeadBand

语法结构如下:

CREATE TABLE TIMESERIES(
    column1 BIGINT CODEC(DELTA),
    name STRING CODEC(GZIP),
    age BIGINT UNSIGNED CODEC(NULL),
    marriage BOOLEAN,
    ID DOUBLE CODEC(GORILLA)
)

在创建数据库时,指定属性的类型后,附加一个CODEC(),括号内是压缩方法,来达到指定压缩方式的效果。

小结

时间序列的压缩主要还是围绕着时间序列的连续性好、相关性强的特点设计压缩算法,而由于数据规模通常较大,以一定精度损失换取极高压缩比的有损压缩算法更广泛地被应用。

本文简单介绍了时间序列压缩任务的来源,压缩算法的分类,并对常见压缩算法的优缺点进行了简介,在CnosDB中的应用也只是略有提及,感兴趣者可以查看参考文献中的内容。

参考文献

[1] FU T-C. A review on time series data mining [J]. Engineering Applications of Artificial Intelligence,2011,24(1):164-181.

[2] WLODARCZYK T W. Overview of time series storage and processing in a cloud environment [C] // 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings,[S.l.],2012:625-628.

[3] NAQVI S N Z,YFANTIDOU S,ZIMÁNYI E. Time series databases and influxdb[J]. Studienarbeit, Université Libre de Bruxelles,2017,12

[4] ANH V N,MOFFAT A. Index compression using 64-bit words[J]. Software: Practice and Experience,2010,40(2):131-147.

[5] GOLOMB S. Run-length encodings (corresp.) [J]. IEEE transactions on information theory,1966,12(3):399-401.

[6] RICE R F. Some practical universal noiseless coding techniques[M] // . 1979.

[7] CANDY J. A use of double integration in sigma delta modulation [J]. IEEE transactions on communications,1985,33(3):249-258.

[8] O’NEAL J. Differential pulse-code modulation (PCM) with entropy coding[J]. IEEE Transactions on Information Theory,1976,22(2):169-174.

[9] OSWAL S,SINGH A,KUMARI K. Deflate compression algorithm [J]. International Journal of Engineering Research and General Science,2016,4(1) :430-436.

[10] GAILLY J-L,ADLER M. GNU gzip [J]. GNU Operating System,1992.

[11] ZHANG Q,BENVENISTE A. Wavelet networks[J]. IEEE transactions on Neural Networks,1992,3(6):889-898.

[12] KINGSBURY N. Complex wavelets for shift invariant analysis and filtering of signals[J]. Applied and computational harmonic analysis,2001,10(3): 234-253.

[13] PELKONEN T,FRANKLIN S,TELLER J,et al. Gorilla: A fast, scalable, inmemory time series database [J]. Proceedings of the VLDB Endowment,2015, 8(12):1816-1827.

[14] COLLET Y,OTHERS. Lz4: Extremely fast compression algorithm[J]. code. google. com,2013.

[15]COLLET Y. Zstandard-fast real-time compression algorithm[J]. Github repository [online],2018.

[16] GUNDERSON S H. Snappy: A fast compressor/decompressor[J]. code. google. com/p/snappy,2015.

[17] CHANDAK S,TATWAWADI K,WEN C,et al. LFZip: Lossy compression of multivariate floating-point time series data via improved prediction [C] // 2020 Data Compression Conference (DCC),[S.l.],2020:342-351.

[18] LIAKOS P,PAPAKONSTANTINOPOULOU K,KOTIDIS Y. Chimp: efficient lossless floating point compression for time series databases [J]. Proceedings of the VLDB Endowment,2022,15(11):3058-3070.

[19] BLALOCK D,MADDEN S,GUTTAG J. Sprintz: Time series compression for the internet of things [J]. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies,2018,2(3):1-23

CnosDB简介

CnosDB是一款高性能、高易用性的开源分布式时序数据库,现已正式发布及全部开源。

欢迎关注我们的社区网站:https://cn.cnosdb.com

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/215013.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Failed to connect to gitee.com port 443: Time out 连接超时提示【Bug已完美解决-鸿蒙开发】

文章目录 项目场景:问题描述原因分析:解决方案:解决方案1解决方案2:解决方案3:此Bug解决方案总结解决方案总结**心得体会:解决连接超时问题的三种方案**项目场景: 导入Sample时遇到导入失败的情况,并提示“Failed to connect to gitee.com port 443: Time out”连接超…

Git:分布式版本控制系统的崛起与演变

简介 Git是一个开源的分布式版本控制系统,旨在有效、高速地处理从很小到非常大的项目版本管理。它是由Linus Torvalds于2005年创建的,最初是为了服务于Linux内核开发的版本控制需求。Git通过强大的分支功能、高效的缓存机制以及可扩展的架构设计&#xf…

分享81个节日PPT,总有一款适合您

分享81个节日PPT,总有一款适合您 81个节日PPT下载链接:https://pan.baidu.com/s/1V0feg5pZ8C1Szycy40CrUw?pwd6666 提取码:6666 Python采集代码下载链接:采集代码.zip - 蓝奏云 学习知识费力气,收集整理更不易…

BGP多跳及BGP4+

一、知识补充 1、BGP4 传统BGP-4只管理IPV4路由信息,对于使用其它网络程协议 (若IPV6等)的应用末给予支持。IETF对BGP-4扩展,提出BGP4,可以提供对IPV6、IPX和MPLS VPN的支持 (简单说: 扩展IPV6协议栈支持)。 2、全互联 在上一篇博文中提…

爬虫学习(一)

文章目录 文件目录结构打开文件操作 爬取网页的理解尝试 文件目录结构 打开文件操作 爬取网页的理解尝试 这个放回值为请求正常

C语言扫雷游戏

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、扫雷游戏的分析和设计1.1扫雷游戏的功能说明1.2数据结构的分析1.3文件结构设计 二、扫雷游戏的代码实现总结 前言 详细介绍扫雷游戏的思路和实现过程。 一…

泊车功能专题介绍 ———— 记忆泊车评价规程(征求意见稿)

文章目录 评价方法指标体系指标权重分配算分方法指标得分计算方法露天停车场一键召唤得分情况说明泊出能力得分情况说明水平划线车位——两侧存在静止车辆水平划线车位——两侧存在静止车辆且车位附近有静止直立儿童垂直划线车位——两侧存在静止车辆垂直划线车位——两侧存在静…

智能优化算法应用:基于JAYA算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用:基于JAYA算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于JAYA算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.JAYA算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…

Java基础语法之数组

数组的定义与初始化 数组的创建 大体上有如下三种创建方式: int[]array1 {1,2,3,4,5}; int[]array2 new int[]{1,2,3,4,5}; int[]array3 new int[5];一般创建框架就是T[ ]new T[ ];T是数组中元素的类型,T[ ]是数组类型 如果是double[],则对应new …

34、AD/DA

AD/DA介绍 AD(Analog to Digital):模拟-数字转换,将模拟信号转换为计算机可操作的数字信号 DA(Digital to Analog):数字-模拟转换,将计算机输出的数字信号转换为模拟信号 AD/DA转换…

已解决:虚拟机集群xsehll连接不上

问题描述: hadoop102能连上,hadoop103、hadoop104无法连接,以前都能连上,今天突然就连不上了 解决方案: 使用ifconfig命令查看有没有ens33 如果没有的话那就证明你的问题和我一样 依次使用以下命令: sys…

维基百科文章爬虫和聚类:高级聚类和可视化

一、说明 维基百科是丰富的信息和知识来源。它可以方便地构建为带有类别和其他文章链接的文章,还形成了相关文档的网络。我的 NLP 项目下载、处理和应用维基百科文章上的机器学习算法。 在我的上一篇文章中,KMeans 聚类应用于一组大约 300 篇维基百科文…

【WinForm.NET开发】演示:创建一个图片查看器 Windows 窗体应用

本文演示将创建一个 Windows 窗体应用程序,用于加载和显示图片。 Visual Studio 集成设计环境 (IDE) 提供了创建应用所需的工具。 1、先决条件 若要完成本教程,必须具有 Visual Studio。 请访问Visual Studio 下载页获取免费版本。 2、创建 Windows …

基于Java SSM框架实现美好生活九宫格日志网站系统项目【项目源码+论文说明】

基于java的SSM框架实现美好生活九宫格日志网站系统演示 摘要 21世纪的今天,随着社会的不断发展与进步,人们对于信息科学化的认识,已由低层次向高层次发展,由原来的感性认识向理性认识提高,管理工作的重要性已逐渐被人…

最强Node js 后端框架学习看这一篇文章就够

距离上次认真花时间写作,似乎已经过了许久许久,前端讲了一个新框架 ,叫 Nest.js 下方是课件,有过一定开发经验可跟随视频学习 B站 地址 : https://www.bilibili.com/video/BV1Lg4y197u1/?vd_sourcead427ffaf8a5c8344…

6-55.汽车类的继承

根据给定的汽车类vehicle(包含的数据成员有车轮个数wheels和车重weight)声明,完成其中成员函数的定义,之后再定义其派生类并完成测试。 小车类car是它的派生类,其中包含载人数passenger_load。每个类都有相关数据的输出…

【预测工具】不须编码的预测和数据可视化工具

有一天,我的同事问我,他应该如何做一个快速预测模型而不是Excel,并产生比线性回归或Excel图中的那些简单方程更好的结果。这是我的答案。 TableCurve 2D (Image by author) Sigmaplot很早以前就推出了这个软件。它已被广泛用于在数据中寻找最…

JDK1.8_X64在LINUX下安装

JDK1.8在LINUX下安装步骤: 在/usr/lib/目录下新建jvm文件夹,如果已有jvm文件夹,则将之前的JDK版本删除,即在jvm目录下执行命令:rm–rf *将JDK文件jdk-8u40-linux-x64.gz拷贝到/home/目录下;在/home/目录下…

Nginx的反向代理与负载均衡

概念介绍 1). 正向代理 正向代理服务器是一个位于客户端和原始服务器(origin server)之间的服务器,为了从原始服务器取得内容,客户端向代理发送一个请求并指定目标(原始服务器),然后代理向原始服务器转交请求并将获得的内容返回给客户端。 …

2023.12.3 分布式SQL查询引擎-Presto

目录 目录 1.Prosto简介 Apache Hadoop-MapReduce Apache Hive 2.Presto的优缺点 3.个人自用启动服务 个人自用启动服务 3.Presto的架构 4.presto和hive的区别 5.presto优化 6.Presto-内存调优 1.Prosto简介 Apache Hadoop-MapReduce 优点:统一、通用、简…