Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: The VLDB Journal 6/2019

04.10.2019 | Regular Paper

One-pass trajectory simplification using the synchronous Euclidean distance

verfasst von: Xuelian Lin, Jiahao Jiang, Shuai Ma, Yimeng Zuo, Chunming Hu

Erschienen in: The VLDB Journal | Ausgabe 6/2019

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

Various mobile devices have been used to collect, store and transmit tremendous trajectory data, and it is known that raw trajectory data seriously wastes the storage, network bandwidth and computing resource. To attack this issue, one-pass line simplification (\(\textsf {LS} \)) algorithms have been developed, by compressing data points in a trajectory to a set of continuous line segments. However, these algorithms adopt the perpendicular Euclidean distance, and none of them uses the synchronous Euclidean distance (\(\textsf {SED} \)), and cannot support spatiotemporal queries. To do this, we develop two one-pass error bounded trajectory simplification algorithms (\(\textsf {CISED} \)-\(\textsf {S} \) and \(\textsf {CISED} \)-\(\textsf {W} \)) using \(\textsf {SED} \), based on a novel spatiotemporal cone intersection technique. Using four real-life trajectory datasets, we experimentally show that our approaches are both efficient and effective. In terms of running time, algorithms \(\textsf {CISED} \)-\(\textsf {S} \) and \(\textsf {CISED} \)-\(\textsf {W} \) are on average 3 times faster than \(\textsf {SQUISH} \)-\(\textsf {E} \) (the fastest existing \(\textsf {LS} \) algorithm using \(\textsf {SED} \)). In terms of compression ratios, \(\textsf {CISED} \)-\(\textsf {S} \) is close to and \(\textsf {CISED} \)-\(\textsf {W} \) is on average \(19.6\%\) better than \(\textsf {DPSED} \) (the existing sub-optimal \(\textsf {LS} \) algorithm using \(\textsf {SED} \) and having the best compression ratios), and they are \(21.1\%\) and \(42.4\%\) better than \(\textsf {SQUISH} \)-\(\textsf {E} \) on average, respectively.
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. VLDBJ 15(3), 211–228 (2006) CrossRef Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. VLDBJ 15(3), 211–228 (2006) CrossRef
2.
Zurück zum Zitat Chan, W., Chin, F.: Approximation of polygonal curves with minimum number of line segments or minimal error. Int. J. Comput. Geom. Appl. 6(1), 378–387 (1996) CrossRef Chan, W., Chin, F.: Approximation of polygonal curves with minimum number of line segments or minimal error. Int. J. Comput. Geom. Appl. 6(1), 378–387 (1996) CrossRef
3.
Zurück zum Zitat Chen, Y., Jiang, K., Zheng, Y., Li, C., Yu, N.: Trajectory simplification method for location-based social networking services. In: LBSN, pp. 33–40 (2009) Chen, Y., Jiang, K., Zheng, Y., Li, C., Yu, N.: Trajectory simplification method for location-based social networking services. In: LBSN, pp. 33–40 (2009)
4.
Zurück zum Zitat Chen, M., Xu, M., Fränti, P.: A fast multiresolution polygonal approximation algorithm for GPS trajectory simplification. IEEE Trans. Image Process. 21(5), 2770–2785 (2012) MathSciNetCrossRef Chen, M., Xu, M., Fränti, P.: A fast multiresolution polygonal approximation algorithm for GPS trajectory simplification. IEEE Trans. Image Process. 21(5), 2770–2785 (2012) MathSciNetCrossRef
5.
Zurück zum Zitat Civilis, A., Jensen, C.S., Pakalnis, S.: Techniques for efficient road-network-based tracking of moving objects. TKDE 17(5), 698–712 (2005) Civilis, A., Jensen, C.S., Pakalnis, S.: Techniques for efficient road-network-based tracking of moving objects. TKDE 17(5), 698–712 (2005)
6.
Zurück zum Zitat Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Can. Cartogr. 10(2), 112–122 (1973) CrossRef Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Can. Cartogr. 10(2), 112–122 (1973) CrossRef
7.
Zurück zum Zitat Dunham, J.G.: Piecewise linear approximation of planar curves. PAMI 8, 9–67 (1986) Dunham, J.G.: Piecewise linear approximation of planar curves. PAMI 8, 9–67 (1986)
8.
Zurück zum Zitat Gotsman, R., Kanza, Y.: A dilution-matching-encoding compaction of trajectories over road networks. GeoInformatica 19(2), 331–3364 (2015) CrossRef Gotsman, R., Kanza, Y.: A dilution-matching-encoding compaction of trajectories over road networks. GeoInformatica 19(2), 331–3364 (2015) CrossRef
9.
Zurück zum Zitat Han, Y., Sun, W., Zheng, B.: Compress: a comprehensive framework of trajectory compression in road networks. TODS 42(2), 11:1–11:9 (2017) MathSciNetCrossRef Han, Y., Sun, W., Zheng, B.: Compress: a comprehensive framework of trajectory compression in road networks. TODS 42(2), 11:1–11:9 (2017) MathSciNetCrossRef
10.
Zurück zum Zitat Heckbert, P.S., Garland, M.: Survey of polygonal surface simplification algorithms. In: SIGGRAPH (1997) Heckbert, P.S., Garland, M.: Survey of polygonal surface simplification algorithms. In: SIGGRAPH (1997)
11.
Zurück zum Zitat Hershberger, J., Snoeyink, J.: Speeding up the Douglas–Peucker line-simplification algorithm. Technical Report, University of British Columbia (1992) Hershberger, J., Snoeyink, J.: Speeding up the Douglas–Peucker line-simplification algorithm. Technical Report, University of British Columbia (1992)
12.
Zurück zum Zitat Hung, C.C., Peng, W., Lee, W.: Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. VLDBJ 24(2), 169–192 (2015) CrossRef Hung, C.C., Peng, W., Lee, W.: Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. VLDBJ 24(2), 169–192 (2015) CrossRef
13.
Zurück zum Zitat Imai, H., Iri, M.: Computational-geometric methods for polygonal approximations of a curve. Comput. Vis. Graph. Image Process. 36, 31–41 (1986) CrossRef Imai, H., Iri, M.: Computational-geometric methods for polygonal approximations of a curve. Comput. Vis. Graph. Image Process. 36, 31–41 (1986) CrossRef
14.
Zurück zum Zitat Lin, X., Ma, S., Zhang, H., Wo, T., Huai, J.: One-pass error bounded trajectory simplification. PVLDB 10(7), 841–852 (2017) Lin, X., Ma, S., Zhang, H., Wo, T., Huai, J.: One-pass error bounded trajectory simplification. PVLDB 10(7), 841–852 (2017)
15.
Zurück zum Zitat Liu, J., Zhao, K., Sommer, P., Shang, S., Kusy, B., Jurdak, R.: Bounded quadrant system: Error-bounded trajectory compression on the go. In: ICDE (2015) Liu, J., Zhao, K., Sommer, P., Shang, S., Kusy, B., Jurdak, R.: Bounded quadrant system: Error-bounded trajectory compression on the go. In: ICDE (2015)
16.
Zurück zum Zitat Liu, J., Zhao, K., Sommer, P., Shang, S., Kusy, B., Lee, J.-G., Jurdak, R.: A novel framework for online amnesic trajectory compression in resource-constrained environments. IEEE Trans. Knowl. Data Eng. 28(11), 2827–2841 (2016) CrossRef Liu, J., Zhao, K., Sommer, P., Shang, S., Kusy, B., Lee, J.-G., Jurdak, R.: A novel framework for online amnesic trajectory compression in resource-constrained environments. IEEE Trans. Knowl. Data Eng. 28(11), 2827–2841 (2016) CrossRef
17.
Zurück zum Zitat Long, C., Wong, R.C.-W., Jagadish, H.: Direction-preserving trajectory simplification. PVLDB 6(10), 949–960 (2013) Long, C., Wong, R.C.-W., Jagadish, H.: Direction-preserving trajectory simplification. PVLDB 6(10), 949–960 (2013)
18.
Zurück zum Zitat Melkman, A., O’Rourke, J.: On polygonal chain approximation. Mach. Intell. Pattern Recognit. 6, 87–95 (1988) MathSciNetCrossRef Melkman, A., O’Rourke, J.: On polygonal chain approximation. Mach. Intell. Pattern Recognit. 6, 87–95 (1988) MathSciNetCrossRef
19.
Zurück zum Zitat Meratnia, N., de By, R.A.: Spatiotemporal compression techniques for moving point objects. In: EDBT (2004) CrossRef Meratnia, N., de By, R.A.: Spatiotemporal compression techniques for moving point objects. In: EDBT (2004) CrossRef
20.
Zurück zum Zitat Metha, R., Mehta, V.K.: The Principles of Physics. S Chand, New Delhi (1999) Metha, R., Mehta, V.K.: The Principles of Physics. S Chand, New Delhi (1999)
22.
Zurück zum Zitat Muckell, J., Hwang, J.-H., Lawson, C.T., Ravi, S.S.: Algorithms for compressing gps trajectory data: an empirical evaluation. In: ACM-GIS (2010) Muckell, J., Hwang, J.-H., Lawson, C.T., Ravi, S.S.: Algorithms for compressing gps trajectory data: an empirical evaluation. In: ACM-GIS (2010)
23.
Zurück zum Zitat Muckell, J., Olsen, P.W., Hwang, J.-H., Lawson, C.T., Ravi, S.S.: Compression of trajectory data: a comprehensive evaluation and new approach. GeoInformatica 18(3), 435–460 (2014) CrossRef Muckell, J., Olsen, P.W., Hwang, J.-H., Lawson, C.T., Ravi, S.S.: Compression of trajectory data: a comprehensive evaluation and new approach. GeoInformatica 18(3), 435–460 (2014) CrossRef
24.
Zurück zum Zitat Nibali, A., He, Z.: Trajic: an effective compression system for trajectory data. TKDE 27(11), 3138–3151 (2015) Nibali, A., He, Z.: Trajic: an effective compression system for trajectory data. TKDE 27(11), 3138–3151 (2015)
25.
Zurück zum Zitat O’Rourke, J., Chien, C.B., Olson, T., Naddor, D.: A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19(4), 384–391 (1982) CrossRef O’Rourke, J., Chien, C.B., Olson, T., Naddor, D.: A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19(4), 384–391 (1982) CrossRef
26.
27.
Zurück zum Zitat Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-object representations. In: SSD (1999) CrossRef Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-object representations. In: SSD (1999) CrossRef
28.
Zurück zum Zitat Popa, I.S., Zeitouni, K., Oria, V., Kharrat, A.: Spatio-temporal compression of trajectories in road networks. GeoInformatica 19(1), 117–145 (2014) CrossRef Popa, I.S., Zeitouni, K., Oria, V., Kharrat, A.: Spatio-temporal compression of trajectories in road networks. GeoInformatica 19(1), 117–145 (2014) CrossRef
29.
Zurück zum Zitat Potamias, M., Patroumpas, K., Sellis, T.K.: Sampling trajectory streams with spatiotemporal criteria. In: SSDBM (2006) Potamias, M., Patroumpas, K., Sellis, T.K.: Sampling trajectory streams with spatiotemporal criteria. In: SSDBM (2006)
30.
Zurück zum Zitat Ramer, U.: An iterative procedure for the polygonal approximation of plane curves. Comput. Graph. Image Process. 1, 244–256 (1972) CrossRef Ramer, U.: An iterative procedure for the polygonal approximation of plane curves. Comput. Graph. Image Process. 1, 244–256 (1972) CrossRef
31.
Zurück zum Zitat Reumann, K., Witkam, A.: Optimizing curve segmentation in computer graphics. In: International Computing Symposium (1974) Reumann, K., Witkam, A.: Optimizing curve segmentation in computer graphics. In: International Computing Symposium (1974)
32.
Zurück zum Zitat Richter, K.-F., Schmid, F., Laube, P.: Semantic trajectory compression: representing urban movement in a nutshell. J. Spat. Inf. Sci. 4(1), 3–30 (2012) Richter, K.-F., Schmid, F., Laube, P.: Semantic trajectory compression: representing urban movement in a nutshell. J. Spat. Inf. Sci. 4(1), 3–30 (2012)
33.
Zurück zum Zitat Schmid, F., Richter, K., Laube, P.: Semantic trajectory compression. In: SSTD, pp. 411–416 (2009) Schmid, F., Richter, K., Laube, P.: Semantic trajectory compression. In: SSTD, pp. 411–416 (2009)
34.
Zurück zum Zitat Shamos, M.I., Dan, H.: Geometric intersection problems. In: Symposium on Foundations of Computer Science, pp. 208–215 (1976) Shamos, M.I., Dan, H.: Geometric intersection problems. In: Symposium on Foundations of Computer Science, pp. 208–215 (1976)
35.
Zurück zum Zitat Shi, W., Cheung, C.: Performance evaluation of line simplification algorithms for vector generalization. Cartogr. J. 43(1), 27–44 (2006) CrossRef Shi, W., Cheung, C.: Performance evaluation of line simplification algorithms for vector generalization. Cartogr. J. 43(1), 27–44 (2006) CrossRef
36.
Zurück zum Zitat Sklansky, J., Gonzalez, V.: Fast polygonal approximation of digitized curves. Pattern Recognit. 12, 327–331 (1980) CrossRef Sklansky, J., Gonzalez, V.: Fast polygonal approximation of digitized curves. Pattern Recognit. 12, 327–331 (1980) CrossRef
37.
Zurück zum Zitat Song, R., Sun, W., Zheng, B., Zheng, Y.: Press: a novel framework of trajectory compression in road networks. PVLDB 7(9), 661–672 (2014) Song, R., Sun, W., Zheng, B., Zheng, Y.: Press: a novel framework of trajectory compression in road networks. PVLDB 7(9), 661–672 (2014)
38.
Zurück zum Zitat Toussaint, G.T.: On the complexity of approximating polygonal curves in the plane. In: International Symposium on Robotics and Automation (IASTED) (1985) Toussaint, G.T.: On the complexity of approximating polygonal curves in the plane. In: International Symposium on Robotics and Automation (IASTED) (1985)
39.
Zurück zum Zitat Trajcevski, G., Cao, H., Scheuermanny, P., Wolfsonz, O., Vaccaro, D.: On-line data reduction and the quality of history in moving objects databases. In: MobiDE (2006) Trajcevski, G., Cao, H., Scheuermanny, P., Wolfsonz, O., Vaccaro, D.: On-line data reduction and the quality of history in moving objects databases. In: MobiDE (2006)
40.
Zurück zum Zitat Williams, C.M.: An efficient algorithm for the piecewise linear approximation of planar curves. Comput. Graph. Image Process. 8, 286–293 (1978) CrossRef Williams, C.M.: An efficient algorithm for the piecewise linear approximation of planar curves. Comput. Graph. Image Process. 8, 286–293 (1978) CrossRef
41.
Zurück zum Zitat Zhang, D., Ding, M., Yang, D., Liu, Y., Fan, J., Shen, H.T.: Trajectory simplification: an experimental study and quality analysis. PVLDB 9(11), 934–946 (2018) Zhang, D., Ding, M., Yang, D., Liu, Y., Fan, J., Shen, H.T.: Trajectory simplification: an experimental study and quality analysis. PVLDB 9(11), 934–946 (2018)
42.
Zurück zum Zitat Zhao, Z., Saalfeld, A.: Linear-time sleeve-fitting polyline simplification algorithms. In: Proceedings of AutoCarto, pp. 214–223 (1997) Zhao, Z., Saalfeld, A.: Linear-time sleeve-fitting polyline simplification algorithms. In: Proceedings of AutoCarto, pp. 214–223 (1997)
43.
Zurück zum Zitat Zheng, Y., Xie, X., Ma, W.: GeoLife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33(2), 32–39 (2010) Zheng, Y., Xie, X., Ma, W.: GeoLife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33(2), 32–39 (2010)
44.
Zurück zum Zitat Züfle, A., Trajcevski, G., Pfoser, D., Renz, M., Rice, M.T., Leslie, T., Delamater, P.L., Emrich, T.: Handling uncertainty in geo-spatial data. In: ICDE (2017) Züfle, A., Trajcevski, G., Pfoser, D., Renz, M., Rice, M.T., Leslie, T., Delamater, P.L., Emrich, T.: Handling uncertainty in geo-spatial data. In: ICDE (2017)
Metadaten
Titel
One-pass trajectory simplification using the synchronous Euclidean distance
verfasst von
Xuelian Lin
Jiahao Jiang
Shuai Ma
Yimeng Zuo
Chunming Hu
Publikationsdatum
04.10.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 6/2019
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-019-00575-8

Weitere Artikel der Ausgabe 6/2019

The VLDB Journal 6/2019 Zur Ausgabe

Premium Partner