Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Integrating Map-Reduce and Stream-Processing for Efficiency (MRSP) Read chapter Read first chapter

2017 | OriginalPaper | Chapter

A Survey on Data Mining Methods for Clustering Complex Spatiotemporal Data

Author : Piotr S. Maciąg

Published in: Beyond Databases, Architectures and Structures. Towards Efficient Solutions for Data Analysis and Knowledge Representation

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

This publication presents a survey on the clustering algorithms proposed for spatiotemporal data. We begin our study with definitions of spatiotemporal datatypes. Next we provide a categorization of spatiotemporal datatypes with the special emphasis on the spatial representation and diversity in temporal aspect. We conduct our deliberation focusing mainly on the complex spatiotemporal objects. In particular, we review algorithms for two problems already proposed in literature: clustering complex spatiotemporal objects as polygons or geographical areas and measuring distances between complex spatial objects. In addition to description of the problems mentioned above, we also attempt to provide a comprehensive references review and provide a general look on the different problems related to the clustering spatiotemporal data.

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!

inform now

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!

inform now

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!

inform now
previous chapter Data Mining - A Tool for Migration Stock Prediction
next chapter Multi-partition Distributed Transactions over Cassandra-Like Database with Tunable Contention Control
Literature
1.
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th International Conference on Very Large Data Bases, VLDB 1994, pp. 487–499. Morgan Kaufmann Publishers Inc., San Francisco (1994)
2.
3.
Alt, H., Godau, M.: Computing the frÉchet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 05(01n02), 75–91 (1995)MATHCrossRef
4.
Ankerst, M., Breunig, M.M., Kriegel, H.P., Sander, J.: OPTICS: ordering points to identify the clustering structure. In: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD 1999, pp. 49–60. ACM, New York (1999)
5.
Atallah, M.J.: A linear time algorithm for the hausdorff distance between convex polygons. Inf. Process. Lett. 17(4), 207–209 (1983)MathSciNetMATHCrossRef
6.
Aydin, B., Angryk, R.: Spatiotemporal frequent pattern mining on solar data: current algorithms and future directions. In: 2015 IEEE International Conference on Data Mining Workshop (ICDMW), pp. 575–581, November 2015
7.
Bazan, J.G.: Hierarchical classifiers for complex spatio-temporal concepts. In: Peters, J.F., Skowron, A., Rybiński, H. (eds.) Transactions on Rough Sets IX. LNCS, vol. 5390, pp. 474–750. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-89876-4_​26 CrossRef
8.
9.
Birant, D., Kut, A.: ST-DBSCAN: an algorithm for clustering spatial-temporal data. Data Knowl. Eng. 60(1), 208–221 (2007). Intelligent Data MiningCrossRef
10.
Buchin, K., Buchin, M., Wenk, C.: Computing the fréchet distance between simple polygons. Comput. Geom. 41(1–2), 2–20 (2008). special Issue on the 22nd European Workshop on Computational Geometry (EuroCG)22nd European Workshop on Computational GeometryMathSciNetMATHCrossRef
11.
Chan, K.P., Fu, A.W.C.: Efficient time series matching by wavelets. In: Proceedings 15th International Conference on Data Engineering (Cat. No. 99CB36337), pp. 126–133, March 1999
12.
Chen, C.-S., Eick, C.F., Rizk, N.J.: Mining spatial trajectories using non-parametric density functions. In: Perner, P. (ed.) MLDM 2011. LNCS (LNAI), vol. 6871, pp. 496–510. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-23199-5_​37 CrossRef
13.
Chen, L., Ng, R.: On the marriage of Lp-norms and edit distance. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, vol. 30, pp. 792–803. VLDB Endowment (2004)
14.
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, SIGMOD 2005, pp. 491–502. ACM, New York (2005)
15.
Damiani, M.L., Issa, H., Fotino, G., Heurich, M., Cagnacci, F.: Introducing ‘presence’ and ‘stationarity index’ to study partial migration patterns: an application of a spatio-temporal clustering technique. Int. J. Geogr. Inf. Sci. 30(5), 907–928 (2016)CrossRef
16.
Eiter, T., Mannila, H.: Computing discrete fréchet distance. Technical report, Vienna University of Technology (1994)
17.
Erwig, M., Güting, R.H., Schneider, M., Vazirgiannis, M.: Spatio-temporal data types: an approach to modeling and querying moving objects in databases. GeoInformatica 3(3), 269–296 (1999)CrossRef
18.
Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Second International Conference on Knowledge Discovery and Data Mining, pp. 226–231. AAAI Press (1996)
19.
Estivill-Castro, V., Lee, I.: Autoclust: automatic clustering via boundary extraction for mining massive point-data sets. In: Proceedings of the 5th International Conference on Geocomputation, pp. 23–25 (2000)
20.
Gora, P., Rüb, I.: Traffic models for self-driving connected cars. Transp. Res. Procedia 14, 2207–2216 (2016). Transport Research Arena (TRA 2016)CrossRef
21.
Gudmundsson, J., van Kreveld, M.: Computing longest duration flocks in trajectory data. In: Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, GIS 2006, pp. 35–42. ACM, New York (2006)
22.
Han, J.: Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco (2005)
23.
Huang, Y., Zhang, L., Zhang, P.: A framework for mining sequential patterns from spatio-temporal event data sets. IEEE Trans. Knowl. Data Eng. 20(4), 433–448 (2008)CrossRef
24.
Iyengar, V.S.: On detecting space-time clusters. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 587–592. ACM (2004)
25.
Izakian, H., Pedrycz, W.: Anomaly detection and characterization in spatial time series data: a cluster-centric approach. IEEE Trans. Fuzzy Syst. 22(6), 1612–1624 (2014)CrossRef
26.
Izakian, H., Pedrycz, W., Jamal, I.: Clustering spatiotemporal data: an augmented fuzzy c-means. IEEE Trans. Fuzzy Syst. 21(5), 855–868 (2013)CrossRef
27.
Izakian, H., Pedrycz, W.: A new PSO-optimized geometry of spatial and spatio-temporal scan statistics for disease outbreak detection. Swarm Evol. Comput. 4, 1–11 (2012)CrossRef
28.
Jeung, H., Yiu, M.L., Zhou, X., Jensen, C.S., Shen, H.T.: Discovery of convoys in trajectory databases. Proc. VLDB Endow. 1(1), 1068–1080 (2008)CrossRef
29.
Joshi, D., Samal, A., Soh, L.K.: A dissimilarity function for clustering geospatial polygons. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2009, pp. 384–387. ACM, New York (2009)
30.
Joshi, D., Samal, A., Soh, L.K.: Spatio-temporal polygonal clustering with space and time as first-class citizens. Geoinformatica 17(2), 387–412 (2013)CrossRef
31.
Kasabov, N., Capecci, E.: Spiking neural network methodology for modelling, classification and understanding of EEG spatio-temporal data measuring cognitive processes. Inf. Sci. 294, 565–575 (2015). Innovative Applications of Artificial Neural Networks in EngineeringMathSciNetCrossRef
32.
Kasabov, N., Scott, N.M., Tu, E., Marks, S., Sengupta, N., Capecci, E., Othman, M., Doborjeh, M.G., Murli, N., Hartono, R., Espinosa-Ramos, J.I., Zhou, L., Alvi, F.B., Wang, G., Taylor, D., Feigin, V., Gulyaev, S., Mahmoud, M., Hou, Z.G., Yang, J.: Evolving spatio-temporal data machines based on the neucube neuromorphic framework: design methodology and selected applications. Neural Netw. 78, 1–14 (2016). special Issue on “Neural Network Learning in Big Data”CrossRef
33.
Keogh, E., Ratanamahatana, C.A.: Exact indexing of dynamic time warping. Knowl. Inf. Syst. 7(3), 358–386 (2005)CrossRef
34.
Kisilevich, S., Mansmann, F., Nanni, M., Rinzivillo, S.: Spatio-temporal clustering. In: Maimon, O., Rokach, L. (eds.) Data Mining and Knowledge Discovery Handbook, pp. 855–874. Springer, Boston (2010)
35.
Kryszkiewicz, M., Lasek, P.: TI-DBSCAN: clustering with DBSCAN by means of the triangle inequality. In: Szczuka, M., Kryszkiewicz, M., Ramanna, S., Jensen, R., Hu, Q. (eds.) RSCTC 2010. LNCS (LNAI), vol. 6086, pp. 60–69. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13529-3_​8 CrossRef
36.
37.
Lee, J.G., Han, J., Whang, K.Y.: Trajectory clustering: a partition-and-group framework. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, SIGMOD 2007, pp. 593–604. ACM, New York (2007)
38.
Li, L., Revesz, P.: A comparison of spatio-temporal interpolation methods. In: Egenhofer, M.J., Mark, D.M. (eds.) GIScience 2002. LNCS, vol. 2478, pp. 145–160. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45799-2_​11 CrossRef
39.
40.
Li, Z., Ding, B., Han, J., Kays, R.: Swarm: mining relaxed temporal moving object clusters. Proc. VLDB Endow. 3(1–2), 723–734 (2010)CrossRef
41.
Mohan, P., Shekhar, S., Shine, J.A., Rogers, J.P.: Cascading spatio-temporal pattern discovery. IEEE Trans. Knowl. Data Eng. 24(11), 1977–1992 (2012)CrossRef
42.
Moon, T.K.: The expectation-maximization algorithm. IEEE Sig. Process. Mag. 13(6), 47–60 (1996)CrossRef
43.
Nanni, M., Pedreschi, D.: Time-focused clustering of trajectories of moving objects. J. Intell. Inf. Syst. 27(3), 267–289 (2006)CrossRef
44.
Ng, R.T., Han, J.: CLARANS: a method for clustering objects for spatial data mining. IEEE Trans. Knowl. Data Eng. 14(5), 1003–1016 (2002)CrossRef
45.
Palma, A.T., Bogorny, V., Kuijpers, B., Alvares, L.O.: A clustering-based approach for discovering interesting places in trajectories. In: Proceedings of the 2008 ACM Symposium on Applied Computing, SAC 2008, pp. 863–868. ACM, New York (2008)
46.
Schubert, E., Zimek, A., Kriegel, H.P.: Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection. Data Min. Knowl. Disc. 28(1), 190–237 (2014)MathSciNetMATHCrossRef
47.
Shekhar, S., Evans, M.R., Kang, J.M., Mohan, P.: Identifying patterns in spatial information: a survey of methods. Wiley Interdisc. Rev.: Data Mining Knowl. Discov. 1(3), 193–214 (2011)
48.
Tork, H.F.: Spatio-temporal clustering methods classification. In: Doctoral Symposium on Informatics Engineering, vol. 1, no. 1, pp. 199–209. FEUP (2012)
49.
Wang, M., Wang, A., Li, A.: Mining spatial-temporal clusters from geo-databases. In: Li, X., Zaïane, O.R., Li, Z. (eds.) ADMA 2006. LNCS (LNAI), vol. 4093, pp. 263–270. Springer, Heidelberg (2006). doi:10.​1007/​11811305_​29 CrossRef
50.
Wang, S., Cai, T., Eick, C.F.: New spatiotemporal clustering algorithms and their applications to ozone pollution. In: Proceedings of the 2013 IEEE 13th International Conference on Data Mining Workshops, ICDMW 2013, pp. 1061–1068. IEEE Computer Society, Washington, DC (2013)
51.
Wang, W., Du, S., Guo, Z., Luo, L.: Polygonal clustering analysis using multilevel graph-partition. Trans. GIS 19(5), 716–736 (2015)CrossRef
52.
Yi, B.K., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: Proceedings of the Fourteenth International Conference on Data Engineering, ICDE 1998, pp. 201–208. IEEE Computer Society, Washington, DC (1998)
53.
Zhang, Y., Eick, C.F.: Novel clustering and analysis techniques for mining spatio-temporal data. In: Proceedings of the 1st ACM SIGSPATIAL PhD Workshop, SIGSPATIAL PhD 2014, pp. 2:1–2:5. ACM, New York (2014)
Metadata
Title
A Survey on Data Mining Methods for Clustering Complex Spatiotemporal Data
Author
Piotr S. Maciąg
Copyright Year
2017
Book
Beyond Databases, Architectures and Structures. Towards Efficient Solutions for Data Analysis and Knowledge Representation

Print ISBN: 978-3-319-58273-3

Electronic ISBN: 978-3-319-58274-0

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-58274-0_10

Premium Partner

    Image Credits