Research on Parallelized Stream Data Micro Clustering Algorithm

Ke Ma, Lingjuan Li, Yimu Ji, Shengmei Luo, Tao Wen2015 · DOI

Abstract

Analysis and mining of stream data is a hot research topic in recent years. In order to improve the clustering efficiency, based on MapReduce, this paper proposes a Parallelized Stream Data Micro Clustering Algorithm (PSDMC) for the micro-clustering phase of the CluStream algorithm. PSDMC algorithm uses a series of containers to store real-time stream data according to the arrival time. Each map node produces real-time local micro-clusters per unit time (such as 1 second). The reduce node puts together these real-time local micro-clusters to produce real-time global micro-clusters by using DBSCAN and the micro-clustering method of CluStream. The global micro-clusters will be used to renew local micro-clusters in every map node and be used to create snapshots to store into a Pyramidal Time Frame. Analysis shows that the efficiency of the PSDMC algorithm can increase nearly linearly with the increase of map nodes while the clustering accuracy can be guaranteed.

Introduction

In the era of the Internet of Things and massive network traffic, data is often produced as a "stream"—a continuous, high-speed, and potentially infinite sequence. Traditional data mining algorithms struggle in this environment because they often require multiple passes over the data.

The classical CluStream algorithm addressed this by using a two-stage approach: an "online" phase that maintains statistical summaries (micro-clusters) and an "offline" phase for final clustering. However, as data speeds increase, the online phase becomes a bottleneck; a single computer simply cannot keep up with the incoming data. This research addresses the urgent need for a parallelized architecture that can distribute this workload across multiple computing nodes using the MapReduce framework.

The PSDMC Algorithm

The proposed PSDMC algorithm adapts the micro-clustering phase of CluStream to the MapReduce programming model. The architecture is divided into initialization, local production, and global merging modules.

Overall architecture of the PSDMC algorithm showing the flow from stream data to Map and Reduce nodes.

Map Node Processing

Each Map node is equipped with a "container" to temporarily store incoming stream data. Every unit of time (e.g., 1 second), the node processes its local data to produce local micro-clusters. This process involves receiving the newest global micro-clusters to renew local state before processing the buffered data.

Flowchart of the Map node processing logic, detailing the decision-making process for handling buffered stream data.

Reduce Node Merging and Feedback

The Reduce node collects local micro-clusters from all Map nodes. It then uses a combination of the original CluStream logic and a modified DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm to merge them into global micro-clusters. These global micro-clusters are sent back to the Map nodes to refresh their state for the next time interval. To allow for historical analysis, the Reduce node creates snapshots of the global clusters and stores them using a Pyramidal Time Frame, which maintains high-resolution data for recent events and lower-resolution data for older events.

Performance and Complexity Analysis

The primary advantage of PSDMC is its ability to decouple computational complexity. The most expensive part—processing raw data points—is distributed across many Map nodes, while the Reduce node only deals with a much smaller set of cluster summaries.

  • Map Node Complexity: $O(q \cdot n \cdot d^2)$, where $n$ is the number of data points.
  • Reduce Node Complexity: $O(k \cdot q \cdot i^2 + m^2)$, where $k$ is the number of nodes and $m$ is the number of clusters.

Since $n \gg k$, the distribution of work is highly effective. The authors' complexity analysis shows that the processing time at the Reduce node is significantly shorter than at the Map nodes. Consequently, the system's overall efficiency increases nearly linearly as more Map nodes are added, while clustering accuracy remains consistent with the non-parallelized version.

Conclusion

PSDMC provides a robust framework for scaling stream data clustering. While it introduces some memory overhead due to the container strategy and requires synchronization between nodes, it effectively breaks the single-node bottleneck. Future work will involve large-scale empirical testing on diverse streaming datasets to optimize parameters such as "unit time" and the thresholds for cluster deletion.

Summary updated

Abstract

Analysis and mining of stream data is a hot research topic in recent years. In order to improve the clustering efficiency, based on MapReduce, this paper proposes a Parallelized Stream Data Micro Clustering Algorithm PSDMC for the micro-clustering phase of CluStream algorithm. PSDMC algorithm uses a series of containers to store real-time stream data according to the arrival time. Each map node produces real-time local micro-clusters per unit time (such as 1 second). The reduce node puts together these real-time local micro-clusters to produce real-time global microclusters by using DBSCAN and the micro clustering method of CluStream. The global microclusters will be used to renew local micro-clusters in every map node and be used to create snapshots to store into Pyramidal Time Frame. Analysis shows that the efficiency of PSDMC algorithm can increase nearly linearly with the increase of map nodes while the clustering accuracy can be guaranteed.
BibTeX
@misc{ma2015research,
  author = {Ke Ma and Lingjuan Li and Yimu Ji and Shengmei Luo and Tao Wen},
  title = {{Research on Parallelized Stream Data Micro Clustering Algorithm}},
  year = {2015},
  doi = {10.2991/ameii-15.2015.116},
}

Loading related content...

Figure