Fast Cartesian Tree Matching

Cheol Ryu; Kunsoo Park; Simone Faro; Siwoo Song; Thierry Lecroq

REVIEW 2 major objections 6 minor 23 references

Fast Cartesian Tree Matching

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Cartesian tree matching reduces to ordinary string matching via a one-bit filter, with one comparison per position for verification.

desk verdict 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. read the letter →

arxiv 1908.04937 v1 pith:IASWAFJV submitted 2019-08-14 cs.DS

Siwoo Song , Cheol Ryu , Simone Faro , Thierry Lecroq , Kunsoo Park This is my paper · ORCID

classification cs.DS MSC 68W32

keywords Cartesiantreematchingprefix-parentrepresentationglobal-parentbinaryfiltrationKMPalgorithmSIMDstringpatternorder-preserving

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

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.

The 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.

Soft 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.

None 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.

Who 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.

Referee Report

2 major / 6 minor

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.

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 (2)

[Section 3, Algorithm 1 and the preceding paragraph] 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 4.1, proof of Theorem 2] 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.

minor comments (6)

[Section 2.1] 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 4.1, proof of Theorem 2] 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 4.3] 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 5, Example 1] 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.
[Table 1] 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.
[General] The paper ends abruptly after the experiments section; a short conclusion summarizing the contributions and possible future work would improve the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new representations and the filtration/verification theorems are proved from first principles, and the only shared-author dependency is a legitimate citation of prior work.

full rationale

The paper's principal new claims are Theorem 1 (local prefix-parent/prefix-child comparison), Theorem 2 (binary representation is a necessary filtration condition), and Theorem 3 (global-parent verification), each with self-contained proofs from the definitions of PP, PC, GP, and PD. The binary filtration result is explicitly a necessary condition, not a disguised equivalent of the target match, and verification by Theorem 3 is proved separately. IKMPCT does invoke a failure function 'computed in the same way as [21]' without restating or proving the KMP border property for Cartesian tree matching; however, this is an ordinary citation of prior work by overlapping authors, not a reduction of the paper's conclusion to its own inputs. No parameter is fitted and then renamed as a prediction, and no known result is merely relabeled. Accordingly, no circular step meeting the paper-quoting standard is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted; all algorithms are parameterized only by pattern length and chosen filtration q-gram. The main inherited assumptions come from [21] and the average-case data model.

assumptions (4)

domain assumption The parent-distance representation has a one-to-one mapping to the Cartesian tree.
Used to justify that prefix-parent representations characterize Cartesian trees; established in [21], not proved in this paper.
domain assumption A KMP failure function for Cartesian tree matching exists and can be computed as in [21]; it has the property that any text suffix matching P[1..q] also matches P[1..pi[q]] on its suffix of length pi[q].
Algorithm 1's fallback q <- pi[q] depends on this, but the paper gives no definition or proof; it is the main inherited premise.
domain assumption For the average-case analysis, the text and pattern elements are independent and uniformly distributed, so adjacent comparison bits are independent across positions.
Section 4.3 relies on this to claim exponentially few candidates; it is an idealized data model, not a guarantee for worst-case or real data.
domain assumption The minimum element in any contiguous interval of a string is determined by the Cartesian tree shape via the LCA of the interval endpoints.
This standard Cartesian tree property underlies the border property of the KMP failure function; the paper does not state it explicitly, but it is needed for the suffix-matching argument.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fast Cartesian Tree Matching." pith.science (2026). https://pith.science/paper/IASWAFJV

@misc{pith2026190804937,
  author       = {Pith},
  title        = {Pith review of: Fast Cartesian Tree Matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IASWAFJV}},
  note         = {Machine review of arXiv:1908.04937}
}

read the original abstract

Cartesian tree matching is the problem of finding all substrings of a given text which have the same Cartesian trees as that of a given pattern. So far there is one linear-time solution for Cartesian tree matching, which is based on the KMP algorithm. We improve the running time of the previous solution by introducing new representations. We present the framework of a binary filtration method and an efficient verification technique for Cartesian tree matching. Any exact string matching algorithm can be used as a filtration for Cartesian tree matching on our framework. We also present a SIMD solution for Cartesian tree matching suitable for short patterns. By experiments we show that known string matching algorithms combined on our framework of binary filtration and efficient verification produce algorithms of good performances for Cartesian tree matching.

