STIPA: A Memory Efficient Technique for Interval Pattern Discovery

Abstract

Increasing popularity of Cyber Physical System in Industry and automation applications generate a large amount of sensor data using IoT Devices. Majority of these sensed data are materialized in the form of interval events, i.e., event with duration. The temporal relationship between interval events, known as Interval Pattern, has many useful applications like, in human activity detection, patient monitoring and anomaly detection, etc. Existing work on Cyber Physical System have not incorporated the interval event analysis. In this paper, we examine the need of interval pattern discovery in CPS and propose a novel efficient algorithm called STIPA (Shrinkable Temporal Index based Pattern-growth Algorithm) for discovering the frequent interval patterns. Existing pattern-growth based interval pattern mining solutions keep index information in memory whereas index size increases monotonically as the length of pattern increases. As a result, existing solutions are not suitable to run pattern mining algorithm on devices which have limited memory. However, STIPA is equipped with a memory efficient indexing technique whose index size shrinks as the length of prefix increases in interval patterns. Moreover, a compressed interval pattern representation is also introduced which further reduces the memory requirement. Our performance study on synthetic and real-world dataset shows that STIPA demands less memory in comparison to existing techniques and it also outperforms the existing methods in execution time.