0
$\begingroup$

I have a program that detects events in a large amount of measurement data. When it detects an event, it writes a timestamp. I have thousands of event timestamps. What I wish to do is detect if there is periodicity in the timestamps I have.

Pictures may aid my explanation: If I have a bunch of events on a timeline, as in the figure below, the events all seem to be random but there may be some kind of periodic component to the events.

Random events with possible periodicity on a timeline

What I wish to do is detect if any of the seemingly random events are following a strict repeating interval. An illustration is given below, where we see that in the seemingly random events above there are some data points that are repeating with a fixed frequency.

Random events with detected periodicity on a timeline

I am not certain what kind of method to apply. I have looked into power spectral density, fourier transform and ARIMA. I applied fourier transform (as in the answer here) but was not able to make anything meaningful out of it.

Properties of the applied method should possibly include:

  1. A quantitative measure of how strict or fixed the intervals are, or how certain we can be that we have detected a fixed cycle
  2. The ability to detect periodicity on different timescales (e.g. events occurring multiple times within the same hour or multiple times during a week with a fixed pattern)

Anyone has suggestions how this could be done?

$\endgroup$
0
$\begingroup$

look at a histogram of inter-arrival times, the time duration between sequential events.

if the inter-arrivals follow an exponential distribution, the events are uniformly random, i.e. are from a Poisson distribution.

if you see strong peaks in the inter-arrival histogram, those peaks should indicate periodic recurrence.

The fineness of your histogram bins is the challenge. The more data you have, the finer you can resolve a periodic pattern but you will loose any short term (transient) periodic patterns.

A mixture of periodic and Poisson events will be more difficult. You can try to make a synthetic “continuous” time series out of your event sequence and use that the autocorrelation of a periodic time series, is periodic. The granularity of that synthetic time series is an issue that needs to be determined.

One characteristic of Poisson processes, is that a superposition of Poisson processes, is a Poisson process where the rates add. Other constraints such as available memory and decision latency bring further complications.

I suggest you try more simple approaches first. The EM algorithm which is really a family of algorithms are usually well suited to mixtures. Unfortunately, there really isn’t a out-of-the-box one-size-fits-all EM algorithm. One needs to construct an algorithm suitable for a specific application.

If you find obvious periods in your data, you can try successive passes of censoring and reprocessing

$\endgroup$
  • $\begingroup$ Thank you for your answer! I will have a go at inter-arrivals and see if I can find some kind of relationship there. Histogram bins will be a challenge. I am considering implementing a sliding window to iterate through the data, by both moving and expanding/shrinking the sliding window. I am not yet sure how to automatically screen the histograms for periodic occurrences, but that might be a question in the future if your suggested approach is successful. I will further look at EM algorithms. I think multiple simple approaches may be preferential given limited time to solve the problem. $\endgroup$ – Espenol Mar 14 at 12:33
0
$\begingroup$

How about a sorted list of events, linked lists, and brute force:

Pseudo-code:

For each FirstPoint in Points
  For each SecondPoint in Points above FirstPoint
    StrideSize = SecondPoint.Spot - FirstPoint

    If FirstPoint And StrideSize are not in a Chain Then

       Start Chain with FirstPoint and SecondPoint

       NextSpot = SecondPoint.Spot + StrideSize
       GapCount = 0

       Do
         If an EventPoint found close enough to NextSpot Then
            GapCount = 0
            Add EventPoint to Chain
            StrideSize = Average( GoodStrides )
         Else
            GapCount += 1
            If GapCount too big Then
               If Chain.Count >= BigEnough Then
                  Save Chain to Chain Collection
                  Exit Do
               End If
            End If
         End If

         NextSpot += StrideSize
       Loop  

    End If
  Next         
Next         

Bible Codes anyone?

$\endgroup$
  • $\begingroup$ Thank you! I had been thinking of something like this. It seems a viable option, and I will likely implement a similar approach if no existing methods or algorithms are found to be applicable. $\endgroup$ – Espenol Mar 18 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.