pGrid: Parallel Grid-Based Data Stream Clustering with MapReduce

Abstract

The ability to quickly understand large volumes of data stream is of great interest to industry, academia, and government. In addition, it is a critical challenge in many application domains such as Internet news feed analysis, network intrusion detection systems, and analysis of scientific data. Real-time pattern recognition from the data streams is a promising approach to this challenge, however, often due to the sheer speed and size of the data, data points must be analyzed on the fly. The one-pass through requirement and the lack of efficient clustering algorithms to identify and distinguish patterns limits the power and scalability of this approach. To overcome these limitations, in this report, we introduce a novel clustering algorithm called pGrid. It is a parallel grid-based data stream clustering method that uses the MapReduce framework to quickly find patterns in the data streams. We present our algorithm with detailed examples, and an in-depth performance evaluation against the D-Stream algorithm. Our evaluation results show that our algorithm performs comparably to the state-of-the-art methods in quality of the clustering results, while it is significantly more efficient and scalable.