Duration-constrained Interval Joins

Daichi Amagata; Naoya Ehara

REVIEW 3 major objections 4 minor 47 references

Duration-constrained Interval Joins

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A grid index and two thresholds compute duration-constrained interval joins without checking every overlapping pair.

desk verdict The optimized algorithm is unsound — a false-positive bug invalidates the main experimental claims; the unoptimized Algorithm 1 is fine, but the paper needs major revision. read the letter →

arxiv 2608.06856 v1 pith:YLRYG4DR submitted 2026-08-07 cs.DB

Naoya Ehara , Daichi Amagata This is my paper · ORCID

classification cs.DB

keywords duration-constrainedintervaljoinoverlapdurationgridindextemporaldatabasesdatapruningbatchprocessing

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces an algorithm for the duration-constrained interval join problem: given two collections of intervals and a threshold $\epsilon > 0$, return every pair whose overlap duration is at least $\epsilon$. The authors argue that the natural approach of running an ordinary interval join and then filtering by duration is wasteful, because it materializes slightly-overlapping noise pairs and pays a duration computation for many pairs that will be discarded. Their algorithm instead stores one collection in a grid over interval endpoints and uses threshold rules to classify cells of the other collection as fully qualifying, fully excluded, or undecided before any per-pair overlap computation. On three real-world interval datasets, the experiments report that the proposed algorithm runs faster than the applicable baselines. The intended contribution is an exact join whose per-pair work is limited to cells the thresholds cannot settle.

What carries the argument

The machinery is the two-dimensional grid $G$ over the $(start,end)$ plane, where each interval $s \in S$ becomes a point and each cell groups intervals with similar endpoints. Cells keep their intervals sorted by start and by end, and the grid maintains, per column, the maximum start point; per cell, the minimum and maximum end points and the minimum start point. For a probe interval $r$, $\theta_{\mathrm{start}}(r)$ and $\theta_{\mathrm{end}}(r)$ determine which columns and cells can contain qualifying pairs: cells whose maximum end is below $\theta_{\mathrm{end}}(r)$ are excluded in batch, cells whose minimum end reaches $\theta_{\mathrm{end}}(r)$ and whose starts are early enough are included in batch, and only cells in the remaining band require explicit duration checks. The optimization defines $\theta_{\min}(c_{i,j})=A^{\mathrm{end,min}}_i[j]-\epsilon$ and $\theta_{\max}(c_{i,j})=A^{\mathrm{end,max}}_i[j]-\epsilon$ to narrow that band further, and the batch layer reuses cell decisions for groups of similar intervals from $R$.

What would settle it

Run Algorithm 2 on $R=\{r=[0,10]\}$, $S=\{[-1,3],[6,10]\}$ with $\epsilon=4$, placing both S-intervals in one grid cell. The cell has $A^{\mathrm{end,min}}_i[j]=3$ and $A^{\mathrm{end,max}}_i[j]=10$, while $\theta_{\mathrm{end}}(r)=4$ and $\theta_{\mathrm{start}}(r)=6$; the algorithm computes $\theta_{\min}=3-4=-1$, $\lambda=\min(\max(0,-1),6)=0$, and adds the interval starting at $-1$ to the result, although its overlap with $r$ is $\min(10,3)-\max(0,-1)=3<4$. Comparing the algorithm's output to a brute-force computation of $l(r,s)$ on such cells settles whether the shortcut is correct.

Watch

Extended reading notes

Core claim

The paper's central claim is that the overlap-duration constraint can be pushed inside the interval join rather than applied afterward. For a probe interval $r$, the thresholds $\theta_{\mathrm{start}}(r)=r.end-\epsilon$ and $\theta_{\mathrm{end}}(r)=r.start+\epsilon$ define boundaries; Theorem 1 gives conditions under which a pair $(r,s)$ is necessarily in the result or necessarily out of it without computing $l(r,s)$. A two-dimensional grid $G$ stores each $s \in S$ as the point $(s.start,s.end)$, with cells holding intervals sorted by start and by end and with per-column and per-cell extremes of start and end. The optimized algorithm adds per-cell values $\theta_{\min}(c_{i,j})$ and $\theta_{\max}(c_{i,j})$ to shrink the undecided region, and a batch variant groups similar intervals of $R$ so that a settled cell is reused across the group. The paper claims this yields exactly the pairs satisfying $l(r,s) \ge \epsilon$ while avoiding unnecessary comparisons for both included and excluded pairs.

Load-bearing premise

The optimized algorithm assumes that whenever it adds entire sets of intervals to the result without computing overlap durations, the cell's earliest end point is already late enough that every interval in that cell satisfies the $\epsilon$ threshold; if a cell's earliest end point falls below that threshold, short-overlap pairs can be reported by the batch shortcut.

Editorial extensions

If this is right

On the BTC, Books, and Renfe datasets, the proposed algorithm reports lower join times than the extended FS, RD-index, and Rel baselines across the evaluated settings of $|R|/|S|$ and $\epsilon$.
Larger $\epsilon$ shrinks both the join result and the set of still-undecided cells, so the pruning advantage grows as the duration constraint tightens.
Batch processing roughly halves join time on dense datasets but can add overhead on sparse ones, so the choice of Algorithm 3 should depend on data density.
The grid on $S$ is built in $O(m \log m)$ time and uses $O(m)$ space, so the preprocessing cost scales with the indexed collection rather than with the join output size.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A targeted comparison of Algorithm 2 against brute-force $l(r,s)$ on cells with $A^{\mathrm{end,min}}_i[j] < \theta_{\mathrm{end}}(r)$ would reveal whether the Theorem 2 shortcut needs an explicit guard before batch-adding intervals.
The thresholding pattern should extend to other monotone interval scores, such as overlap ratio or Jaccard similarity, by replacing the additive $\epsilon$ with the corresponding monotone bound.
The group heuristic's $\gamma$ could be chosen adaptively from the local density of $R$ and $\epsilon$, which might avoid the sparse-data slowdown observed on BTC.
Because the grid is built once on $S$ and reused for every $r \in R$, the same structure could serve duration-constrained self-joins and incremental insertions into $R$ without a full rebuild.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things. First, the core problem is not new: the authors admit in a remark after acceptance that [47] already studied it. Second, and more importantly, Algorithm 2 — the method used in the experiments — is incorrect. It applies Theorem 2 in a branch where the precondition theta_end(r) <= A_end,min_i[j] is not guaranteed, so it can add non-join pairs. Concretely, take r=[50,150], eps=10, and a grid cell containing [0,5] and [55,65] with A_end,min=5 and A_end,max=65. The algorithm adds ([50,150],[0,5]) because s.start=0 <= lambda, but the overlap duration is -45 < 10. This is not a contrived edge case: the grid construction imposes no bound on the spread of end points within a cell, and the FIND-INDEX on A_end,max only ensures theta_end <= A_end,max, not <= A_end,min.

What the paper does well: Theorem 1 and its corollaries are derived correctly and the unoptimized Algorithm 1 appears exact. The experiments are extensive, on three real datasets, with multiple baselines and an ablation. The after-acceptance remark retracting the novelty claim is honest, though the conclusion still says "for the first time," which contradicts it.

The soft spots are proportionate: the bug in Algorithm 2 is load-bearing. Since the experiments evaluate Algorithm 2 ("Ours"), the speedups in Figures 7–8 and Table IV are for an algorithm that returns incorrect results. Algorithm 3 inherits the bug whenever it calls lines 11–22. The fix is not hard: either check theta_end <= A_end,min before using the batch addition, or compute l(r,s) for every s in that cell. If fixed, the paper would be a solid incremental contribution to interval join processing.

Who this is for: researchers in temporal, spatial, uncertain, and trajectory databases who care about pruning overlap-duration constraints. A serious referee should engage with it, because the base idea is sound and the bug is fixable, but the current version should not be accepted as is.

Referee Report

3 major / 4 minor

Summary. The paper defines the duration-constrained interval join problem (Definition 2), proposes a grid-based algorithm with threshold pruning (Algorithm 1), and adds two optimizations: a cell-level comparison-avoidance scheme (Algorithm 2) and a batch-grouping scheme (Algorithm 3). The authors claim that the proposed algorithm returns exactly the pairs with overlap duration at least ε and outperforms existing interval-join and range-search baselines on three real-world datasets. An appended remark acknowledges prior work [47], but the conclusion still claims the problem is addressed 'for the first time.'