Figures

Figures reproduced from arXiv: 1908.04937 by the authors.

**Figure 2.** PPS,PCS, GPS for S = (3, 1, 6, 4, 8, 6, 7, 5, 9). 3 Fast linear Cartesian tree matching The previous algorithm for Cartesian tree matching due to Park et al. [21] is based on the KMP algorithm [19]. They changed the pattern and the text to parent-distance representations and found matches using the KMP algorithm. To compute the parent-distance representations of substrings of the text using O(m) space, however, they… view at source ↗

**Figure 3.** Execution times for the random character dataset. [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[21]

Cartesian Tree Matching and Indexing

Park, S.G., Amir, A., Landau, G.M., Park, K.: Cartesian tree matching and in- dexing. Accepted to CPM (2019), https://arxiv.org/abs/1905.08974

work page Pith review arXiv 2019
[1]

Journal of Algorithms 37(2), 247–266 (2000)

Amir, A., Aumann, Y., Landau, G.M., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. Journal of Algorithms 37(2), 247–266 (2000)

work page 2000
[2]

Information and Computation 181(1), 57–74 (2003)

Amir, A., Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: Overlap matching. Information and Computation 181(1), 57–74 (2003)

work page 2003
[3]

Information Processing Letters 49(3), 111–115 (1994)

Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Information Processing Letters 49(3), 111–115 (1994)

work page 1994
[4]

Information Processing Letters 83(1), 33–39 (2002)

Amir, A., Lewenstein, M., Porat, E.: Approximate swapped matching. Information Processing Letters 83(1), 33–39 (2002)

work page 2002
[5]

In: Proceedings of the Twenty-ﬁfth Annual ACM Symposium on Theory of Computing

Baker, B.S.: A theory of parameterized pattern matching: Algorithms and appli- cations. In: Proceedings of the Twenty-ﬁfth Annual ACM Symposium on Theory of Computing. pp. 71–80. ACM (1993)

work page 1993
[6]

International Journal of Foundations of Computer Science 23(2), 357–374 (2012)

Burcsi, P., Cicalese, F., Fici, G., Liptak, Z.: Algorithms for jumbled pattern match- ing in strings. International Journal of Foundations of Computer Science 23(2), 357–374 (2012)

work page 2012
[7]

Discrete Applied Mathematics (2018)

Cantone, D., Faro, S., Kulekci, M.O.: The order-preserving pattern matching prob- lem in practice. Discrete Applied Mathematics (2018)

work page 2018

Show all 23 references

[8]

In: Combinatorial Pattern Matching

Charras, C., Lecroq, T., Pehoushek, J.D.: A very fast string matching algorithm for small alphabets and long patterns. In: Combinatorial Pattern Matching. pp. 55–64 (1998)

1998
[9]

In: Proceedings of the Prague Stringology Conference 2015

Chhabra, T., Kulekci, M.O., Tarhio, J.: Alternative algorithms for order-preserving matching. In: Proceedings of the Prague Stringology Conference 2015. pp. 36–46 (2015)

2015
[10]

Infor- mation Processing Letters 116(2), 71–74 (2016)

Chhabra, T., Tarhio, J.: A ﬁltration method for order-preserving matching. Infor- mation Processing Letters 116(2), 71–74 (2016)

2016
[11]

Information Processing Letters 115(2), 397–402 (2015)

Cho, S., Na, J.C., Park, K., Sim, J.S.: A fast algorithm for order-preserving pattern matching. Information Processing Letters 115(2), 397–402 (2015)

2015
[12]

Information Processing Letters 110(4), 148–152 (2010)

Durian, B., Holub, J., Peltola, H., Tarhio, J.: Improving practical exact string matching. Information Processing Letters 110(4), 148–152 (2010)

2010
[13]

In: Proceedings of the Prague Stringology Conference

Faro, S., Lecroq, T., Borzi, S., Mauro, S.D., Maggio, A.: The string matching algorithms research tool. In: Proceedings of the Prague Stringology Conference
[14]

In: String Processing and Information Retrieval

Fredriksson, K., Grabowski, S.: Practical and optimal string matching. In: String Processing and Information Retrieval. pp. 376–387 (2005)

2005
[15]

Software: Practice and Experi- ence 10(6), 501–506 (1980) 14 S

Horspool, R.N.: Practical fast searching in strings. Software: Practice and Experi- ence 10(6), 501–506 (1980) 14 S. Song et al

1980
[16]

Intel: Intel (R) 64 and IA-32 Architectures Optimization Reference Manual (2019)

2019
[17]

Mathematics in Computer Science 11(2), 127– 136 (2017)

Kim, J., Amir, A., Na, J.C., Park, K., Sim, J.S.: On representations of ternary order relations in numeric strings. Mathematics in Computer Science 11(2), 127– 136 (2017)

2017
[18]

Theoretical Computer Science 525, 68–79 (2014)

Kim, J., Eades, P., Fleischer, R., Hong, S.H., Iliopoulos, C.S., Park, K., Puglisi, S.J., Tokuyama, T.: Order-preserving matching. Theoretical Computer Science 525, 68–79 (2014)

2014
[19]

SIAM Journal on Computing 6(2), 323–350 (1977)

Knuth, D.E., Morris, Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing 6(2), 323–350 (1977)

1977
[20]

Information Processing Letters 113(12), 430–433 (2013)

Kubica, M., Kulczynski, T., Radoszewski, J., Rytter, W., Walen, T.: A linear time algorithm for consecutive permutation pattern matching. Information Processing Letters 113(12), 430–433 (2013)

2013
[22]

Software: Practice and Experience 27(7), 851–861 (1997)

Tarhio, J., Peltola, H.: String matching in the DNA alphabet. Software: Practice and Experience 27(7), 851–861 (1997)

1997
[23]

Communications of the ACM 23(4), 229–239 (1980)

Vuillemin, J.: A unifying look at data structures. Communications of the ACM 23(4), 229–239 (1980)

1980

Pith tools

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

[1] [21]

Cartesian Tree Matching and Indexing

Park, S.G., Amir, A., Landau, G.M., Park, K.: Cartesian tree matching and in- dexing. Accepted to CPM (2019), https://arxiv.org/abs/1905.08974

work page Pith review arXiv 2019

[2] [1]

Journal of Algorithms 37(2), 247–266 (2000)

Amir, A., Aumann, Y., Landau, G.M., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. Journal of Algorithms 37(2), 247–266 (2000)

work page 2000

[3] [2]

Information and Computation 181(1), 57–74 (2003)

Amir, A., Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: Overlap matching. Information and Computation 181(1), 57–74 (2003)

work page 2003

[4] [3]

Information Processing Letters 49(3), 111–115 (1994)

Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Information Processing Letters 49(3), 111–115 (1994)

work page 1994

[5] [4]

Information Processing Letters 83(1), 33–39 (2002)

Amir, A., Lewenstein, M., Porat, E.: Approximate swapped matching. Information Processing Letters 83(1), 33–39 (2002)

work page 2002

[6] [5]

In: Proceedings of the Twenty-ﬁfth Annual ACM Symposium on Theory of Computing

Baker, B.S.: A theory of parameterized pattern matching: Algorithms and appli- cations. In: Proceedings of the Twenty-ﬁfth Annual ACM Symposium on Theory of Computing. pp. 71–80. ACM (1993)

work page 1993

[7] [6]

International Journal of Foundations of Computer Science 23(2), 357–374 (2012)

Burcsi, P., Cicalese, F., Fici, G., Liptak, Z.: Algorithms for jumbled pattern match- ing in strings. International Journal of Foundations of Computer Science 23(2), 357–374 (2012)

work page 2012

[8] [7]

Discrete Applied Mathematics (2018)

Cantone, D., Faro, S., Kulekci, M.O.: The order-preserving pattern matching prob- lem in practice. Discrete Applied Mathematics (2018)

work page 2018