CODEWITHSUNDEEP
javadata-structurestime-complexity
Radosław Łazarz
Radosław Łazarz

Reputation: 968

Data structure that provides a way to acquire intersecting periods with low computational cost

I have a (large) set of data. It consists of elements with timestamp property, so I would call them events for clarity (although it could be any comparable property).

If I want to be able to acquire all events with timestamp between A and B quickly I should store them in a TreeMap. But it is not the end of the story.

There are discrete events (with single timestamp) and continuous events (with two timestamps - one for begin and one for end).

Now, let there be four timestamps A B C D, such that A < B < C < D. There is also a continuous event x that starts at A and ends at D.

I wonder if there is an efficient data structure that, when asked for events between B and C, would also return event x (because it has a common part with period we are querying for). The most important for me is the cost of acquiring elements, but the cost of constructing and updating the structure matters also.

And finally, it would be even better if there is a Java implementation of such structure already available.

Upvotes: 1

Views: 63

Answers (1)

avim
avim

Reputation: 1019

You are looking for a Segment-Tree. Implementation of single event is trivial (choose the easy one depends on the tree implementation) -

  • with equal timestamps: [A,A], or:
  • with "epsilon" range: [A,A+e] such that e is the smallest positive number that can be represented.

Look at this question, and you can search/ask with this tag also. enjoy

Upvotes: 2

Related Questions