Distributed top-k similarity query on big trajectory streams

Abstract

Recently, big trajectory data streams are generated in distributed environmentswith the popularity of smartphones and other mobile devices. Distributed top-k similarity query, which finds k trajectories that are most similar to a given query trajectory from all remote sites, is critical in this field. The key challenge in such a query is how to reduce the communication cost due to the limited network bandwidth resource. Although this query can be solved by sending the query trajectory to all the remote sites, in which the pairwise similarities are computed precisely. However, the overall cost, O(n · m), is huge when n or m is huge, where n is the size of query trajectory and m is the number of remote sites. Fortunately, there are some cheap ways to estimate pairwise similarity, which filter some trajectories in advance without precise computation. In order to overcome the challenge in this query, we devise two general frameworks, into which concrete distance measures can be plugged. The former one uses two bounds (the upper and lower bound), while the latter one only uses the lower bound. Moreover, we introduce detailed implementations of two representative distance measures, Euclidean and DTW distance, after inferring the lower and upper bound for the former framework and the lower bound for the latter one. Theoretical analysis and extensive experiments on real-world datasets evaluate the efficiency of proposed methods.

Keywords

top-k similarity query / trajectory stream / communication cost

References

[1] Dai J P, Teng J, Bai X, Shen Z H, Xuan D. Mobile phone based drunk driving detection. In: Proceedings of the 4th International Conference on Pervasive Computing Technologies for Healthcare. 2010, 1–8

[2] Zeinalipour Yazti D, Laoudias C, Costa C, Vlachos M, Andreou M I, Gunopulos D. Crowdsourced trace similarity with smartphones. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(6): 1240–1253

[3] Ding H, Trajcevski G, Scheuermann P. Efficient similarity join of large sets of moving object trajectories. In: Proceedings of the 15th International Conference on Temporal Representaion and Reasoning. 2008, 79–87

[4] Ma C Y, Lu H, Shou L D, Chen G. KSQ: top-k similarity query on uncertain trajectories. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(9): 2049–2062

[5] Skoumas G, Skoutas D, Vlachaki A. Efficient identification and approximation of k-nearest moving neighbors. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2013, 264–273

[6] Sacharidis D, Skoutas D, Skoumas G. Continuous monitoring of nearest trajectories. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2014, 361–370

[7] Yeh M Y, Wu K L, Yu P S, Chen M S. Leewave: level-wise distribution of wavelet coefficients for processing knn queries over distributed streams. Proceedings of the VLDB Endowment, 2008, 1(1): 586–597

[8] Hsu C C, Kung P H, Yeh M Y, Lin S D, Gibbons P B. Bandwidthefficient distributed k-nearest-neighbor search with dynamic time warping. In: Proceedings of the 2015 IEEE International Conference on Big Data. 2015, 551–560

[9] Zhang Z G, Wang Y L, Mao J L, Qiao S J, Jin C Q, Zhou A Y. DTKST: distributed top-k similarity query on big trajectory streams. In: Proceedings of the 22nd International Conference on Database Systems for Advanced Applications. 2017, 199–214

[10] Faloutsos C, Ranganathan M, Manolopoulos Y. Fast subsequence matching in time-series databases. In: Proceedings of the 1994 ACM International Conference on Management of Data. 1994, 419–429

[11] Kanth K V R, Agrawal D, Singh A K. Dimensionality reduction for similarity searching in dynamic databases. In: Proceedings of the 1998 ACM International Conference on Management of Data. 1998, 166–176

[12] Popivanov I, Miller R J. Similarity search over time-series data using wavelets. In: Proceedings of the 18th International Conference on Data Engineering. 2002, 212–221

[13] Yi B K, Faloutsos C. Fast time sequence indexing for arbitrary Lp norms. In: Proceedings of the 26th International Conference on Very Large Data Bases. 2000, 385–394

[14] Chakrabarti K, Keogh E, Mehrotra S, Pazzani M. Locally adaptive dimensionality reduction for indexing large time series databases. ACM Transactions on Database Systems, 2002, 27(2): 188–228

[15] Cao H, Wolfson O, Trajcevski G. Spatio-temporal data reduction with deterministic error bounds. The VLDB Journal, 2006, 15(3): 211–228

[16] Papadopoulos A N, Manolopoulos Y. Distributed processing of similarity queries. Distributed and Parallel Databases, 2001, 9(1): 67–92

[17] Kashyap S, Karras P. Scalable KNN search on vertically stored time series. In: Proceedings of the 17th ACM International Conference on Knowledge Discovery and Data Mining. 2011, 1334–1342

[18] Vernica R, Carey M J, Li C. Efficient parallel set-similarity joins using mapreduce. In: Proceedings of the 16th ACM International Conference on Management of Data. 2010, 495–506

[19] Kim Y, Shim K. Parallel top-k similarity join algorithms using mapreduce. In: Proceedings of the 28th IEEE International Conference on Data Engineering. 2012, 510–521

[20] Yazti D Z, Lin S, Gunopulos D. Distributed spatio-temporal similarity search. In: Proceedings of the 2006 ACM International Conference on Information and Knowledge Management. 2006, 14–23

[21] Costa C, Laoudias C, Yazti D Z, Gunopulos D. Smarttrace: finding similar trajectories in smartphone networks without disclosing the traces. In: Proceedings of the 27th International Conference on Data Engineering. 2011, 1288–1291

[22] Chan K P, Fu A W C, Yu C T. Haar wavelets for efficient similarity search of time-series: with and without time warping. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(3): 686–705

[23] Liu H P, Jin C Q, Zhou A Y. Popular route planning with travel cost estimation. In: Proceedings of the 21st International Conference on Database Systems for Advanced Applications. 2016, 403–418

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature