1
$\begingroup$

This question was originally posed to Math SE. It was suggested that DSP SE would be more suitable.

Background & Motivation:

I have three lists of timestamps (UNIX timestamps, plus a subsecond part (e.g. 1451606400.9475839201)). They are not necessarily of the same size, however they are ordered. Each such list corresponds to a real-life instrument, of which there are three. The instruments in question record a time stamp each time they observe an "event". We may assume that their clocks are synchronized.

The issue is that the instruments are so sensitive, they record timestamps very frequently (on the order of 10 Hz), and only a small portion correspond to actual events. It is difficult to put a number on precisely how many timestamps are real events (perhaps a handful per year).

Further, the instruments are close in proximity, so if one instrument "sees" and event, the other two almost certainly do as well. The clocks are precise enough to record the difference in observation time, even over miniscule differences.

The data is for one year, the same year for each of the three lists. We may assume that the "random" timestamps are uniformly distributed. There are, however, gaps in the data (e.g. maybe all three instruments were off for the months of March, April, May). The gaps will be the same for all three lists.


Goal:

Using only the timestamps, I want to attempt to find those which are "likely" to correspond to a "real" event, such that further analysis can be conducted. The "events" in question are light signals, so I can restrict my search to only those for which the difference in observation for some triplet of timestamps is less than the transit time between two observers.

My first inclination was to, from the three lists, produce a list of triplets, one timestamp contributed by each list, such that $max(A,B,C) - min(A,B,C)$ was minimized. Unfortunately, this found very few "triplets" which a) fell in the restriction mentioned previously and b) corresponded to "real" events. I mentioned previously that there are very few events, however I expect there to be far more than what this found.

I then tried doing the above, but minimizing the $\chi^2$ error, which I defined for some triplet $A,B,C$ (one from each list/instrument) as $(A-B)^2 + (A-C)^2 + (B-C)^2$. This found even fewer "triplets", and no real events.


Problem:

What techniques can be used to extract "coincidences" (the "real events") from a set of more-or-less uniformly distributed data, where there is far more random than "real" data? Here, we assume that I have access only to the timestamps.

$\endgroup$
1
  • $\begingroup$ Hi! Does one physical event lead to at most one timestamp per sensor, or is it likely that one physical leads to multiples? $\endgroup$ – Marcus Müller Jan 27 at 9:53
1
$\begingroup$

Judging from your description alone, I'd say an algorithm to find appropriate 3-clusters of timestamps would be something like:

  1. compare the three first elements of your sorted lists. Pick the earliest of the three.
  2. Remove the element from its list.
  3. determine difference of that element to the other two first
  • If both difference are below a "simultaneity" threshold, register a new "common event".
  1. return to 1

Often, you'd also remove the two "matches" from the other two list in 3., but that reduces your ability to detect ongoing physical excitation of your sensor as one by post-processing your "common events" list.

Seeing you're only dealing with about a billion timestamps in total, this simplified variation of your distance-limited cluster detector should allow for quick experimentation¹.


But:

Reading through your question, it seems likely that one physical phenomenon can lead to multiple adjacent timestamps in a single list, so that would be another factor that might help to characterize real events vs false alarm. In that case, better modelling might be highly desirable, but as a rough idea:

Imagine your three lists as three parallel lines in three-dimensional space. They are arranged with equal distance to each other, i.e. there's a fourth parallel line in their "middle" that has the same distance to each one of them.

Now, imagine your timestamps are points on the respective lines.

For every point on your magical middle line, you draw a sphere around that point and count the time stamps in that sphere. Setting an appropriate sphere radius and threshold allows for good detection.

If you have a mathematical model for how observed timestamps relate to real phenomena, that can change the shape of your sphere, and make it "fuzzy", i.e. weighing points further away less than nearby.

In the end, you'd have a function that says "for each time on my middle line, this is the likelihood of a real event having happened"; you can then build a maximum likelihood detector.


¹ hint: This might be a bad stereotype, but you sound like a matlab user. If there's one easy thing matlab is slow at, it's doing actual m-code loops and removing heads from lists; it's always preferable to just work at the end of a contiguous vector of data, since all you need to do to "remove" an element is change your own notion of length.

$\endgroup$
1
  • $\begingroup$ @KeithMadison that makes your loops more efficient, definitiely! Still look for the usual container performance pitfalls (linked lists are slow, inserting into a std::vector is slow, removing elements from a vector anywhere but the end is slow) $\endgroup$ – Marcus Müller Feb 1 at 7:29

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.