Significance. The problem is relevant and the threshold-based pruning idea is natural; Algorithm 1 and its Corollaries 1-4 appear internally sound, and the use of three real datasets is a strength. However, the central exactness claim rests on Algorithm 2, and that algorithm applies Theorem 2 without checking its precondition. The consequence is a concrete false-positive result: Algorithm 2 can return pairs with overlap duration below ε. Since the experiments identify 'Ours' as Algorithm 2 (Section IV-A), the reported timings are not timings of an exact algorithm. The contribution is therefore not established as stated, although the error is localized and may be repairable by adding the missing precondition check and re-running the evaluation.

major comments (3)

[Section III-A, Algorithm 2 lines 10-24] The load-bearing correctness bug is that Algorithm 2 applies Theorem 2 to cells for which the theorem's hypothesis θ_end(r) ≤ A_end,min_i[j] is not verified. The FIND-INDEX on A_end,max_i at line 3 only guarantees θ_end(r) ≤ A_end,max_i[j]; the cell's minimum end point can be smaller. Concretely, let r=[0,10], ε=8, so θ_start(r)=2 and θ_end(r)=8. Let the grid have one start column with A_max_col[0]=2, and let cell c_0,0 contain intervals [0,2] and [1,9], so A_start,min=0, A_end,min=2, A_end,max=9. Then idx=idx'=0, and Algorithm 2 reaches line 24 and executes lines 11-22. It computes θ_min(c_0,0)=2−8=−6 and λ=min(max{0,−6},2)=0, then adds [0,2] because 0≤0. But l(r,[0,2]) = min(10,2)−max(0,0) = 2 < 8, so a non-qualifying pair is emitted. The root cause is that Theorem 2's proof uses min{r.end, A_end,min}=A_end,min, which requires the stated precondition; when A_end,min < θ_end(r), the batch-add loop at lines 12-16 is unsound. The fix is to guard lines 11-22 by the explicit test θ_end(r) ≤ A_end,min_i[j] and fall back to computing l(r,s) otherwise.
[Section III-B, Algorithm 3 line 28] Algorithm 3 inherits the same correctness flaw. At line 28, the batch path executes lines 11-22 of Algorithm 2 without first checking θ_end(r) ≤ A_end,min_i[j], so the counterexample from Major Comment 1 can be embedded in a group (e.g., G(r)={r}) and Algorithm 3 will emit the same false positive. The batch-addition paths at lines 12-15 and 25-26 also rely on Corollary 5, whose condition θ_end(r_b) ≤ A_end,min_i[j] must be verified cell by cell; the current pseudocode does not ensure this before adding intervals without computing l(r,s). Any revision must repair both algorithms and re-examine the batch rules.
[Section IV, Figures 7-8 and Tables IV, VI] The experimental evaluation does not measure a correct algorithm. Section IV-A states that 'Ours' is Algorithm 2, and Table IV and Figures 7-8 report its join time; Table VI reports Algorithm 3. Because Algorithm 2 (and hence Algorithm 3) can return false positives, all performance comparisons against FS, RD-index, and Rel are invalid as evidence for the paper's exactness and efficiency claims. The revised version should compare a corrected algorithm and should include a brute-force correctness check (e.g., verifying that the output equals the exact result on small samples) to support the exactness claim.

minor comments (4)

[Section VI and appended Remark] The appended 'Remark after acceptance' states that the 'first time' claim is removed because [47] already considers the problem, yet Section VI still says 'This work addressed the problem of duration-constrained interval join for the first time.' This contradiction must be resolved before publication.
[Section III, Data structure] The definition of A_end,max_i is garbled: the text says 'A_end,max_i is an array, where A_end,min_i[j] maintains the maximum end point,' which should read A_end,max_i[j].
[Algorithm 2, line 9 and Algorithm 1, line 30] The notation S^st is undefined and should be S^start or S_start_i,j, and the typo 'iffl(r,s))' in Algorithm 1 line 30 should be corrected.
[Section IV-A] The GitHub repository URL contains a space ('duration-constrained interval joins') and is not a valid link; also, Table IV's 'Ours without optimization' should be explicitly identified as Algorithm 1 for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: thresholds and pruning rules are derived algebraically from the definition of overlap duration, and the empirical evaluation is against external baselines and datasets.

