3
$\begingroup$

I'm in search for a data structure which efficiently operates over closed intervals with the following properties:

  • dynamically add or remove an interval

  • set, and anytime change, a number ("depth") for each interval. no two depths are ever the same

  • find all intervals that overlap with any given interval, sorted by "depth"

The closest structure I found is Interval tree but it lists the found intervals in arbitrary order with respect to their depths. I could collect all the "unsorted" intervals as reported and sort them afterwards but I was hopping it was possible to avoid to sort the result for every query.

Please, does anyone know of such data structure or have any suggestion how (if at all possible) to enhance the Interval tree to support such sorting?

Example:

  1. add [1,2] to the empty structure and set its depth to 1

  2. add [10,100], depth = 2

  3. add [5,55], depth = 3

  4. query for [5,50] reports [10,100] and [5,55]

  5. set depth of [10,100] to 3, and of [5,55] to 2

  6. query for [5,50] reports [5,55] and [10,100]

Edit

I'm more interested in fast adds/removes and queries, than in updating of depths. A depth can take as much as O(n), if that helps speed-up the other operations.

$\endgroup$
  • 1
    $\begingroup$ I suggest a simpler problem, so it might be easier to find references. Consider the case where all query intervals are single points. So you get the standard stabbing query problem. Section 3 might be relevant, but it seems to only output the top-$k$ intervals in sorted order, where $k$ is a constant. $\endgroup$ – Chao Xu Feb 13 '15 at 23:43
3
$\begingroup$

Using an interval tree and sorting results is a great solution. It will have quite good running time. You can add, remove, or find an interval in $O(\log n)$ time and change the depth of an interval in $O(1)$ time once you've found it. Also, you can process an intersection query (report all intervals that overlap a given interval) in $O(\log n + m \log m)$ time, where $n$ is the total number of intervals and $m$ is the number of results.

Can you do better? It seems clear that you can't do very much better. Obviously, no comparison-based data structure can beat $\Omega(\log n + m)$ running time for intersection queries, so this trivial lower bound shows you are at most $\log m$ times slower than optimal.

Also, we can prove that no comparison-based data structure can beat $\Omega(\log n + m \log m)$ time for an intersection query in general, if you can change the depth of an interval in $O(1)$ time. Consider the case $n=m$, and where all intervals overlap and should be returned. If you could answer the intersection query faster than $O(m \log m)$ time, you could sort $m$ numbers faster than $O(m \log m)$ time, which we know is impossible for comparison-based algorithms. (Well, more precisely, if you have $t$ arrays of length $m$, and if you knew how to answer intersection queries in $O(\log n + m)$ time and change depths in $O(1)$ time, you could sort all $t$ of those arrays in $O(m \log m + t (m + \log m)) = O(m (t+ \log m))$ time using your data structure by adding $m$ copies of the same interval, changing all their depths based on the first array, doing an intersection query, then changing all of their depths based on the second array, and so on. However $O(m(t+\log m))$ running time is provably impossible for this task: the standard lower bound on comparison-based sorting shows that this takes $\Omega(t m \log m)$ time, and when $t$ is large enough, this is a contradiction -- e.g., when $t=m$, this would give a way to sort $m$ arrays of length $m$ in $O(m^2)$ time, when we know it actually takes $\Omega(m^2 \log m)$ time.)

So, if you want to hope for a data structure that allows intersection queries to run strictly faster than $\Theta(\log n + m \log m)$, you either need to allow changing the depth of an interval to take longer than $O(1)$ time, or you need to consider non-comparison-based data structures.

If you knew that your depths were all small integers, you could speed up this algorithm by using a faster sorting algorithm optimized for that case (e.g., counting sort). However in practice existing sorting algorithms are already very fast so it's not clear whether this would make a big difference in practice.

So this algorithm already seems quite good, and it seems unlikely that we can beat it using comparison-based data structures. If you want to do better, you'll have to specify a model of computation (e.g., the RAM model), but it's unclear that algorithms with a better asymptotic running time will lead to something that is faster in practice.

$\endgroup$
  • $\begingroup$ The lower bound argument for intersection doesn't work. The argument shows it takes at least $\Omega(n\log n)$ time to insert $n$ intervals then do an query. It doesn't bound how much time the query takes. $\endgroup$ – Chao Xu Feb 13 '15 at 22:25
  • $\begingroup$ @ChaoXu, you are right. Thank you! My reasoning is only correct if you also assume that changing the depth can be done in $O(1)$ time [as is the case for the interval tree + sorting approach]. If you are willing to allow changing the depth to take longer, then I cannot rule out the possibility of intersection queries that run faster than $O(\log n + m \log m)$ time. I've edited my answer accordingly, and to spell out the proof in more detail to take into account the $\Omega(n \log n)$ part of the running time. See the 3rd and 4th paragraph of my edited answer above. Does it look good now? $\endgroup$ – D.W. Feb 13 '15 at 22:33
  • $\begingroup$ It looks good. I usually assume update operation is just a delete followed by a insert. (Most data structure function this way, although there are exceptions...) $\endgroup$ – Chao Xu Feb 13 '15 at 22:51
  • $\begingroup$ Thanks a lot for the thorough answer! Now that I think of it, I really don't need $O(1)$ depth changing. In fact, it could even be as slow as $O(n)$, I would much prefer fast interval edits and querying. In such case, do any other data structures come to your mind? I edited the question to reflect this. $\endgroup$ – Ecir Hana Feb 16 '15 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.