{"id":"0bc77fa9-317f-4eb6-b48f-94a627212abd","arxiv_id":"2608.06856","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A grid-indexed duration-constrained interval join is proposed, but the optimized variant can return pairs whose overlap is shorter than the required duration.","lead":"This paper proposes a grid-indexed algorithm for interval joins that keeps only pairs overlapping for at least a user-set duration. The general idea is plausible, but the optimized version can emit pairs with too-short overlaps, and the paper's own remark concedes the problem was already studied.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's Theorem 2 shortcut adds intervals without verifying its precondition: at lines 12–15, a cell with A_end,min < theta_end(r) <= A_end,max can yield false positives, so the claimed exactness fails.","rationale":"The reader's weakest assumption is exactly the load-bearing failure: Algorithm 2 invokes the batch-addition shortcut of Theorem 2 without establishing theta_end(r) <= A_end,min_i[j]. My independent counterexample confirms the failure is real and not merely a boundary case: for r=[50,150], eps=10, a cell containing s=[0,5] with A_end,min=5 and A_end,max=65 is reached because theta_end=60 <= A_end,max, and the code adds s because s.start=0 <= lambda=50, although l(r,s)<0. Thus the algorithm can emit pairs that do not even overlap, let alone satisfy the duration constraint. This directly contradicts Definition 2 and the abstract's claim that the algorithm returns 'only' the qualified pairs. The error is in the optimized Algorithm 2, which is the version evaluated as 'Ours' throughout Section IV; Algorithms 1 and 3 do not rescue the central claim, and Algorithm 3 inherits the flaw when it runs Algorithm 2 lines 11–22. I considered whether line 8's r.end < A_end,min check or line 5's skip prevents the counterexample; they do not, because in the example r.end=150 >= A_end,min=5 and A_start,min=0 <= theta_start=140. The fix would require filtering by s.end or checking the missing precondition before line 14, but as written the exactness claim is unsound. Secondary issues about the 'first time' claim and the omitted [47] baseline are real but subordinate; the correctness defect alone justifies the reader's REJECT verdict.","tokens_in":15132,"tokens_out":9107,"duration_ms":87372,"concrete_test":"Implement Algorithm 2 exactly (lines 1–25) in C++ or Python, using a grid with one start column covering starts 0..99, one start column covering starts 100..199, and one end row covering ends 0..99 (so [0,5] and [55,65] fall in the same cell, c_0,0). Set R={[50,150]}, S={[0,5],[55,65],[145,160]}, eps=10. Run the algorithm and print its output. The exact duration-constrained join is {([50,150],[55,65])}; if the run also emits ([50,150],[0,5]), Algorithm 2 is unsound. Any grid binning that places [0,5] and [55,65] in the same start column and keeps [145,160] in a later start column reproduces the failure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The exactness claim for Algorithm 2 depends on Theorem 2 (Section III-A), whose stated hypothesis is theta_end(r) <= A_end,min_i[j]. Algorithm 2 never tests this condition before batch-adding intervals at lines 12–15. FIND-INDEX on A_end,max only ensures theta_end(r) <= A_end,max_i[j]; it permits A_end,min_i[j] < theta_end(r). In that range, line 14's test s.start <= lambda is not sufficient. Concretely, take r=[50,150], eps=10, so theta_start=140 and theta_end=60. Put S={[0,5],[55,65],[145,160]} in a grid whose start columns have max starts 55 and 145, with the cell c_0,0 containing [0,5] and [55,65]. Then idx=0 and idx'=1. For c_0,0, A_end,min=5, A_end,max=65, and A_start,min=0. The code computes theta_min=5-10=-5, lambda=min(max(50,-5),140)=50, and adds [0,5] because 0<=50. But l(r,[0,5])=-45 < 10, so a non-join pair is emitted. The condition 's.start <= r.start' in Theorem 2(i) only guarantees l>=eps when the precondition theta_end<=A_end,min holds; here it does not. Algorithm 3 inherits this bug whenever it calls Algorithm 2 lines 11–22. Since the experiments evaluate Algorithm 2 ('Ours'), the central correctness and efficiency claims are unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.'","tokens_in":15546,"tokens_out":20423,"duration_ms":195752,"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":[{"comment":"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":"Section III-A, Algorithm 2 lines 10-24"},{"comment":"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":"Section III-B, Algorithm 3 line 28"},{"comment":"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.","section":"Section IV, Figures 7-8 and Tables IV, VI"}],"minor_comments":[{"comment":"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":"Section VI and appended Remark"},{"comment":"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].","section":"Section III, Data structure"},{"comment":"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":"Algorithm 2, line 9 and Algorithm 1, line 30"},{"comment":"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.","section":"Section IV-A"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern lands: Algorithm 2's false-positive counterexample is valid and directly violates Definition 2. I recommend major revision rather than rejection because the error is localized: adding the missing precondition check before applying Theorem 2 would restore exactness, and the corrected algorithm can be re-evaluated. However, if the guarded algorithm no longer retains a performance advantage, the paper's central efficiency claim would be unsupported. The internal contradiction about the 'first time' claim should also be fixed in the next version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":16003,"tokens_out":5623,"would_cite":false,"duration_ms":50328,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A grid index and two thresholds compute duration-constrained interval joins without checking every overlapping pair.","keywords":["duration-constrained interval join","interval join","overlap duration","grid index","temporal databases","interval data","pruning","batch processing"],"falsifier":"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.","tokens_in":14919,"feed_emoji":"🕒","tokens_out":17765,"duration_ms":158190,"temperature":0.7,"pith_summary":"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.","feed_headline":"Interval joins requiring a minimum overlap get a faster algorithm","feed_subtitle":"The algorithm prunes most pairs before computing any overlap duration, avoiding the noise and cost of join-then-filter.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the state-of-the-art interval join algorithm FS, the primary baseline in the experiments.","marker":"[9], [10]"},{"why":"Provides the grid index structure that the proposed algorithm builds on to manage $S$.","marker":"[30]"},{"why":"Defines the RD-index baseline for range-duration queries, which the experiments extend to the overlap-duration join.","marker":"[34]"},{"why":"Defines the relevance-query approach Rel, a competing method compared in the experiments.","marker":"[33]"},{"why":"Establishes that geometric set cover is NP-complete, used to prove that minimizing the number of groups is NP-hard.","marker":"[31]"}],"fun_headline_variants":["Push overlap-duration constraint inside interval join to prune early","Interval joins that skip pairs with too-short overlaps get faster","New algorithm prunes interval pairs before duration checks","Avoid join-then-filter: enforce minimum overlap during join"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Push overlap-duration constraint inside interval join to prune early","Interval joins that skip pairs with too-short overlaps get faster","New algorithm prunes interval pairs before duration checks","Avoid join-then-filter: enforce minimum overlap during join"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000453,"raw_usage":{"total_tokens":2316,"prompt_tokens":1019,"completion_tokens":1297,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":1231}},"tokens_in":635,"tokens_out":1297,"duration_ms":10155,"temperature":1.0,"reasoning_tokens":1231,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:26:01.079796+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Indexing temporal relations for range-duration queries,","cited_arxiv_id":null,"evidence_quote":"Provides the grid index structure that the proposed algorithm builds on to manage $S$."},{"cited_title":"Indexing temporal relations for range-duration queries,","cited_arxiv_id":null,"evidence_quote":"Defines the RD-index baseline for range-duration queries, which the experiments extend to the overlap-duration join."},{"cited_title":"Relevance queries for interval data,","cited_arxiv_id":null,"evidence_quote":"Defines the relevance-query approach Rel, a competing method compared in the experiments."},{"cited_title":"Optimal packing and covering in the plane are np-complete,","cited_arxiv_id":null,"evidence_quote":"Establishes that geometric set cover is NP-complete, used to prove that minimizing the number of groups is NP-hard."}],"review_version":1}