# Indexing Temporal Relations for Range-Duration Queries

Matteo Ceccarello  Faculty of Computer Science
Free University of Bozen-Bolzano, Italy<EMAIL_ADDRESS>,  Anton Dignös
Faculty of Computer Science
Free University of Bozen-Bolzano, Italy<EMAIL_ADDRESS>,  Johann Gamper
Faculty of Computer Science
Free University of Bozen-Bolzano, Italy<EMAIL_ADDRESS>and  Christina
Khnaisser  Faculté de médecine et des sciences de la santé
Université de Sherbrooke, Canada<EMAIL_ADDRESS>
###### Abstract.

Temporal information plays a crucial role in many database applications,
however support for queries on such data is limited. We present an index
structure, termed RD-index, to support _range-duration queries_ over interval
timestamped relations, which constrain both the _range_ of the tuples’
positions on the timeline and their _duration_. RD-index is a grid structure
in the two-dimensional space, representing the position on the timeline and
the duration of timestamps, respectively. Instead of using a regular grid, we
consider the data distribution for the construction of the grid in order to
ensure that each grid cell contains approximately the same number of
intervals. RD-index features provable bounds on the running time of all the
operations, allow for a simple implementation, and supports very predictable
query performance. We benchmark our solution on a variety of datasets and
query workloads, investigating both the query rate and the behavior of the
individual queries. The results show that RD-index performs better than the
baselines on range-duration queries, for which it is explicitly designed.
Furthermore, it outperforms specialized indexes also on workloads containing
queries constraining either only the duration or the range.

##  1\. Introduction

Temporal information plays a crucial role in many database applications: in
fact, many database management systems and the SQL standard
(DBLP:journals/sigmod/KulkarniM12, ) provide automated version control of the
data and time travel facilities, allowing to efficiently access past history.
Past research mainly concentrated on efficient solutions for important
temporal operators, such as temporal aggregation (DBLP:conf/icde/KlineS95, ;
DBLP:journals/tkde/MoonLI03, ; DBLP:conf/edbt/BohlenGJ06, ;
DBLP:conf/ssd/PiatovH17, ), temporal joins (DBLP:conf/icde/PiatovHD16, ;
DBLP:journals/vldb/BourosMTT21, ; DBLP:journals/vldb/DignosBGJM21, ), and time
travel (DBLP:conf/sigmod/KaufmannMVFKFM13, ) queries. All these approaches
consider only the position of intervals along the timeline, ignoring another
important aspect, namely the _duration_ of intervals. As a result, index
structures to support more general selection queries that constrain both the
duration and the position in time of intervals have been missing
(DBLP:journals/sigmod/KulkarniM12, ; DBLP:journals/tods/DignosBGJ16, ;
DBLP:conf/ebiss/BohlenDGJ17, ) until recently (BehrendDGSVRK_SSTD19_period-
index, ). In many application domains, however, both aspects of temporal
information are useful to formulate queries.

###### Example 1.1.

As a concrete use case, consider the use of antibiotics in healthcare.
Antibiotic resistance is a world challenge, and the emergence of new
resistance factors is very difficult to monitor and to predict due to the
diversity of antibiotic usage and events (e.g., environment, species
evolution, medical practices, etc.) (Hayashi2011, ; Larsson2021, ). Selecting
the most appropriate antibiotic and the appropriate treatment duration is an
essential step to reduce antibiotic resistance (Hayashi2011, ). Thus, defining
guidelines for the duration of antibiotic treatments, measuring the adherence
to these guidelines, and developing stewardship tools regarding antibiotics
usage can help clinicians in choosing the optimal treatment considering the
patient’s medical history (Shapiro2021, ; Larsson2021, ). Such measures should
be implemented at a national level in order to monitor and audit antibiotic
resistance on a larger scale. In this context, the following types of temporal
queries are frequent:

  * $Q1$:

_“Find all antibiotics prescriptions from October 1, 2016 to March 31, 2017.”_

  * $Q2$:

_“Find all antibiotics prescriptions with a treatment duration between 5 and 8
days.”_

  * $Q3$:

_“Find all antibiotics prescriptions from October 1, 2016 to March 31, 2017,
with a treatment duration between 1 and 2 weeks.”_

The first query $Q1$ retrieves tuples based on the position of the events on
the timeline; we call it _range query_. In contrast, query $Q2$ imposes
constraints on the duration of matching events, and we call it _duration
query_. Finally, query $Q3$ constrains both types of information; we call it
_range-duration query_. This type of queries can be found and have been
reported as a primitive operation in other application scenarios that deal
with interval data, e.g., in air traffic analysis (DBLP:conf/gis/SchullerBM10,
; DBLP:conf/adbis/BehrendMSW09, ; DBLP:conf/adbis/SchullerSB12, ), event
detection for video surveillance (DBLP:conf/cikm/PersiaBH17, ), or the
analysis of clinical data (DBLP:conf/adbis/BehrendSXFGLCG14, ).

Existing index structures typically support only one of the two aspects,
either the position of the interval on the timeline or the duration of the
interval. For instance, the well-known relational interval tree
(DBLP:conf/vldb/KriegelPS00, ) is optimized for efficiently determining
temporal relationships between intervals but not interval lengths. In the
worst case, the entire index tree must be traversed if a query solely contains
restrictions on the interval length. Alternatively, the duration of the
intervals can be indexed straightforwardly using a classic data structure such
as a B-tree. In this case, however, queries constraining only the range of the
intervals will need to traverse the entire tree. Combining the two indexes is
typically inefficient since a query can have different selectivities in the
two dimensions. Therefore, to efficiently support workloads involving a mix of
all three types of queries mentioned above we seek a new index structure that
supports both dimensions at the same time.

In this paper, we introduce RD-index, a novel two-dimensional data structure
that indexes time intervals both on their position on the timeline and their
duration. Our index structure partitions the intervals in a grid according to
their start times and durations. Rather than constructing a regular grid, the
boundaries between the grid cells are determined by taking into account the
data distribution. Such a strategy ensures that each cell contains
approximately the same number of intervals, with the exception of some edge
cases if the distribution of the intervals is extremely skewed. The uniform
distribution of the data over all grid cells allows to obtain very predictable
query times, which are proportional to the selectivity of the query. We prove
that the time for answering a range-duration query with RD-index is
$O(\frac{n}{s^{2}}\log\frac{n}{s}+\frac{n}{s}+s^{2}+k)$, where $n$ is the size
of the input relation, $k$ is the number of intervals matching the query
predicate, and $s$ is the page size. The index can be constructed in $O(n\log
n)$ time. The page size $s$ is the only parameter of our index structure, and
it is independent of the data distribution. The index structure also lends
itself to a rather simple implementation. While being explicitly designed to
address range-duration queries, RD-index also supports range-only and
duration-only queries efficiently.

We present the results of a detailed experimental evaluation. The results show
that the overhead introduced by the data structure is indeed negligible and
that the running time in practice is largely proportional to the selectivity
of the query. This is in contrast to the competitors we compare to. On range-
duration queries we find that RD-index clearly outperforms the competitors. On
mixed workloads comprising all three types of queries, we find that RD-index
outperforms the competitors in the vast majority of the workloads, even for
cases for which specialized solutions exist.

Our contributions can be summarized as follows:

  * •

We describe RD-index, a novel index structure that supports temporal queries
involving both the duration and the range of time intervals.

  * •

We prove bounds on the performance of RD-index, which can be tuned with a
single page size parameter $s$.

  * •

We provide an extensible open source implementation, which we benchmark
against state-of-the-art competitors, showing significantly better performance
across several workloads. In particular, we show how RD-index can efficiently
handle mixed workloads where all three types of queries coexist.

The rest of the paper is organized as follows. In Section 2 we review the
state of the art, before laying out the fundamental concepts underlying our
approach in Section 3. Our data structure is introduced in Section 4, and the
complexity of all operations is analyzed in Section 5. Experimental results
are presented in Section 6, before drawing our conclusions in Section 7.

##  2\. Related work

The type of selection queries we are studying in this paper are queries with a
conjunctive predicate, where one predicate in the conjunction restricts the
position of intervals on the time line and the second the duration of
intervals. In this section, we review indexing structures that are (partially)
suitable for such selection queries, and also review structures similar to our
approach that are used for interval joins.

There are several approaches devoted to indexing interval timestamped data.
Edelsbrunner’s Interval Tree (edelsbrunner80, ) is one of the most popular
indexing structure for intervals. It is asymptotically optimal for selection
queries involving the overlap predicate, and there exists an implementation
using standard relational database technology based on B-tree indexes
(DBLP:conf/vldb/KriegelPS00, ). A shortcoming of the interval tree is that, in
contrast to our indexing structure, it does not provide a mechanism to
restrict the duration of intervals, and thus can only solve one part of a
range-duration query. A similar indexing structure is the segment tree
(deBerg00, ). It builds disjoint segments over intervals at the leaf level
using all start and end points in a relation, and recursively merges segments
in intermediate nodes of the tree. This data structure was originally designed
for point queries over intervals (also known as time travel queries), i.e.,
for retrieving all intervals overlapping a given time point. The segment tree
also supports selection queries with the overlap predicate given a query
interval, albeit in this case a duplicate elimination step for intervals
retrieved multiple times is required. Another index structure that support
time travel queries is the timeline index (DBLP:conf/sigmod/KaufmannMVFKFM13,
; DBLP:journals/pvldb/Kaufmann13, ). The timeline index stores the start and
end points of intervals in an event list in sorted order and allows to
retrieve all tuples that overlap a given time point by scanning through the
event list and discarding tuples that ended before the given time point. To
avoid scanning through the entire event list, the index maintains regular
checkpoints that store all tuples that overlap the time point of the
checkpoint. Similarly to the interval tree, the segment tree and timeline
index do not support to restrict the duration of intervals.

