Optimal Interval Partitioning for Temporal Databases

Author:	Thomas Zurek
Date:	July 1997
Published in:	Proc. of the BIWIT Workshop, Biarritz, France
Publisher:	IEEE Computer Society Press
Pages:	140-147

Download

Full Paper (60 kB, not available to the public for copyright reasons)
slides of my conference talk (162 kB)

Abstract

We analyse the problem of partitioning a collection of intervals into two or more subcollections, each of them holding intervals that intersect with a certain range of the intervals' domain.

Intervals that intersect with more than one range impose a considerable overhead on processing and indexing interval data. The goal of interval partitioning (IP) is to find partitions that minimise the number of overlapping intervals. We describe an algorithm for finding optimal partitions and prove its correctness. An example scenario that is used throughout the paper gives an idea of the benefits of optimal interval partitioning.

Keywords

interval partitioning, temporal databases, parallel temporal joins, temporal index structures

Thomas Zurek, <tz@dcs.ed.ac.uk>