Data structure for representing and querying future time intervals

Question

I would like to represent the predicted state of an element of my system in the future. The element can either be in state S1 or S2. S1 predictions are non-overlapping intervals of the form <t_start, t_end> where the t_s are relative times in the future. The absence of an S1 interval implies the state is S2 and only S1 predictions are ever made. The main operations are adding predicted intervals and querying the state for an arbitrary future time. State queries will happen a couple of orders of magnitude more frequently than queries. Intervals can be added for any time in a finite horizon, in any order relative to existing intervals. The other important operation is the progress of time, which means that predictions get closer and eventually pass into the past where they can be forgotten. Predictions may be removed very infrequently, but this isn't essential. The underlying model of time could be continuous, or discretised to integer timesteps.

I already have an implementation of this using a linked list where the position in the list represents time (using time discretised to integers) and the node content is either S1 or S2. This is great for updating as time proceeds (you just the drop the first node), and reasonably fast to query (linear in number of future time steps). However, because you're enumerating all possible timeslices it is a little ugly in terms of adding predictions, and it scales badly as you increase the time horizon or the precision of the timeslice. I am therefore looking for an alternative approach (e.g. based on interval somehow).

This would be determined by the fidelity of the timeslice and the size of the horizon. 6000 would be a typical number I think. — Nick Hawes, Jul 17 '13 at 16:46
(6000 is a small enough number that, given the prevalence of queries, a bitmap might be a good idea.) — David Eisenstat, Jul 17 '13 at 16:54
Agreed. I prefer the elegance of the tree approach, but I will profile both in the full system to check. — Nick Hawes, Jul 19 '13 at 01:50

score 1 · Accepted Answer · answered Jul 17 '13 at 00:29

1

One possibility is to store the intervals in a binary search tree. I would suggest a splay tree if you can stand its linear-time worst case behavior, because it adjusts itself to deal with favorable query patterns in amortized constant time.

Since the intervals don't overlap, searching the BST is pretty straightforward. If the query point is contained in the current interval, then we're done. If it lies to the left, search the left subtree. If it lies to the right, search the right subtree.

answered Jul 17 '13 at 00:29

David Eisenstat

64,237
7
60
120

This makes sense, and a custom query for points within intervals could actually be faster than searching for a particular leaf node (I think...). I will have a play and see how well it works. – Nick Hawes Jul 17 '13 at 16:48
I went with a red-black tree in the end, as I'm never querying for specifically stored instances so the splay tree optimisations are unnecessary. – Nick Hawes Jul 19 '13 at 01:49

Data structure for representing and querying future time intervals

1 Answers1