(Big?) Data Question: Searching in a large dataset | Hacker News Reader

(Big?) Data Question: Searching in a large dataset

4 pointsgeorgismilyanov10 comments

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

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 analysing 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.

I expect your simulation simulates the movements of all mice simultaneously in time order.

If so, it might be easier to directly create the overlap results from the simulation. For example, when a mouse enters a box, check and remember what other mice are there. When that mouse leaves, check again and create the record for the stay.

If that isn't possible or feasible, check whether your database supports range types and queries. It might be worthwhile to migrate to PostgreSQL just for this (see https://wiki.postgresql.org/images/7/73/Range-types-pgopen-2...)

It is not simultaneous. I use the Gillespie technique for stochastic simulation. I select a mouse at random to change boxes, depending on its transition rate compared to the transition rate of the system as a whole.

Are the mice interchangeable? If so, can you simulate one, get a distribution of box occupancy from it, and compute interactions from that?

No. That's the point. It is a simulation of a complex system. The interactions between the mice are everything.

How about having a table where each row corresponds to a duration of time?

time | total | mice_ids (a json string. or use mongo)

And then, run through all your data and assign each mouse to a certain duration (ie, minute one, minute two, etc), updating the total counts every time as well as the mice_ids. Then, you could query by minute and see which minutes had meetings in them (ie, select mice where total > 2)

Thank you! But I am thinking, could I be able to obtain easily the duration of each meeting using this setup? This is what I would ultimately need (to construct the empirical cdf, social network, etc.)

It also doesn't strike me as especially expensive. A dumb, brute force query (that is, something in 0(N^2)) wouldn't take so long with only a few million rows. So I would just try doing through each row, doing a full table scan to find meetings, and just let that cook for a little while.

It's not like you're ingesting gobs and gobs of data in real time :)

Hmm. How are you defining a meeting? Is a meeting a pair of mice? Or is it a pair of mice with a time component? So a pair of mice + the duration of time they were together?

Exactly.

There are four types of meeting: mouse 1 entered -> mouse 2 entered -> mouse 2 left -> mouse 1 left; mouse 1 entered -> mouse 2 entered -> mouse 1 left -> mouse 2 left; mouse 2 entered -> mouse 1 entered -> mouse 1 left -> mouse 2 left; mouse 2 entered -> mouse 1 entered -> mouse 2 left -> mouse 1 left.

Then the meeting record contains the times the two were together and the duration of this.

The dumb approach is very slow. Would it be a good idea to read all stay results in Scala (or whatever) and try to do the searching in memory, completely eliminating th db? But then the comparisons would be more expensive...

Try a columnar database solution for time series.

Reply on news.ycombinator.com