Efficient Similarity Join over Multiple Stream Time Series
Efficient Similarity Join over Multiple Stream Time Series
复制标题
多个流时间序列上的高效相似性连接
DOI：
10.1109/tkde.2009.27
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
Xiang Lian
中科院分区：
文献类型：
--
作者：
Lei Chen;Xiang Lian
时间序列数据库中的相似性连接（SJ）具有广泛的应用，例如数据清理和挖掘。具体来说，SJ 查询从两个时间序列数据库中检索彼此 epsiv 匹配的所有（子）序列对，其中 epsiv 是匹配阈值。以前关于这个问题的工作通常考虑静态时序数据库，其中查询是在基于静态数据构建的基于磁盘的多维索引上执行的，或者是通过没有索引的嵌套循环连接（NLJ）执行的。多流时间序列上的SJ，从流时间序列中连续输出成对的相似子序列，强烈要求低内存消耗、低处理成本以及本身能够适应时变流数据的查询过程。这些要求使静态数据库中的现有方法失效。在本文中，我们提出了一种高效且有效的方法来增量地在多个流时间序列中执行 SJ。特别是，我们提出了一种新颖的方法，即基于自适应半径的搜索（ARES），它可以回答相似性搜索而不会出现误报，并且可以无缝集成到 SJ 处理中。最重要的是，我们为ARES提供了一个正式的成本模型，基于该模型ARES可以适应数据特征，实现最小数量的细化候选对，从而适合流处理。此外，根据成本模型，我们利用为流时间序列构建的节省空间的概要来进一步减少候选集。大量的实验证明了我们提出的方法的效率和有效性。
Similarity join (SJ) in time-series databases has a wide spectrum of applications such as data cleaning and mining. Specifically, an SJ query retrieves all pairs of (sub)sequences from two time-series databases that epsiv-match with each other, where epsiv is the matching threshold. Previous work on this problem usually considers static time-series databases, where queries are performed either on disk-based multidimensional indexes built on static data or by nested loop join (NLJ) without indexes. SJ over multiple stream time series, which continuously outputs pairs of similar subsequences from stream time series, strongly requires low memory consumption, low processing cost, and query procedures that are themselves adaptive to time-varying stream data. These requirements invalidate the existing approaches in static databases. In this paper, we propose an efficient and effective approach to perform SJ among multiple stream time series incrementally. In particular, we present a novel method, Adaptive Radius-based Search (ARES), which can answer the similarity search without false dismissals and is seamlessly integrated into SJ processing. Most importantly, we provide a formal cost model for ARES, based on which ARES can be adaptive to data characteristics, achieving the minimum number of refined candidate pairs, and thus, suitable for stream processing. Furthermore, in light of the cost model, we utilize space-efficient synopses that are constructed for stream time series to further reduce the candidate set. Extensive experiments demonstrate the efficiency and effectiveness of our proposed approach.
登录
查看更多内容
DOI：
--
发表时间：
2004
期刊：
--
影响因子：
--
作者：
Lei Chen;R. Ng
通讯作者：
Lei Chen;R. Ng
DOI：
--
发表时间：
2000-09
期刊：
--
影响因子：
--
作者：
Byoung-Kee Yi;C. Faloutsos
通讯作者：
Byoung-Kee Yi;C. Faloutsos
DOI：
--
发表时间：
1997-08
期刊：
--
影响因子：
--
作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
通讯作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
DOI：
--
发表时间：
2005-08
期刊：
--
影响因子：
--
作者：
S. Michel;P. Triantafillou;G. Weikum
通讯作者：
S. Michel;P. Triantafillou;G. Weikum
DOI：
10.1016/b978-155860651-7/50124-8
发表时间：
2001-08
期刊：
--
影响因子：
--
作者：
Stefan Berchtold;D. Keim;H. Kriegel
通讯作者：
Stefan Berchtold;D. Keim;H. Kriegel