Efficient Algorithms for Flock Detection in Large Spatio-Temp oral Data

摘要

Increasing availability of location-based applications and sensor devices have necessitated quicker analysis of moving object data streams in order to identify patterns. The efficiency of currently available algorithms used in pattern detection is not adequate to handle large scale data streams that are increasingly available. We focus on the particular problem of flock detection in moving object data and our goal is to detect, flocks quickly and using fast algorithms. Firstly, we employ a triangular grid to reduce the search space of clustering algorithms which has a significant effect in case of dense objects. As a second step, we implement a modified flock membership function and pipeline creation that ensures better memory and time performance during cluster detection. We show that this refinement also improves the rate of flock detection. Finally, we parallelize our algorithm to further enhance the handling of massive data streams. Based on an extensive empirical evaluation of these algorithms across a variety of moving object data sets, we show that our method is significantly faster than the existing comparable methods over sliding windows. In particular, it requires lesser time to identify flocks and is 2-4 times faster thus confirming the efficiency and effectiveness of our approach.