Duration-constrained Interval Joins

arXiv:2608.06856v1 [cs.DB] 7 Aug 2026

Duration-constrained Interval Joins Naoya Ehara

Daichi Amagata

Graduate School of Information Science and Technology The University of Osaka Osaka, Japan ehara.naoya@ist.osaka-u.ac.jp

Graduate School of Information Science and Technology The University of Osaka Osaka, Japan amagata.daichi@ist.osaka-u.ac.jp

Abstract—Many databases, including temporal, uncertain, spatial, and trajectory databases, use interval data, and interval joins are among the most frequently used operators. Many studies proposed efficient interval join algorithms, but they do not consider the overlap duration. They return any pairs of intervals, even if they overlap very slightly, e.g., with no essential correlation or relationship. Subsequent applications may suffer from such interval pairs, as they may be noise or unnecessary for the analysis. Furthermore, outputting such pairs also increases join time. To address the above issues, this paper addresses the problem of duration-constrained interval join. Given two interval collections R and S and an overlap duration constraint ϵ, this problem returns all interval pairs (r, s) such that r ∈ R, s ∈ S, and the overlap duration between r and s is at least ϵ. A straightforward approach for this problem is to run a state-ofthe-art interval join algorithm and then filter qualified interval pairs. However, this is inefficient, as it generates unnecessary interval pairs and incurs duration computations, which cannot overcome the above efficiency concern. We propose an efficient algorithm for this problem that removes the above drawback. Furthermore, we propose two optimization techniques to improve the efficiency of our algorithm. We conduct extensive experiments on three real-world interval datasets, and the results demonstrate that our algorithm outperforms existing techniques applicable to our problem. Index Terms—interval data, join, overlap duration

I. I NTRODUCTION An interval r is a pair of start and end points, i.e., r = [r.start, r.end]. Many database systems, including temporal databases [1], [2], uncertain databases [3], [4], spatial databases [5], [6], and trajectory databases [7], manage interval data. Hence, efficient processing of interval data remains an important research topic. Interval joins are one of the most important and frequently used operations in (temporal-related) databases [8]. Given two interval collections R and S, an interval join returns all interval pairs (r, s) such that r ∈ R and s ∈ S overlap. Figure 1 illustrates an example of an interval join between R = {r1 , r2 } and S = {s1 , s2 , s3 , s4 }. This query has many applications that require entity linking. For example, consider employee databases that record the working period of each employee in different departments [9]–[12]. An interval join returns all pairs of employees whose working period overlaps. Moreover, interval joins are used in IoT environments, such as sensor networks [13] and traffic monitoring in data centers [14]. It is known, in addition, that an interval join can be used for a spatial join and equi-join on uncertain data [9], [10].

A. Motivation Although interval joins are useful in real-world applications, their computational cost is high when |R| = n and |S| = m are large, because it requires O(nm) time in the worst case. To alleviate this cost, many works [11], [13], [15]–[19] devised efficient interval join algorithms. However, they do not consider the overlap duration between two intervals. Overlap joins return (r, s) even if r and s overlap slightly. In the above employee database example, two employees who almost never work together are included in the output, e.g., (r1 , s1 ) in Figure 1. Pairs of slightly overlapping intervals can be noise, potentially affecting analysis accuracy negatively. Introducing the overlap duration as a constraint can remove this concern and obtain a more reasonable result. Bioinformatics [20], medical data tests [21], and overlap functions [22] put importance on the overlap duration between intervals. In addition, many mobile applications also benefit from this setting. For example, GPS points can generate mobile user records of the store stay periods [23]. Given a set of these intervals, a set of intervals of the store’s advertisements (and/or promotions), and a duration constraint, this store can analyze how each promotion affects users while removing slightly overlapping intervals, which can be noise [24]. Another example is life logs. Wearable devices can record activity sessions and vital health sensor readings. Assuming a database that maintains such historical records, joining them while considering a sufficient temporal overlap helps analyze causal relationships in users’ health status. Therefore, we consider duration-constrained interval joins in this paper. B. Challenge A straightforward approach for the problem of durationconstrained interval join is to run a state-of-the-art interval join algorithm and then pick all interval pairs that satisfy the duration constraint among the join result. This approach has two drawbacks: (i) it requires an additional cost of computing the overlap duration for each join result, and (ii) the original join cost remains, although it can contain many interval pairs that do not satisfy a given overlap duration constraint. Another approach is to evaluate the overlap duration, instead of evaluating whether overlapping or not, when running the interval join algorithm. When there are many pairs of overlapping intervals, this approach needs to compute the overlap duration at least for each pair. Thus, this approach also incurs a huge

𝑟1 𝑠1

Note that ϵ is application-dependent and is specified on demand. Our problem is defined as follows:

𝑟2 𝑠2

D EFINITION 2 (Duration-constrained interval join problem). Given two interval sets R and S and a duration constraint ϵ > 0, this problem returns R ▷◁ϵ S such that

𝑠3 𝑠4

𝑡 Fig. 1. Example of an interval join. The result of join between R and S includes (r1 , s1 ), (r1 , s2 ), and (r2 , s3 ).

computational cost. These challenges suggest that using a state-of-the-art interval join algorithm is not appropriate for duration-constrained interval joins, and an algorithm optimized for this problem is required.

R ▷◁ϵ S = {(r, s) ∈ R ▷◁ S | l(r, s) ≥ ϵ}. We see that the interval join problem is a special case of our problem with l(r, s) > 0. In this work, as with many existing studies that consider interval data, e.g., [9], [10], [13], [16]–[18], [25]–[29], we assume that R and S are memory-resident and do not receive (frequent) updates. The objective of this work is to devise an efficient algorithm for the duration-constrained interval join problem.

C. Contribution To address the above challenges, this paper makes the following contributions. (1) We propose a novel algorithm for the duration-constrained interval join problem. By exploiting a new thresholding approach with a grid index, our algorithm avoids unnecessary comparisons for both interval pairs included and not included in the result. (2) We propose two optimization techniques for our algorithm. The first optimization reduces the cost of comparisons between intervals. Because our algorithm employs a nested-loop join, our second optimization exploits batch processing for similar intervals. (3) We conduct extensive experiments on three real-world interval datasets. The experimental results demonstrate that our algorithm outperforms existing techniques applicable to our problem.