In a two dimensional space, intervals can be represented as 2D points, where
one dimension is the start point and the second dimension is either the end
point or the duration of an interval. In such a space, a selection query with
the overlap predicate corresponds to a selection query over a 2D area. For
this, multidimensional indices can be used. R-trees
(DBLP:conf/sigmod/BeckmannKSS90, ; DBLP:journals/talg/ArgeBHY08, ) are
multidimensional indices that group objects in a multidimensional space using
minimum bounding (hyper) rectangles. Quadtrees and octrees
(DBLP:journals/acta/FinkelB74, ; Ulrich00, ; Samet05, ) recursively divide the
space into partitions and place objects into the best fitting partition
according to some criteria. All of the aforementioned indexes are linked data
structures, which suffer from poor locality, both when implemented in-memory
and on disk. In contrast, our RD-index can be implemented by means of simple
arrays, and thus enjoys high cache locality.

Another multidimensional index structure is the grid file
(DBLP:journals/tods/NievergeltHS84, ). In the context of time intervals, the
idea would be to partition the span of durations and of starting times into
cells of equal width, thus allowing efficient access to both dimensions. The
main drawback of this data structure is that in case of skewed data
distributions the load of the cells is unequal, which might significantly harm
the performance.

A recent approach to multidimensional indexing is that of _learned indexes_
(DBLP:conf/sigmod/KraskaBCDP18, ): the proposition is that index structures
are _models_ mapping keys to records. Therefore machine learning models can be
used to provide this mapping, in lieu of the classic data structures. In
particular, Flood and Tsunami (DBLP:conf/sigmod/NathanDAK20, ;
DBLP:journals/corr/abs-2006-13282, ) use Recursive Model Index
(DBLP:conf/sigmod/KraskaBCDP18, ) and a variant of decision trees to model the
position of records in the database, adapting to the distribution of the data
and of the query workload. Our approach shares some ideas with this line of
work, namely adapting to the data distribution by means of the conditional
cumulative distribution function. However, while our index supports both
insertions and deletions, both Flood and Tsunami are tailored at read-only
workloads. Furthermore, we prove bounds on the worst case running times for
all the operations, while (DBLP:conf/sigmod/NathanDAK20, ;
DBLP:journals/corr/abs-2006-13282, ) provide an empirical evaluation. Finally,
our approach is arguably simpler, in that it is based just on sorting and
iterating through records.

Very recently, Behrend et al. (BehrendDGSVRK_SSTD19_period-index, ) proposed
an index, named Period-Index$\star$, that explicitly supports range-duration
queries. The index partitions the time domain in _buckets_. An interval is
assigned to all buckets it intersects with. Within each bucket, intervals are
further partitioned in _levels_ according to their duration, with the minimum
duration indexed within each level decreasing geometrically. To support
efficient indexing along the start time dimension, each level is further
partitioned in the time domain. This data structure is adaptive to the
distribution of start times, while it assumes a Zipf-like distribution for the
duration of the intervals. Our index structure removes this assumption, thus
supporting datasets with arbitrary distributions of the tuples’ duration.
Furthermore, our index features only one data-independent parameter, instead
of the two data-dependent parameters of Period-Index$\star$, and it allows to
control whether to index first by duration or time. Moreover, we do not
replicate intervals in the index, yielding a significantly smaller structure,
thereby avoiding the consequent possible performance degradation. Finally,
Period-Index$\star$ does not support updates of the index.

In recent years, algorithms for interval joins, which can be seen as a
sequence of range queries, have been actively studied. Approaches based on the
timeline index (DBLP:conf/sigmod/KaufmannMVFKFM13, ) process sets of intervals
as sorted event lists of their start and end points. The interval join is
computed by scanning these event lists in an interleaved fashion, thereby
keeping and joining sets of active intervals, i.e., intervals whose start has
been encountered but not the end point. To improve the performance of the
original linked list data structure for storing active intervals, a gapless
hash map has been proposed in (DBLP:conf/icde/PiatovHD16, ) that provides a
higher performance for scanning active intervals. The same idea has also been
extended for joins using general Allen’s predicates
(DBLP:journals/vldb/PiaDHP21, ) rather than only overlap predicates. The works
in (DBLP:journals/pvldb/BourosM17, ; DBLP:journals/vldb/BourosMTT21, ;
DBLP:journals/vldb/DignosBGJM21, ) compute an interval join using sorting and
backtracking. First, the input relations are sorted by start time and then an
interleaving merge-join is performed to compute the temporal join between the
two relations. Other approaches (DBLP:conf/sigmod/DignosBG14, ;
DBLP:journals/vldb/CafagnaB17, ) for the interval join are based on
partitioning intervals according to their position and then produce the join
result by joining relevant partitions. While all these approaches for the
interval join provide mechanisms to join overlapping intervals, in contrast to
our work they are not applicable for general selection queries as they always
require to read the entire relations. Moreover, the duration of intervals is
not considered at all in these works.

##  3\. Preliminaries

We assume a linearly ordered, discrete time domain, $\Omega^{T}$. A time
interval is a set of contiguous time points, and $t=[t_{s},t_{e})$ denotes the
closed-open interval of points from $t_{s}$ to $t_{e}$. We use
$|t|=t_{e}-t_{s}$ to denote the duration of time interval $t$ and $t\cap
t^{\prime}$ to denote the set of time points shared by two intervals $t$ and
$t^{\prime}$, which, if not empty, is itself an interval. The schema of a
temporal relation is given by $R=(A_{1},\dots,A_{m},T)$, where
$A_{1},\dots,A_{m}$ are the non-temporal attributes with domains $\Omega_{i}$
and $T$ is the time interval attribute with domain
$\Omega^{T}\times\Omega^{T}$ representing, for instance, the tuple’s valid
time. A temporal relation $\mathbf{r}$ with schema $R$ is a finite set of
tuples, where each tuple has a value in the appropriate domain for each
attribute in the schema. We use $r.A_{i}$ to denote the value of attribute
$A_{i}$ in tuple $r$, and $r.T=[r.T_{s},r.T_{e})$ to refer to its time
interval.

The index we propose efficiently supports the three following types of
temporal queries (defined as in (BehrendDGSVRK_SSTD19_period-index, )).

###### Definition 3.1 (Range query).

Given a temporal interval $t=[t_{s},t_{e})$ and a temporal relation
$\mathbf{r}$, a _range query_ is defined as

$Q(\mathbf{r},t)=\left\\{r\in\mathbf{r}:r.T\cap t\neq\emptyset\right\\}$

###### Definition 3.2 (Duration query).

Given a duration interval $d=[d_{min},d_{max}]$ and a temporal relation
$\mathbf{r}$, a _duration query_ is defined as

$Q(\mathbf{r},d)=\left\\{r\in\mathbf{r}:|r.T|\in[d_{min},d_{max}]\right\\}$

###### Definition 3.3 (Range-duration query).

Given a temporal interval $t=[t_{s},t_{e})$, a duration interval
$d=[d_{min},d_{max}]$, and a temporal relation $\mathbf{r}$, a _range-duration
query_ is defined as

$Q(\mathbf{r},t,d)=\left\\{r\in\mathbf{r}:r.T\cap
t\neq\emptyset\wedge|r.T|\in[d_{min},d_{max}]\right\\}$

A range query retrieves all tuples whose time interval intersects with the
query range $t$. A duration query retrieves all tuples whose time interval has
a duration that is between $d_{min}$ and $d_{max}$. A range-duration query is
a combination of the former two.

###### Example 3.4.

As a running example, we consider real-world drug prescriptions from the
MIMICIII open source database (mimiciii, ) (cf. use case in Example 1.1). It
stores antibiotic prescriptions, characterized by a start date and an end date
of the prescription and the duration of the treatment. An excerpt of four
tuples is shown in Figure 1(a). Consider the following range-duration query:
Retrieve all prescriptions in the period from June 15 to July 15 with a
treatment duration between 5 and 15 days. Figure 1(b) shows a graphical
representation of the relation and the query, where the time intervals are
drawn by thick solid horizontal lines. The red area indicates the constraint
on the position. The red segment below of each timestamp interval denotes the
duration constraint, where the dotted red line indicates the range of minimum
and maximum duration. Hence, an interval satisfies the range constraint if it
intersects with the red area, and it satisfies the duration constraint if its
end point is within the dotted red line. Tuple $r_{1}$ satisfies only the
duration constraint, tuple $r_{2}$ satisfies neither constraint, tuple $r_{3}$
satisfies only the range constraint, and tuple $r_{4}$ satisfies both.

| drug | $T_{s}$ | $T_{e}$ | duration
---|---|---|---|---
$r_{1}$ | Amoxicillin | June 08 | June 14 | (6 days)
$r_{2}$ | Amoxicillin | June 10 | June 12 | (2 days)
$r_{3}$ | Ceftriaxone | June 20 | July 05 | (15 days)
$r_{4}$ | Levofloxacin | June 24 | July 04 | (10 days)
(a) Sample of relation with antibiotic prescriptions

$r_{2}$$r_{3}$$r_{4}$$r_{1}$Jun 15Jul 01Jul 15 (b) Range-duration query

Figure 1. Running example.

##  4\. The RD-index Structure

###  4.1. Overview

Figure 2. Drug prescription dataset in the start time/duration plane. The gray
dots are tuples. The red polygon is the range-duration query of Example 3.4.

An interval can be completely described by its starting time and duration,
alternatively, to its starting and ending time. Therefore, a set of temporal
intervals can be represented as a set of points in a two dimensional space,
with one coordinate being the start time and the other the duration. A range-
duration query $Q(\mathbf{r},t,d)$ with $t=[t_{s},t_{e})$ and
$d=[d_{min},d_{max}]$ in such a space is represented by a polygon containing
all tuples $r\in\mathbf{r}$ such that

(1) $\displaystyle|r.T|\in[d_{min},d_{max}]$ (2) $\displaystyle r.T_{e}>t_{s}$
(3) $\displaystyle r.T_{s}<t_{e}$

###### Example 4.1.

Figure 2 shows a sample of 31 192 drug prescriptions from the MIMICIII dataset
in the two dimensional space, where each point represents a timestamp interval
of a tuple. The red polygon indicates the query of Example 3.4, i.e., the
prescriptions from June 15 to July 15 with a duration between 5 and 15 days.
Note that the points are not uniformly distributed, hence efficiently indexing
this dataset requires to be adaptive in both the start time and duration
dimension.

