Many modern applications produce massive streams of data series that need to be analyzed, requiring efficient similarity search operations. However, the state-of-the-art data series indexes that are used for this purpose do not scale well for massive datasets in terms of performance, or storage costs. We pinpoint the problem to the fact that existing summarizations of data series used for indexing cannot be sorted while keeping similar data series close to each other in the sorted order. To address this problem, we present Coconut, the first data series index based on sortable summarizations and the first efficient solution for indexing and querying streaming series. The first innovation in Coconut is an inverted, sortable data series summarization that organizes data series based on a z-order curve, keeping similar series close to each other in the sorted order. As a result, Coconut is able to use bulk loading and updating techniques that rely on sorting to quickly build and maintain a contiguous index using large sequential disk I/Os. We then explore prefix-based and median-based splitting policies for bottom-up bulk loading, showing that median-based splitting outperforms the state of the art, ensuring that all nodes are densely populated. Finally, we explore the impact of sortable summarizations on variable-sized window queries, showing that they can be supported in the presence of updates through efficient merging of temporal partitions. Overall, we show analytically and empirically that Coconut dominates the state-of-the-art data series indexes in terms of construction speed, query speed, and storage costs.
翻译:许多现代应用程序产生大量需要分析的数据序列流, 需要高效的相似搜索操作。 但是, 用于此目的的最先进的数据序列指数在性能或存储成本方面对大规模数据集来说并不十分适合。 我们将问题归结为以下事实, 即用于编制索引的现有数据序列总和无法在排序顺序上保持相似的数据序列的相互接近。 为了解决这个问题, 我们提出第一个基于可排序的分析性速度总和的数据序列指数, 以及用于索引和查询流序序列的第一个有效解决方案。 科科努特的第一个创新是一个反向的、 可排序的数据序列总和, 用来组织基于 Z- 顺序曲线的数据序列, 使相似的序列在排序顺序上相互接近。 因此, 科努特能够使用大量加载和更新技术, 依靠对快速构建和保持一个以大型连续的指数, 使用大型的测序盘 I/ Os 。 然后我们探索基于前和中位的分解政策, 用于编制和查询流序列的索引序列。 科科科特的首次创新是一个反向反向反向、 可排序的、 可排序的数据集序的数据集列的序列缩缩缩缩缩缩算, 显示我们最后显示以正缩缩缩缩缩缩缩缩缩缩缩缩缩的计算。