最适合极大时间序列的品种索引数据结构

我想问问其他SO'ers对于用于索引时间序列的最佳品种数据结构的意见（又名列式数据，又名扁平线性）。最适合极大时间序列的品种索引数据结构

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

普通离散（每个样品取与公共频率）
不规则离散（样品取在arbitary时间点），将被要求

查询：

在时间范围内的所有值[T0，T1]
在时间范围[T0，T1]是大于/小于V0
中的所有时间值中的所有值范围[T0，T1]是在数值范围[V0，V1]

的数据集由概括的时间序列（其排序越过不规则离散）的，和多变量的时间序列。所讨论的数据集大小约为15-20TB，因此处理是以分布式方式执行的 - 因为上述某些查询将导致数据集大于任何一个系统上可用的物理内存量。

在这种情况下的分布式处理还意味着调度所需的数据特定计算以及时间序列查询，以便计算尽可能接近数据发生 - 从而减少节点到节点的通信类似于map/reduce范例） - 在计算和数据的短时间内非常关键。

该指数应该能够应对的另一个问题是，绝大多数数据是静态/历史（99.999％），但是每天增加新数据，请考虑“在现场传感器“或”市场数据“。这个想法/要求是能够以尽可能低的延迟更新任何正在运行的计算（平均值，garch等），其中一些运行计算需要历史数据，其中一些数据将超过可合理缓存的数据。

我已经考虑过HDF5，对于较小的数据集，它可以很好/有效地工作，但随着数据集变大而开始拖动，而且前端没有本地并行处理功能。

寻找建议，联系，进一步阅读等。（C或C++的解决方案，库）

来源

2012-04-02 Xander Tulip

类型1-3的查询通常被称为“正交范围报告”。 – oldboy 2012-04-11 15:08:25

http://dba.stackexchange.com/questions/16583/using-an-rdbms-for-querying-tenth-of-terabytes-of-time-series-data – 2012-04-16 20:16:27

@Martin：谢谢你，但问题与只有一把锤子就是一切看起来像钉子 - 在高度面向db/dba的Q/A网站中提出这样一个问题，会带来轻微的偏见。 – 2012-04-17 05:25:21

总体思路：

问题1是相当普遍的：创建一个适合你的RAM，并有链接索引到辅助存储器上的数据（数据结构：B-Tree family）。由于数据太大，问题2/3非常复杂。您可以将数据划分为时间范围并计算该时间范围的最小/最大值。使用这些信息，您可以过滤掉时间范围（例如，范围的最大值为50，并且您搜索v0> 60，那么时间间隔不存在）。其余的需要通过查看数据进行搜索。效果在很大程度上取决于数据的变化速度。

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

来源

2012-04-02 07:56:57

使用具有时间序列的b-树结构的问题是绝大多数时间序列模型的“连续”值。例如：30度的房间温度在达到20之前需要下降到25度，b-树不使用这种见解，因此对于时间序列的索引是无效的。对于问题1， – 2012-04-16 02:28:31

，您的评论对我没有意义。如果您想要在温度为30度的所有时间点进行搜索，则必须先指定您获得的数据。关于问题2和3 - 我没有看到矛盾。它实际上假定数据是连续的 - 否则使用最小值/最大值来确定数据在中间不起作用。 – 2012-04-17 11:57:14

请重新阅读我的原创评论给你。如果你过去曾使用过类似的数据，那么它应该是有意义的。 – 2012-04-18 06:20:07

您可能会想要使用某种类型的大型平衡树。像Tobias提到的那样，B树是解决第一个问题的标准选择。如果你也关心如何快速插入和更新，那么在麻省理工学院和CMU等地，有很多新的工作正在进入这些新的“缓存遗忘B树”。对于这些事情的实施上进行了一些讨论，查找Tokutek DB，他们已经得到了一些很好的介绍如下所示：

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

问题2和3是在一般的要困难得多，因为它们涉及更高维度范围搜索。这样做的标准数据结构是range tree（它以O（n log^d（n））存储为代价给出O（log^{d-1}（n））查询时间。你一般会而不是想要使用k-d树来做这样的事情。尽管kd树具有最优的O（n）存储成本是事实，但是如果仅仅只有你才能比O（n^{（d-1）/ d}）更快地评估范围查询使用O（n）存储。对于d = 2，这将是O（sqrt（n））时间复杂度;坦白地说，如果你有10^10个数据点（谁希望等待O（10^5）磁盘读取在一个简单的范围查询上完成，那么它不会削减它）

幸运的是，它听起来像你真的不需要太担心一般情况。因为所有数据都来自时间序列，所以每个时间坐标最多只能有一个值。假设，你可以做的只是使用范围查询来拉取点的间隔，然后在后处理过程中逐点应用v约束。这将是我会尝试的第一件事（在获得一个好的数据库实现之后），如果它工作，那么你就完成了！如果继续运行[t0，t1] x [-infty，+ infty]中的点数大于[t0中的点数的数量级的情况下尝试优化后两个查询，，t1] x [v0，v1]。

来源

2012-04-14 13:30:48 Mikola

另一方面，在价值2000美元的硬盘（20TB *大约100美元/ TB，以今日价格计算）的情况下，在存储装置中使用额外的对数因子（假设没有大-O常数）为80,000美元。在程序员成本不到一年的时间里，这可能是值得的，但祝你的经理能够以这种方式看待事情。 – oldboy 2012-04-14 14:24:57

@mikola：确实很有趣！任何时间序列索引结构都可以利用值的固有价值结构进行建模，值得一看。 – 2012-04-16 02:29:52

由你自己来实现这将会非常耗时和复杂。我建议你使用Cassandra。 Cassandra可以为您提供横向扩展性，冗余度，并允许您在未来运行复杂的地图缩减功能。要了解如何在卡桑德拉存储时间序列，请看看： http://www.datastax.com/dev/blog/advanced-time-series-with-cassandra 和http://www.youtube.com/watch?v=OzBJrQZjge0。

来源

2012-04-18 01:48:14

考虑到基本要求，延迟和数据大小，管理的任何东西显然都不足。 – 2012-04-18 06:18:37

最适合极大时间序列的品种索引数据结构

回答

相关问题