DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing
Abstract Spatial concentrations (or spatial clusters) of moving objects, such as vehicles and humans, is a mobility pattern that is relevant to many applications. Fast detection of this pattern and its evolution, e.g., if the cluster is shrinking or growing, is useful in numerous scenarios, such as...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Brazilian Computing Society (SBC)
2019-04-01
|
| Series: | Journal of Internet Services and Applications |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13174-019-0107-x |
| _version_ | 1818345262960082944 |
|---|---|
| author | Marcos Roriz Junior Bruno Olivieri Markus Endler |
| author_facet | Marcos Roriz Junior Bruno Olivieri Markus Endler |
| author_sort | Marcos Roriz Junior |
| collection | DOAJ |
| description | Abstract Spatial concentrations (or spatial clusters) of moving objects, such as vehicles and humans, is a mobility pattern that is relevant to many applications. Fast detection of this pattern and its evolution, e.g., if the cluster is shrinking or growing, is useful in numerous scenarios, such as detecting the formation of traffic jams or detecting a fast dispersion of people in a music concert. On-Line detection of this pattern 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 spatial cluster detection operate in batch mode, where moving objects location updates are recorded during time periods of a 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. Further, they extensively use spatial data structures and operators, which can be troublesome to maintain or parallelize in on-line scenarios. To address these issues, in this paper we propose DG2CEP, a parallel algorithm that combines the well-known density-based clustering algorithm DBSCAN with the data stream processing paradigm Complex Event Processing (CEP) to achieve continuous and timely detection of spatial clusters. Our experiments with real-world data streams indicate that DG2CEP is able to detect the formation and dispersion of clusters with small latency while having higher similarity to DBSCAN than batch-based approaches. |
| first_indexed | 2024-12-13T16:59:35Z |
| format | Article |
| id | doaj.art-3686cb153be847049277980843f59e45 |
| institution | Directory Open Access Journal |
| issn | 1867-4828 1869-0238 |
| language | English |
| last_indexed | 2024-12-13T16:59:35Z |
| publishDate | 2019-04-01 |
| publisher | Brazilian Computing Society (SBC) |
| record_format | Article |
| series | Journal of Internet Services and Applications |
| spelling | doaj.art-3686cb153be847049277980843f59e452022-12-21T23:37:50ZengBrazilian Computing Society (SBC)Journal of Internet Services and Applications1867-48281869-02382019-04-0110112810.1186/s13174-019-0107-xDG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processingMarcos Roriz Junior0Bruno Olivieri1Markus Endler2Faculdade de Ciências e Tecnologia, Universidade Federal de GoiásDepartamento de Informática, Pontifícia Universidade Católica do Rio de JaneiroDepartamento de Informática, Pontifícia Universidade Católica do Rio de JaneiroAbstract Spatial concentrations (or spatial clusters) of moving objects, such as vehicles and humans, is a mobility pattern that is relevant to many applications. Fast detection of this pattern and its evolution, e.g., if the cluster is shrinking or growing, is useful in numerous scenarios, such as detecting the formation of traffic jams or detecting a fast dispersion of people in a music concert. On-Line detection of this pattern 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 spatial cluster detection operate in batch mode, where moving objects location updates are recorded during time periods of a 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. Further, they extensively use spatial data structures and operators, which can be troublesome to maintain or parallelize in on-line scenarios. To address these issues, in this paper we propose DG2CEP, a parallel algorithm that combines the well-known density-based clustering algorithm DBSCAN with the data stream processing paradigm Complex Event Processing (CEP) to achieve continuous and timely detection of spatial clusters. Our experiments with real-world data streams indicate that DG2CEP is able to detect the formation and dispersion of clusters with small latency while having higher similarity to DBSCAN than batch-based approaches.http://link.springer.com/article/10.1186/s13174-019-0107-xSpatial stream clusteringOn-line clusteringReal-time clusteringMobility patternsComplex event processingSmart city |
| spellingShingle | Marcos Roriz Junior Bruno Olivieri Markus Endler DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing Journal of Internet Services and Applications Spatial stream clustering On-line clustering Real-time clustering Mobility patterns Complex event processing Smart city |
| title | DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing |
| title_full | DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing |
| title_fullStr | DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing |
| title_full_unstemmed | DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing |
| title_short | DG2CEP: a near real-time on-line algorithm for detecting spatial clusters large data streams through complex event processing |
| title_sort | dg2cep a near real time on line algorithm for detecting spatial clusters large data streams through complex event processing |
| topic | Spatial stream clustering On-line clustering Real-time clustering Mobility patterns Complex event processing Smart city |
| url | http://link.springer.com/article/10.1186/s13174-019-0107-x |
| work_keys_str_mv | AT marcosrorizjunior dg2cepanearrealtimeonlinealgorithmfordetectingspatialclusterslargedatastreamsthroughcomplexeventprocessing AT brunoolivieri dg2cepanearrealtimeonlinealgorithmfordetectingspatialclusterslargedatastreamsthroughcomplexeventprocessing AT markusendler dg2cepanearrealtimeonlinealgorithmfordetectingspatialclusterslargedatastreamsthroughcomplexeventprocessing |