An on-line algorithm for cluster detection of mobile nodes through complex event processing
Autor: | Marcos Roriz Junior, Francisco José da Silva e Silva, Markus Endler |
---|---|
Rok vydání: | 2017 |
Předmět: |
DBSCAN
Clustering high-dimensional data Computer science Data stream mining Complex event processing OPTICS algorithm 02 engineering and technology computer.software_genre Data stream clustering Hardware and Architecture 020204 information systems 0202 electrical engineering electronic engineering information engineering Batch processing 020201 artificial intelligence & image processing Data mining Cluster analysis computer Algorithm Software Information Systems |
Zdroj: | Information Systems. 64:303-320 |
ISSN: | 0306-4379 |
Popis: | 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. HighlightsWe present an on-line algorithm (DG2CEP) for clustering position data streams.DG2CEP combines data stream mining with complex event processing concepts.DG2CEP can detect both the formation and the dispersion of clusters as data pass.Experimental results demonstrate that DG2CEP can rapidly detect cluster formations.Experiments also show that DG2CEP results are highly similar to off-line approaches (DBSCAN). |
Databáze: | OpenAIRE |
Externí odkaz: |