| Burst detection on data streams has broad potential applications, such as network monitoring, finance prediction and sensor networks, etc. Traditional burst detection algorithms are based on aggregation functions, thus they are not suitable for all the practical applications. This thesis proposes a novel burst detection algorithm, Narrowest Parallelogram Coverage. It uses a narrow parallelogram to represent a series of points which have a similar trend, and ensures that the errors are bounded. With these parallelograms, data arrives on equal time interval can be restored, so bursts based on arbitrary functions can be detected. We introduces an algorithm to find the narrowest parallelogram with the time complexity bounded to O(h), where h is the number of points that construct the convex hull covered by the parallelogram.As far as burst detections based on aggregation functions are concerned, this thesis extends the narrowest parallelogram coverage algorithm. That makes it be based on the suffix sums of the original data, and improves the time performance significantly.At last, a few experiments demonstrate that our algorithm has high efficiency in processing and lower cost on storage, and is better than other algorithms.The main contributions of this thesis can be conclued as:·Proposed the narrowest parallelogram coverage algorithm according to the data distribution of most data streams. This algorithm can support all kinds of burst detection functions. As far as we know, this was the first time convex hull was introduced to data streams.·Improved the basic algorithm, which dropped the time complexity from O(hn) to O(h).·Extended the algorithm, that made it usable on aggregation functions directly, and had a much better performance on aggregation functions.This algorithm is based on theoretical analyses and its effects and efficiency are verified by experiments. It can be deployed in various kinds of environment, and can meet users' requirements. |
PDF Full Text Request