CODEWITHSUNDEEP
algorithmdata-structuresbigdata
thisismytemp
thisismytemp

Reputation: 441

How do you efficiently calculate large overlapping groups?

I have 2 VERY large groups of birds that fly in an X-mile radius circle which each has a tracker on them so I can determine where they are at any given moment. There is a portion of these two cirlces overlapping (similar to what a Venn diagram looks like).

Since these are birds, at any point in time, bird A (in circle 1) could be in the overlapping area or not, randomly.

On a periodic basis, I want to calculate the birds in the intersection and determine WHICH birds they are.

The problem I am having is determining the correct data structure for this. I have thought about using a Bloom filter, but it doesn't allow removals (bird moves out of the overlap) and is quite memory intensive.

I am open to any idea (store data in Redis to read from, etc).

Upvotes: 2

Views: 90

Answers (1)

mcdowella
mcdowella

Reputation: 19611

If the circles have fixed centers and radii, when you receive a location you can tell if that location is in the overlap (e.g., if the distance to each center is less than the radius). So your problem is maintaining a set from which items are deleted and inserted. The first things I would try would be a perfectly ordinary database, or an in memory HashSet.

If Redis suits you, the easy thing to do would be to create a key when a bird is in the overlap and delete it when it is not. This allows you to test to see if any bird is in the overlap, but not to read out which birds are in it efficiently. You could of course increment a counter when a bird was inserted and had not previously been in the overlap, and decrement it when a bird moved out of the overlap, to keep a running count of birds in the overlap.

It seems to me that you could use a Redis sorted set to maintain a set of birds in the overlap - see e.g. ZRANGE, ZADD, ZREM. If you hit some sort of limit with this, you could store, for each bird, a record with next and previous links to other bird records, and build a doubly linked list of birds in the overlap region - using Redis or any key-value store you trust.

Upvotes: 1

Related Questions