| Presentation | 2021-05-08 An Extension of Cartesian Tree Matching Based-on Subsequences Takeshi Kai, Kenta Mitsuyoshi, Isamu Furuya, Hiroki Arimura, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we consider the Cartesian tree matching problem, originally introduced by Park et al. in 2019. Despite of its usefulness in finance data analysis, the requirement for consecutive substrings seems too rigid to handle real world sequences with potential errors. By relaxing this requirement, we propose its extension, called Cartesian tree subsequence matching problem, where we allow patterns to match non-consecutive subsequences of a text sequence rather than consecutive substrings. For this new problem, we propose an efficient algorithm based on dynamic programming for the problem. Furthermore, we also presented algorithms for computing traces of matching, and for the sliding window version of the matching problem. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | String alogorithm / subsequence matching / dynamic programming / slinding window |
| Paper # | COMP2021-6 |
| Date of Issue | 2021-04-30 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2021/5/7(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Vice Chair | Hirotaka Ono(Nagoya Univ) |
| Secretary | Hirotaka Ono(NAIST) / (Senshu Univ.) |
| Assistant | Yota Otachi(Nagoya Univ) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Extension of Cartesian Tree Matching Based-on Subsequences |
| Sub Title (in English) | |
| Keyword(1) | String alogorithm |
| Keyword(2) | subsequence matching |
| Keyword(3) | dynamic programming |
| Keyword(4) | slinding window |
| 1st Author's Name | Takeshi Kai |
| 1st Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| 2nd Author's Name | Kenta Mitsuyoshi |
| 2nd Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| 3rd Author's Name | Isamu Furuya |
| 3rd Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| 4th Author's Name | Hiroki Arimura |
| 4th Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| Date | 2021-05-08 |
| Paper # | COMP2021-6 |
| Volume (vol) | vol.121 |
| Number (no) | COMP-11 |
| Page | pp.pp.39-45(COMP), |
| #Pages | 7 |
| Date of Issue | 2021-04-30 (COMP) |