III. P ROPOSED A LGORITHM This section presents our proposed algorithm. Main idea. A join between n and m objects requires O(nm) time, because the join size is O(nm) in the worst case. Therefore, to improve the practical efficiency of the durationconstrained interval join, it is important to reduce constant factors, i.e., unnecessary comparisons between intervals. To this end, we require a technique that identifies whether (r, s) ∈ R ▷◁ϵ S or not without comparisons. As the first step for achieving this, we define two thresholds. D EFINITION 3. Given an interval r ∈ R and a duration constraint ϵ, θstart (r) and θend (r) are respectively defined as follows. θstart (r) = r.end − ϵ θend (r) = r.start + ϵ Then, we have the following theorems.

D. Organization The rest of this paper is organized as follows. Section II introduces the formal problem definition. Section III presents our algorithm. We report our experimental results in Section IV, and related works are reviewed in Section V. Finally, this paper is concluded in Section VI. II. P RELIMINARY An interval r is represented as r = [r.start, r.end], i.e., r starts at r.start and ends at r.end. The interval length of r is denoted by |r|, and |r| = r.end − r.start. For ease of understanding, we first define the interval join problem. D EFINITION 1 (Interval join problem). Given two interval sets R and S, this problem returns R ▷◁ S such that R ▷◁ S = {(r, s) | r ∈ R, s ∈ S, (r.start ≤ s.end) ∧ (s.start ≤ r.end)}. We consider a variant of the above problem. Let l(r, s) be the overlap duration between r and s. Then, l(r, s) = min{r.end, s.end} − max{r.start, s.start}.

T HEOREM 1. Given two intervals r ∈ R and s ∈ S and a duration constraint ϵ, assume that |r| ≥ ϵ and |s| ≥ ϵ. (i) If s.start ≤ r.start and θend (r) ≤ s.end, we have (r, s) ∈ R ▷◁ϵ S. (ii) If θstart (r) < s.start or s.end < θend (r), we have (r, s) ∈ / R ▷◁ϵ S. Proof. In the case of (i), we have l(r, s) = min{r.end, s.end} − max{r.start, s.start} ≥ θend (r) − r.start = (r.start + ϵ) − r.start =ϵ The inequality holds since s.end ≥ θend (r) and r.end ≥ θend (r). In the case of (ii), if θstart (r) < s.start, we have l(r, s) < min{r.end, s.end} − θstart (r) = min{r.end, s.end} − (r.end − ϵ) ≤ r.end − (r.end − ϵ) =ϵ

𝜃𝑠𝑡𝑎𝑟𝑡 𝑟

𝜀

𝜃𝑒𝑛𝑑 𝑟

𝑟 𝑠1

𝑠2 𝑠3 𝑠4 𝑠5

𝑡 𝜀 Fig. 2. Example of Theorem 1 𝑒𝑛𝑑

Data structure. To this end, we employ a two-dimensional grid structure G to manage S. Note that each interval can be represented as a two-dimensional point; the coordinates of an interval r are (r.start, r.end), and Figure 3 illustrates this observation1 . Consider G as a matrix, and each cell of G is start end represented as ci,j . We use Si,j and Si,j to denote the sets of intervals in ci,j that are respectively sorted based on start and end points (ascending order). In addition, we maintain max • an array Acol to manage the maximum start point in each column; e.g., Amax col [i] is the maximum start point among the intervals in the i-th column. Notice that Amax col [i] < Amax col [i + 1] for any i ≥ 0. Similarly, for each i-th column, we maintain additional arrays: end,min • Ai is an array, where Aend,min [j] maintains the i minimum end point among the intervals in ci,j . end,max • Ai is an array, where Aend,min [j] maintains the i maximum end point among the intervals in ci,j . start,min • Ai is an array, where Astart,min [j] is the minimum i start point among the intervals in ci,j . Comparison skipping for s in a batch. For a given r ∈ R, these structures support skipping interval comparisons for some intervals ∈ S in a batch, without losing correctness, in the following cases.

𝑠𝑡𝑎𝑟𝑡

Fig. 3. Two-dimensional representation of intervals

C OROLLARY 1. Given an interval r ∈ R, let i be the minimum column number such that θstart (r) ≤ Amax col [i]. Then, for every interval s in ci′ ,j such that i′ > i and j ≥ 0, we have (r, s) ∈ / R ▷◁ϵ S. Proof. In this case, we have

If s.end < θend (r), we have

θstart (r) ≤ Amax col [i] =

l(r, s) < θend (r) − max{r.start, s.start}

<

= (r.start + ϵ) − max{r.start, s.start}

max s.start

s ∈ ∪j ci,j

min

s ∈ ∪j ci′ ,j

s.start,

≤ (r.start + ϵ) − r.start

which falls into case (ii) of Theorem 1.

=ϵ

C OROLLARY 2. Given an interval r ∈ R, if θend (r) ≤ Aend,min [j] and s.start ≤ r.start, for every interval s in i ci,j , we have (r, s) ∈ R ▷◁ϵ S.

Therefore, this theorem holds. E XAMPLE 1. Figure 2 illustrates an example of Theorem 1. We see that s1 and s2 have case (i). Also, s3 and s4 fall into case (ii). Only s5 needs to be evaluated whether l(r, s5 ) ≥ ϵ or not. Theorem 1 yields several conditions that identify whether (r, s) ∈ R ▷◁ϵ S or not, without computing l(r, s). However, the cost of checking the condition (i) or (ii) is the same as that of computing l(r, s), for given r and s. We thus next need a data structure which, for a given r ∈ R, can find a set S ′ of intervals ∈ S falling into case (i) or (ii) in a batch. Specifically, for any r ∈ R, to efficiently find a set of intervals ∈ S satisfying case (i) or (ii), it is required that S is sorted by start and end points. In addition, if (r, s) ∈ R ▷◁ϵ S and s and s′ are similar, (r, s′ ) tends to be in R ▷◁ϵ S. The data structure, thus, should group similar intervals to avoid redundant interval comparisons.

Proof. This case has θend (r) ≤ Aend,min [j] = min s.end. i s ∈ ci,j

As s.start ≤ r.start, this case falls into case (i) of Theorem 1. C OROLLARY 3. Given an interval r ∈ R, if Aend,max [j] < i θend (r), for every interval s in ci,j , we have (r, s) ∈ / R ▷◁ϵ S. Proof. This case has Aend,max [i] = max s.end < θend (r) i s ∈ ci,j

1 Although an interval range query q can be transformed into a 2-sided orthogonal range search (−∞, q.end] × [q.start, ∞) on two-dimensional points, this orthogonal range query cannot consider the overlap duration. Therefore, using a spatial index, such as R-tree and kd-tree, is not useful for our problem.

which falls into case (ii) of Theorem 1. C OROLLARY 4. Given an interval r ∈ R, if θstart (r) < [j], for every interval s in ci,j , we have (r, s) ∈ / Astart,min i R ▷◁ϵ S. Proof. This case has

Algorithm 1: Proposed Algorithm Input: G, r, and ϵ Output: Jr = r ▷◁ϵ S 1 if |r| < ϵ then 2 return Jr ← ∅ θstart (r) ← r.end − ϵ 5 θend (r) ← r.start + ϵ max 6 idx ← F IND -I NDEX (Acol , r.start) ′ max 7 idx ← F IND -I NDEX (Acol , θstart (r)) 8 for i ← 0 to idx − 1 do 9 j ← F IND -I NDEX(Aend,max , θend (r)) i | do 10 while j ≤ |Aend,max i 11 I←∅ [j] then 12 if θend (r) ≤ Aend,min i end 13 I ← Si,j 14 else end 15 I ← {s ∈ Si,j | θend (r) ≤ s.end} 3

θstart (r) < Astart,min [j] = min s.start, i s ∈ ci,j

which falls into case (ii) of Theorem 1. We exploit these observations to reduce unnecessary interval comparisons. Note that our algorithm can employ an arbitrary grid structure. In our experiments, we use the state-of-the-art one [30]. Pre-processing time. Assume that G is built on S. Mapping an interval ∈ S to the corresponding cell needs O(1) time, so building G of S takes O(m) time. Note that we do not create empty cells, thus the number of cells is bounded by m. This means that the size of each array is also bounded by m. Therefore, making the four arrays needs O(m log m) time. In total, our pre-processing time is O(m log m).

4

17

foreach s ∈ I do Jr ← Jr ∪ {(r, s)}

18

j ←j+1

16

Space complexity. From the above pre-processing time, the space complexity of G is O(m). Again, the size of each array is also bounded by m. The space complexity of our data structures is hence O(m).

19

Update. Although we do not assume (frequent) updates, our data structures are easy to update. Given a new interval, we map it to the corresponding cell. Assume that this cell is ci,j . If this insertion affects Aend,min [j], Aend,max [j], or i i start,min Ai [j], we update the corresponding array. Furthermore, if this new interval has the maximum start point in the i-th column, we update Amax col [i]. If an existing interval is removed from S, we do similar updates to the above insertion.

25

Algorithm description. Our join algorithm employs a nestedloop join approach. Assume that |R| ≤ |S|; otherwise, we swap them. For each r ∈ R, we run Algorithm 1. If |r| < ϵ, as it cannot satisfy the overlap duration constraint, we skip this interval. Otherwise, we set θstart (r) and θend (r). We then run a binary search on Amax to find the first column col number, idx, that has r.start ≤ Amax col [·]. Also, we run a binary search on Amax to find the first column number, idx′ , col max that has θstart (r) ≤ Acol [·]. We do not access the idx′ + α (α ≥ 1) column of G from Corollary 1. Consider each i-th column of G where i ∈ [0, idx − 1]. S This column guarantees that s.start < r.start for any s in j ci,j end,max since Amax [j] < col [i] < r.start. For a cell ci,j of G, if Ai θend (r), all intervals in ci,j are not included in R ▷◁ϵ S from Corollary 3. Hence, we focus on cell ci,j such that θend (r) ≤ Aend,max [j]. This can be achieved by running a binary search i end,max on Ai . If θend (r) ≤ Aend,min [j], from Corollary 2, all i intervals in ci,j are included in R ▷◁ϵ S, so they are added into the result without comparisons. If θend (r) > Aend,min [j], we i add all intervals s ∈ ci,j such that θend (r) ≤ s.end without comparisons.

for i ← idx to idx′ do 20 j ← F IND -I NDEX(Aend,max , θend (r)) i 21 while j ≤ |Aend,max | do i 22 if θstart (r) < Astart,min [j] then i 23 j ←j+1 24 continue 26 27 28 29 30

if i < idx′ then if r.end ≤ Aend,min [j] then i start Jr ← Jr ∪ {(r, s)}, ∀s ∈ Si,j else start foreach s ∈ Si,j s.t. l(r, s) ≥ ϵ do Jr ← Jr ∪ {(r, s)}

32

else Run lines 29–30

33

j ←j+1

31

Next, consider each i-th column of G where i ∈ [idx, idx′ − 1]. We run similar operations to the above case. If θstart (r) < Astart,min [j], from Corollary 4, all intervals in ci,j are not i included in R ▷◁ϵ S, thereby we skip this cell. Otherwise, we start add all intervals in Si,j to the result if r.end ≤ Aend,min [j]. i In the other cases, we compute l(r, s) for each s ∈ Si,j and add (r, s) iff l(r, s)) ≥ ϵ. Last, given the idx′ -th column, we do almost the same operations as above. One difference is that this column does not have the case of r.end ≤ Aend,min [j]. i E XAMPLE 2. Figure 4 depicts an example of Algorithm 1 assuming that r, such that |r| ≥ ϵ, is given. After identifying

𝑒𝑛𝑑

𝜀

𝜃𝑚𝑎𝑥 𝑐𝑖,𝑗

𝑐0,5

𝑐1,5

…

𝑐𝑖𝑑𝑥,5 𝑐𝑖𝑑𝑥 ′ ,5

…

𝑐0,4

𝑐1,4

…

𝑐𝑖𝑑𝑥,4 𝑐𝑖𝑑𝑥 ′ ,4

…

𝑐0,3

𝑐1,3

…

𝑐𝑖𝑑𝑥,3 𝑐𝑖𝑑𝑥 ′ ,3

…

𝜀

𝐴𝑒𝑛𝑑,𝑚𝑎𝑥 [𝑗] 𝑖 𝐴𝑒𝑛𝑑,𝑚𝑖𝑛 [𝑗] 𝑖

𝑟1

𝑠1 𝑠2 𝑠3

…

…

𝑠4

…

…

𝑠5 𝑠6

…

…

𝑡 𝑠𝑡𝑎𝑟𝑡

𝜃𝑚𝑖𝑛 𝑐𝑖,𝑗

𝜃𝑠𝑡𝑎𝑟𝑡 𝑟

Fig. 4. Illustration of Example 2

