Joachim Faulhaber wrote:
2010/2/23 Phil Endecott <spam_from_boost_dev@chezphil.org>:
I was hoping to find that this library was an implementation of an interval tree. ?But it is not: it is built on top of normal standard-library containers. ?The implementation used can find the intervals that overlap a point in O(M + log N) time, but to do so it needs worst-case O(N^2) space and I think it needs O(N^2 log N) time to build that structure.
This is a very limited view on the library. I never claimed it has it's strengths in performing stabbing queries. I has so many more aspects and applications where it is useful and efficient.
It might help the discussion to describe some of these applications in depth. I can only think of examples where the O(N^2) space happens. Example: consider a building access-control system where users check in and out with cards; the system records a set of (in_time,out_time)->name records. If N people work in the building, it will take O(N^2) space to store each day's data.
If you insert N intervals in an interval_map the number of intervals (nodes) in the map is limited to 2*N-1. So space is O(N). A single addition of an interval into an interval_map has worst case time performance of O(N). So the worst case time for the addition of N interval value pairs is O(N^2). Which is not as bad as you write.
No, I believe my assessment is correct. See Luke's explanation.
The most frequent usage of interval_maps are aggregations, where you need all of the aggregated values. If, in the worst case N^2 aggregations are involved, you have to perform them anyway. If you'd use an interval tree to hold the data, you would not be able to store the the aggregation results for N+k segments in your N nodes. For what interval containers and specifically interval_maps are used most of the time, interval_trees are not an adequate data structure as far as I can see.
I don't entirely understand that paragraph. In an interval tree, I don't store the "aggregation results"; I just store the key-intervals and data. Aggregation occurs when I perform a lookup; I find all of the intervals that overlap my point or interval of interest, and merge their data in some appropriate way at that time. Regards, Phil.