Optimal Window Change Detection

It is recognized that change detection is an important feature in many data stream applications. An appealing approach is to reformulate the problem of change detec- tion in data streams to the successive application of two sample tests, as proposed in [7]. Usually the underlying data-generation process is unknown. Consequently, non- parametric tests like the Kolmogorov-Smirnov (KS) test are desirable. Maintenance of the KS-test statistic can be per- formed efficiently in O(log(n)) per example, where n is the window size. However this can only be achieved by assum- ing a fixed window size. Because there exist no any time optimal window size, it is highly desirable to obtain a vari- able size window algorithm. In this paper we propose an efficient approximate algorithm for the maintenance of the KS-test statistic under the optimal window size.