{"id":"13bde1c9-3c41-4f49-be6e-db4a43325325","arxiv_id":"1908.04937","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"New prefix-parent, prefix-child, and global-parent representations enable faster Cartesian tree matching, and a binary filtration framework turns any exact string matching algorithm into a Cartesian tree matcher.","lead":"This paper introduces new representations of Cartesian trees that make Cartesian tree matching faster, plus a binary-filtering framework that lets any exact string matching algorithm act as a filter. It also presents a SIMD method for short patterns and experiments showing a 35 percent speedup for the linear-time algorithm and strong practical gains for filtration-based methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"IKMPCT's correctness depends on an unstated and unproved KMP failure-function border property inherited from [21]; the paper defines neither the function nor the lemma, so the improved linear-time claim is not self-contained.","rationale":"Reader's weakest assumption matches mine: the missing failure-function definition/proof is the load-bearing issue. I did not find a flaw in Theorems 1–3; the prefix-parent/child local comparison, the beta filtration necessary condition, and the global-parent one-comparison verification all check out. The average-case sublinear argument in §4.3 is heuristic and assumes near-independence of beta bits, but it is not part of the abstract's central correctness claim, and the experimental section is explicitly practical. The absence of code/data weakens reproducibility but does not undermine the theoretical core. Therefore I keep the reader's CONDITIONAL verdict and do not escalate.","tokens_in":11913,"tokens_out":16237,"duration_ms":161127,"concrete_test":"Implement Algorithm 1 as written, taking the failure function defined in Park et al. [21], and compare its output against a brute-force O(nm) Cartesian-tree matcher on every pair of strings over alphabet {0,1,2} with pattern length at most 8 and text length at most 10. A single mismatch would refute the inherited border property; a clean pass would indicate the missing lemma is true, reducing the concern to a presentational gap that still needs a written proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 (Section 3) invokes FAILURE-FUNC(P) at line 3 and uses q ← π[q] in the mismatch loop, exactly as in standard KMP. For the while loop to preserve the invariant that the text suffix of length q matches P[1..q], π must satisfy a Cartesian-tree analogue of the border property: whenever P[1..q] matches a text substring ending at the current position, the suffix of length π[q] of that text substring also matches P[1..π[q]]. The paper says only \"We compute the failure function π in the same way as [21] does\" and never states this property or proves it. Park et al. [21] is a concurrent preprint, so the correctness of the improved linear-time algorithm IKMPCT—the main algorithmic improvement in Section 3—is externally assumed. Theorems 1–3 and the filtration framework are otherwise coherent: Theorem 1's local comparison is correct, Theorem 2's necessary-condition filtration is true, and Theorem 3's one-comparison verification is supported by its proof. The gap is not an observed counterexample; it is a missing formal dependency. Because a KMP-style failure function for a nontransitive matching relation is exactly where hidden assumptions break, this is the most load-bearing weakness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Cartesian tree matching problem and makes three main contributions. It introduces prefix-parent, prefix-child, and global-parent representations of strings, which allow Cartesian tree equality to be checked locally. It presents Algorithm 1 (IKMPCT), a KMP-style linear-time text search that avoids the deque-based parent-distance computation of the prior algorithm, and it builds a binary filtration framework: any exact string matching algorithm can be run on binary representations of the pattern and text, with candidates verified by one comparison per pattern position using the global-parent representation. The paper also describes a SIMD variant for short patterns and reports experiments on random integer, random character, and Seoul temperature datasets, showing practical speedups over the previous KMPCT algorithm.","tokens_in":12169,"tokens_out":13689,"duration_ms":120439,"significance":"If correct, the paper gives a useful practical improvement over the prior Cartesian tree matching algorithm and provides a flexible filtration framework that leverages the extensive literature on exact string matching. The new representations (prefix-parent, prefix-child, global-parent) are elegant, and Theorems 1 and 3 appear sound. The binary-representation filtration theorem (Theorem 2) is a valuable observation, and the experimental evaluation is reasonably thorough. However, the correctness of Algorithm 1 is not self-contained because the failure function is inherited from a concurrent preprint without statement or proof of the required border property, and the proof of Theorem 2 contains an indexing error. These issues are fixable but must be addressed before the paper can be accepted.","major_comments":[{"comment":"Algorithm 1 invokes FAILURE-FUNC(P) at line 3 and uses the transition q ← π[q] at line 10, but the failure function π is never defined in this paper; the text only says 'We compute the failure function π in the same way as [21] does.' The correctness of the KMP-style loop relies on a border property for Cartesian tree matching: whenever P[1..q] matches a text suffix, the suffix of length π[q] of that text suffix must also match P[1..π[q]]. This property is neither stated nor proved here, and it is load-bearing because it justifies the failure transitions in the improved linear-time algorithm. Please state the definition of the failure function, prove the required border property (or give a precise reference to a published version containing the proof), and add a correctness proof of Algorithm 1 showing that the loop invariant is preserved.","section":"Section 3, Algorithm 1 and the preceding paragraph"},{"comment":"The proof claims that if CT(P[1..m]) = CT(T[i..i+m−1]), then PP_P(j+1) = PP_T(i+j) for 0≤j≤m−1, and uses this equality to conclude βP[j] = βT[i+j−1]. However, PP_T is defined on the entire text T, not on the substring T[i..i+m−1]. This equality is false in general; for example, with P = (5,4,3), T = (0,5,4,3), and i = 2, the substring T[2..4] matches P, but PP_P(2) = 2 while PP_T(3) = 1. The theorem's conclusion is nonetheless true, because two strings with the same Cartesian tree must have the same relative order on every adjacent pair, and therefore the binary representations agree on the aligned positions. The proof should be rewritten to argue directly from the Cartesian tree structure, or by defining prefix-parents relative to the substring rather than using the global PP_T.","section":"Section 4.1, proof of Theorem 2"}],"minor_comments":[{"comment":"The symbol ≼ is used in Theorem 1, Algorithm 1, and Theorem 3, but it is never formally defined; please define S[i] ≼ S[j] as S[i] ≺ S[j] or i = j.","section":"Section 2.1"},{"comment":"The proof states the equality PP_P(j+1) = PP_T(i+j) for 0≤j≤m−1, but βP is only defined for 1≤j≤m−1; the case j=0 is not used and should be removed from the indexing range.","section":"Section 4.1, proof of Theorem 2"},{"comment":"The average-case sublinearity claim is presented as a proof sketch, but the argument only computes a per-position matching probability and does not rigorously bound the expected verification cost or the dependence of the filtration algorithm's running time on the input distribution; please either make it explicit that this is a heuristic argument or provide a more formal analysis.","section":"Section 4.3"},{"comment":"The example shows R1, R4, and R5, but the final computation uses R3≪2; it would be clearer to explain explicitly that R3 is obtained as R1 (since 1−GP_P(1) = 3−GP_P(3)) before it is shifted.","section":"Section 5, Example 1"},{"comment":"The column headers in Table 1 are difficult to parse because the q values are interleaved with the algorithm names; please reformat the table so that each column is clearly associated with a single algorithm and parameter.","section":"Table 1"},{"comment":"The paper ends abruptly after the experiments section; a short conclusion summarizing the contributions and possible future work would improve the presentation.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely acceptable after revision. The main substantive issues are (i) the failure function for IKMPCT is not defined and its border property is not proved, making Section 3 not self-contained, and (ii) the proof of Theorem 2 contains a clear indexing error even though the theorem is true. Both are fixable. I would also encourage the authors to either strengthen or soften the Section 4.3 sublinearity claim, since the current argument is heuristic. The experimental work is solid and the new representations are a genuine contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this. It makes Cartesian tree matching meaningfully faster with two genuinely new ideas: prefix-parent/prefix-child representations that check a match in constant time without deque overhead, and a binary filtration framework that lets any exact string matching algorithm act as a filter, with verification in one comparison per position via the global-parent representation. These are not incremental tweaks. Theorem 1 is correct and useful; Theorem 2's necessary-condition filtration is right; Theorem 3's one-comparison verification is supported by the proof. The paper also explains clearly why the existing order-preserving filtrations don't transfer, which is a nice piece of honesty.\n\nThe experiments show IKMPCT about 35% faster than the previous KMPCT, and the filtration-based variants are substantially faster on both random and real data. That is credible, though no code or data is shipped, so the numbers are plausible rather than independently reproducible.\n\nSoft spots, in order of importance. First, Algorithm 1's failure function is inherited from [21] without being defined or proved. The sentence \"We compute the failure function pi in the same way as [21] does\" hides a load-bearing assumption: that the usual KMP border property holds for Cartesian tree matching. That is not obvious, because the matching relation is nontransitive, and the correctness of the improved linear-time algorithm rests entirely on this unstated property. It might well be true, but as written the paper is not self-contained. This is a completeness gap, not an observed counterexample. Second, the sublinear-on-average argument is a sketch. It asserts exponential decay of candidates and vanishing verification time without formalizing the filtration cost for the concrete algorithms used. As a heuristic it is fine; as a theorem it is incomplete. Third, minor notational sloppiness in the proof of Theorem 2's indices and a somewhat ad hoc complexity statement in the SIMD section.\n\nNone of these undermine the central conceptual contributions. The paper deserves serious refereeing, but the referee should push the authors to state and prove the failure-function property, or replace it with a self-contained construction, and to tighten the average-case analysis.\n\nWho is this for? People working on Cartesian tree matching, order-preserving matching, or filtration-based string matching will get real value, especially from Section 4. For outsiders, the binary filtration idea is the main takeaway. My recommendation: send it to peer review with requests for revision, not desk-reject.","headline":"Solid practical advance in Cartesian tree matching; the new representations and binary filtration are real contributions, but Algorithm 1's honesty depends on an unproved failure-function property inherited from a concurrent paper.","tokens_in":12676,"tokens_out":1704,"would_cite":false,"duration_ms":18661,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cartesian tree matching reduces to ordinary string matching via a one-bit filter, with one comparison per position for verification.","keywords":["Cartesian tree matching","prefix-parent representation","global-parent representation","binary filtration","KMP algorithm","SIMD string matching","pattern matching","order-preserving matching"],"falsifier":"Run IKMPCT and brute-force Cartesian tree matching on all pattern and text pairs of length up to 8 over the alphabet {1,2,3}; any disagreement in reported match positions would falsify the linear-time claim. Because the filtration and verification theorems are proved, a disagreement would most plausibly trace to the unproved KMP border property of the inherited failure function.","tokens_in":11735,"feed_emoji":"🌳","tokens_out":9339,"duration_ms":89045,"temperature":0.7,"pith_summary":"This paper is about finding all substrings of a text whose Cartesian trees, the heap-ordered trees formed by recursively taking minima, match a pattern's Cartesian tree. The authors introduce a prefix-parent representation that lets a new text character be checked against the pattern in constant time, avoiding the deque overhead of the previous linear-time algorithm, and a binary representation of each string that is preserved under Cartesian tree matching. Because the binary encoding is preserved, any ordinary exact string matching algorithm can filter candidates; a global-parent representation then verifies each candidate with one comparison per pattern position. The paper also gives a SIMD method for short patterns and reports experiments showing that filtration-based algorithms beat the linear-time approach on longer patterns, while the improved linear-time algorithm is about 35 percent faster than the earlier one.","feed_headline":"Cartesian tree matching now runs at string-matching speed","feed_subtitle":"New encodings let any exact string matcher find candidates, then verify each with one comparison per position.","key_machinery":"The machinery is a family of representations of a string's Cartesian tree. The prefix-parent representation PP_S(i) records the nearest previous element smaller than S[i], or i itself; the prefix-child representation PC_S(i) records the root of the interval between PP_S(i) and i, which is the child of S[i] in the Cartesian tree of the prefix. Together they let Algorithm 1 check a new text character against the pattern in constant time. The binary representation βS[i]=0 iff PP_S(i+1)=i, which holds exactly when S[i]≺S[i+1], turns each string into an ordinary binary string that any exact string matcher can scan. The global-parent representation GP_S(i) is PP_S(i) unless some j>i has PC_S(j)=i, in which case GP_S(i)=j; Theorem 3 states that two strings have the same Cartesian tree iff S[GP_P(i)]≼S[i] for every i, reducing verification to one comparison per position.","core_discovery":"The central discovery is that Cartesian tree matching splits cleanly into a necessary-condition binary filter and an exact one-comparison-per-position verifier. For any string S, define βS[i]=0 exactly when S[i] is the prefix-parent of S[i+1], equivalently S[i]≺S[i+1]; any substring whose Cartesian tree equals the pattern's must have the same binary string β as the pattern. Thus every exact string matching algorithm, whether KMP, Boyer-Moore-Horspool, Alpha skip search, or SBNDM, can be run on βP and βT to produce candidates. A candidate is accepted exactly when T[i+GP_P(q)−1]≼T[i+q−1] for every position q, where GP_P is the global-parent representation: the entry GP_P(i) is either the parent of i in the Cartesian tree or the unique child that points back to i. This single check replaces the two comparisons per element needed with prefix-parent and prefix-child representations, and the improved linear-time algorithm IKMPCT removes the deque overhead of the earlier KMP-based method by testing text characters directly against PP_P and PC_P.","pith_inferences":["The same filter-and-verify split should transfer to the order-dual variant where the Cartesian tree is built from maxima instead of minima, since the prefix-parent identities are symmetric under reversing the order.","Because the binary representation depends only on adjacent comparisons, the filter could be applied directly to time series where only signs of successive differences are available, without storing full values.","The exponential decay of β-matches with pattern length implies that for long patterns the practical bottleneck is the filter's own speed rather than verification, so engineering faster filters with wider q-grams or wider SIMD registers is the natural next step."],"forward_implications":["IKMPCT is linear time, O(n+m), with no deque and no per-character parent-distance computation; experiments show it is about 35 percent faster than the previous KMP-based algorithm.","Any exact string matching algorithm, classical, bit-parallel, or SIMD, can be dropped into the filtration phase and will return exactly the candidates that then pass the one-comparison global-parent verification.","Verification cost is m comparisons per candidate, down from two comparisons per element in the prefix-parent and prefix-child check.","For 1-byte alphabets and pattern length m≤16, the SIMD window method runs in O(mn/(17−m)) SIMD instructions, making it the fastest method for short patterns in the reported experiments.","On longer patterns, the filtration-based algorithms, especially Alpha skip search with q-grams, dominate in running time, so the practical choice of algorithm depends on pattern length and data regularity."],"supporting_citations":[{"why":"Supplies the parent-distance representation and the KMP-style failure function on which the improved linear-time algorithm is built.","marker":"[21]"},{"why":"Provides the KMP automaton and failure-function framework that both the earlier and improved Cartesian tree matching algorithms adapt.","marker":"[19]"},{"why":"Defines the Cartesian tree itself, the object whose equality defines the matching relation.","marker":"[23]"},{"why":"Supplies the average-case sublinearity analysis for filtration-based order-preserving matching that Section 4.3 adapts to Cartesian tree matching.","marker":"[10]"},{"why":"Provides the Boyer-Moore-Horspool filter used in the BMHCT experiments.","marker":"[15]"},{"why":"Provides the Alpha skip search filter used in the SKSCT experiments, which perform best for long patterns.","marker":"[8]"},{"why":"Demonstrates SIMD filtration for order-preserving matching whose packing approach the paper's SIMD solutions follow.","marker":"[7]"},{"why":"Shows SIMD and bit-parallel filtration algorithms for order-preserving matching that inform the SIMD packing choices.","marker":"[9]"},{"why":"Provides the SBNDM filtration method used as the SBNDMCT filter on binary representations.","marker":"[12]"},{"why":"Supplies the string matching research tool implementations of SBNDM q used in the experiments.","marker":"[13]"}],"fun_headline_variants":["Binary encoding turns Cartesian tree matching into string matching","Any string algorithm now filters Cartesian tree matches","One comparison per position verifies Cartesian tree matches","SIMD acceleration for short-pattern Cartesian tree matching","Faster Cartesian tree matching with a binary filter and verify"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The improved linear-time algorithm inherits, without proof here, the assumption that the failure function built for the pattern has the standard KMP border property for Cartesian tree matching: whenever a prefix of the pattern matches a text suffix, the shorter prefix selected by the failure pointer also matches that same text suffix.","fun_headline_variants_meta":{"raw":{"variants":["Binary encoding turns Cartesian tree matching into string matching","Any string algorithm now filters Cartesian tree matches","One comparison per position verifies Cartesian tree matches","SIMD acceleration for short-pattern Cartesian tree matching","Faster Cartesian tree matching with a binary filter and verify"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001013,"raw_usage":{"total_tokens":4250,"prompt_tokens":891,"completion_tokens":3359,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":3286}},"tokens_in":507,"tokens_out":3359,"duration_ms":24189,"temperature":1.0,"reasoning_tokens":3286,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:32:28.169011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run IKMPCT and brute-force Cartesian tree matching on all pattern and text pairs of length up to 8 over the alphabet {1,2,3}; any disagreement in reported match positions would falsify the linear-time claim. Because the filtration and verification theorems are proved, a disagreement would most plausibly trace to the unproved KMP border property of the inherited failure function.","supporting_citations":[{"cited_title":"Cartesian Tree Matching and Indexing","cited_arxiv_id":"1905.08974","evidence_quote":"Supplies the parent-distance representation and the KMP-style failure function on which the improved linear-time algorithm is built."},{"cited_title":"SIAM Journal on Computing 6(2), 323–350 (1977)","cited_arxiv_id":null,"evidence_quote":"Provides the KMP automaton and failure-function framework that both the earlier and improved Cartesian tree matching algorithms adapt."},{"cited_title":"Communications of the ACM 23(4), 229–239 (1980)","cited_arxiv_id":null,"evidence_quote":"Defines the Cartesian tree itself, the object whose equality defines the matching relation."},{"cited_title":"Infor- mation Processing Letters 116(2), 71–74 (2016)","cited_arxiv_id":null,"evidence_quote":"Supplies the average-case sublinearity analysis for filtration-based order-preserving matching that Section 4.3 adapts to Cartesian tree matching."},{"cited_title":"Software: Practice and Experi- ence 10(6), 501–506 (1980) 14 S","cited_arxiv_id":null,"evidence_quote":"Provides the Boyer-Moore-Horspool filter used in the BMHCT experiments."},{"cited_title":"In: Combinatorial Pattern Matching","cited_arxiv_id":null,"evidence_quote":"Provides the Alpha skip search filter used in the SKSCT experiments, which perform best for long patterns."},{"cited_title":"Discrete Applied Mathematics (2018)","cited_arxiv_id":null,"evidence_quote":"Demonstrates SIMD filtration for order-preserving matching whose packing approach the paper's SIMD solutions follow."},{"cited_title":"In: Proceedings of the Prague Stringology Conference 2015","cited_arxiv_id":null,"evidence_quote":"Shows SIMD and bit-parallel filtration algorithms for order-preserving matching that inform the SIMD packing choices."},{"cited_title":"Information Processing Letters 110(4), 148–152 (2010)","cited_arxiv_id":null,"evidence_quote":"Provides the SBNDM filtration method used as the SBNDMCT filter on binary representations."},{"cited_title":"In: Proceedings of the Prague Stringology Conference","cited_arxiv_id":null,"evidence_quote":"Supplies the string matching research tool implementations of SBNDM q used in the experiments."}],"review_version":1}