Skip to main content


Swipe to navigate through the articles of this issue

13-02-2021 | Regular Paper | Issue 3/2021 Open Access

The VLDB Journal 3/2021

Cache-efficient sweeping-based interval joins for extended Allen relation predicates

The VLDB Journal > Issue 3/2021
Danila Piatov, Sven Helmer, Anton Dignös, Fabio Persia
Important notes

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


We develop a family of efficient plane-sweeping interval join algorithms for evaluating a wide range of interval predicates such as Allen’s relationships and parameterized relationships. Our technique is based on a framework, components of which can be flexibly combined in different manners to support the required interval relation. In temporal databases, our algorithms can exploit a well-known and flexible access method, the Timeline Index, thus expanding the set of operations it supports even further. Additionally, employing a compact data structure, the gapless hash map, we utilize the CPU cache efficiently. In an experimental evaluation, we show that our approach is several times faster and scales better than state-of-the-art techniques, while being much better suited for real-time event processing.
About this article

Other articles of this Issue 3/2021

The VLDB Journal 3/2021 Go to the issue

Premium Partner

    Image Credits