idx and idx′ , this algorithm first accesses the 0-th column. It runs a binary search on Aend,max , and accesses cells in 0 order of c0,3 → c0,4 → c0,5 . Each yellow cell assumes the case of θend (r) ≤ s.end, so it adds all intervals s ∈ c0,3 such that θend (r) ≤ s.end without comparisons. Each orange cell assumes the case of θend (r) ≤ Aend,min [j], so it adds all i intervals ∈ c0,4 ∪ c0,5 without comparisons. At the idx-th column, the blue cell assumes the case of r.end ≤ Aend,min [j]. i start Hence, all intervals in Sidx,3 are added to the result. The gray cell assumes the case of θstart (r) < Astart,min [j], so cidx,4 i is skipped. At the idx′ -th column, the green cells assume that the other cases, i.e., it computes l(r, s) for every interval in ci,j .

𝜃𝑒𝑛𝑑 𝑟

Fig. 5. Example of Theorem 2

rem 1. When r.start < s.start ≤ θmin (ci,j ) ≤ θstart (r), l(r, s) = min{r.end, s.end} − max{r.start, s.start} ≥ min{r.end, Aend,min [j]} − θmin (ci,j ) i = Aend,min [j] − (Aend,min [j] − ϵ) i i =ϵ Note that θmin (ci,j ) = Aend,min [j] − ϵ ≤ θstart (r) = r.end − i ϵ, so we have min{r.end, Aend,min [j]} = Aend,min [j]. In the i i case of (ii), when θstart (r) < θmax (ci,j ), l(r, s) < ϵ from Theorem 1. When θmax (ci,j ) ≤ θstart (r) < s.start, because θmax (ci,j ) = Aend,max [j] − ϵ < θstart = r.end − ϵ, we have i l(r, s) = min{r.end, s.end} − max{r.start, s.start} < Aend,max [j] − θmax (ci,j ) i

A. Optimization Although Algorithm 1 exploits Theorem 1 and its corollaries to reduce computing l(r, s) for many intervals ∈ S, at lines 29 and 32, it computes l(r, s) for each s ∈ ci,j . We next reduce this computational cost by introducing additional pruning rules. D EFINITION 4. Given a cell ci,j of G and an overlap duration constraint ϵ, θmin (ci,j ) and θmax (ci,j ) are respectively defined as follows: θmin (ci,j ) = Aend,min [j] − ϵ i θmax (ci,j ) = Aend,max [j] − ϵ i This definition yields the following pruning rules: T HEOREM 2. Given an interval r ∈ R and an overlap duration constraint ϵ, consider ci,j such that θend (r) ≤ Aend,min [j]. (i) If s.start ≤ r.start or r.start < s.start ≤ i θmin (ci,j ) ≤ θstart (r), we have (r, s) ∈ R ▷◁ϵ S. (ii) If min{θmax (ci,j ), θstart (r)} < s.start, we have (r, s) ∈ / R ▷◁ϵ S.

= Aend,max [j] − (Aend,max [j] − ϵ) i i =ϵ Therefore, this theorem holds. E XAMPLE 3. Assume ci,j having lines 29 and 32 of Algorithm 1. Figure 5 describes this case. We see that s1 and s2 have case (i). Also, s5 and s6 have case (ii) as they satisfy θmax (ci,j ) < s.start. Therefore, in this example, only s3 and s4 require computing l(r, s). Algorithm description. Algorithm 2 extends Algorithm 1 by incorporating Theorem 2. The difference from Algorithm 1 is lines 11–22. After computing θmin (ci,j ), Algorithm 2 applies case (i) of Theorem 2, and every interval s in ci,j satisfying this case is included in the join result without computing l(r, s). Next, after computing θmax (ci,j ), Algorithm 2 applies case (ii) of Theorem 2 to filter intervals not included in the start result. Specifically, it computes l(r, s) for each s ∈ Si,j that does not satisfy cases (i) and (ii), and once the current s start satisfies case (ii), scanning Si,j is terminated. B. Batch Processing

Assume that θend (r) ≤ Aend,min [j] for cell ci,j . In the i

Proof. case of (i), when s.start ≤ r.start, l(r, s) ≥ ϵ from Theo-

Algorithms 1 and 2 employ a nested-loop approach and handle each r ∈ R one by one. This approach may incur

Algorithm 2: Proposed Algorithm with Optimization Input: G, r, and ϵ Output: Jr = r ▷◁ϵ S 1 Run lines 3–18 of Algorithm 1 ′ 2 for i ← idx to idx do 3 j ← F IND -I NDEX(Aend,max , θend (r)) i | do 4 while j ≤ |Aend,max i 5 if Astart,min [j] > θstart (r) then i 6 j ← j + 1, continue 7 8 9 10 11 12

13 14 15 16

if i < idx′ then [j] then if r.end < Aend,min i st Jr ← Jr ∪ {(r, s)}, ∀s ∈ Si,j else [j] − ϵ θmin (ci,j ) ← Aend,min i λ← min{max{r.start, θmin (ci,j )}, θstart (r)} start s ← the first interval in Si,j while s.start ≤ λ do Jr ← Jr ∪ {(r, s)} start s ← next interval in Si,j

21

θmax (ci,j ) ← Aend,max [j] − ϵ i λ ← min{θmax (ci,j ), θstart (r)} while s.start ≤ λ do if l(r, s) ≥ ϵ then Jr ← Jr ∪ {(r, s)}

22

st s ← next interval in Si,j

17 18 19 20

24

else Run lines 11–22

25

j ←j+1

23

redundant computations. For example, if r1 and r2 have similar start and end points, computing r1 ▷◁ϵ S and r2 ▷◁ϵ S tends to share a similar interval access pattern. Therefore, we consider an approach that groups some intervals ∈ R, say {ra , ..., rb }. Assume that each r ∈ {ra , ..., rb } is similar to each other. For a given cell ci,j , if l(ra , s) ≥ ϵ or l(ra , s) < ϵ for every s in ci,j , any r ∈ {ra , ..., rb } also has such a case in expectation. If so, we can further skip interval comparisons. To maximize the improvement by this approach, it is important to consider how to make groups. We propose the following approach to make groups. D EFINITION 5. Given an interval r ∈ R, all intervals in the group of r satisfy the following rules: r and r′ can be mapped into the same cell of G. ′ • r.start ≤ r .start ≤ r.start + γ, where γ ≥ 0 is a hyperparameter. max • Let Acol [j] be the minimum value that satisfies θstart (r) ≤ Amax ≤ r′ .end ≤ col [j]. Then, r.end max min{r.end + γ, Acol [j] + ϵ}. •

𝛾

𝛾

𝑟1

Fig. 6. Example of making a group of r1 ∈ R

Figure 6 illustrates a brief example of making a group of r1 ∈ R. To minimize the interval comparisons, we should minimize the number of groups, i.e., similar intervals should be placed in the same group as much as possible. However, making such groups is NP-hard. T HEOREM 3. The problem of minimizing the number of groups satisfying Definition 5 is NP-hard. Proof. We prove this theorem by showing that an instance of this problem includes an NP-hard problem. Assume that every interval r ∈ R is mapped to one of the i-th column cells, which satisfies the first rule in Definition 5. Also, assume that ϵ is sufficiently large so that min{r.end + γ, Amax col [j] + ϵ} min{r.end + γ, Amax [j] + ϵ} = r.end + γ. Then, let the col group of r be G(r), and r′ belongs to G(r) iff 1) r.start ≤ r′ .start ≤ r.start + γ, and 2) r.end ≤ r′ .end ≤ r.end + γ. Consider that r is a 2-dimensional point of (r.start, r.end). We can draw a square S(r) of length γ whose left-bottom point is r. If G(r) contains r′ , r′ is inside S(r) geometrically. Hence, the problem stated in Theorem 3 is to partition R into disjoint subsets G(ri ), ..., G(rj ) while minimizing the number of subsets. From the above geometric representation, this problem is equivalent to the problem of geometric set cover, which is NP-hard [31]. Now we see that an instance of our problem contains the NP-hard problem, thereby this theorem holds. Making batches/groups. Since Theorem 3 proves that an optimal set of groups is hard to obtain efficiently in practice, we propose a heuristic approach. We sort the intervals of R by start point in ascending order. We make groups (batches) in a greedy manner. Let r be the first interval in R, and we make a group of r by sequentially accessing R. That is, if rj satisfies Definition 5, rj is included in the group of r. (Once the second condition of Definition 5 is not satisfied, we early stop the scan.) After the scan is terminated, we exclude the group of r from R, and iterate the above scan from the first interval in the remaining intervals. This is repeated until R becomes empty. Note that making groups does not require query inputs, hence it can be done offline. If a new interval r is added to R, we find a group G(·) that satisfies Definition 5 for r,

and then add it to the group. On the other hand, if an existing interval r′ is removed from R, we simply remove it from the corresponding group. Comparison skipping for r and s in a batch. Thanks to the grouping technique, we can further reduce interval comparisons. C OROLLARY 5. Given a group G(ra ) of an interval ra ∈ R, let rb be the last interval of G(ra ). If θend (rb ) ≤ Aend,min [j] i and s.start ≤ ra .start, for every interval s in ci,j , we have (r, s) ∈ R ▷◁ϵ S for all r ∈ G(ra ). Proof. From Definition 5, it is guaranteed that ra .start ≤ rb .start and θend (ra ) ≤ θend (rb ). Hence, from Corollary 2, this corollary holds. C OROLLARY 6. Given a group G(ra ) of an interval ra ∈ R, if Astart,min [j] > θstart (ra ) + γ, for every interval s in ci,j i and every interval r ∈ G(ra ), we have (r, s) ∈ / R ▷◁ϵ S. Proof. From Corollary 4.