full rationale

The paper's derivation chain is self-contained. The thresholds theta_start(r) = r.end - epsilon and theta_end(r) = r.start + epsilon are direct algebraic rearrangements of the overlap-duration definition l(r,s) = min(r.end,s.end) - max(r.start,s.start), and Theorems 1 and 2 are proven from that definition without importing external results. Corollaries 1-6 and Algorithms 1-3 apply these conditions to the grid's stored aggregates; the grid is taken from [30] only as an implementation vehicle, and the corollaries are proven from the aggregates' definitions. The empirical claims compare against external datasets and baseline implementations, not against values fitted by the paper, and the hyperparameter gamma is tuned only for runtime (Section IV-G footnote), not for output correctness. The 'Remark after acceptance' retracts the priority claim 'for the first time' and is a novelty correction, not a circular justification. A potential correctness risk exists in Algorithm 2 lines 10-22: Theorem 2's hypothesis theta_end(r) <= A_end,min_i[j] is not checked before applying its conclusions, so false positives are possible; this is a bug concern, not a circularity, and does not affect the circularity score. Overall, no circular step was found.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

All free parameters affect runtime rather than the mathematical definition of the join. The correctness of the unoptimized Algorithm 1 rests only on interval arithmetic and grid summaries. The optimized Algorithm 2 additionally relies on an unstated precision assumption that Theorem 2's precondition holds for every batch-added cell; this assumption is false in general and is the source of the reported counterexample. No new physical or data entities are introduced.

free parameters (2)

batch tolerance gamma = 2 x l_avg (BTC), 0.12 x l_avg (Books), 0.0004 x l_avg (Renfe)
Batch tolerance in Definition 5; empirically tuned to optimize join time in Section IV-G. It does not affect correctness but is needed to reproduce the reported speedups.
grid resolution / cell width = not reported; inherited from RD-index grid [30]
The grid cell boundaries determine the min/max summaries and the behavior of the pruning rules; without reporting cell width, the fast path of the algorithm is not fully specified.

assumptions (5)

domain assumption R and S are memory-resident and do not receive frequent updates (Section II).
The grid is static over S; the paper explicitly scopes the work to in-memory static interval collections and does not claim external-memory or update-heavy performance.
domain assumption The grid cell summaries (A_max_col, A_end,min, A_end,max, A_start,min) correctly reflect the intervals in each cell and are maintained sorted (Section III, Data structure).
All pruning corollaries are stated relative to these per-cell summaries; if the summaries are not exact, the pruning is not exact. This is an implementation invariant rather than an external mathematical fact.
ad hoc to paper In Algorithm 2, every cell processed by the Theorem 2 bulk-add rule satisfies theta_end(r) <= A_end,min_i[j].
This is the precondition of Theorem 2, but it is not checked and is not implied by the grid structure. A cell with A_end,min=2 and A_end,max=9 violates it, causing false positives. This is the unsound assumption behind the optimized algorithm.
standard math Algebraic properties of min and max used in Theorems 1 and 2 hold over real-valued interval endpoints (Section III).
No exotic background; interval arithmetic is elementary and the inequalities in the proofs are standard.
ad hoc to paper The grouping heuristic in Section III-B is allowed to fail to find optimal groups; only Definition 5 and Corollaries 5 and 6 are needed for correctness.
The paper proves optimal grouping NP-hard and uses a greedy heuristic. Correctness of the join does not rely on optimal grouping, but the claimed speedup does.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Duration-constrained Interval Joins." pith.science (2026). https://pith.science/paper/YLRYG4DR

@misc{pith2026260806856,
  author       = {Pith},
  title        = {Pith review of: Duration-constrained Interval Joins},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YLRYG4DR}},
  note         = {Machine review of arXiv:2608.06856}
}

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 $\epsilon$, this problem returns all interval pairs $(r,s)$ such that $r \in R$, $s \in S$, and the overlap duration between $r$ and $s$ is at least $\epsilon$. A straightforward approach for this problem is to run a state-of-the-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.

Figures

Figures reproduced from arXiv: 2608.06856 by the authors.

