On the Partitioning of Intervals
31.03.2017
| Date | 31.03.2017 |
|---|---|
| Time | 10:45 |
| Place |
|
| Speaker | Michael Böhlen |
| Area of expertise | Physics |
| Host | Dep. Physik |
| Contact | |
| Abstract | An interval join is a basic operation with applications in temporal, spatial, and uncertain databases. Unfortunately, basic algorithms to efficiently evaluate joins, which are the core operations of database systems, deteriorate if the data includes intervals. This happens because for intervals no total order exists and either the start or end point is used for the sorting. Doing so leads to inefficient solutions with lots of unproductive comparisons. We propose Disjoint Interval Partitioning (DIP), a technique to efficiently perform sort-based operators on interval data. DIP divides an input relation into the minimum number of partitions, such that all tuples in a partition are non-overlapping. This yields efficient sort-merge computations where the number of unproductive comparisons is linear in the number of partitions. |