Loading...
Please wait, while we are loading the content...
Similar Documents
Neighbor-based pattern detection for windows over streaming data (2009).
| Content Provider | CiteSeerX |
|---|---|
| Author | Yang, Di Rundensteiner, Elke A. Ward, Matthew O. |
| Abstract | The discovery of complex patterns such as clusters, outliers, and associations from huge volumes of streaming data has been recognized as critical for many domains. However, pattern detection with sliding window semantics, as required by applications ranging from stock market analysis to moving object tracking, remains largely unexplored. Applying static pattern detection algorithms from scratch to every window is prohibitively expensive due to their high algorithmic complexity. This work tackles this problem by developing the first solution for incremental detection of neighbor-based patterns specific to sliding window scenarios. The specific pattern types covered in this work include density-based clusters and distance-based outliers. Incremental pattern computation in highly dynamic streaming environments is challenging, because purging a large amount of to-be-expired data from previously formed patterns may cause complex pattern changes including migration, splitting, merging and termination of these patterns. Previous incremental neighbor-based pattern detection algorithms, which were typically not designed to handle sliding windows, such as incremental DBSCAN, are not able to solve this problem efficiently in terms of both CPU and memory consumption. To overcome this, we exploit the “predictability" property of sliding windows to elegantly discount the effect of expiring objects on the remaining pattern structures. Our solution achieves minimal CPU utilization, while still keeping the memory utilization linear in the number of objects in the window. Our comprehensive experimental study, using both synthetic as well as real data from domains of stock trades and moving object monitoring, demonstrates superiority of our proposed strategies over alternate methods in both CPU and memory utilization. |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Window Streaming Data Neighbor-based Pattern Detection Many Domain High Algorithmic Complexity Real Data Huge Volume Neighbor-based Pattern Applying Static Pattern Detection Algorithm Stock Trade Stock Market Analysis Window Scenario Distance-based Outlier Incremental Detection Memory Utilization Linear Complex Pattern Change Memory Consumption Pattern Structure Predictability Property Alternate Method Specific Pattern Type Incremental Dbscan Object Tracking Complex Pattern Comprehensive Experimental Study Pattern Detection Window Semantics First Solution Object Monitoring To-be-expired Data Incremental Pattern Computation Minimal Cpu Utilization Large Amount Memory Utilization Density-based Cluster |
| Content Type | Text |
