Interavl

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 It

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:?})");
}

Performance

Lookup operations against an IntervalTree are fast, executing against millions / billions of keys per second:

Interval stabbing and membership queries are particularly fast due to the use of subtree pruning to reduce the search space.[^filter-perf]

• 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).

[^filter-perf]: Interval stabbing filters ~53 billion intervals per second.