Algorithm 3: Proposed Algorithm for Batch Intervals Input: G, G(r), and ϵ Output: JG(r) = G(r) ▷◁ϵ S 1 JG(r) ← ∅ 2 θstart (r) ← r.end − ϵ 3 θend (r) ← r.start + ϵ max 4 idx ← F IND -I NDEX (Acol , r.start) ′ max 5 idx ← F IND -I NDEX (Acol , θstart (r)) 6 C ←∅ ′ ′ 7 foreach r ∈ G(r) s.t. |r | ≥ ϵ in the reverse order do 8 foreach i = 0 to idx − 1 do , θend (r)) 9 j ← F IND -I NDEX(Aend,max i end,max | do 10 while j ≤ |Ai 11 if ci,j ∈ / C then 12 if θend (r′ ) ≤ Aend,min [j] then i end and r′′ ∈ G(r) 13 foreach s ∈ Si,j s.t. r′′ .start ≤ r′ .start do 14 JG(r) ← JG(r) ∪ {(r′′ , s)}

18

C ← C ∪ {ci,j } else end foreach s ∈ Si,j s.t. ′ θend (r ) ≤ s.end do JG(r) ← JG(r) ∪ {(r′ , s)}

19

j ←j+1

15

Algorithm description. Algorithm 3 describes the join procedure between G(r) (i.e., an interval group of r) and S. It is based on Algorithm 2 and optimized for interval groups. (This algorithm is iterated for each group to obtain R ▷◁ϵ S.) The main differences appear in lines 12–15 and lines 30–32. The first one uses Corollary 5 to include the join result of end G(r) × Si,j in a batch, and this cell is never accessed again. The other uses Corollary 6 to skip the cell for every r′ ∈ G(r), and this cell is never accessed in the future for this group.

17

20 21 22

IV. E XPERIMENT

23

This section reports our experimental results. All experiments were conducted on an Ubuntu 24.04 LTS machine with an Intel Core i9-10980XE@3.0GHz CPU and 128GB of RAM.

24 25 26 27 28

A. Setting 2

Dataset. We used three real-world datasets: BTC , Books [10], and Renfe3 , which are used in recent interval works [25]–[27], [32], [33]. • BTC is a set of historical price intervals of Bitcoin. We used low and high prices as the start and end points, respectively. • Books is a set of the borrowing periods of books in the Aarhus libraries. • Renfe is Spanish rail trip data. We used departure time and arrival time as the start and end points, respectively. Table I shows the statistics of each dataset. For each dataset, we randomly sampled some intervals, and they were used as R, and the remaining intervals were used as S. In our experiments, we varied |R|/|S| in the range of {0.25, 0.5, 0.75, 1.0}, and, by default, |R|/|S| = 1. Notice that R ▷◁ϵ S = S ▷◁ϵ R, so the case of |R|/|S| > 1 does not occur by exchanging 2 https://www.kaggle.com/datasets/swaptr/bitcoin-historical-data 3 https://www.kaggle.com/datasets/thegurusteam/ spanish-high-speed-rail-system-ticket-pricing

16

29 30

31 32 33 34

foreach i = idx to idx′ do j ← F IND -I NDEX(Aend,max , θend (r)) i end,max while j ≤ |Ai | do if ci,j ∈ / C then if i < idx′ then if r.end + γ < Aend,min [j] then i Run lines 13–15 else Run lines 11–22 of Algorithm 2 else if Astart,min [j] > θstart (r) + γ i then C ← C ∪ {ci,j }, j ← j + 1 continue Run line 28 j ←j+1

R and S. Furthermore, let lavg be the average length of the intervals in a given dataset. We used p × lavg as ϵ, and varied p in the range of {0.2, 0.4, 0.6, 0.8}. By default, p = 0.4. Evaluated algorithm. Our experiments evaluated the following algorithms. •

FS [9], [10]: This is the state-of-the-art interval join algorithm. To deal with our problem, i.e., the overlap duration

TABLE I DATASET STATISTICS

Cardinality Domain size Minimum length Maximum length

TABLE III M EMORY USAGE [MB]

BTC

Books

Renfe

3,766,762 6,876,400 0 547,077

2,312,602 31,507,200 0 31,406,400

38,753,060 52,163,400 1,320 44,700

TABLE II P RE - PROCESSING TIME [ SEC ]

FS RD-index Rel Ours

BTC

Books

Renfe

0.24 0.48 3.49 0.57

0.11 0.24 0.71 0.27

2.42 3.95 28.97 4.37

RD-index Rel Ours

BTC

Books

Renfe

32.06 198.28 63.84

20.53 94.50 39.66

327.66 929.87 653.62

usage is omitted. Rel requires more memory than the others, as it employs a hierarchical structure with a non-contiguous memory layout. Ours requires almost twice the memory usage of RD-index. This is because ours maintains intervals in two arrays, sorted based on start and end points. Nevertheless, the memory usage of our structure is reasonable for about 40 million intervals (i.e., Renfe). D. Join Time

constraint, we extended FS as follows. When it identifies that r and s overlap, it computes l(r, s) and adds this pair into the result iff l(r, s) ≥ ϵ. • RD-index [30], [34]: This is the state-of-the-art algorithm that considers interval duration (not overlap duration). Because this algorithm does not consider joins but searches, we run a search query r ∈ R on S, i.e., we ran nested-loop join. • Rel [33]: This algorithm considers threshold queries, which output every interval for which the overlap duration between a query and the interval is at least the given threshold. Similar to RD-index, we ran this search on S by using each r ∈ R as a query. We used an interval tree as its base index. 4 • Ours : This is our proposed algorithm shown in Algorithm 2. Note that Algorithm 3 is evaluated in Section IV-G. These algorithms were single-threaded, implemented in C++, and compiled by g++ 13.3.0 with -O3 flag. B. Pre-processing Time Table II shows the pre-processing (i.e., indexing) time of each algorithm. Note that each algorithm sorts R and S. Although RD-index, Rel, and ours build a data structure on S only, they sort R by start point to improve the cache hit ratio. FS needs a shorter pre-processing time because it does not build a complex data structure. Although RD-index and ours build a similar data structure, ours requires a longer pre-processing time than RD-index. This is because ours prepares additional sorted arrays shown in Section III. The pre-processing time of Rel is much slower than that of the others, because it builds a hierarchical structure and requires recursive partitioning. This processing is more complex than building a grid-based structure. C. Memory Usage Table III exhibits the memory usage of each algorithm. Note that FS does not build any data structure offline, so its memory 4 https://github.com/NaoyaEhara/duration-constrained interval joins

Figure 7 shows the results of experiments varying |R|/|S|. As |R|/|S| increases, the join result size increases, thereby all algorithms need longer join time. Our algorithm outperforms all competitors and usually requires 0.5x the time of the best baseline algorithm. This result demonstrates the efficacy of our pruning rules based on Theorems 1 and 2. Although RD-index and ours share a similar data structure, the performance difference is substantial. This difference highlights the effectiveness of exploiting the grid structure for Theorems 1 and 2. Ours can filter (r, s) quickly if 0 < l(r, s) < ϵ, whereas FS has to evaluate all interval pairs ∈ R ▷◁ S. Therefore, ours is always faster than FS. Rel also has an ability that filters (r, s) if 0 < l(r, s) < ϵ. The performance difference between ours and Rel suggests that our pruning is more efficient and tighter. E. Impact of ϵ We next investigate the impact of ϵ by varying p, see Section IV-A. Figure 8 shows the result. As p, i.e., ϵ, increases, |R ▷◁ϵ S| decreases. That is, many (r, s) become unqualified, thereby pruning efficiency improves. Even when p is small or large, our algorithm still keeps outperforming the baseline algorithms. F. Ablation Study Here, we investigate the efficiency of the optimization proposed in Section III-A. We thus compared the performance of Algorithms 1 and 2. Table IV shows the comparison result. We observe that ours, i.e., Algorithm 2, consistently outperforms ours without opt, i.e., Algorithm 1. This result demonstrates that our proposed optimization functions well in practice and reduces unnecessary comparisons between intervals. G. Impact of Batch Processing Table V shows the time to form groups/batches5 . Compared with Table II, we find that grouping is not a bottleneck. 5 We empirically tuned γ to optimize the join time, and set γ was 2 × l avg , 0.12 × lavg , and 0.0004 × lavg on BTC, Books, and Renfe, respectively.

(a) BTC

(b) Books

(c) Renfe

Fig. 7. Impact of |R|/|S|: “◦” shows ours, “⋄” shows FS, “□” shows RD-index, and “△” shows Rel.

(a) BTC

(b) Books

(c) Renfe

Fig. 8. Impact of ϵ (p): “◦” shows ours, “⋄” shows FS, “□” shows RD-index, and “△” shows Rel.

TABLE IV A BLATION STUDY ( JOIN TIME [ SEC ])

Ours Ours without optimization

TABLE VI I MPACT OF BATCH PROCESSING ( JOIN TIME [ SEC ])

BTC

Books

Renfe

0.92 1.61

85.92 139.02

244.53 393.36

TABLE V G ROUPING TIME [ SEC ]

Ours (batch)

Ours Ours with batch processing

BTC

Books

Renfe

0.92 1.45

85.92 50.20

244.53 151.15

the dense case usually succeeds the batch filtering, thereby reducing the total time from the nested-loop-based join.

BTC

Books

Renfe

0.46

0.14

2.60

V. R ELATED W ORK This section reviews existing works w.r.t. interval joins and range search.

Recall that it is pre-processing, so the time to form groups is reasonable. Table VI shows the efficacy of Algorithm 3. We see that our batch processing is useful when intervals are dense (i.e., Books and Renfe), whereas it is not when intervals are sparse (i.e., BTC). If batch filtering (i.e., the main differences to Algorithm 2) fails, it becomes an additional cost. The sparse case usually has such failures, so the batch-based join is slower than the nested-loop-based join on BTC. On the other hand,

A. Interval Join The problem of interval join is defined in Definition 1. Many works addressed this problem [9]–[13], [15]–[18], [35]. We introduce some representative algorithms. OIP [12] divides the domain of a given interval set into disjoint partitions. Each interval is assigned to the minimum number of partitions that cover this interval. An interval join query is processed based on partitions of R and S. That is,

mini-joins are performed between overlapping partitions. DIP [35] improves this approach by arranging each partition so that its intervals are disjoint. This disjoint property reduces the number of interval comparisons. EBI and LEBI [13], [18] are join algorithms based on the plane-sweep method. They are designed to be cacheefficient and parallel-friendly. FS [9], [10] is the state-ofthe-art interval join algorithm. It is also based on the planesweep method and improves EBI and LEBI. FS alleviates unnecessary interval comparisons when the sweep-line stops at a start or an end point, compared with EBI and LEBI. FS includes optimizations, such as bucketing, grouping, loop unrolling, and a decomposed data layout, which also support multi-threading. Note that their performances tend to degrade when dealing with long intervals, e.g., see Figure 7(b). OMJ [11] decomposes an interval join into two range joins. Its approach is compatible with existing database management systems (e.g., PostgreSQL), because it employs B+ -tree to run range joins. However, as the experimental results in [11] confirm, it is (slightly) outperformed by FS. The above algorithms do not consider the overlap duration, so they need to employ one of the two approaches introduced in Section I-B to handle our problem. In Section IV, we empirically show that this approach is slower than our algorithm. B. Range Search A range search on interval data S retrieves a subset S ′ ⊆ S such that s ∈ S ′ satisfies l(r, s) > 0 for a given query interval r. (Similar to our join algorithm, interval join can be conducted by repeating range search of r on S for every r ∈ R.) A classic yet still state-of-the-art range search structure is the interval tree [36]. It can return S ′ in O(log n + |S ′ |) time. Timeline index [37] is implemented in SAP HANA [38]. This index is essentially a list, where the start and end points of all intervals are sorted. HINT [39], [40] is a hierarchical one-dimensional grid. Its design objective is similar to ours: HINT can identify intervals in the search result in a comparison-free manner. [41] considers the range search problem in the external memory setting. These works do not consider any duration constraint, so they are not appropriate for our problem. Period index [42] considers range-duration queries. The concept of range-duration queries is similar to our duration constraint, but it is different. A range-duration query r returns every interval s ∈ S such that l(r, s) > 0 and dmin ≤ |s| ≤ dmax , where dmin and dmax are the duration constraints. That is, this query considers not the overlap duration but the interval duration. The period index is also a hierarchical onedimensional grid. RD-index [30], [34] also considers rangeduration queries and improves the period index. We extended the RD-index to deal with the overlap duration constraint. Section IV confirms that our algorithm significantly outperforms this version of the RD-index. In [33], the authors define relevance queries: They measure the similarity between two intervals based on the Jaccard similarity, overlap ratio, and overlap duration. They proposed lower- and upper-bounding techniques for these measures to filter unnecessary similarity

computations. In Section IV, we compared our algorithm with this approach, and the result demonstrates that our algorithm is faster in our problem. To reduce the output size, [25], [26], [43] consider the independent range sampling problem on interval data, and this problem returns t random samples of the range search result. Some works [27], [28], [32], [44], [45] assume that each interval has a weight, and they consider returning k intervals overlapping a given query interval with the best weight. On the other hand, [46] considers keywords as a constraint, i.e., it considers returning intervals that overlap a given query interval and have the specified keywords. The settings of these works are totally different from ours. VI. C ONCLUSION This work addressed the problem of duration-constrained interval join for the first time. Applying existing join and search techniques to this problem is inefficient, so we proposed a new algorithm that filters unnecessary computations in a batch. To improve this algorithm, we proposed two optimization techniques. We conducted extensive experiments on real-world interval data, and the results demonstrate that our algorithm outperforms existing techniques. Remark after acceptance. Although the proceedings version claims that our problem has not been studied yet, [47] already considers it. We hence remove this claim in this version. ACKNOWLEDGMENT This research is partially supported by JSPS KAKENHI Grant Number 24K14961. R EFERENCES [1] R. Snodgrass et al., “Temporal databases,” Computer, vol. 19, no. 09, pp. 35–42, 1986. [2] M. H. Böhlen, A. Dignös, J. Gamper, and C. S. Jensen, “Temporal data management–an overview,” European Business Intelligence and Big Data Summer School, pp. 51–83, 2017. [3] R. Cheng, D. V. Kalashnikov, and S. Prabhakar, “Evaluating probabilistic queries over imprecise data,” in SIGMOD, 2003, pp. 551–562. [4] N. Dalvi and D. Suciu, “Efficient query evaluation on probabilistic databases,” The VLDB Journal, vol. 16, no. 4, pp. 523–544, 2007. [5] T. Georgiadis and N. Mamoulis, “Raster intervals: an approximation technique for polygon intersection joins,” Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. 1–18, 2023. [6] T. Georgiadis, E. Tzirita Zacharatou, and N. Mamoulis, “Raster interval object approximations for spatial intersection joins,” The VLDB Journal, vol. 34, no. 1, pp. 1–25, 2025. [7] L. Wang, Y. Zheng, X. Xie, and W.-Y. Ma, “A flexible spatio-temporal indexing scheme for large-scale gps track retrieval,” in MDM, 2008, pp. 1–8. [8] D. Gao, C. S. Jensen, R. T. Snodgrass, and M. D. Soo, “Join operations in temporal databases,” The VLDB journal, vol. 14, no. 1, pp. 2–29, 2005. [9] P. Bouros and N. Mamoulis, “A forward scan based plane sweep algorithm for parallel interval joins,” Proceedings of the VLDB Endowment, vol. 10, no. 11, pp. 1346–1357, 2017. [10] P. Bouros, N. Mamoulis, D. Tsitsigkos, and M. Terrovitis, “In-memory interval joins,” The VLDB journal, vol. 30, no. 4, pp. 667–691, 2021. [11] A. Dignös, M. H. Böhlen, J. Gamper, C. S. Jensen, and P. Moser, “Leveraging range joins for the computation of overlap joins,” The VLDB Journal, vol. 31, no. 1, pp. 75–99, 2022. [12] A. Dignös, M. H. Böhlen, and J. Gamper, “Overlap interval partition join,” in SIGMOD, 2014, pp. 1459–1470.

[13] D. Piatov, S. Helmer, and A. Dignös, “An interval join optimized for modern hardware,” in ICDE, 2016, pp. 1098–1109. [14] J. Pilourdault, V. Leroy, and S. Amer-Yahia, “Distributed evaluation of top-k temporal joins,” in SIGMOD, 2016, pp. 1027–1039. [15] H. Gunadhi and A. Segev, “Query processing algorithms for temporal intersection joins,” in ICDE, 1991, pp. 336–344. [16] P. Bouros, K. Lampropoulos, D. Tsitsigkos, N. Mamoulis, and M. Terrovitis, “Band joins for interval data,” in EDBT, 2020, pp. 443–446. [17] P. Bouros and N. Mamoulis, “Interval count semi-joins.” in EDBT, 2018, pp. 425–428. [18] D. Piatov, S. Helmer, A. Dignös, and F. Persia, “Cache-efficient sweeping-based interval joins for extended allen relation predicates,” The VLDB Journal, vol. 30, no. 3, pp. 379–402, 2021. [19] H. Zhang, X. Zeng, S. Zhang, X. Liu, M. Lu, and Z. Zheng, “Scalable online interval join on modern multicore processors in openmldb,” in ICDE, 2023, pp. 3031–3042. [20] S. Sarmashghi and V. Bafna, “A note on computing interval overlap statistics,” bioRxiv, p. 517987, 2019. [21] J. Cho, D. M. Seo, and Y. Uh, “Clinical application of overlapping confidence intervals for monitoring changes in serial clinicalchemistry test results,” Annals of Laboratory Medicine, vol. 40, no. 3, pp. 930–937, 2020. [22] T. da Cruz Asmus, G. P. Dimuro, B. Bedregal, J. A. Sanz, S. Pereira Jr, and H. Bustince, “General interval-valued overlap functions and intervalvalued overlap indices,” Information Sciences, vol. 527, pp. 27–50, 2020. [23] R. Shirai, R. Imai, S. P. Liew, D. Amagata, T. Takahashi, and T. Hara, “Estimating visited stores through positive-unlabeled learning,” in DASFAA, 2024, pp. 377–389. [24] D. Amagata, R. Shirai, and R. Imai, “Target and non-target category classification from gps and check-in data,” in SSTD, 2025, pp. 181–191. [25] D. Amagata, “Independent range sampling on interval data,” in ICDE, 2024, pp. 449–461. [26] ——, “Independent range sampling on interval data (longer version),” arXiv preprint arXiv:2405.08315, 2024. [27] D. Amagata, J. Yamada, Y. Ji, and T. Hara, “Efficient algorithms for top-k stabbing queries on weighted interval data,” in DEXA, 2024, pp. 146–152. [28] D. Amagata and J. Lee, “Top-k range search on weighted interval data,” in SSTD, 2025, pp. 218–228. [29] P. Bouros, A. Titkov, G. Christodoulou, C. Rauch, and N. Mamoulis, “Hint on steroids: Batch query processing for interval data.” in EDBT, 2024, pp. 440–446. [30] M. Ceccarello, A. Dignös, J. Gamper, and C. Khnaisser, “Indexing temporal relations for range-duration queries,” Distributed and Parallel Databases, vol. 43, no. 7, 2025. [31] R. J. Fowler, M. S. Paterson, and S. L. Tanimoto, “Optimal packing and covering in the plane are np-complete,” Information Processing Letters, vol. 12, no. 3, pp. 133–137, 1981. [32] D. Amagata, J. Yamada, Y. Ji, and T. Hara, “Efficient algorithms for top-k stabbing queries on weighted interval data (full version),” arXiv preprint arXiv:2405.05601, 2024. [33] P. Bouros and N. Mamoulis, “Relevance queries for interval data,” Proceedings of the ACM on Management of Data, vol. 3, no. 3, pp. 1–26, 2025. [34] M. Ceccarello, A. Dignös, J. Gamper, and C. Khnaisser, “Indexing temporal relations for range-duration queries,” in SSDBM, 2023, pp. 3:1–3:12. [35] F. Cafagna and M. H. Böhlen, “Disjoint interval partitioning,” The VLDB Journal, vol. 26, no. 3, pp. 447–466, 2017. [36] H. Edelsbrunner, Dynamic Rectangle Intersection Searching, 1980. [37] 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, 2013, pp. 1173–1184. [38] F. Färber, S. K. Cha, J. Primsch, C. Bornhövd, S. Sigg, and W. Lehner, “Sap hana database: Data management for modern business applications,” SIGMOD Record, vol. 40, no. 4, pp. 45–51, 2012. [39] G. Christodoulou, P. Bouros, and N. Mamoulis, “Hint: a hierarchical interval index for allen relationships,” The VLDB Journal, pp. 1–28, 2023. [40] ——, “Hint: A hierarchical index for intervals in main memory,” in SIGMOD, 2022, pp. 1257–1270. [41] K. Wang, M. H. Moti, and D. Papadias, “Tide: Indexing time intervals by duration and endpoint,” in SSTD, 2025, pp. 207–217.

[42] 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, 2019, pp. 100–109. [43] D. Amagata, P. Simatis, P. Bouros, and N. Mamoulis, “Firas: A framework for interval range search and sampling,” Proceedings of the ACM on Management of Data, vol. 4, no. 3, pp. 1–24, 2026. [44] J. Xu and H. Lu, “Efficiently answer top-k queries on typed intervals,” Information Systems, vol. 71, pp. 164–181, 2017. [45] J. Lee and D. Amagata, “Efficient algorithms for top-k range search on weighted interval data,” Geoinformatica, 2026. [46] C. Rauch and P. Bouros, “Fast indexing for temporal information retrieval,” Proceedings of the ACM on Management of Data, vol. 3, no. 4, pp. 1–28, 2025. [47] X. Hu, S. Sintos, J. Gao, P. K. Agarwal, and J. Yang, “Computing complex temporal join queries efficiently,” in SIGMOD, 2022, pp. 2076– 2090.

Related documents

• Passage, Persistence and Precision#752329
• Dynamic Interval Scheduling with Random Start and End Times#1116206
• Relations, ch.1#776137
• Interest in Mixed Integer Programming (MPSX on NIC 360/91 at CCN)#212039
• Interest in Mixed Integer Programming (MPSX on NIC 360/91 at CCN)#211308