Searching in a large dataset

Question

I am working on a model of social interactions in mice. I have mice and boxes and a simulation that outputs which mouse stays in which box during which time period (this comes out as a mouse is selected randomly to change a box). The problem is how to obtain, in the end and from this, the meetings of two mice which were in the same box in an overlapping period. I need this to look at the CDF of meeting durations, build a social network for each day, etc..

Right now I have a MySQL database where the simulation directly inserts each stay result. And then another tool,written in Scala, just retrieves all stay result, in portions of a few hundred, loops through them and for each asks the database which stays were overlapping with it, and inserts each pair into the database, like this:

box,id1, res_id1, id2, res_id2, from, to, dt, typ

This means that mice id1 and id2 were in the box "box" in the interval between "from" and "to" with duration "dt" and the meetings was of type "typ". There could be four types of meetings depending on when each mouse was in the box (e.g. when the one entered and exited relative to the other). "res_id1" and "res_id2" tell which stay results were used to generate the meeting result.

Obviously, this is very inefficient. What would be a better way of doing it? I am not constrained to using a RDMS, but I though this would be the easiest as I am reading and further analyzing the data in R afterwards. Would it make sense to output the stays in a text file and then use Hadoop to generate the meetings somehow? Or anything else?

For the duration of an approximately one quarter of one trial of the simulation I generate around 1.5 million stay results.

Answer 1

You need to think "out of the box" (pun intended). Because you have a database of stays in the boxes, you think of your algorithm of looping over all stays. But to find overlaps, you need to compare each stay with each other stay -- so your algorithm has ${\cal O}(N_s^2)$ complexity where $N_s$ is the number of stays. This is expensive, as you have noticed.

So turn it around. Instead of a loop over all stays, have a loop over all boxes and do this:

• For each box, extract those stay events that are associated with this box into a list or subset (complexity: ${\cal O}(N_s)$).

• Sort this subset by start time (complexity: ${\cal O}(N_{s,b} \log N_{s,b})$ where $N_{s,b}$ is the number of stays in box $b$). If your database was filled in ascending start times of stays, this step is not even necessary.

• Within this subset, loop over all stays and compare whether the end time of one event is later than the start time of the next event. This indicates an overlap. (Complexity: ${\cal O}(N_{s,b})$.)

What I describe is a pretty common strategy: If a loop over a collection of data is inefficient, think whether there is a different way of looking at the data set and loop over something else instead.