Parallelization of Searching and Mining Time Series Data using Dynamic Time Warping

被引：0

作者：

Shabib, Ahmed ^{[1
]}

Narang, Anish ^{[1
]}

Niddodi, Chaitra Prasad ^{[1
]}

Das, Madhura ^{[1
]}

Pradeep, Rachita ^{[1
]}

Shenoy, Varun ^{[1
]}

Auradkar, Prafullata ^{[1
]}

Vignesh, T. S. ^{[1
]}

Sitaram, Dinkar ^{[1
]}

机构：

[1] PES Inst Technol, Dept Comp Sci & Engn, Bangalore, Karnataka, India

来源：

2015 INTERNATIONAL CONFERENCE ON ADVANCES IN COMPUTING, COMMUNICATIONS AND INFORMATICS (ICACCI) | 2015年

关键词：

Time series; Dynamic time warping; Multicore; Spark;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Among the various algorithms present for data mining, the UCR Dynamic Time Warping (DTW) suite provided a solution to search and mine large data sets of time series data more efficiently as compared to the previously existing method of using Euclidean Distance. The UCR DTW algorithm was developed for a single CPU core. In this paper, we consider 2 methods of parallelizing the DTW algorithm. First, we consider a multi-core implementation, followed by a cluster implementation using Spark. From the multi-core implementation, we achieve nearly linear speedup. In the Spark implementation, we find that a straightforward implementation of DTW does not perform well. This is because; a major step in DTW is parallel computation of a lower bound. This paradigm is not supported well by Spark, which supports (i) broadcast variables that are broadcasts of read-only variables (ii) accumulation variables that represent distributed sums. We show how to compute distributed lower bounds efficiently in Spark and achieve nearly linear speedup with DTW in a Spark computation as well.

引用

页码：343 / 348

页数：6