<p>Cartesian tree matching is a form of generalized pattern matching where a substring of the text matches with the pattern if they share the same Cartesian tree. This form of matching finds application for time series of stock prices and can be of interest for melody matching between musical scores. For the indexing problem, the state-of-the-art data structure is a Burrows–Wheeler transform based solution due to [Kim and Cho, CPM’21], which uses nearly succinct space and can count the number of substrings that Cartesian tree match with a pattern in time linear in the pattern length. The authors address the construction of their data structure with a straightforward solution that, however, requires pointer-based data structures, resulting in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(n\,\text{lg}\, n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mspace width="0.166667em" /> <mtext>lg</mtext> <mspace width="0.166667em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> bits of space, where <i>n</i> is the text length [Kim and Cho, CPM’21, Section A.4]. We address this bottleneck by a construction that requires <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(n\,\text{lg}\, \sigma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mspace width="0.166667em" /> <mtext>lg</mtext> <mspace width="0.166667em" /> <mi>σ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> bits of space and has a time complexity of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(n\frac{\text{lg}\, \sigma \,\text{lg}\, n}{\textrm{lg}\, \,\textrm{lg}\, n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mfrac> <mrow> <mtext>lg</mtext> <mspace width="0.166667em" /> <mi>σ</mi> <mspace width="0.166667em" /> <mtext>lg</mtext> <mspace width="0.166667em" /> <mi>n</mi> </mrow> <mrow> <mtext>lg</mtext> <mspace width="0.166667em" /> <mspace width="0.166667em" /> <mtext>lg</mtext> <mspace width="0.166667em" /> <mi>n</mi> </mrow> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation> is alphabet size. Additionally, we can extend Kim and Cho’s index for indexing multiple circular texts in the spirit of the extended Burrows–Wheeler transform. We show that the extended index maintains the same complexities and present a dynamic variant, where we pay a logarithmic slowdown and need space linear in the input texts in bits for the extra functionality that we can incrementally add and remove texts. As an application, we give the computation of circular matching statistics. Our extended setting is of interest for finding repetitive motifs common in the aforementioned applications, independent of offsets and scaling.</p>

The ceBWT Index: An Index for Circular Cartesian Tree Matching on Multiple Texts

期刊论文
发表日期：

2026年4月11日

查看全文

Eric M. Osterkamp,
Dominik Köppl

摘要

Cartesian tree matching is a form of generalized pattern matching where a substring of the text matches with the pattern if they share the same Cartesian tree. This form of matching finds application for time series of stock prices and can be of interest for melody matching between musical scores. For the indexing problem, the state-of-the-art data structure is a Burrows–Wheeler transform based solution due to [Kim and Cho, CPM’21], which uses nearly succinct space and can count the number of substrings that Cartesian tree match with a pattern in time linear in the pattern length. The authors address the construction of their data structure with a straightforward solution that, however, requires pointer-based data structures, resulting in $O(n\,\text{lg}\, n)$ $O (n lg n)$ bits of space, where n is the text length [Kim and Cho, CPM’21, Section A.4]. We address this bottleneck by a construction that requires $O(n\,\text{lg}\, \sigma )$ $O (n lg σ)$ bits of space and has a time complexity of $O(n\frac{\text{lg}\, \sigma \,\text{lg}\, n}{\textrm{lg}\, \,\textrm{lg}\, n})$ $O (n \frac{lg σ lg n}{lg lg n})$ , where $\sigma $ $σ$ is alphabet size. Additionally, we can extend Kim and Cho’s index for indexing multiple circular texts in the spirit of the extended Burrows–Wheeler transform. We show that the extended index maintains the same complexities and present a dynamic variant, where we pay a logarithmic slowdown and need space linear in the input texts in bits for the extra functionality that we can incrementally add and remove texts. As an application, we give the computation of circular matching statistics. Our extended setting is of interest for finding repetitive motifs common in the aforementioned applications, independent of offsets and scaling.