The VLDB Journal · 2021 · 20 citations · 31 references
ComputingComputer ScienceComputer SystemsData StructuresDatabasesJoiningDatabase ManagementHash TablesQuery OptimizationQuery ProcessingRelational AlgebraTemporal DatabasesAllen's Interval AlgebraReal-time Event ProcessingReal-time ProcessingTemporal AlgebraTemporal IndexingTemporal Join ProcessingTemporal Query ProcessingTemporal Relational Databases
Abstract 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.
31
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
Maintaining knowledge about temporal intervals
James F. Allen · Communications of the ACM · 1983 · 7.5K citations · Full text
Rina Dechter, Itay Meiri, Judea Pearl · Artificial Intelligence · 1991 · 1.8K citations
Temporal reasoning based on semi-intervals
Christian Freksa · Artificial Intelligence · 1992 · 673 citations