针对极大时间序列的最佳索引数据结构

Question

我想问一些SO'ers他们关于用于索引时间序列的最佳数据结构的意见(也就是列式数据,也就是扁平线性).

基于采样/离散特征存在两种基本类型的时间序列:

1. 定期离散(每个样本采用共同频率)

2. 不规则的离散化(样本在任意时间点进行)

需要的查询:

1. 时间范围内的所有值[t0,t1]

2. 时间范围[t0,t1]中的所有值都大于/小于v0

3. 时间范围[t0,t1]中值范围为[v0,v1]的所有值

数据集包括汇总的时间序列(通过不规则离散化的那种)和多变量时间序列.所讨论的数据集大小约为15-20TB,因此处理以分布式方式执行 - 因为上述一些查询将导致数据集大于任何一个系统上可用的物理内存量.

此上下文中的分布式处理还意味着调度所需的数据特定计算以及时间序列查询,以便计算可以尽可能接近数据发生 - 从而减少节点到节点的通信(有点类似于map /减少范式) - 在计算和数据的短暂接近是非常关键的.

该指数应该能够应对的另一个问题是,绝大多数数据是静态/历史性的(99.999 ...%),但是每天都会增加新数据,想想"在现场传感器"或"市场数据".想法/要求是能够以尽可能低的延迟更新任何正在运行的计算(平均值,garch等),其中一些运行计算需要历史数据,其中一些将超过可以合理缓存的数据.

我已经考虑过HDF5,它对于较小的数据集效果很好/有效但随着数据集变大而开始拖动,前端也没有本机并行处理功能.

寻找建议,链接,进一步阅读等(C或C++解决方案,库)

Answer 1

您可能想要使用某种类型的大型平衡树.像托比亚斯提到的那样,B树将是解决第一个问题的标准选择.如果你也关心快速插入和更新,那么在麻省理工学院和CMU这样的地方有很多新的工作要做到这些新的"缓存遗忘的B树".有关这些内容实现的一些讨论,请查看Tokutek DB,他们有很多很好的演示文稿,如下所示:

http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf

问题2和3通常要困难得多,因为它们涉及更高维度范围的搜索.执行此操作的标准数据结构将是范围树(以O(n log ^ d(n))存储为代价提供O(log ^ {d-1}(n))查询时间.你通常不希望使用kd树来做这样的事情.虽然kd树确实具有最佳的O(n)存储成本,但事实是如果你只是你不能比O(n ^ {(d-1)/ d}更快地评估范围查询)使用O(n)存储.对于d = 2,这将是O(sqrt(n))时间复杂度; 并且坦率地说,如果你有10 ^ 10个数据点(谁想要在一个简单的范围查询上等待O(10 ^ 5)磁盘读取完成,那么它不会削减它？)

幸运的是,这听起来像你的情况,你真的不需要担心一般情况.由于您的所有数据都来自时间序列,因此每个时间坐标最多只能有一个值.假设,您可以做的只是使用范围查询来拉出一些点间隔,然后在后期处理过程中逐点应用v约束.这将是我尝试的第一件事(在获得良好的数据库实现之后),如果它有效,那么你就完成了!这真的只是有意义的尝试优化后的两个查询,如果你继续运行到哪里点的[T0,T1]×[-infty,+ infty]的数量级比点的数量较大的订单[T 0的情况下,t1] x [v0,v1].

Answer 2

总体思路：

问题 1 相当常见：创建一个适合 RAM 的索引，并链接到辅助存储上的数据（数据结构：B 树系列）。由于数据太大，问题 2 / 3 非常复杂。您可以将数据划分为时间范围并计算该时间范围的最小值/最大值。使用该信息，您可以过滤掉时间范围（例如，范围的最大值为 50，并且您搜索 v0>60，则时间间隔超出）。剩下的就需要通过资料去查找了。有效性很大程度上取决于数据变化的速度。

您还可以通过组合较低级别的时间范围来执行多个索引，以更快地进行过滤。