Name
Abstract | ||
|---|---|---|
We study the fundamental k-nearest neighbor (kNN) search problem on distributed time series. A server has constantly received various reference time series Q of length X and seeks the exact kNN over a collection of time series distributed across a set of M local sites. When X and M are large, and when the amount of query increases, simply sending each Q to all M sites incurs high communication bandwidth costs, which we would like to avoid. Prior work has presented a communication-efficient kNN algorithm for the Euclidean distance similarity measure. In this paper, we present the first communication-efficient kNN algorithm for the dynamic time warping (DTW) similarity measure, which is generally believed a better measure for time series. To handle the complexities of DTW, we design a new multi-resolution structure for the reference time series, and multi-resolution lower bounds that can effectively prune the search space. We present a new protocol between the server and the local sites that leverages multi-resolution pruning for communication efficiency and cascading lower bounds for computational efficiency. Empirical studies on both real-world and synthetic data sets show that our method reduces communication bandwidth by up to 92%. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/BigData.2015.7363799 | 2015 IEEE International Conference on Big Data (Big Data) |
Keywords | Field | DocType |
multiresolution structure,DTW similarity measure,Euclidean distance similarity measure,reference time series,distributed time series,kNN search problem,dynamic time warping,bandwidth-efficient distributed k-nearest-neighbor search | k-nearest neighbors algorithm,Data mining,Time series,Dynamic time warping,Similarity measure,Computer science,Server,Euclidean distance,Bandwidth (signal processing),Artificial intelligence,Search problem,Machine learning | Conference |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chin-Chi Hsu | 1 | 25 | 2.38 |
| Perng-Hwa Kung | 2 | 22 | 2.22 |
| Mi-Yen Yeh | 3 | 268 | 25.85 |
| Shou-De Lin | 4 | 706 | 84.81 |
| Phillip B. Gibbons | 5 | 6863 | 624.14 |