Abstract : Cartesian trees are associated to strings of numbers. They are structured as heap and original strings can be recovered by symmetrical traversal of the trees. Let x be a string of numbers of length m. The Cartesian tree of x is the binary tree where:
– the root corresponds to the index i of the minimal element of x (if there are several occurrences of the minimal element, the leftmost one is chosen);
– the left subtree of the root corresponds to the Cartesian tree of x[1..i-1];
– the right subtree of the root corresponds to the Cartesian tree of x[i+1..m]. Cartesian pattern matching can be applied to find patterns in time series data.
In this talk, we will review the existing Cartesian pattern matching algorithms and describe more in details solutions for the following problems:
– given a text and a pattern that consist of sequences of numbers, find all the substrings of the text that have the same Cartesian tree than the pattern;
– given a text and a finite set of patterns that consist of sequences of numbers, find all the substrings of the text that have the same Cartesian tree than one of the patterns.
– given two strings that consist of sequences of numbers, find the length of the longest substring of both strings that have the same Cartesian tree.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne