CODEWITHSUNDEEP
c#algorithmdata-structuresintervalsset-operations
Mikkel R. Lund
Mikkel R. Lund

Reputation: 2627

Data Structure for Fast Set Operations

I'm working on a C# implementation of the Interval Binary Search Tree by Hanson and Chaabouni. In short terms, it is a data structure for dynamic interval collections that allows you to quickly find intervals that overlap a point. The data structure is an augmented binary search tree (BST) using an AVL balancing scheme.

Each node in the tree contains three sets of intervals. When doing rotations, we need to do a lot of set operations in order to maintain the invariant. We need support for iterating the intervals in a set, addition and subtraction of sets and set intersections. If the collection contains duplicate intervals (intervals that have the same endpoints, but are not the same object) they will be contained in the same sets.

We need to be able to do these set operations as fast as possible - it is our limiting factor atm. Is there any data structures that supports these operations efficiently?

Bonus info:

Upvotes: 1

Views: 527

Answers (1)

Stoian Hadzhiyski
Stoian Hadzhiyski

Reputation: 1

I use a similar approach for implementing IntervalSet collection, storing generic intervals. This is my GitHub repository. Below is part of the docs, describing details about IntervalSet:

Manipulation over sets of intervals is done with IntervalSet collection. It's an implementation of Augmented Interval Tree abstract data structure, using self-balancing Binary Search Tree (BST) - AA Tree. IntervalSet provides basic operations - Add, Remove, Union, UnionWith, Intersect, Except, Merge. It's initialization and union algorithms are influenced by Sorted Set from System.Collections.Generic.

IntervalSet implements ISet, hence also IEnumerable and iteration is supported. Intervals are stored ordered by start and then by end. Iteration is also done in that order. Addition and substraction of interval sets can be done using Union, UnionWith and ExceptWith.

The differences are that for simplicity I use AA Tree instead of AVL tree, each interval stores a value along with it's start and end limit, and there are no duplications - IntervalSet stores only unique intervals (by limits). Check the docs for more info.

The primary focus of the Augmented Interval Tree is to support a broader range of interval-based queries and computations through its augmented attributes (in my case max end limit as shown in the Wiki). However, it must be fully capable of efficiently finding intervals that overlap with a specific point. This can be done by using the Intersect method overload of IntervalSet, accepting only single limit. Here is an example:

var intervalSet = new IntervalSet<int, int?>
{
    (3, 7), // [3, 7]
    (5, 10), // [5, 10]
    (8, 12), // [8, 12]
    (1, 5), // [1, 5]
    (15, 20) // [15, 20]
};

var intersectedIntervals = intervalSet.Intersect(6); // returns an interval set with [[3, 7], [5, 10]]

I've also published a NuGet package called NeatIntervals. You can get IntervalSet collection from there.

Upvotes: 0

Related Questions