This crate implements an interval tree backed by an augmented, balanced binary search tree (an AVL tree - interavl - get it?!)
The IntervalTree maps half-open intervals to opaque values, and provides
efficient querying of all stored (interval, value) tuples that match a variety
of temporal relations described by Allen's interval algebra.
use interavl::IntervalTree;
// Initialise an empty tree.
let mut t = IntervalTree::default();
// Insert interval & value tuples into the tree.
//
// Intervals can be composed of any type that implements "Ord" such
// as timestamps, strings, etc.
t.insert(24..80, "Bob");
t.insert(10..100, "Doris");
t.insert(40..55, "Frank");
t.insert(100..400, "Nigel");
// Find which intervals overlap with a query interval:
for (interval, name) in t.iter_overlaps(&(42..50)) {
println!("{name} overlaps (matching interval is {interval:?})");
}Lookup operations against an IntervalTree are fast, executing against
millions / billions of keys per second:
| Tree Size | Build Tree | Lookup Value | Stabbing Query |
|---|---|---|---|
| 100 tuples | 3µs | 7ns | 59ns |
| 1,000 tuples | 81µs | 8ns | 101ns |
| 10,000 tuples | 1ms | 9ns | 172ns |
Interval stabbing and membership queries are particularly fast due to the use of subtree pruning to reduce the search space.1
- Build Tree: insert the N keys listed into an empty tree (inclusive of random value generation)
- Lookup Value: find an interval in the tree and return the value for it
- Stabbing Query: yield all intervals that overlap with a given query interval
The above measurements capture the single-threaded performance of operations against a tree containing varying numbers of keys on a M1 MacBook Pro.
The benchmarks to generate these numbers are included in this repo (run cargo bench).
Footnotes
-
Interval stabbing filters ~53 billion intervals per second. ↩