The RD-index we are presenting is a two-dimensional grid, partitioning the
tuples into disjoint buckets according to the start time and the duration of
the intervals. The boundaries between cells are defined by using the empirical
cumulative distribution function of the tuples’ duration and the starting
times, so that each cell contains approximately the same number of intervals,
which corresponds to the _page size_ $s$ of our index. This allows the index
to adapt to the distribution of the input and to different scenarios. In a
main memory scenario, the parameter $s$ could be set such that a cell fits in
a cache line. In an external memory setting, it might be set to the disk block
size.

To simplify the presentation, in the following we will focus on the timestamp
interval attribute $T$ of relation $\mathbf{r}$: in the discussion we assume
that each interval being inserted in the index is associated with a reference
to the tuple in $\mathbf{r}$ it belongs to.

###  4.2. Index Construction

The grid structure of the RD-index partitions an array of tuples first along
either the start time or duration dimension of the intervals, and then along
the other. The choice of which dimension to index first may impact the
performance of the index, depending on the query workload and the data
distribution (cf. Section 6. In the following we assume that the start time
dimension is partitioned first, followed by the duration dimension. All the
descriptions, considerations, and proofs also hold with the dimensions
swapped.

Before describing the algorithm to build the index, we present the subroutine
NextSubseq, which partitions an array of tuples that is sorted according to a
given key function. We will use this subroutine to determine columns and cells
of the grid structure, using first the start time and then duration as keys.
Given an index $h$ and a size parameter $b$, NextSubseq returns a subsequence
starting at $h$ that either contains at most $b$ tuples, or contains tuples
that all share the same key. Additionally, all the tuples with the same key
are part of the same subsequence. The pseudocode is reported in Algorithm 1
and works as follows. Starting from index position $h$, if there are fewer
than $b$ elements after $h$ then we return all the tuples from $h$ onwards.
Otherwise, we look at the tuple at position $h^{\prime}=h+b$ and consider two
cases111Therefore $h^{\prime}$ is the end index of the subsequence, _non-
inclusive_.. If the tuples at position $h$ and $h^{\prime}$ have the same key,
then we scan forward until the first tuple with a different key occurs (lines
1–1). Otherwise, we scan backward until two consecutive tuples have different
keys (lines 1–1). In both cases, the rationale is to avoid splitting runs of
same-key tuples between different subsequences.

Note that Algorithm 1 might return a subsequence with more than $b$ elements
if and only if all share the same key. In such case we deem the returned
subsequence _heavy_ , otherwise we deem it _light_.

12447810131313131313131313131314151617192123first groupsecond group
(heavy)third groupx8451099235679101113141517184245128Start time:Duration:

Figure 3. Partitioning a sequence of intervals sorted by start time using
NextSubseq with parameter $b=9$, with the start time being the _key function_.

Input: Relation $\mathbf{r}$ sorted according to $k$; current index position
$h$; subsequence size $b$; _key_ function $k$

Output: Subsequence of $\mathbf{r}$ starting from position $h$, either of size
$\leq b$ or with all tuples having the same key

1

2if  _$h+b\geq|\mathbf{r}|$_ then

3 return subsequence
$\langle\mathbf{r}_{h},\dots,\mathbf{r}_{|\mathbf{r}|-1}\rangle$;

4

5$h^{\prime}$ $\leftarrow$ $h+b$;

6if  _$k(\mathbf{r}_{h})=k(\mathbf{r}_{h^{\prime}})$_ then

7 while  _$h^{\prime} <|\mathbf{r}|\wedge
k(\mathbf{r}_{h})=k(\mathbf{r}_{h^{\prime}})$_ do

8 $h^{\prime}$ $\leftarrow$ $h^{\prime}+1$

9

10 else

11 while  _$k(\mathbf{r}_{h^{\prime}-1})=k(\mathbf{r}_{h^{\prime}})$_ do

12 $h^{\prime}$ $\leftarrow$ $h^{\prime}-1$

13

14return subsequence
$\langle\mathbf{r}_{h},\mathbf{r}_{h+1},\dots,\mathbf{r}_{h^{\prime}-1}\rangle$;

Algorithm 1 NextSubseq $(\mathbf{r},h,b,k)$

Input: Temporal relation $\mathbf{r}$ and page size parameter $s$

Output: Grid $G$ partitioning $\mathbf{r}$ by start time and duration, along
with auxiliary arrays.

1

2grid $\leftarrow$ [][];

3 col_minstart $\leftarrow$ [];

4 col_maxend $\leftarrow$ [];

5 cell_mindur $\leftarrow$ [][];

6 cell_maxdur $\leftarrow$ [][];

7

8Sort $\mathbf{r}$ by interval start time;

$h$ $\leftarrow$ $0$ /* position in $\mathbf{r}$ */

$i$ $\leftarrow$ $0$ /* column index */

9 while  _$h <|\mathbf{r}|$_ do

10 column $\leftarrow$ NextSubseq$(\mathbf{r},h,s^{2},r.T\rightarrow
r.T_{s})$;

11 col_minstart[i] $\leftarrow$ $\min\\{r.T_{s}:r\in\texttt{column}\\}$;

12 col_maxend[i] $\leftarrow$
$\max\\{\texttt{col\\_maxend[i-1]},\\{r.T_{e}:r\in\texttt{column}\\}\\}$ ;

13

14 Sort column by duration;

15

$k$ $\leftarrow$ $0$ /* position in column */

$j$ $\leftarrow$ $0$ /* cell index */

16 while  _$k <|\texttt{column}|$_ do

17 cell $\leftarrow$ NextSubseq$(\texttt{column},k,s,r.T\rightarrow|r.T|)$;

18 Sort cell by end time;

19 grid[i][j] $\leftarrow$ cell ;

20 cell_mindur[i][j] $\leftarrow$
$~{}\qquad\qquad\qquad\min\\{|r.T|:r\in\texttt{cell}\\}$;

21 cell_maxdur[i][j] $\leftarrow$
$~{}\qquad\qquad\qquad\max\\{|r.T|:r\in\texttt{cell}\\}$;

22 $j$ $\leftarrow$ $j+1$;

23 $k$ $\leftarrow$ $k+|\texttt{cell}|$;

24

25 $i$ $\leftarrow$ $i+1$;

26 $h$ $\leftarrow$ $h+|\texttt{column}|$;

27

28

29return (grid, col_minstart, col_maxend, cell_mindur, cell_maxdur);

Algorithm 2 BuildIndex$(\mathbf{r},s)$

###### Example 4.2.

Figure 3 depicts three invocations of NextSubseq on a sequence of sorted start
times, with parameter $b=9$. The first jump by 9 positions would split the run
of intervals with start time $13$. Therefore, the algorithm iterates back
until the first start time $<13$. The second invocation would again split the
same run since it contains more than 9 intervals with start time $13$. This
time, since the endpoints of the jump have the same value, the algorithm
iterates forward until the last interval with the same start time, thus
finding a _heavy_ subsequence. The last jump defines the third group.

Figure 4. Instantiation of RD-index with page size $s=70$ on the example
dataset. Above the plot we report the col_minstart and col_maxend arrays.

We are now ready to describe the index construction procedure BuildIndex,
which is shown in Algorithm 2. Let $s$ be the _page size_ parameter, and
$\mathbf{r}$ be the relation to be indexed. First, we sort $\mathbf{r}$ by
increasing start time. Then, we repeatedly invoke NextSubseq (line 2) to
divide the relation into _columns_ of $s^{2}$ tuples each, based on their
start times. Defining columns in this way allows, intuitively, to then further
partition each column in $s$ cells of $s$ elements each222We could use two
separate parameters to control the number of partitions in the two dimensions,
but using $s$ and $s^{2}$ makes for a simpler exposition, analysis and
implementation.. As a special case, if there are more than $s^{2}$ tuples with
the same start time, NextSubseq will assign them to the same column, which we
then deem _heavy_. We also keep track of the minimum start time in each column
using an auxiliary array col_minstart. Similarly, the array col_maxend stores
the cumulative maximum end time in the columns, i.e., the maximum end time
found so far in the relation. Both of these arrays will be used at query time:
the first to find the first column to inspect for a given query, the second to
determine when to stop iterating through columns. Note that col_maxend records
the _cumulative_ maximum end time of columns. This ensures that no interval in
columns $\leq i$ ends after col_maxend[i], which will be useful at query time.

Each column is further partitioned in _cells_ in a similar way. First we sort
the tuples in the column by increasing duration. Then we define cells of size
$s$ by repeatedly invoking NextSubseq (line 2). Again, if there are more than
$s$ tuples with the same duration, they will all be assigned to the same cell,
which will then be deemed _heavy_. Similarly to columns, also cells are
complemented by two arrays of ancillary information: cell_mindur stores the
minimum duration in each cell to be used at query time to find the first cell
to inspect, while cell_maxdur stores the maximum duration in each cell, which
at query time will determine when to stop iterating through cells.

Finally, tuples in each cell are sorted by the end time. This is useful at
query time, since it allows to stop queries early, as we shall discuss in the
proof of Theorem 5.3.

We now formally define light and heavy columns and cells, since they play a
key role in the proof of the performance of our index structure.

###### Definition 4.3.

For a given page size $s$, a _heavy_ column (resp. cell) contains $>s^{2}$
(resp. $>s$) intervals. Conversely, a _light_ column (resp. cell) contains
$\leq s^{2}$ (resp. $\leq s$) intervals.

###### Example 4.4.

Figure 4 shows the grid constructed by Algorithm 2 on our example relation
from Figure 2, with page size parameter $s=70$. Note that the columns, which
contain $s^{2}=4\,900$ tuples each, span different ranges of start times,
adapting to the density of the points. Within each column, the points are
partitioned according to the distribution of durations. Since many drug
prescriptions have the same short durations, the cells at the bottom of the
columns are _heavy_ (or span only a few different duration values). In this
setting, a uniform grid would suffer from a high imbalance in the number of
tuples in each cell.

###  4.3. Querying the Index

Given a range-duration query with time range $t=[t_{s},t_{e})$ and duration
interval $d=[d_{min},d_{max}]$, recall that a tuple $r\in\mathbf{r}$ satisfies
the query if the conditions (1), (2), and (3) specified in Section 4.1 are
met. We report the conditions here for convenience:

(1) $\displaystyle|r.T|\in[d_{min},d_{max}]$ (2) $\displaystyle r.T_{e}<t_{s}$
(3) $\displaystyle r.T_{s}<t_{e}$

The pseudocode for querying the index structure is reported in Algorithm 3.
First, we seek the index of the last column that might contain matching
tuples. To this end, we perform a binary search on the array col_minstart to
find the last column $i$ such that the minimum start time in the column (which
is the column bound) is strictly less than the query end time $t_{e}$ (line
3). This ensures that the column contains at least one tuple satisfying
condition (3). Then, we iterate _backwards_ through columns until column $i$
cannot possibly contain tuples satisfying the query. For this, we use the
support array col_maxend: if $\texttt{col\\_maxend[i]}\leq t_{s}$ then we know
that all the columns at index $\leq i$ contain tuples that stop earlier than
the start of the query range. Hence, we can avoid inspecting them because of
condition (2).

For each column that we consider, a binary search on the array cell_mindur[i]
is performed, looking for the last cell $j$ such that the minimum duration in
the cell (which is the cell bound) is $\leq$ to the maximum duration $d_{max}$
specified in the query (line 3). Doing so ensures that at least one tuple in
the cell satisfies the upper bound of condition (1). Then, we iterate
backwards through the cells until we reach a cell whose maximum duration is
less than the minimum duration $d_{min}$ of the query. At this point we stop
since condition (1) can no longer be satisfied.

Finally, we iterate through the tuples of each considered cell by decreasing
end time and stop as soon as condition (2) is no longer satisfied (line 3).
All the intervals that satisfy the query are returned in the result.

Input: A range duration query with time range $[t_{s},t_{e})$ and duration
range $[d_{min},d_{max}]$; An index grid with the ancillary arrays
col_minstart, cell_mindur, col_maxend, and cell_maxdur

1

2$res$ $\leftarrow$ $\emptyset$;

3 $i$ $\leftarrow$
$\operatorname{argmax}_{i}\texttt{col\\_minstart[i]}<t_{e}$;

4 while  _$i\geq 0\wedge t_{s} <\texttt{col\\_maxend[i]}$_ do

5 $j$ $\leftarrow$ $\operatorname{argmax}_{j}\texttt{cell\\_mindur[i][j]}\leq
d_{max}$;

6 while  _$j\geq 0\wedge\texttt{cell\\_maxdur[i][j]}\geq d_{min}$_ do

7 for  _$r\in\texttt{grid[i][j]}$_ do

8 if  _$r.T_{e}\leq t_{s}$_ then

9 break;

10

11 if  _$|r.T|\in[d_{min},d_{max}]\wedge r.T_{s} <t_{e}$_ then

12 $res$ $\leftarrow$ $res\cup\\{r\\}$;

13

14

15 $j$ $\leftarrow$ $j-1$;

16

17 $i$ $\leftarrow$ $i-1$;

18

return $res$

Algorithm 3 Query (grid, $[t_{s},t_{e})$, $[d_{min},d_{max}]$)

###  4.4. Updating the Index

Our index data structure can be extended to support both insertion and removal
of tuples.

#### Interval Insertion.

To insert a tuple $r$, we query the index for the start time $r.T_{s}$and the
duration $|r.T|$ to identify the cell that should contain $r$. Inserting new
intervals into cells might make them grow too large to be able to maintain the
performance guarantees on the query time. Luckily, as we shall see in Section
5, _heavy_ columns and cells do not present issues upon insertions by virtue
of containing intervals that all share either the same start time or the same
duration. If a light column exceeds size $s^{2}$, we replace it with two new
columns. Similarly, if a light cell exceeds size $s$, we replace it with two
new cells.

Splitting a column entails to consider all the intervals it contains, using
NextSubseq with $b=s^{2}/2+1$ to find the breakpoint at which to split (this
way, we balance the size of the new columns). For each of the two new columns
that replace the original column, we apply NextSubseq to split them into
cells, exactly as in the inner loop of the index construction. The array
col_minstart and col_maxend are updated to reflect the replacement of the old
column with the new ones.

Similarly, to split a cell that exceeds size $s$ in column $i$ we use
NextSubseq with $b=s/2+1$ to find a new breakpoint and replace the cell with
two new cells. The auxiliary structures cell_mindur[i] and cell_maxdur[i] are
updated accordingly.

Both in the case of column and cell splitting, we sort all the intervals in
the newly created cells by end time.

#### Interval Removal.

As for the removal of a tuple $r$ from the index, we query the index to find
the cell grid[i][j] that contains $r.T$ and remove the interval from the cell.
As a consequence, the cell might contain fewer than $s/2$ items. As we shall
see with Lemma 5.2, it is crucial for the performance of the index that cells
contain at least $s/2$ intervals.

Therefore, upon removal of an element from a cell, we check whether the sum of
elements of the cell and either of the adjacent ones is less than $s$. In such
case, we _merge_ the two cells, i.e., we replace them with a single cell where
all intervals are then sorted by decreasing end time. After cells are merged,
the arrays cell_mindur[i] and cell_maxdur[i] are updated as well to reflect
the changes.

Similarly, a removal might cause a column to have fewer than $s^{2}/2$
elements. We then apply a similar reasoning. If the sum of the number of items
in the column and either adjacent ones is smaller than $s^{2}/2$, we merge the
two columns, i.e., the two columns are replaced by a single one. NextSubseq is
then called to find the breakpoints to divide the newly created column into
cells. After the two columns are merged, the arrays col_minstart and
col_maxend are updated to reflect the changes.

##  5\. Analysis

In this section, we provide guarantees on the time required by all the
operations supported by our index structure. We assume that the index is built
by partitioning first in the time dimension, and then in the duration
dimension. The asymptotic results presented in this section hold for both
dimension orderings.

###  5.1. Querying the Index

Before stating our main result, we establish the following fundamental facts
about heavy columns and cells.

###### Lemma 5.1.

A heavy cell in a heavy column contains only copies of the same interval.

###### Proof.

By construction, a heavy column contains only intervals with the same start
time. Similarly, a heavy cell contains only intervals with the same duration.
Therefore, a heavy cell in a heavy column contains intervals with the same
start time and duration, i.e., multiple copies of the same interval. ∎∎

###### Lemma 5.2.

The RD-index with parameter $s$ over $n$ intervals has
$O\left(\frac{n}{s^{2}}\right)$ columns, each having
$O\left(\frac{n}{s}\right)$ cells.

###### Proof.

To upper bound the number of columns into which a relation can be partitioned,
we first devise a set of intervals that will force RD-index to use the maximum
number of columns. Consider a relation such that exactly $s^{2}/2+1$ intervals
have start time 1, $s^{2}/2$ intervals have start time 2, $s^{2}/2+1$
intervals have start time 3, and so on. RD-index will have to build a separate
light column for each distinct start time. Note that if the subsets of
intervals with the same start time were any smaller, RD-index would create
columns containing more than one start time, resulting in fewer columns
overall. Therefore, each column has size $\geq s^{2}/2$, which implies that
there are $O\left(n/s^{2}\right)$ columns.

As for cells, the worst case occurs if all intervals fall in the same column.
With a reasoning similar to the above argument, we have that these $n$
intervals in one column are partitioned in $O\left(n/s\right)$ cells. ∎∎

###### Theorem 5.3.

Given an index over a set of $n$ intervals and a page size $s$, the time for
answering a range-duration query is

$\displaystyle
O\left(\frac{n}{s^{2}}\log\frac{n}{s}+\frac{n}{s}+s^{2}+k\right)$

where $k$ is the number of intervals matching the query predicate.

###### Proof.

Let $t=[t_{s},t_{e})$ be the query interval and $d=[d_{min},d_{max}]$ be the
duration range of the query. Recall that the index construction algorithm may
create a heavy column or cell when it cannot break down a group of intervals
because they all share the same start time or duration. Furthermore, recall
that by construction _light_ columns (resp. cells) are of size $\leq s^{2}$
(resp. $\leq s$).

A range-duration query defines a _query polygon_ in the start time $\times$
duration space, as depicted in Figure 4. For a given cell grid[i][j], we
denote by $k_{ij}$ the number of intervals in the cell that match the query.
The query time is comprised of two parts: (a) we have to find the correct
range of cells to query, and (b) we have to filter the intervals in each cell
to retrieve the ones that are part of the answer.

As for part (a), finding the cells to inspect, we first determine the last
column that can contain tuples satisfying the query constraint. For this we
use binary search over the $O\left(n/s^{2}\right)$ boundaries between columns
(Lemma 5.2) in $O\left(\log(n/s^{2})\right)$ time. Iterating backwards through
the columns visits at most $O\left(n/s^{2}\right)$ columns. In each such
column, to find the last cell with intervals satisfying the duration
constraint, we do a binary search over the $O\left(n/s\right)$ cells in the
column (Lemma 5.2). Therefore, the overall time to find the correct cells is

$\displaystyle
O\left(\log\frac{n}{s^{2}}+\frac{n}{s^{2}}\log\frac{n}{s}\right)=O\left(\frac{n}{s^{2}}\log\frac{n}{s}\right)$

As for part (b), enumerating the results from the cells, we can distinguish
four possible cases for a cell grid[i][j]:

  1. (1)

Both the cell’s durations range and start times range fall within the query
polygon. In such cells, the query constraints on the duration and the start
time are satisfied by construction. The algorithm considers just the intervals
of grid[i][j], which are part of the output (since it iterates over the cell’s
intervals by decreasing end time). Therefore, the time spent enumerating
intervals from the cell is $O\left(k_{ij}\right)$. Also, note that this is the
only case in which a heavy cell in a heavy column is visited by the query
algorithm. Such cells can potentially have $O\left(n\right)$ copies of the
same interval. If the algorithm visits the cell, then it means that such
copies are all part of the output, hence we pay $\Theta\left(k_{ij}\right)$ in
the complexity.

  2. (2)

The cell’s start times all satisfy the query constraints, but not all its
durations do so. The cell must be light, otherwise all its durations would be
equal and would need to satisfy the duration constraint, contradicting the
assumption. Therefore, the algorithm has to evaluate $O\left(s\right)$
intervals.

  3. (3)

The cell’s durations all satisfy the query constraints, but not all its start
times do. In this case we cannot be in a heavy column (which contains a single
start time) and thus the column contains at most $s^{2}$ intervals.

  4. (4)

Only some of the cell’s intervals satisfy both constraints. In this case
neither the column nor the cell can be heavy, therefore the algorithm must
only evaluate $O\left(s\right)$ intervals.

All the cells of type (1) account for at most $O\left(k\right)$ in terms of
running time. As for cells of type (2) there are at most
$O\left(n/s^{2}\right)$ of them. Overall they account for
$O\left(\frac{n}{s}\right)$ interval evaluations. Cells of type (3) account
for $O\left(s^{2}\right)$ interval evaluations overall. Finally, there is a
constant number of cells of type (4) (which are at the corners of the query
polygon). These cells therefore account for at most $O\left(s\right)$ interval
evaluations in total. Overall, the time to evaluate the intervals in the cells
is $O\left(\frac{n}{s}+s^{2}+k\right)$.

Combining this last result with the time to find the range of cells to query,
we have that the overall query time is

$\displaystyle
O\left(\frac{n}{s^{2}}\log\frac{n}{s}+\frac{n}{s}+s^{2}+k\right).$

∎∎

The above theorem exposes a fundamental tradeoff of our data structure: using
a smaller page size allows to improve the precision of the data structure (by
looking at fewer intervals that are not part of the query output), while at
the same time increasing the number of columns that need to be queried. In
Section 6.5 we investigate experimentally the effect of $s$ on the
performance, finding that the best performance is attained for
$n/s^{2}\in[50,500]$.

The choice of the order of partitioning has no impact on the theoretical
complexity results, however it affects the practical performance as we will
discuss in Section 6 (Figure 10). It turns out that generally it is better to
index first the duration and then the start time, as summarized in the
following observation.

###### Observation 1.

While changing the order in which dimensions are indexed does not change the
asymptotic behavior of RD-index, the choice of such order affects the
practical performance. In fact range and duration constraints play different
roles in queries. When querying for duration, the position of start times on
the timeline does not affect the outcome of a query. Conversely, a range query
can be rephrased in terms of start times and durations. Therefore, range
queries can benefit from a partition of the duration dimension, since it
implies a partition of the end times. Furthermore, duration constraints are
typically much more selective than range constraints. Therefore, indexing
first by duration might imply that a query has to iterate through fewer
columns, compared to the case where start times are indexed first.

###  5.2. Index Construction and Update

###### Theorem 5.4.

Given a set of $n$ intervals, building the index requires time $O\left(n\log
n\right)$.

###### Proof.

Computing column boundaries for the duration requires time $O\left(n\log
n\right)$ for sorting the tuples, while invoking Algorithm 1 requires time
$O\left(n\right)$ for iterating through the sorted intervals to find the
boundaries: in fact, each of the $n$ intervals is visited at most once.

Let $n_{i}$ be the number of intervals in the $i$-th column. Sorting the
column requires time $O\left(n_{i}\log n_{i}\right)$. Then, the invocation of
Algorithm 1 to find cell boundaries requires time $O\left(n_{i}\right)$,
following the same argument as above. Similarly, let $n_{ij}$ be the size of
cell $ij$. Sorting its tuples by end time requires time $O\left(n_{ij}\log
n_{ij}\right)$. Therefore, the time for running the inner loop is
$O\left(n\log n\right)$ overall, and the theorem follows. ∎∎

###### Theorem 5.5.

Inserting a tuple $r$ into the index requires time $O\left(\log
n/s+n/s+s^{2}\log s\right)$.

###### Proof.

Finding the cell that should contain $r.T$ requires performing first a binary
search over the $O\left(\frac{n}{s^{2}}\right)$ columns and then over the
$O\left(\frac{n}{s}\right)$ cells of the resulting column (by Lemma 5.2), for
a total time $O\left(\log n/s\right)$.

Note that a heavy column or cell does not need to be split, since by
definition they can contain more than $s^{2}$ (resp. $s$) intervals, as long
as they all have the same start time (resp. duration). Therefore we consider
only the case of splitting a light column or light cell. Splitting a column
with $s^{2}+1$ intervals requires to first apply Algorithm 1 (which takes time
$O\left(s^{2}\right)$), sort the newly created columns (requiring time at most
$O\left(s^{2}\log s\right)$) and then applying again Algorithm 1 on the new
columns to find the cells (for an overall time of $O\left(s^{2}\right)$).
Furthermore, inserting the new column boundaries in order in the sorted array
of boundaries requires $O\left(\frac{n}{s^{2}}\right)$ time. By similar
reasoning, splitting a cell with $s+1$ intervals requires time $O\left(s\log
s\right)$, and updating cell boundaries by inserting in-order requires
$O\left(\frac{n}{s}\right)$. ∎∎

In a similar way we can prove the following theorem.

###### Theorem 5.6.

Removing a tuple $r$ from the index requires time $O\left(\log
n/s+n/s\right)$.

##  6\. Experimental Evaluation

In this section, we evaluate experimentally our proposed index. To frame this
evaluation, we consider the following data structures as baselines: The
implementation of B-Tree provided by the Rust standard library, which is
optimized for CPU cache usage; intervals are indexed by duration in this case.
The Interval-Tree index (DBLP:conf/vldb/KriegelPS00, ), which we implemented
ourselves, indexing intervals by their position on the timeline. The Grid-File
(DBLP:journals/tods/NievergeltHS84, ) and Period-Index$\star$
(BehrendDGSVRK_SSTD19_period-index, ), which we also implemented, and which
index both start times and durations. We also consider the R-Tree as a
baseline, specifically the R*-Tree (DBLP:conf/sigmod/BeckmannKSS90, ):
intervals are mapped to points identified by the start time and duration of
the interval, and then indexed by the R*-Tree. Our proposed data structure
will be denoted with RD-index-td when start time is indexed before duration,
and with RD-index-dt otherwise. In cases where the order of the dimensions is
not relevant to the discussion, we will use RD-index instead. To account for
the potential shortcomings of our implementations, we will also evaluate the
relative performance of the data structures with implementation-independent
metrics (DBLP:journals/kais/KriegelSZ17, ).

We aim to answer the following questions:

(Q1):

How robust are the indices over different workloads? (§ 6.2)

(Q2):

How do indices compare on mixed workloads? (§ 6.3)

(Q3):

How do query times relate with the query selectivity? (§ 6.4)

(Q4):

How does the page size parameter affect the performance of the index? (§ 6.5)

(Q5):

How does the performance scale with respect to the size of the dataset? (§
6.6)

(Q6):

What is the performance of updating the index? (§ 6.7)

###  6.1. Setup and Datasets

Figure 5. Histograms of the start times and durations of the three real-world
datasets considered in this paper.

We implemented our index and the baseline competitors in Rust 1.44.1, using a
configurable and extensible framework (DBLP:conf/sisap/AumullerC20, ). Code
and data are available at https://github.com/Cecca/temporal-index. The
experiments presented in this section were run on a machine equipped with 94
GB of memory and a Intel®Xeon®CPU E5-2667 v3 @ 3.20GHz processor.

As a benchmark we consider the following datasets and workloads:

####  Flight:

A set of 701 353 flights, identified by their takeoff and landing time at the
granularity of minute, covering August 2018. Query ranges on this dataset are
generated at random. Time range durations are uniformly distributed between
one and 31 days, and duration ranges are uniformly distributed between one
minute and one day.

####  Webkit:

1 547 419 file edits in the Webkit source code repository. Intervals represent
the timespan between successive edits to a file. Query ranges on this dataset
are generated at random. Time range durations are uniformly distributed
between one minute and one year, and duration ranges are uniformly distributed
between up to three years.

####  MimicIII:

4 134 909 drug prescriptions from the open MimicIII database (mimiciii, ).
Each prescription is characterized by its start and end day. Queries,
generated at random, span the entire domain of times and durations: the former
take values $\in[1,40\,251]$, the latter $\in[1,200]$. The large span of start
times (110 years) is due to the anonymization procedure applied to the
database.

####  Synthetic:

Randomly generated datasets with 10 million intervals by default. The interval
start times are uniformly distributed in $[1,n]$, where $n$ is the size of the
dataset; interval durations follow a Zipf distribution with $\beta=1$.

Figure 5 reports the distribution of start times and durations of the three
real-world datasets. Note that the start times of the Flight dataset are
approximately uniformly distributed, with durations geometrically distributed.
The MimicIII dataset has similarly distributed start times, and duration
values which are very concentrated. Finally, the Webkit dataset has a
distribution of durations similar to Flight, but the distribution of start
times is skewed towards recent times, meaning that more file edits have been
done recently.

In the experiments we run a count query subject to range and duration
constraints. Evaluating a count query rather than reporting the matching
tuples, allows to measure the time to retrieve the tuples, rather than the
time to print them to screen or write them to a file.

###  6.2. Robustness of Index Structures Across Different Workloads

Table 1.  Performance attained by the tested indices on different workloads.
Performance is characterized in terms of three numbers: the number of queries
per second (larger is better), the time to build the index in milliseconds
(smaller is better), and the index size (smaller is better) expressed as the
number of bytes used for each indexed interval. Configurations with a dark
blue background are the ones with the best throughput for a dataset/queryset
combination, light blue cells denote the second-best data structure. The
fastest index construction times are underlined, and the smallest indices are
highlighted in bold.

| Queries per second $~{}|~{}$ Index build time $~{}|~{}$ Bytes per interval
---|---
dataset | query | RD-index-td | RD-index-dt | Grid-File | Period-Index$\star$ | R*-Tree | Interval-Tree | B-Tree
| range-only |  415$~{}|~{}$1 024$~{}|~{}$16.1 |  602$~{}|~{}$889$~{}|~{}$16.1 |  468$~{}|~{}$445$~{}|~{}$27.7 |  242$~{}|~{}$2 392$~{}|~{}$57.1 |  12$~{}|~{}$3 358$~{}|~{}$80.0 |  272$~{}|~{}$3 636$~{}|~{}$50.1 |  8$~{}|~{}$2 505$~{}|~{}$31.4
| duration-only |  842$~{}|~{}$1 030$~{}|~{}$16.1 |  734$~{}|~{}$785$~{}|~{}$17.1 |  77$~{}|~{}$983$~{}|~{}$24.1 |  69$~{}|~{}$6 139$~{}|~{}$178.1 |  106$~{}|~{}$3 398$~{}|~{}$80.0 |  12$~{}|~{}$3 636$~{}|~{}$50.1 |  43 103$~{}|~{}$2 469$~{}|~{}$31.4
Synthetic | range-duration |  11 737$~{}|~{}$1 052$~{}|~{}$16.1 |  14 085$~{}|~{}$829$~{}|~{}$16.5 |  1 581$~{}|~{}$857$~{}|~{}$24.1 |  1 403$~{}|~{}$6 566$~{}|~{}$178.1 |  2 591$~{}|~{}$3 402$~{}|~{}$80.0 |  215$~{}|~{}$3 674$~{}|~{}$50.1 |  502$~{}|~{}$2 529$~{}|~{}$31.4
| range-only |  54 945$~{}|~{}$42$~{}|~{}$17.1 |  57 471$~{}|~{}$44$~{}|~{}$16.1 |  49 505$~{}|~{}$20$~{}|~{}$23.2 |  15 015$~{}|~{}$80$~{}|~{}$40.0 |  4 921$~{}|~{}$195$~{}|~{}$97.9 |  51 813$~{}|~{}$139$~{}|~{}$44.5 |  2 798$~{}|~{}$39$~{}|~{}$23.3
| duration-only |  4 182$~{}|~{}$44$~{}|~{}$16.1 |  4 218$~{}|~{}$33$~{}|~{}$21.3 |  3 791$~{}|~{}$20$~{}|~{}$23.2 |  538$~{}|~{}$111$~{}|~{}$62.9 |  378$~{}|~{}$205$~{}|~{}$97.9 |  683$~{}|~{}$150$~{}|~{}$44.5 |  714 286$~{}|~{}$43$~{}|~{}$23.3
Flight | range-duration |  232 558$~{}|~{}$45$~{}|~{}$16.7 |  208 333$~{}|~{}$39$~{}|~{}$16.6 |  188 679$~{}|~{}$20$~{}|~{}$23.2 |  29 940$~{}|~{}$95$~{}|~{}$62.9 |  21 786$~{}|~{}$193$~{}|~{}$97.9 |  43 860$~{}|~{}$139$~{}|~{}$44.5 |  13 514$~{}|~{}$47$~{}|~{}$23.3
| range-only |  416$~{}|~{}$116$~{}|~{}$16.1 |  467$~{}|~{}$115$~{}|~{}$16.1 |  445$~{}|~{}$56$~{}|~{}$23.0 |  83$~{}|~{}$540$~{}|~{}$119.0 |  30$~{}|~{}$468$~{}|~{}$97.7 |  384$~{}|~{}$274$~{}|~{}$48.3 |  47$~{}|~{}$252$~{}|~{}$36.4
| duration-only |  2 544$~{}|~{}$112$~{}|~{}$16.1 |  2 520$~{}|~{}$104$~{}|~{}$16.9 |  1 938$~{}|~{}$52$~{}|~{}$23.0 |  57$~{}|~{}$559$~{}|~{}$124.4 |  234$~{}|~{}$469$~{}|~{}$97.7 |  157$~{}|~{}$274$~{}|~{}$48.3 |  3 393$~{}|~{}$255$~{}|~{}$36.4
Webkit | range-duration |  3 159$~{}|~{}$112$~{}|~{}$16.1 |  3 133$~{}|~{}$99$~{}|~{}$16.9 |  2 322$~{}|~{}$51$~{}|~{}$23.0 |  80$~{}|~{}$737$~{}|~{}$322.6 |  258$~{}|~{}$468$~{}|~{}$97.7 |  256$~{}|~{}$274$~{}|~{}$48.3 |  758$~{}|~{}$252$~{}|~{}$36.4
| range-only |  372$~{}|~{}$240$~{}|~{}$16.0 |  391$~{}|~{}$213$~{}|~{}$16.0 |  391$~{}|~{}$143$~{}|~{}$23.5 |  381$~{}|~{}$451$~{}|~{}$24.3 |  38$~{}|~{}$1 112$~{}|~{}$81.2 |  347$~{}|~{}$717$~{}|~{}$46.6 |  127$~{}|~{}$138$~{}|~{}$21.2
| duration-only |  3 560$~{}|~{}$275$~{}|~{}$16.0 |  2 876$~{}|~{}$202$~{}|~{}$17.5 |  2 075$~{}|~{}$184$~{}|~{}$27.7 |  520$~{}|~{}$718$~{}|~{}$41.3 |  452$~{}|~{}$1 175$~{}|~{}$81.2 |  76$~{}|~{}$733$~{}|~{}$46.6 |  2 500 000$~{}|~{}$141$~{}|~{}$21.2
MimicIII | range-duration |  10 246$~{}|~{}$241$~{}|~{}$16.0 |  10 730$~{}|~{}$201$~{}|~{}$17.5 |  5 227$~{}|~{}$185$~{}|~{}$27.7 |  1 779$~{}|~{}$720$~{}|~{}$41.3 |  1 384$~{}|~{}$1 081$~{}|~{}$81.2 |  232$~{}|~{}$721$~{}|~{}$46.6 |  3 347$~{}|~{}$135$~{}|~{}$21.2

In the first set of experiments, we consider both real-world and synthetic
datasets (with 10 million intervals). Table 1 reports, under different
combinations of dataset/query workload, an overview on the performance of
different index structures on three indicators: the queries per second, the
time to build the index, and the size of the index. The latter is measured in
terms of bytes per interval, i.e., the number of bytes that the index uses for
each input interval. Since we are representing intervals as pairs of 64-bits
unsigned integers, 16 bytes per interval are required just to represent the
data, and thus are a lower bound on this performance metric. Dark blue and
light blue cells denote, respectively, the best and second-best performing
data structures in terms of queries per second. For index structures that take
parameters, we report on the best configuration. In particular, we defer the
discussion of the effect of different parameterizations of RD-index to Section
6.5.

We remark that the overall difference in throughput for different workloads is
due to the different output sizes: duration-only queries are in general less
selective than range-duration queries, hence it takes more time to iterate
through the output. This explains why, in general, range-duration queries
enjoy a higher throughput across all the index structures.

Consider first the performance in terms of throughput, i.e., the first
measure. We observe that RD-index always performs better than competitors on
range-duration queries and on range-only queries (with the exception of
MimicIII, where it ties with Grid-File). For duration-only queries it is
always the second best solution after the B-Tree. We will, however, see in the
next section how RD-index surpasses the B-Tree as soon as a few queries
constraining also the range are introduced in the workload.

We also observe that the grid-file ranks second or third in several cases.
Recall that this data structure is rather similar to RD-index, the difference
being that the latter is adaptive to the input distribution. This shows the
performance benefits of a data structure that takes into account the data
distribution.

Concerning the other performance indicators, we note that the index
construction time of RD-index is comparable with the one of the Grid-File and
B-Tree, and generally much faster than the other approaches. As for the size
of the index, RD-index always produces the smallest index, across all tested
configurations, using just slightly more than the minimum 16 bytes to
represent an interval. The other approaches, especially pointer-based data
structures such as B-Tree, Interval-Tree, and R*-Tree require significantly
more space. The Period-Index$\star$ has a much higher space requirement
compared to the others, since each interval may be replicated several times.

In summary, RD-index is a data structure that provides fast query times, is
fast to build, and has negligible space overhead.

###  6.3. Mixed Query Workloads

Figure 6.  Ternary plots of best performing index structure for different
mixed workloads, on the four different datasets. The online supplementary
material provides an interactive version of this plot.

We now consider mixed query workloads, consisting of a mix of range-only,
duration-only, and range-duration queries. Rather than fixing a particular
combination of queries, we use the data of Table 1 to estimate the throughput
of workloads composed by any combination of queries. Let $f_{rd}$, $f_{r}$,
and $f_{d}$ be, respectively, the fraction of range-duration, range-only, and
duration-only queries in the mixed query workload, with
$f_{rd}+f_{r}+f_{d}=1$. Similarly, for a given algorithm and dataset, let
$\phi_{rd}$, $\phi_{r}$, and $\phi_{d}$ be the throughputs of range-duration,
range-only, and duration-only queries, as reported in Table 1. The throughput
of the combined workload will then be the weighted harmonic mean of the
average rates reported in Table 1

$\displaystyle\frac{1}{\frac{f_{rd}}{\phi_{rd}}+\frac{f_{d}}{\phi_{d}}+\frac{f_{r}}{\phi_{r}}}.$

Figure 6 provides a summary of the best performing algorithm for any workload
that can be concocted with the formula above. In each ternary plot, each point
in the triangle identifies a combination of range-only, duration-only, and
range-duration queries. For instance, the center of each triangle corresponds
to a workload composed in equal parts by the three types of queries. Portions
of the triangles are colored according to the best-performing index for the
corresponding workloads. We observe that RD-index is the best performing index
structure in the vast majority of workloads. The exception is for workloads
where duration-only queries are the majority, where the B-Tree outperforms RD-
index. On mixed workloads, we observe that the performance of RD-index is
rather robust to the ordering of indexing dimensions. This can be verified in
Figure 13 in Appendix A, which reports ternary plots of the throughput of all
algorithms on all datasets for all mixed workloads. The online supplemental
material333https://cecca.github.io/temporal-index/ provides an interactive
tool to explore the performance of all different index structures on any mixed
workload.

###  6.4. Distribution of Query Times Against Selectivity

Figure 7.  Heatmaps of the performance of index structures against selectivity
in the time and duration dimensions. The top row reports the time, in
milliseconds, required to answer a query with a given time and duration
selectivity. The plots report the fraction of intervals (over the total
$n=10^{7}$) examined by each query. A fraction larger than 1 means that a
query examined the same interval more than once. For readability the color
scales are binned every 5 percentiles, therefore the scales are non linear. In
both plots, lighter is better.

Time versus selectivity in two dimensions

Figure 8.  Number of examined intervals against selectivity of the query. Each
point represents a query: red dots $\bullet$ are range-only queries, blue dots
$\bullet$ are duration-only queries, black dots $\bullet$ are range-duration
queries. The black line represents the ideal behavior, in which only matching
intervals are examined. Note that all the plots except for the one related to
the Period-Index$\star$ share the $y$ axis: in all plots the black diagonal
has slope 1.

Time versus selectivity

We investigate the relationship between the selectivity of queries (i.e., the
fraction of the input that satisfies them) and the time taken by different
data structures to answer them. Given that range-duration queries constrain
both the time and the duration ranges, for a query we can define the _time
selectivity_ as the fraction of the input that satisfies the time range
constraint of the query, and the _duration selectivity_ as the fraction of the
input satisfying the duration constraint of the query.

For a given dataset, we build a query set such that queries are uniformly
distributed on the _time_ $\times$  _duration_ selectivity plane: this way we
have queries that are very selective in only one dimension, very selective in
both dimensions, or not selective at all. The goal is to investigate the
behavior of each index structure for queries with different characteristics.
To account for the overhead of measuring time and to level out the effect of
the CPU cache, we run each query 100 consecutive times and report the average.
For RD-index, we set the page size to $s=200$, which is a good parameter
choice of all the datasets we consider.

Figure 7 reports the results for such a setup, with 1024 queries arranged in a
32 $\times$ 32 grid, running on a synthetic dataset with 10 million intervals,
with uniformly distributed start times and Zipf distributed durations. Colors
encode the fraction of the dataset inspected by each query. This metric allows
a more implementation-independent assessment of the relative performance of
different data structures. When reading Figure 7, remember that less selective
queries require more time just to iterate through the output. Interestingly,
different data structures exhibit different patterns in this plot, as a result
of how they access data.

The Interval-Tree plot exhibits vertical bands. The data structure is able to
select intervals only based on their position on the timeline. Therefore, for
a fixed time selectivity of the query the fraction of intervals inspected (and
thus the time to answer the query) does not depend on the selectivity in the
duration dimension, since all the candidate intervals need to be examined. For
similar reasons, the B-Tree shows horizontal bands. Data structures that
explicitly index both dimensions, instead, tend to exhibit a more _diagonal_
pattern, in particular RD-index, with a milder effect for Grid-File and
R*-Tree. The pattern exhibited by Period-Index$\star$ tends to be more similar
to the Interval-Tree. This means that this index is more responsive to queries
that are selective in the time dimension. This is to be expected since Period-
Index$\star$ is adaptive to the distribution of start times in the dataset.
Its worse performance compared to RD-index and Grid-File for queries of a
given selectivity is explained by the fact that some intervals might be
represented multiple times in the index.

Figure 8 reports the performance against the _overall_ selectivity of the same
queries. The performance is assessed in terms of the fraction of the input
inspected by each query, which are represented as dots whose position along
the $x$ axis encodes their overall selectivity. Ideally, a data structure
should answer queries by inspecting just the tuples which are part of the
output. This behavior is represented by the black diagonal in Figure 8. We
observe that RD-index indeed shows the ideal behavior. As for the Grid-File,
since the efficiency in answering a query depends on the density of the cells
being considered, the performance is in many cases far from ideal. This can be
seen from the fact that several queries are far away from the ideal diagonal.
The B-Tree indexes intervals by their duration. As such, duration-only queries
are answered most efficiently: In Figure 8 such queries lie on the ideal
diagonal. On the other hand, range-only queries are answered by simply
enumerating the entire dataset, thus scoring 1 on Figure 8. Similar
considerations hold for the Interval-Tree, with range-only queries performing
the best and duration-only queries performing the worst. Finally, Period-
Index$\star$ inspects the same tuples multiple times for the majority of
queries, which are thus very far away from the ideal diagonal line in the
plot.

Figure 9. Performance of RD-index under a non-optimal parameter configuration.

So far, we have reported on the performance of a good configuration (i.e.
$s=200$) of RD-index, which gives a behavior close to optimal. Figure 9
reports, in the same scenario of Figure 8, the performance of RD-index with a
time-duration ordering and page size $s=10$. As we will see in the next
section, this configuration is not ideal (the page size is too small): indeed,
for several queries we have to visit more intervals than the precision of the
query. This is especially true for duration-only queries (blue dots).
Nevertheless, even under this non-optimal setting, RD-index still performs
better than the other approaches, i.e., points are more concentrated towards
the diagonal.

###  6.5. Dependency on the Page Size and the Indexing Order

The aim of this section is to investigate the influence of the page size and
the order in which the two dimensions are indexed. We use two datasets with 10
million intervals each: the first has uniform start times and skewed durations
(Zipf distribution), the second has skewed start times and uniformly
distributed durations. As for the query workload, batches of 10 000 range-
duration, range-only, and duration-only queries are considered. The page size
is varied between 1 and 10 000.

Due to the size of the dataset, any page size $s$ above $\sqrt{n}\approx
3\,162$ results in a degenerate configuration, where there is a single column
(of size $s^{2}=n$) that contains all the intervals. In this case the
intervals are partitioned according to a single dimension, with the number of
cells controlled by the page size parameter. This situation might also occur
at lower values of the page size parameter, depending on the number of
distinct values in the dimension being partitioned. On the other hand, for
page size $1$, each cell of the grid contains only intervals with the same
start time and duration, and it contains all of them. Querying the data
structure in this case amounts to perform binary searches directly on the
values of the domains of start times and durations.

Figure 10 reports the results of this experiment in terms of queries per
second. To ease the comparison between the plots, we rescale the throughput by
the highest value for each combination of dataset and query workload.
Degenerate configurations resulting in a single column are reported as
triangles rather than dots. We observe very different trends for different
query workloads.

Consider first the dataset with skewed durations. For range-duration queries,
both orderings of dimensions exhibit a similar behavior. The peak performance
is reached by intermediate values around the page size. If we consider
duration-only queries the profile changes. Indexing first by duration (blue
line) slightly favors smaller page sizes, which imply smaller columns and thus
a more fine grained access to the data. Indexing first by time, instead,
requires a duration-only query to traverse all the columns. In this scenario
high page sizes are favored, since they translate into fewer columns to be
iterated through. For range-only queries we observe a symmetric pattern.

When data has skew on the start times, the patterns exhibited by the two
indexing orders are rather different. First, we note that the gap between the
best configurations of the two indexing orders for range-duration queries is
much wider than with the other dataset. Second, while indexing first by
duration exhibits a similar pattern on both datasets, indexing first by start
time performs best in the degenerate cases of a single column, i.e., with no
partitioning of the start times at all. This is a consequence of Observation
1. In particular, having skewed start times exacerbates the difference in
selectivity between the range and duration constraints: when start times are
very concentrated on the timeline, the range constraint of a query is
satisfied by either most of the intervals or by almost none.

Overall, we observe that indexing first by duration has either better or
comparable performance compared to indexing first by time. Therefore, we
recommend to choose the former ordering of dimensions when building an RD-
index.

Figure 10. Dependency of the performance, in terms of queries per second, on
the page size parameter.

###  6.6. Scalability with Respect to the Input Size

To test the scalability of the index structures, we consider range-duration
queries and datasets of increasing size, while maintaining the output size
constant. This allows to assess the influence of the input size on the
performance without conflating the results with the time required to iterate
over larger outputs.

We consider the three real-world datasets, along with a synthetic one with
uniform start times and Zipf-distributed durations, which is representative of
the distribution of many real-world datasets. Then, we artificially increase
their size as follows. Given a dataset and a scale parameter $\eta$, let
$\bar{t}$ be the span of time covered by all the intervals in the dataset. We
make $\eta$ copies of each interval and shift copy $i$ in time by
$i\cdot\bar{t}$, for $i\in[0,\eta)$. The underlying idea is to repeat the
temporal patterns of the dataset on a longer time scale, simulating the
scenario in which the relation grows over time.

Figure 11 reports for each scale factor the performance of the best
configuration of each algorithm. First, we note that in general the relative
performance of the data structures does not change at different dataset
scales. There are some notable exceptions. The performance of B-Tree degrades
by a factor $\approx$10 from scale 1 to scale 10. The reason is that the
B-Tree indexes the durations, and under our synthetic construction the number
of intervals associated to each duration increases by the same scale of the
dataset. For similar reasons, the performance of RD-index-dt degrades, albeit
in a much less pronounced way.

On Webkit, the performance of Grid-File and Period-Index$\star$ increases with
the scale as the dataset: the effect of our synthetic construction in this
case is to compensate for the skew in the start times, giving to both data
structures the chance of better partitioning the time dimension.

Figure 11. Scalability of the index structures for the increasing dataset
sizes. Performance is measured in queries per second. Each point corresponds
to the best configuration of the given data structure for a particular dataset
scale, up to 50 times the original size. The workload is of range-duration
queries.

Scalability figure, showing that our proposed approach has superior
performance for all tested dataset sizes, and scales gracefully.

###  6.7. Insertion Performance

(a) Intervals inserted in random order

(b) Intervals inserted by increasing start time

Figure 12. Performance of the insertion for different index structures. The
left group of plots (a) reports the throughput of insertions when intervals
are added in random order. The right group of plots (b) focuses on insertions
by increasing start time, i.e. a _append only_ scenario.

We now focus on the insertion operation, considering RD-index, B-Tree,
R*-Tree, and Interval-Tree. We omit from the comparison Period-Index$\star$,
which does not support updates, and Grid-File, which is a static data
structure that requires to know the range of the data beforehand.

For each of the four datasets we considered in the previous sections, we
insert intervals into initially empty indices. The expectation is that the
insertion performance degrades as the index grows larger. To measure this
effect, we insert the intervals in batches of 50 000, measuring the time for
each batch in order to be able to estimate the throughput of the insertions as
the size of the index grows. We perform two sets of experiments. In the first
set of experiments, the intervals are inserted in random order. In the second
set of experiments, intervals are inserted by increasing start time, which
simulates a natural _append only_ scenario for time-related data.

Figure 12 reports the results of these experiments. The x-axis reports the
fraction of the dataset that has been inserted into the index. The y-axis
reports, in logarithmic scale, the number of insertions per second. In most
cases, the best performing data structure for the insertion workload is the
B-Tree, both when data is presented in random and sorted order. RD-index
follows on the second place for most datasets, with the ordering first by time
and then by duration usually performing better. For randomly-ordered
insertions, we note that the performance of RD-index tends to slightly
decrease as the index size increases. In the more realistic append only
scenario, instead, the insertion throughput of RD-index is more stable and
tends to remain constant over time. This is expected, since in such a setting
only the last column (when the start time is the first dimension being
indexed, otherwise the last cell of each column) is ever restructured,
requiring very little data to be moved. Furthermore, the performance in this
scenario improves compared to the random order of insertions, in particular on
the MimicIII dataset, and is on par with the B-Tree on all datasets.

##  7\. Conclusions

RD-index is an index data structure for temporal intervals that allows to
answer efficiently range-duration queries. Our approach, which has provable
theoretical guarantees, lends itself to a simple and efficient implementation.
In particular, its ability to adapt to the distribution of the input data
makes it compare favorably with the state of the art on a variety of
workloads. In particular, RD-index has superior performance on a vast array of
mixed workloads.

A direction of future work is to extend the RD-index to support interval joins
(DBLP:journals/vldb/PiaDHP21, ), thus addressing several needs with a single
index. Furthermore, the favorable comparison with the R*-Tree suggests that a
promising research direction is to extend the ideas on which RD-index is based
to the case of multidimensional spatial data.

## References

  * [1] L. Arge, M. de Berg, H. J. Haverkort, and K. Yi.  The priority r-tree: A practically efficient and worst-case optimal r-tree.  ACM Trans. Algorithms, 4(1):9:1–9:30, 2008.
  * [2] M. Aumüller and M. Ceccarello.  Running experiments with confidence and sanity.  In SISAP, volume 12440 of Lecture Notes in Computer Science, pages 387–395. Springer, 2020.
  * [3] N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger.  The r*-tree: An efficient and robust access method for points and rectangles.  In SIGMOD, pages 322–331. ACM Press, 1990.
  * [4] A. Behrend, A. Dignös, J. Gamper, P. Schmiegelt, H. Voigt, M. Rottmann, and K. Kahl.  Period index: A learned 2d hash index for range and duration queries.  In SSTD, pages 100–109. ACM, 2019.
  * [5] A. Behrend, R. Manthey, G. Schüller, and M. Wieneke.  Detecting moving objects in noisy radar data using a relational database.  In ADBIS, volume 5739 of Lecture Notes in Computer Science, pages 286–300. Springer, 2009.
  * [6] A. Behrend, P. Schmiegelt, J. Xie, R. Fehling, A. Ghoneimy, Z. H. Liu, E. S. Chan, and D. Gawlick.  Temporal state management for supporting the real-time analysis of clinical data.  In ADBIS (2), volume 312 of Advances in Intelligent Systems and Computing, pages 159–170. Springer, 2014.
  * [7] M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf.  More geometric data structures.  In Computational Geometry, pages 211–233. Springer Berlin Heidelberg, 2000.
  * [8] M. H. Böhlen, A. Dignös, J. Gamper, and C. S. Jensen.  Temporal data management - an overview.  In eBISS, volume 324 of Lecture Notes in Business Information Processing, pages 51–83. Springer, 2017.
  * [9] M. H. Böhlen, J. Gamper, and C. S. Jensen.  Multi-dimensional aggregation for temporal data.  In EDBT, pages 257–275, 2006.
  * [10] P. Bouros and N. Mamoulis.  A forward scan based plane sweep algorithm for parallel interval joins.  PVLDB, 10(11):1346–1357, 2017.
  * [11] P. Bouros, N. Mamoulis, D. Tsitsigkos, and M. Terrovitis.  In-memory interval joins.  VLDB J., 30(4):667–691, 2021.
  * [12] F. Cafagna and M. H. Böhlen.  Disjoint interval partitioning.  VLDB J., 26(3):447–466, 2017.
  * [13] A. Dignös, M. H. Böhlen, and J. Gamper.  Overlap interval partition join.  In SIGMOD, pages 1459–1470. ACM, 2014.
  * [14] A. Dignös, M. H. Böhlen, J. Gamper, and C. S. Jensen.  Extending the kernel of a relational DBMS with comprehensive support for sequenced temporal queries.  ACM Trans. Database Syst., 41(4):26:1–26:46, 2016.
  * [15] A. Dignös, M. H. Böhlen, J. Gamper, C. S. Jensen, and P. Moser.  Leveraging range joins for the computation of overlap joins.  VLDB J., 2021.
  * [16] J. Ding, V. Nathan, M. Alizadeh, and T. Kraska.  Tsunami: A learned multi-dimensional index for correlated data and skewed workloads.  CoRR, abs/2006.13282, 2020.
  * [17] H. Edelsbrunner.  Dynamic rectangle intersection searching.  Technical Report 47, Institute for Information Processing, Technical University of Graz, Austria, 1980.
  * [18] R. A. Finkel and J. L. Bentley.  Quad trees: A data structure for retrieval on composite keys.  Acta Informatica, 4:1–9, 1974.
  * [19] Y. Hayashi and D. L. Paterson.  Strategies for reduction in duration of antibiotic use in hospitalized patients.  52(10):1232–1240, Apr. 2011.
  * [20] A. E. W. Johnson, T. J. Pollard, L. Shen, L.-W. H. Lehman, M. Feng, M. Ghassemi, B. Moody, P. Szolovits, L. A. Celi, and R. G. Mark.  Mimic-iii, a freely accessible critical care database.  Scientific data, 3(1):1–9, 2016.
  * [21] M. Kaufmann.  Storing and processing temporal data in a main memory column store.  Proc. VLDB Endow., 6(12):1444–1449, 2013.
  * [22] M. Kaufmann, A. A. Manjili, P. Vagenas, P. M. Fischer, D. Kossmann, F. Färber, and N. May.  Timeline index: a unified data structure for processing queries on temporal data in SAP HANA.  In SIGMOD, pages 1173–1184. ACM, 2013.
  * [23] N. Kline and R. T. Snodgrass.  Computing temporal aggregates.  In ICDE, pages 222–231. IEEE Computer Society, 1995.
  * [24] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis.  The case for learned index structures.  In SIGMOD, pages 489–504. ACM, 2018.
  * [25] H. Kriegel, M. Pötke, and T. Seidl.  Managing intervals efficiently in object-relational databases.  In PVLDB, pages 407–418. Morgan Kaufmann, 2000.
  * [26] H. Kriegel, E. Schubert, and A. Zimek.  The (black) art of runtime evaluation: Are we comparing algorithms or implementations?  Knowl. Inf. Syst., 52(2):341–378, 2017.
  * [27] K. G. Kulkarni and J. Michels.  Temporal features in SQL: 2011.  SIGMOD Rec., 41(3):34–43, 2012.
  * [28] D. G. J. Larsson and C.-F. Flach.  Antibiotic resistance in the environment.  Nov. 2021.
  * [29] B. Moon, I. F. V. López, and V. Immanuel.  Efficient algorithms for large-scale temporal aggregation.  IEEE Trans. Knowl. Data Eng., 15(3):744–759, 2003.
  * [30] V. Nathan, J. Ding, M. Alizadeh, and T. Kraska.  Learning multi-dimensional indexes.  In SIGMOD, pages 985–1000. ACM, 2020.
  * [31] J. Nievergelt, H. Hinterberger, and K. C. Sevcik.  The grid file: An adaptable, symmetric multikey file structure.  ACM Trans. Database Syst., 9(1):38–71, 1984.
  * [32] F. Persia, F. Bettini, and S. Helmer.  An interactive framework for video surveillance event detection and modeling.  In CIKM, pages 2515–2518. ACM, 2017.
  * [33] D. Piatov and S. Helmer.  Sweeping-based temporal aggregation.  In SSTD, volume 10411 of Lecture Notes in Computer Science, pages 125–144. Springer, 2017.
  * [34] D. Piatov, S. Helmer, and A. Dignös.  An interval join optimized for modern hardware.  In ICDE, pages 1098–1109. IEEE Computer Society, 2016.
  * [35] D. Piatov, S. Helmer, A. Dignös, and F. Persia.  Cache-efficient sweeping-based interval joins for extended allen relation predicates.  VLDB J., 2021.
  * [36] H. Samet.  Foundations of multidimensional and metric data structures.  Morgan Kaufmann, 2006.
  * [37] G. Schüller, A. Behrend, and R. Manthey.  AIMS: an sql-based system for airspace monitoring.  In GIS-IWGS, pages 31–38. ACM, 2010.
  * [38] G. Schüller, P. Schmiegelt, and A. Behrend.  Supporting phase management in stream applications.  In ADBIS, volume 7503 of Lecture Notes in Computer Science, pages 332–345. Springer, 2012.
  * [39] D. J. Shapiro, M. Hall, S. C. Lipsett, A. L. Hersh, L. Ambroggio, S. S. Shah, T. V. Brogan, J. S. Gerber, D. J. Williams, C. G. Grijalva, A. J. Blaschke, and M. I. Neuman.  Short- versus prolonged-duration antibiotics for outpatient pneumonia in children.  234:205–211.e1, July 2021.
  * [40] T. Ulrich.  Loose octrees.  In Game Programming Gems, pages 444–453. Charles River Media, 2000\.

##  Appendix A Additional Figures

In this appendix we report on the complete results for mixed workloads of
which Figure 6 in Section 6.3 is a compact summary.

Figure 13 reports a collection of ternary plots, each focusing on a particular
combination of dataset (columns) and index structure (rows). In order to
accommodate on a readable color scale the wide range of throughputs
encompassed by indices, we color-code the throughput divided by percentiles.
Therefore, brighter colors correspond to high throughputs, dark colors
correspond to low throughputs. Furthermore, these throughput percentiles are
computed _per dataset_.

Therefore, we can read Figure 13 as follows. For a given dataset (say Random)
we can take two different algorithms (e.g. RD-index and B-Tree) and compare
the color in any given area of the two corresponding ternary plots. For
instance focusing on the bottom-right corner of the ternary plots,
corresponding to workloads comprised mostly of range-duration queries, we
observe that the plot for RD-index features a brighter color than the one for
B-Tree. This means that the throughput of RD-index is higher than the one of
B-Tree for those workloads.

From Figure 13 we can therefore notice that the behavior of RD-index-dt and
RD-index-td is very similar, across all datasets. Furthermore, we notice that
with the exception of workloads where the vast majority of queries are
duration-only, RD-index enjoys a higher throughput than other indices.

Figure 13. Performance of all index structures on all considered datasets, for
different mixed workloads.