The discovery of events in time series can have important implications, such as identifying microlensing events in astronomical surveys, or changes in a patient's electrocardiogram. Current methods for identifying events require a sliding window of a fixed size, which is not ideal for all applications and could overlook important events. In this work, we develop probability models for calculating the significance of an arbitrary-sized sliding window and use these probabilities to find areas of significance. Because a brute force search of all sliding windows and all window sizes would be computationally intractable, we introduce a method for quickly approximating the results. We apply our method to over 100,000 astronomical time series from the MACHO survey, in which 56 different sections of the sky are considered, each with one or more known events. Our method was able to recover 100 of these events in the top 1 of the results, essentially pruning 99 of the data. Interestingly, our method was able to identify events that do not pass traditional event discovery procedures.
Existing methods in scan statistics currently do not address the problem of large data sets (e.g., millions or billions of time series). In many applications, one requires an event detection algorithm that can be performed quickly on many time series. In addition, because much of the data for these applications has noise that is difficult to understand and model, it is critical to develop a method that is independent of the noise characteristics. The current methods in scan statistics are generally based on particular noise models, such as Poisson distributions @cite_11 and binomial probabilities @cite_21 . Both of these characteristics exist in astronomy, and thus our goal in this paper is to address both of these issues. Due to the intractability of current scan statistics methods, we cannot compare our method. Thus, we are compelled to compare to anomaly detection due to its speed, efficiency and that it does not require first modeling the noise.
@cite_21 @cite_11
2105550309 2331623931
The scan statistic evaluates whether an apparent cluster of disease in time is due to chance. The statistic employs a ‘moving window’ of length w and finds the maximum number of cases revealed through the window as it scans or slides over the entire time period T. Computation of the probability of observing a certain size cluster, under the hypothesis of a uniform distribution, is infeasible when N, the total number of events, is large, and w is of moderate or small size relative to T. We give an approximation that is an asymptotic upper bound, easy to compute, and, for the purposes of hypothesis testing, more accurate than other approximations presented in the literature. The approximation applies both when N is fixed, and when N has a Poisson distribution. We illustrate the procedure on a data set of trisomic spontaneous abortions observed in a two year period in New York City. This article investigates the accuracy of approximations for the distribution of ordered m-spacings for i.i.d. uniform observations in the interval (0, 1). Several Poisson approximations and a compound Poisson approximation are studied. The result of a simulation study is included to assess the accuracy of these approximations. A numerical procedure for evaluating the moments of the ordered m-spacings is developed and evaluated for the most accurate approximation.