An interval sequence is a finite even-length sequence of a strictly weak ordered set . Subsequent pairs of this sequence are called intervals. Each interval represents the set . The interval sequence represents the union of its intervals. Note that an interval is empty whenever , but still well-defined. Sometimes it is useful to restrict to non-decreasing interval sequences, so that union, intersection, and difference, of interval sequences, can be computed efficiently.
The motivation for this concept was originally to represent a sliding window over a time-series when using the PointKdTree. When the window was moved, only the symmetric difference between the old window and the new window needed to be updated. Since the window needed to be of such a shape that the center of the window needed to be excluded, something more general was needed rather than just intervals. This assumed a non-decreasing interval sequence.
The interval sequences are also used in the query algorithms for the temporal kd-tree, to represent the time-subset over which the query is made. Here there are no restrictions for the interval sequences.