# Cartesian Tree Matching and Indexing

arXiv: https://arxiv.org/abs/1905.08974 · HTML: https://mlsanity.com/paper/1905.08974/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2019.

## Built on by (most cited first, 1 of 1)

- [CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees](https://mlsanity.com/paper/2610.05330/) (2026)

## Abstract (arXiv)

We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we define single pattern matching for a text of length n and a pattern of length m, and multiple pattern matching for a text of length n and k patterns of total length m. We present an O(n+m) time algorithm for single pattern matching, and an O((n+m) log k) deterministic time or O(n+m) randomized time algorithm for multiple pattern matching. We also define an index data structure called Cartesian suffix tree, and present an O(n) randomized time algorithm to build the Cartesian suffix tree. Our efficient algorithms for Cartesian tree matching use a representation of the Cartesian tree, called the parent-distance representation.