Finding periodicity in discrete events

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?

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

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

• 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. Mar 14, 2019 at 12:33

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
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?

• 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. Mar 18, 2019 at 10:26