An on-line algorithm for cluster detection of mobile nodes through complex event processing

Clusters of mobile elements, such as vehicles and humans, are a common mobility pattern of interest for many applications. The on-line detection of them from large position streams of mobile entities is a challenging task because it requires algorithms that are capable of continuously and efficiently processing the high volume of position updates in a timely manner. Currently, the majority of approaches for cluster detection operate in batch mode, where position updates are recorded during time periods of certain length and then batch processed by an external routine, thus delaying the result of the cluster detection until the end of the time period. However, if the monitoring application requires results at a higher frequency than the one delivered by batch algorithms, then results might not reflect the current clustering state of the entities. To overcome this limitation, in this paper we propose DG2CEP, an algorithm that combines the well-known density-based clustering algorithm DBSCAN with the data stream processing paradigm Complex Event Processing (CEP) to achieve continuous, on-line detection of clusters. Our experiments with synthetic and real world datasets indicate that DG2CEP is able to detect the formation and dispersion of clusters with small latency and higher similarity to DBSCAN׳s output than batch-based approaches.