DG2CEP: A Density-Grid Stream Clustering Algorithm based on Complex Event Processing for Cluster Detection

• Marcos Roriz PUC-Rio
• Markus Endler PUC-Rio

Resumo

Applications such as fleet and mobile task force management, or traffic control can largely benefit from the on-line detection of collective mobility patterns of vehicles, goods or persons. A common mobility pattern is a cluster, a concentration of mobile nodes in a certain region, e.g., a mass protest, a rock concert, or a traffic jam. Current approaches require previous knowledge of the locations where the cluster might happen. In this paper, we propose DG2CEP, an algorithm inspired by data mining algorithms and based on Complex Event Processing, for on-line detection of such clusters. It can detect the formation and dispersion of clusters from streams of position data without the need of specifying the possible locations of clusters in advance.

Referências

Aggarwal, C., Han, J., Wang, J. and Yu, P. (2003). A framework for clustering evolving data streams. In Proc. of the 29th Intl. Conf. on Very Large Data Bases - Volume 29.

Amini, A., Wah, T. and Saboohi, H. (2014). On Density-Based Data Streams Clustering Algorithms: A Survey. Journal of Computer Science and Technology, v. 29, n. 1.

Amini, A. and Ying, W. (2012). DENGRIS-Stream: A density-grid based clustering algorithm for evolving data streams over sliding window. In Proc. International Conference on Data Mining and Computer Engineering.

Baptista, G. L. B., Roriz, M., Vasconcelos, R., et al. (2013). On-line Detection of Collective Mobility Patterns through Distributed Complex Event Processing. Monografias em Ciência da Computação 12/2013, PUC-Rio, ISSN 0103-9741.

Barouni, F. and Moulin, B. (2012). An extended complex event processing engine to qualitatively determine spatiotemporal patterns. In Proc. of Global Geospatial Conf.

ção, F., Ester, M., Qian, W. and Zhou, A. (2006). Density-Based Clustering over an Evolving Data Stream with Noise. In Proc. of the 2006 SIAM Conf. on Data Mining.

Chen, Y. and Tu, L. (2007). Density-based Clustering for Real-time Stream Data. In Proc. of the 13th Intl. Conf. on Knowledge Discovery and Data Mining.

Codehaus (2014). Esper - Complex Event Processing. http://esper.codehaus.org/,

Ester, M., Kriegel, H., Sander, J. and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining.

Etzion, O. and Niblett, P. (2010). Event Processing in Action. 1st. ed. Greenwich, CT, USA: Manning Publications Co.

Garofalakis, M., Gehrke, J. and Rastogi, R. (2002). Querying and Mining Data Streams: You Only Get One Look a Tutorial. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. , SIGMOD ’02. ACM.

Han, J., Kamber, M. and Pei, J. (2011). Data Mining: Concepts and Techniques. 3rd. ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

Jain, A. K. (2010). Data clustering: 50 years beyond K-means. Pattern Recognition Letters, v. 31, n. 8, p. 651–666.

Kim, B., Lee, S., Lee, Y., et al. (2011). Mobiiscape: Middleware support for scalable mobility pattern monitoring of moving objects in a large-scale city. Journal of Systems and Software, v. 84, n. 11, p. 1852–1870.

Luckham, D. C. (2001). The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems. USA: Addison-Wesley., Inc.

Silva, J. A., Faria, E. R., Barros, R. C., et al. (2013). Data Stream Clustering: A Survey. ACM Comput. Surv., v. 46, n. 1, p. 13:1–13:31.

Tu, L. and Chen, Y. (2009). Stream data clustering based on grid density and attraction. ACM Transactions on Knowledge Discovery from Data, v. 3, n. 3.

Yuan, J., Zheng, Y., Xie, X. and Sun, G. (2011). Driving with Knowledge from the Physical World. In Proc. of the 17th Intl. Conf. on Knowledge Discovery and Data Mining.