indexing - 如何优化压缩时间序列数据集的倒排索引
问题描述
我正在尝试以 25% 的压缩率压缩时间序列数据集。这对我来说变成了仇杀。
数据是 1 个月内的 1 分钟间隔历史股票报价(参见数据集注释),缺失数据为 0。这相当于大约 9000 个 uint32_t 类型的数据点(我不做小数)
我的第一次尝试是对所有数据使用 FastPFor 压缩。这导致了约 80% 的压缩比。还不够好。所以 -
我首先摆脱所有时间戳(明显)
然后我对历史数据进行了排序并删除了所有重复项。这将唯一值的数量从 ~ 5000 减少到 1000。从那里,我使用差分SIMD 压缩算法进一步压缩它。这些也有点包装。这导致最终约 5% 的压缩比。伟大的!问题来了。
要重建数据集,您必须能够将其按顺序放回原处。我的想法是为上面每个处理过的值设置倒排索引——每个索引都指向它的原始位置。这当然只是添加了 9000 个数字。这使尺寸几乎达到原始尺寸。
例子:
Values Indexes
10 ===> 40, 20, 55, 100, 56, 21
25 ===> 1, 5
...
结果,我尝试压缩倒排索引。
- 对它们进行排序
- 去掉与前一个值 (RLE) 相比 +1 的任何值
- 使用 Lemire 的 SIMDCompression github 压缩每个索引列表(我还尝试了他的FastPFor算法)
不幸的是,这种压缩索引的尝试并不好。在实际压缩使用每个整数 20-64 位之后,它只产生了约 75% 的压缩率。请注意,之前我提到我使用的是 32 位数字。压缩使索引列表只有 1 个数字,是其原始大小的 2 倍(我希望它保持不变)。
使用倒排索引的尝试是徒劳的——当它与原始大小相当时,不足以证明额外处理是合理的。
我还有一些其他的想法:
确定最常见的数字序列,使用“霍夫曼”类型编码,您可以在其中指定某个值来表示它。
压缩算法在处理更多数据时效果更好 - 可能将所有索引连接到 1 个数组中,然后压缩一次?
压缩倒排索引的最佳方法是什么?
有理论上的最小压缩吗?
你知道我可以用什么方法来代替这个吗?
任何输入表示赞赏。
示例数据
- 使用索引“quote --> [indexes]”格式化的股票价格- (不对索引进行处理)
笔记
- 索引的使用将仅用于重建数据集,而不用于任何其他查询。
解决方案
整个排序的事情似乎毫无意义。
我取了你的 8000(不是 9000)值系列,取了差异,并将它们写为可变长度整数,产生大约 14,000 个字节。然后我用 gzip 压缩得到大约 6000 字节。你没有说你的 25% 的起点是什么,但如果是四字节二进制整数(32,000 字节),那么这种方法会将其减少到 20% 以下。
推荐阅读
- javascript - 重复 if 语句到 for 循环内的一个干净的 if 语句中
- java - SwaggerUI 响应示例不适用于 mediaType JSON
- python - 使用 bazel py_binary 传递 python 命令行参数
- javascript - React Material UI ListItem 点击
- spring-boot - 2 个映射表之间的 HQL 连接并以 dto 类型返回
- aws-lambda - 从 lambda 调用 DynamoDB 停止死亡,甚至没有错误
- android - 在我的适配器中获取数据位置索引 21- 大小 20 时出错
- c# - 是否有接受 Span 的 MemoryStream
或内存 ? - python - 带有 select.select() 的套接字客户端
- java - 为经常运行的代码创建私有静态对象与实例化对象是否有价值?