**Figure 1.** Example of an interval join. The result of join between [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** Example of Theorem 1 𝑒𝑛𝑑 𝑠𝑡𝑎𝑟𝑡 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Figures from the paper (5 more)

**Figure 3.** Figure 3: Two-dimensional representation of intervals [PITH_FULL_IMAGE:figures/full_fig_p003_3.png]

**Figure 4.** Figure 4: Illustration of Example 2 idx and idx′ , this algorithm first accesses the 0-th column. It runs a binary search on A end,max 0 , and accesses cells in 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 s…

**Figure 6.** Figure 6: Example of making a group of r1 ∈ R [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

**Figure 7.** Figure 7: Impact of |R|/|S|: “◦” shows ours, “⋄” shows FS, “□” shows RD-index, and “△” shows Rel. (a) BTC (b) Books (c) Renfe [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]

**Figure 8.** Figure 8: Impact of ϵ (p): “◦” shows ours, “⋄” shows FS, “□” shows RD-index, and “△” shows Rel. TABLE IV ABLATION STUDY (JOIN TIME [SEC]) BTC Books Renfe Ours 0.92 85.92 244.53 Ours without optimization 1.61 139.02 393.36 TABLE V GROUPING TIME [SEC] BTC Books Renfe Ours (batch) …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

[47]

Computing complex temporal join queries efficiently,

X. Hu, S. Sintos, J. Gao, P. K. Agarwal, and J. Yang, “Computing complex temporal join queries efficiently,” inSIGMOD, 2022, pp. 2076– 2090

work page 2022
[1]

Temporal databases,

R. Snodgrasset al., “Temporal databases,”Computer, vol. 19, no. 09, pp. 35–42, 1986

work page 1986
[2]

Temporal data management–an overview,

M. H. B ¨ohlen, A. Dign ¨os, J. Gamper, and C. S. Jensen, “Temporal data management–an overview,”European Business Intelligence and Big Data Summer School, pp. 51–83, 2017

work page 2017
[3]

Evaluating probabilistic queries over imprecise data,

R. Cheng, D. V . Kalashnikov, and S. Prabhakar, “Evaluating probabilistic queries over imprecise data,” inSIGMOD, 2003, pp. 551–562

work page 2003
[4]

Efficient query evaluation on probabilistic databases,

N. Dalvi and D. Suciu, “Efficient query evaluation on probabilistic databases,”The VLDB Journal, vol. 16, no. 4, pp. 523–544, 2007

work page 2007
[5]

Raster intervals: an approximation technique for polygon intersection joins,

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

work page 2023
[6]

Raster interval object approximations for spatial intersection joins,

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

work page 2025
[7]

A flexible spatio-temporal indexing scheme for large-scale gps track retrieval,

L. Wang, Y . Zheng, X. Xie, and W.-Y . Ma, “A flexible spatio-temporal indexing scheme for large-scale gps track retrieval,” inMDM, 2008, pp. 1–8

work page 2008

Show all 47 references

[8]

Join operations in temporal databases,

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

2005
[9]

A forward scan based plane sweep algo- rithm for parallel interval joins,

P. Bouros and N. Mamoulis, “A forward scan based plane sweep algo- rithm for parallel interval joins,”Proceedings of the VLDB Endowment, vol. 10, no. 11, pp. 1346–1357, 2017

2017
[10]

In-memory interval joins,

P. Bouros, N. Mamoulis, D. Tsitsigkos, and M. Terrovitis, “In-memory interval joins,”The VLDB journal, vol. 30, no. 4, pp. 667–691, 2021

2021
[11]

Leveraging range joins for the computation of overlap joins,

A. Dign ¨os, M. H. B ¨ohlen, 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

2022
[12]

Overlap interval partition join,

A. Dign ¨os, M. H. B ¨ohlen, and J. Gamper, “Overlap interval partition join,” inSIGMOD, 2014, pp. 1459–1470

2014
[13]

An interval join optimized for modern hardware,

D. Piatov, S. Helmer, and A. Dign ¨os, “An interval join optimized for modern hardware,” inICDE, 2016, pp. 1098–1109

2016
[14]

Distributed evaluation of top-k temporal joins,

J. Pilourdault, V . Leroy, and S. Amer-Yahia, “Distributed evaluation of top-k temporal joins,” inSIGMOD, 2016, pp. 1027–1039

2016
[15]

Query processing algorithms for temporal intersection joins,

H. Gunadhi and A. Segev, “Query processing algorithms for temporal intersection joins,” inICDE, 1991, pp. 336–344

1991
[16]

Band joins for interval data,

P. Bouros, K. Lampropoulos, D. Tsitsigkos, N. Mamoulis, and M. Ter- rovitis, “Band joins for interval data,” inEDBT, 2020, pp. 443–446

2020
[17]

Interval count semi-joins

P. Bouros and N. Mamoulis, “Interval count semi-joins.” inEDBT, 2018, pp. 425–428

2018
[18]

Cache-efficient sweeping-based interval joins for extended allen relation predicates,

D. Piatov, S. Helmer, A. Dign ¨os, 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

2021
[19]

Scalable online interval join on modern multicore processors in openmldb,

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

2023
[20]

A note on computing interval overlap statistics,

S. Sarmashghi and V . Bafna, “A note on computing interval overlap statistics,”bioRxiv, p. 517987, 2019

2019
[21]

Clinical application of overlapping confidence intervals for monitoring changes in serial clinicalchemistry test results,

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

2020
[22]

General interval-valued overlap functions and interval- valued overlap indices,

T. da Cruz Asmus, G. P. Dimuro, B. Bedregal, J. A. Sanz, S. Pereira Jr, and H. Bustince, “General interval-valued overlap functions and interval- valued overlap indices,”Information Sciences, vol. 527, pp. 27–50, 2020

2020
[23]

Estimating visited stores through positive-unlabeled learning,

R. Shirai, R. Imai, S. P. Liew, D. Amagata, T. Takahashi, and T. Hara, “Estimating visited stores through positive-unlabeled learning,” inDAS- FAA, 2024, pp. 377–389

2024
[24]

Target and non-target category classification from gps and check-in data,

D. Amagata, R. Shirai, and R. Imai, “Target and non-target category classification from gps and check-in data,” inSSTD, 2025, pp. 181–191

2025
[25]

Independent range sampling on interval data,

D. Amagata, “Independent range sampling on interval data,” inICDE, 2024, pp. 449–461

2024
[26]

Independent range sampling on interval data (longer version),

——, “Independent range sampling on interval data (longer version),” arXiv preprint arXiv:2405.08315, 2024

2024 arXiv
[27]

Efficient algorithms for top-k stabbing queries on weighted interval data,

D. Amagata, J. Yamada, Y . Ji, and T. Hara, “Efficient algorithms for top-k stabbing queries on weighted interval data,” inDEXA, 2024, pp. 146–152

2024
[28]

Top-k range search on weighted interval data,

D. Amagata and J. Lee, “Top-k range search on weighted interval data,” inSSTD, 2025, pp. 218–228

2025
[29]

Hint on steroids: Batch query processing for interval data

P. Bouros, A. Titkov, G. Christodoulou, C. Rauch, and N. Mamoulis, “Hint on steroids: Batch query processing for interval data.” inEDBT, 2024, pp. 440–446

2024
[30]

Indexing temporal relations for range-duration queries,

M. Ceccarello, A. Dign ¨os, J. Gamper, and C. Khnaisser, “Indexing temporal relations for range-duration queries,”Distributed and Parallel Databases, vol. 43, no. 7, 2025

2025
[31]

Optimal packing and covering in the plane are np-complete,

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

1981
[32]

Efficient algorithms for top-k stabbing queries on weighted interval data (full version),

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

2024 arXiv
[33]

Relevance queries for interval data,

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

2025
[34]

Indexing temporal relations for range-duration queries,

M. Ceccarello, A. Dign ¨os, J. Gamper, and C. Khnaisser, “Indexing temporal relations for range-duration queries,” inSSDBM, 2023, pp. 3:1–3:12

2023
[35]

Disjoint interval partitioning,

F. Cafagna and M. H. B ¨ohlen, “Disjoint interval partitioning,”The VLDB Journal, vol. 26, no. 3, pp. 447–466, 2017

2017
[36]

Edelsbrunner,Dynamic Rectangle Intersection Searching, 1980

H. Edelsbrunner,Dynamic Rectangle Intersection Searching, 1980

1980
[37]

Timeline index: a unified data structure for processing queries on temporal data in sap hana,

M. Kaufmann, A. A. Manjili, P. Vagenas, P. M. Fischer, D. Kossmann, F. F ¨arber, and N. May, “Timeline index: a unified data structure for processing queries on temporal data in sap hana,” inSIGMOD, 2013, pp. 1173–1184

2013
[38]

Sap hana database: Data management for modern business applica- tions,

F. F ¨arber, S. K. Cha, J. Primsch, C. Bornh ¨ovd, S. Sigg, and W. Lehner, “Sap hana database: Data management for modern business applica- tions,”SIGMOD Record, vol. 40, no. 4, pp. 45–51, 2012

2012
[39]

Hint: a hierarchical interval index for allen relationships,

G. Christodoulou, P. Bouros, and N. Mamoulis, “Hint: a hierarchical interval index for allen relationships,”The VLDB Journal, pp. 1–28, 2023

2023
[40]

Hint: A hierarchical index for intervals in main memory,

——, “Hint: A hierarchical index for intervals in main memory,” in SIGMOD, 2022, pp. 1257–1270

2022
[41]

Tide: Indexing time intervals by duration and endpoint,

K. Wang, M. H. Moti, and D. Papadias, “Tide: Indexing time intervals by duration and endpoint,” inSSTD, 2025, pp. 207–217

2025
[42]

Period index: A learned 2d hash index for range and duration queries,

A. Behrend, A. Dign ¨os, J. Gamper, P. Schmiegelt, H. V oigt, M. Rottmann, and K. Kahl, “Period index: A learned 2d hash index for range and duration queries,” inSSTD, 2019, pp. 100–109

2019
[43]

Firas: A frame- work for interval range search and sampling,

D. Amagata, P. Simatis, P. Bouros, and N. Mamoulis, “Firas: A frame- work for interval range search and sampling,”Proceedings of the ACM on Management of Data, vol. 4, no. 3, pp. 1–24, 2026

2026
[44]

Efficiently answer top-k queries on typed intervals,

J. Xu and H. Lu, “Efficiently answer top-k queries on typed intervals,” Information Systems, vol. 71, pp. 164–181, 2017

2017
[45]

Efficient algorithms for top-k range search on weighted interval data,

J. Lee and D. Amagata, “Efficient algorithms for top-k range search on weighted interval data,”Geoinformatica, 2026

2026
[46]

Fast indexing for temporal information retrieval,

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

2025

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [47]

Computing complex temporal join queries efficiently,

X. Hu, S. Sintos, J. Gao, P. K. Agarwal, and J. Yang, “Computing complex temporal join queries efficiently,” inSIGMOD, 2022, pp. 2076– 2090

work page 2022

[2] [1]

Temporal databases,

R. Snodgrasset al., “Temporal databases,”Computer, vol. 19, no. 09, pp. 35–42, 1986

work page 1986

[3] [2]

Temporal data management–an overview,

M. H. B ¨ohlen, A. Dign ¨os, J. Gamper, and C. S. Jensen, “Temporal data management–an overview,”European Business Intelligence and Big Data Summer School, pp. 51–83, 2017

work page 2017

[4] [3]

Evaluating probabilistic queries over imprecise data,

R. Cheng, D. V . Kalashnikov, and S. Prabhakar, “Evaluating probabilistic queries over imprecise data,” inSIGMOD, 2003, pp. 551–562

work page 2003

[5] [4]

Efficient query evaluation on probabilistic databases,

N. Dalvi and D. Suciu, “Efficient query evaluation on probabilistic databases,”The VLDB Journal, vol. 16, no. 4, pp. 523–544, 2007

work page 2007

[6] [5]

Raster intervals: an approximation technique for polygon intersection joins,

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

work page 2023

[7] [6]

Raster interval object approximations for spatial intersection joins,

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

work page 2025

[8] [7]

A flexible spatio-temporal indexing scheme for large-scale gps track retrieval,

L. Wang, Y . Zheng, X. Xie, and W.-Y . Ma, “A flexible spatio-temporal indexing scheme for large-scale gps track retrieval,” inMDM, 2008, pp. 1–8

work page 2008