Ask HN: Fast data structures for disjoint intervals?

Your description of the problem smells a bit like job-shop scheduling. Optimizing job-shop scheduling is NP-Hard, so at best one general purpose algorithm might be better than another, but you can't determine which by simple inspection. Efficiency will vary based on the actual details of your data.

The standard approach (after managing IO) is to tune for the regularities in your data. Regularities are what makes your arbitrary data arbitrary data and not random values. Tuning the algorithm can get you a long way in the time domain. No data structure alone can get you out of NP. Good luck.

An RTree is the first structure that comes to mind, but the way you describe the problem, it sounds like the intervals never overlap, so I have my doubts. Sounds like you might be looking to optimize the query "what is the first interval of at least N days?" Maybe look at priority trees. They're good at queries that are bounded in one dimension and half-open in the other.

The improved cache behavior alone can make an order-of-magnitude difference. The cost you pay, of course, is on inserts and removals, but perhaps these can be ammortized in a read-heavy workload (build up a list of changes, and then rebuild in one go).

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

However, that was mainly for the case where I needed to detect overlapping intervals. Depending on your application perhaps a K-d tree, in this case, K=2 (one dimension for start-time the other for the end-time)? If you know that all you intervals are entirely disjoint (no overlap at all) I don't think you'll be able to do better than just an ordered map or list.

I imagine the answer depends on exactly what queries you need. If you have a bunch of different standard event sizes, then managing multiple different sorted freelists for the next open 1 hour slot, the next open 3 hour slot, etc might work. If you need high concurrency and "next available slot" is allowed to be fuzzy, then managing four distinct "event heaps" and parallelizing across them might work.

I’m not sure how applicable my solution is to your problem, but it might work well. I implemented a custom btree with the semantics I needed, since btrees are fast and have great cache locality. The trick is making one that understands ranges, not just singular keys like std BtreeMap.

The code is here if you’re curious. It’s implemented on top of a pair of vecs - which makes it 100% safe rust, and curiously faster than the equivalent tree-of-raw-allocations approach. Please forgive the poor documentation - it’s an internal only type and the code is new enough that the paint hasn’t dried yet.

https://github.com/josephg/diamond-types/blob/master/src/ost...

Have you tried roaring bitmaps?, it will internally use either a sparse or dense representation based on the bits set and uses SIMD for all its operations.

Do consider to explicitly use 16(-ish) bit pointers instead of native sized ones, and go for a SIMD-friendly binary trie; with some degree of implicitnes where it is addressed as if it was storing a set of mutually prefix-free variable-length (capped to something though, like 32 in your example) bitstrings (no entry is a prefix of another entry), but you're not looking to distinguish `{00, 01}` from `{0}`.

Operations are restricted, but it should be able to be very fast for "find first empty of at least X large starting at or after Y" as well as "clear from X to Y inclusive" and "add/mark from X to Y inclusive".

Something to look into would be to ensure that the starts of intervals are sorted after the ends of intervals if they happen to be at the same time. If you got that then the starts and ends of intervals simply alternate and most queries easily translate to one or two lookups.

A few thousand elements is still small for a computer. I would be curious to see a benchmark comparing sorted arrays of intervals against the fancier structures.

One which came to mind which possibly might be interesting would be the Bounding Interval Hierarchy[2], where you partition the space but also keep the min/max intervals of all children in each node. The "Instant ray tracing" paper[3] details some interesting techniques for speeding up construction.

Or perhaps it's a rubbish idea, haven't really thought it through.

[1]: https://en.wikipedia.org/wiki/Binary_space_partitioning

[2]: https://en.wikipedia.org/wiki/Bounding_interval_hierarchy

[3]: http://ainc.de/Research/BIH.pdf

"Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility" by George Varghese and Tony Lauck

http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing...

You mentioned shop scheduling below as well. If your intervals represent booked time, you could also insert 'unavailable' time into the coalesced set, so that, when fully booked, the interval set is reduced to a single interval.

--

1: https://or-tools.github.io/docs/cpp/classoperations__researc...

If you need second level precision for scheduling, you probably do, but a u16 will cover a 45 day range with minute level precision.

Make a binary tree where node sizes are powers of 2. I'm assuming you can define some "zero" time. To add an interval, first check if it exceeds the tree size and if so, double the size of the tree until it fits inside. Doubling involves making a new root node and inserting the existing tree under it (this was extra fun in 3D). Then decide what node size your interval should reside in. I would use the first power of 2 less than or equal to the interval size. Then insert that interval into all nodes of that determined size. Yes, I allow more than one object in a node, as well as allowing smaller nodes under one containing an object. An object may also span more than one node. In other words the objects (intervals) determine their own position in this tree regardless of others in the tree. It's not perfectly optimal but it allows inserts and deletes in O(logN) as well as intersection checks.

If this sounds not too terrible for the 1D case, I can elaborate on the data structure a bit.

Edit: From another comment "quickly finding the nearest gaps of at least duration X is most important." That possibly invalidates this whole approach.

Each interval is represented by a particle of radius half the interval, positioned at the middle of the interval.

Because the radius vary, you can either use adaptive algorithm, or split the interval into multiple small particles.

There is not a lot to gain when doing a single query, but when you are batching queries, you can share the computation and memory accesses. Using radix sort for sorting the integers you get a complexity for iterating over all collisions of O( NbKeys + NbQueries + NbCollisions ).

1st - Put all the actual data in a sorted / linked list. Keep this updated as you always have

2nd - As a separate thread, Keep an ordered set of lists, each list matching a time in the past, present, future, with increasing increments as you move from the present. Each of those lists can be all the items available at that time. The past is for reporting on old events, etc.

  -365 days
  -180 days
  -90 days
  -45 days
  -30 days
  -29 days...
  -1 day
  -23 hours... -1 hour

  NOW

  +1 hour... +23 hours
  +1 day...  +30 days
  +45, 90, 180, 365 days

If there's a pointer error, scan the whole list, the slow but reliable way.

BTreeMap should be nearly optimal, up to fiddling with the layout, changing the number of entries stored in one node, and vectorizing your within-node query function.

For people who need to store sorted sparse records and have memory to spare, or who know the keys of their sorted sparse records take on few values (like only a few million?), they can use a robinhood hash table without any hash function. The whole thing may not fit in a relevant cache, but you generally won't hit more than 1 cache line for the types of queries described. Again, I can't really recommend a library, but it's pretty easy to write this yourself.

Edit: Here's a link to one robinhood hash table: https://github.com/dendibakh/perf-challenge6/blob/Solution_R...

For queries like "next/previous free interval with length at least K", scanning within the appropriate level of a Fenwick tree may be better than scanning within a list of occupied intervals. Maybe you could use a layout that keeps all the entries for a level together, rather than the usual layout that mixes in less useful information and puts useful information powers-of-2 apart just to make the cache behavior as bad as possible. For example, if you have K=100, then you could look in the level that has sums of runs of 64. It's necessary but not sufficient to see 2 consecutive entries with at most 28 missing or 3 consecutive entries with at most 92 missing and the middle entry completely empty. Generalizing to arbitrary K is left as an exercise for the reader.