Re: dynamic structure for storing/querying intervals

Googmeister wrote:
Mark P wrote:
I'm looking for advice on an efficient data structure that can store
intervals on a line (or, in possibly degenerate cases, just points).
I'd like to be able to query the structure by providing a range (again,
possibly degenerating to a point) and retrieve all intervals which
overlap the query range. Additionally, and this is where some of the
conventional structures I've found fall short, I'd like the structure to
support dynamic insertions and deletions. That is, inserts and deletes
may be mixed in with the queries.

Currently I'm using a structure of my own invention which is a balanced
search tree of all interval endpoints, which additionally keeps track of
which intervals start at or contain each such point, updating this data
as intervals are added or removed. The drawback to this approach is
that when many intervals overlap the performance degrades significantly.

I think you want an interval search tree. It's a balanced BST of
intervals,
sorted by left endpoint. Each node also contains the maximum endpoint
in its subtree. This suffices to do insert, overlap, and delete
efficiently.

http://en.wikipedia.org/wiki/Interval_tree


Ah, thanks. Funny, I had looked at the Interval Tree in CLR some time ago and had somehow been left with the impression that it didn't support dynamic operations. But you are indeed correct that it does all of the things I've asked for.

Thanks,
Mark
.

Relevant Pages

  • Re: dynamic structure for storing/querying intervals
    ... intervals on a line (or, in possibly degenerate cases, just points). ... I'd like to be able to query the structure by providing a range (again, ... that when many intervals overlap the performance degrades significantly. ... Each node also contains the maximum endpoint ...
    (comp.programming)
  • Re: dynamic structure for storing/querying intervals
    ... intervals on a line (or, in possibly degenerate cases, just points). ... I'd like to be able to query the structure by providing a range and retrieve all intervals which overlap the query range. ... I imagine a collection of points, each point with an indication of whether it's left or right end-point, and a reference to the interval object it belongs to, stored separately. ... While succeeding points are inside the search interval, store the points in some intermediate structure, sorted or hashed on their interval object references. ...
    (comp.programming)
  • Re: Availability between dates
    ... The interval does not overlap at all the interval [fromThis, ... make a second query which will look at all the items not in the first set. ... ID and belonging to a category, e.g. seats, chairs, tables, etc ... that will return which products can be hired based on the hire request ...
    (microsoft.public.access.queries)
  • Re: Date range overlap
    ... This will provide excellent support for my ... way the query works. ... Is the overlap a weekday? ... rather than allenbrowne at mvps dot org. ...
    (microsoft.public.access.formscoding)
  • Re: dynamic structure for storing/querying intervals
    ... intervals on a line (or, in possibly degenerate cases, just points). ... I'd like to be able to query the structure by providing a range and retrieve all intervals which overlap the query range. ... I imagine a collection of points, each point with an indication of whether it's left or right end-point, and a reference to the interval object it belongs to, stored separately. ... While succeeding points are inside the search interval, store the points in some intermediate structure, sorted or hashed on their interval object references. ...
    (comp.programming)
Loading