A local algorithm to approximate the global clustering of streams generated in ubiquitous sensor networks

• Type: Article in International Scientific Journal
• Date: 2018

Authors

Pedro Pereira Rodrigues (Author) FMUP; Araujo, J (Author) Other; João Gama (Author) FEP; Lopes, L (Author) FCUP

Journal

Title: International Journal of Distributed Sensor Networks

Vol. 14

ISSN: 1550-1329

Publisher: SAGE

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 3 Citations

Other information

Authenticus ID: P-00P-RYT

DOI: 10.1177/1550147718808239

Abstract (EN): In ubiquitous streaming data sources, such as sensor networks, clustering nodes by the data they produce gives insights on the phenomenon being monitored. However, centralized algorithms force communication and storage requirements to grow unbounded. This article presents L2GClust, an algorithm to compute local clusterings at each node as an approximation of the global clustering. L2GClust performs local clustering of the sources based on the moving average of each node's data over time: the moving average is approximated using memory-less statistics; clustering is based on the furthest-point algorithm applied to the centroids computed by the node's direct neighbors. Evaluation is performed both on synthetic and real sensor data, using a state-of-the-art sensor network simulator and measuring sensitivity to network size, number of clusters, cluster overlapping, and communication incompleteness. A high level of agreement was found between local and global clusterings, with special emphasis on separability agreement, while an overall robustness to incomplete communications emerged. Communication reduction was also theoretically shown, with communication ratios empirically evaluated for large networks. L2GClust is able to keep a good approximation of the global clustering, using less communication than a centralized alternative, supporting the recommendation to use local algorithms for distributed clustering of streaming data sources.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19