Finding periodicity in discrete events

Question

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.

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.

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?

Answer 1

See "ePeriodicity: Mining Event Periodicity from Incomplete Observations" by Zhenhui Li, Jingjing Wang, and Jiawei Han (2013); preprint at https://faculty.ist.psu.edu/jessieli/Publications/tkde14.pdf

Answer 2

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

Answer 3

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?