Skip to main content
Top

2018 | OriginalPaper | Chapter

MDTK: Bandwidth-Saving Framework for Distributed Top-k Similar Trajectory Query

Authors : Zhigang Zhang, Jiali Mao, Cheqing Jin, Aoying Zhou

Published in: Database Systems for Advanced Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

During the past decade, with the popularity of smartphones and other mobile devices, big trajectory data is generated and stored in a distributed way. In this work, we focus on the DTW distance based top-k query over the distributed trajectory data. Processing such a query is challenging due to the limited network bandwidth and the computation overhead. To overcome these challenges, we propose a communication-saving framework MDTK (Multi-resolution based Distributed Top-K). MDTK sends the bounding envelopes of the reference trajectory from coarse to finer-grained resolutions and devises a level-increasing communication strategy to gradually tighten the proposed upper and lower bound. Then, distance bound based pruning strategies are imported to reduce both the computation and communication cost. Besides, we embed techniques including: indexing, early-stopping and cascade pruning, to improve the query efficiency. Extensive experiments on real datasets show that MDTK outperforms the state-of-the-art method.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. VLDB J. 15(3), 211–228 (2006)CrossRef Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. VLDB J. 15(3), 211–228 (2006)CrossRef
2.
go back to reference Chakrabarti, K., Keogh, E., Mehrotra, S., Pazzani, M.: Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst. (TODS) 27(2), 188–228 (2002)CrossRef Chakrabarti, K., Keogh, E., Mehrotra, S., Pazzani, M.: Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst. (TODS) 27(2), 188–228 (2002)CrossRef
3.
go back to reference Chan, F.P., Fu, A.C., Yu, C.: Haar wavelets for efficient similarity search of time-series: with and without time warping. TKDE 15(3), 686–705 (2003) Chan, F.P., Fu, A.C., Yu, C.: Haar wavelets for efficient similarity search of time-series: with and without time warping. TKDE 15(3), 686–705 (2003)
4.
go back to reference Costa, C., Laoudias, C., Zeinalipour-Yazti, D., Gunopulos, D.: SmartTrace: finding similar trajectories in smartphone networks without disclosing the traces. In: Proceedings of the 27th ICDE, pp. 1288–1291 (2011) Costa, C., Laoudias, C., Zeinalipour-Yazti, D., Gunopulos, D.: SmartTrace: finding similar trajectories in smartphone networks without disclosing the traces. In: Proceedings of the 27th ICDE, pp. 1288–1291 (2011)
5.
go back to reference Demetrios, Z.Y., Christos, L., Constandinos, C.: Crowdsourced trace similarity with smartphones. TKDE 25(6), 1240–1253 (2013) Demetrios, Z.Y., Christos, L., Constandinos, C.: Crowdsourced trace similarity with smartphones. TKDE 25(6), 1240–1253 (2013)
6.
go back to reference Faloutsos, C., Ranganathan, M., Manolopoulos, Y.: Fast subsequence matching in time-series databases. In: Proceedings of the 1994 ACM SIGMOD, pp. 419–429 (1994)CrossRef Faloutsos, C., Ranganathan, M., Manolopoulos, Y.: Fast subsequence matching in time-series databases. In: Proceedings of the 1994 ACM SIGMOD, pp. 419–429 (1994)CrossRef
7.
go back to reference Hsu, C.C., Kung, P.H., Yeh, M.Y., Lin, S.D., Gibbons, P.B.: Bandwidth-efficient distributed k-nearest-neighbor search with dynamic time warping. In: Proceedings of the 2015 ICBD, pp. 551–560. IEEE (2015) Hsu, C.C., Kung, P.H., Yeh, M.Y., Lin, S.D., Gibbons, P.B.: Bandwidth-efficient distributed k-nearest-neighbor search with dynamic time warping. In: Proceedings of the 2015 ICBD, pp. 551–560. IEEE (2015)
8.
go back to reference Jiangpeng, D., Jin, T., Xiaole, B., Zhaohui, S., Dong, X.: Mobile phone based drunk driving detection. In: Proceedings of the 2010 ICPCTH, pp. 1–8. IEEE (2010) Jiangpeng, D., Jin, T., Xiaole, B., Zhaohui, S., Dong, X.: Mobile phone based drunk driving detection. In: Proceedings of the 2010 ICPCTH, pp. 1–8. IEEE (2010)
9.
go back to reference Kanth, K.V.R., Agrawal, D., Singh, A.K.: Dimensionality reduction for similarity searching in dynamic databases. In: Proceedings of the 1998 ACM SIGMOD, pp. 166–176 (1998) Kanth, K.V.R., Agrawal, D., Singh, A.K.: Dimensionality reduction for similarity searching in dynamic databases. In: Proceedings of the 1998 ACM SIGMOD, pp. 166–176 (1998)
10.
go back to reference Keogh, E.: Exact indexing of dynamic time warping. In: Proceedings of the 28th VLDB, pp. 406–417 (2002)CrossRef Keogh, E.: Exact indexing of dynamic time warping. In: Proceedings of the 28th VLDB, pp. 406–417 (2002)CrossRef
11.
go back to reference Keogh, E.J., Chu, S., Hart, D.M., Pazzani, M.J.: An online algorithm for segmenting time series. In: Proceedings of the 2001 ICDM, pp. 289–296 (2001) Keogh, E.J., Chu, S., Hart, D.M., Pazzani, M.J.: An online algorithm for segmenting time series. In: Proceedings of the 2001 ICDM, pp. 289–296 (2001)
12.
go back to reference Papadopoulos, A.N., Manolopoulos, Y.: Distributed processing of similarity queries. Distrib. Parallel Databases 9(1), 67–92 (2001)CrossRef Papadopoulos, A.N., Manolopoulos, Y.: Distributed processing of similarity queries. Distrib. Parallel Databases 9(1), 67–92 (2001)CrossRef
13.
go back to reference Popivanov, I., Miller, R.J.: Similarity search over time-series data using wavelets. In: Proceedings of the 18th ICDE, pp. 212–221 (2002) Popivanov, I., Miller, R.J.: Similarity search over time-series data using wavelets. In: Proceedings of the 18th ICDE, pp. 212–221 (2002)
14.
go back to reference Rakthanmanon, T., Campana, B.J.L., Mueen, A.: Searching and mining trillions of time series subsequences under dynamic time warping. In: The 18th ACM SIGKDD, pp. 262–270 (2012) Rakthanmanon, T., Campana, B.J.L., Mueen, A.: Searching and mining trillions of time series subsequences under dynamic time warping. In: The 18th ACM SIGKDD, pp. 262–270 (2012)
15.
go back to reference Sakurai, Y., Yoshikawa, M., Faloutsos, C.: FTW: fast similarity search under the time warping distance. In: Proceedings of the 24th ACM PODS, pp. 326–337 (2005) Sakurai, Y., Yoshikawa, M., Faloutsos, C.: FTW: fast similarity search under the time warping distance. In: Proceedings of the 24th ACM PODS, pp. 326–337 (2005)
16.
go back to reference Xie, D., Li, F., Phillips, J.M.: Distributed trajectory similarity search. PVLDB 10(11), 1478–1489 (2017) Xie, D., Li, F., Phillips, J.M.: Distributed trajectory similarity search. PVLDB 10(11), 1478–1489 (2017)
17.
go back to reference 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. PVLDB 1(1), 586–597 (2008) 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. PVLDB 1(1), 586–597 (2008)
18.
go back to reference Yi, B., Faloutsos, C.: Fast time sequence indexing for arbitrary Lp norms. In: Proceedings of 26th VLDB, pp. 385–394 (2000) Yi, B., Faloutsos, C.: Fast time sequence indexing for arbitrary Lp norms. In: Proceedings of 26th VLDB, pp. 385–394 (2000)
20.
go back to reference Zeinalipour-Yazti, D., Lin, S., Gunopulos, D.: Distributed spatio-temporal similarity search. In: Proceedings of the 2006 CIKM, pp. 14–23 (2006) Zeinalipour-Yazti, D., Lin, S., Gunopulos, D.: Distributed spatio-temporal similarity search. In: Proceedings of the 2006 CIKM, pp. 14–23 (2006)
21.
go back to reference Zhang, Z., Wang, Y., Mao, J., Qiao, S., Jin, C., Zhou, A.: DT-KST: distributed top-k similarity query on big trajectory streams. In: Proceedings of the 22nd DASFAA, Part I, pp. 199–214 (2017)CrossRef Zhang, Z., Wang, Y., Mao, J., Qiao, S., Jin, C., Zhou, A.: DT-KST: distributed top-k similarity query on big trajectory streams. In: Proceedings of the 22nd DASFAA, Part I, pp. 199–214 (2017)CrossRef
Metadata
Title
MDTK: Bandwidth-Saving Framework for Distributed Top-k Similar Trajectory Query
Authors
Zhigang Zhang
Jiali Mao
Cheqing Jin
Aoying Zhou
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-91452-7_40

Premium Partner