2
$\begingroup$

I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. if $I_q$ is a super-interval of some interval of the structure (so the answer of the query is just boolean, no need to output all such intervals on the structure) at the fastest possible time complexity.

I have searched for such a combination, and found out that probably an Interval Tree would be appropriate for my situation, with $O(\log n)$ interval insertion and overlapping intervals query (so it's not exactly my desired query, but I think that it could possibly be turned to it. Also I can avoid the output complexity dependence, since the desired output is boolean and therefore on the first match I would know the answer is true).

Furthermore, here (https://en.wikipedia.org/wiki/Interval_tree) it is stated that:

If the endpoints of intervals are within a small integer range (e.g., in the range [1,...,O(n)]), faster data structures exist with preprocessing time O(n) and query time O(1+m) for reporting m intervals containing a given query point.

Since I also can guarantee that both interval ends are going to be small integers (i.e. not floats, but natural integers up to $\approx 10^6$), what would be the best data-structure/algorithmic way (considering time-complexity of the above two operations) to implement those two operations I would like to have?

If the fastest time-complexity would be an Interval Tree, then how can I modify the overlapping-intervals query to support my query in $O(\log n)$ time, i.e. not $O(k\cdot\log n)$ where $k$ is $I_q$'s range? However, I am quite interested in the above quoted passage, and how I could possibly (with another data structure, maybe?) manage such a fast complexity, so in that case Interval Trees wouldn't matter.

Note: In my attempt to test such an algorithm and speed on an Interval Tree, I have found out the following library: https://github.com/chaimleib/intervaltree/blob/master/intervaltree/intervaltree.py where a similar query seems to be implemented on the envelop query with a time-complexity of $O(m+k\cdot\log n)$, where "$n$ = size of the tree, $m$ = number of matches, $k$ = size of the search range", which however is not as fast as I would like (especially considering the $k$ multiplying factor).

$\endgroup$
  • $\begingroup$ I don't see how to support this query in a way that achieves guaranteed worst-case efficiency if you're using an interval tree. If you care about worst-case performance, you might need to consider other data structures. $\endgroup$ – D.W. Aug 14 '19 at 16:35

Your Answer

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

Browse other questions tagged or ask your own question.