Order-preserving matching
We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2014
|
| Online Access: | http://hdl.handle.net/20.500.11937/13024 |
| _version_ | 1848748238155284480 |
|---|---|
| author | Kim, J. Eades, P. Fleischer, R. Hong, S. Iliopoulos, Costas Park, K. Puglisi, Simon Tokuyama, T. |
| author_facet | Kim, J. Eades, P. Fleischer, R. Hong, S. Iliopoulos, Costas Park, K. Puglisi, Simon Tokuyama, T. |
| author_sort | Kim, J. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching is closely related to the representation of order relations of a numeric string. We define the prefix representation and the nearest neighbor representation of the pattern, both of which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(nlogm) time algorithm and optimize it further to obtain O(n+mlogm) time. For the multiple pattern case, we give an O(nlogm) time algorithm. |
| first_indexed | 2025-11-14T07:01:52Z |
| format | Journal Article |
| id | curtin-20.500.11937-13024 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:01:52Z |
| publishDate | 2014 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-130242018-03-29T09:06:09Z Order-preserving matching Kim, J. Eades, P. Fleischer, R. Hong, S. Iliopoulos, Costas Park, K. Puglisi, Simon Tokuyama, T. We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching is closely related to the representation of order relations of a numeric string. We define the prefix representation and the nearest neighbor representation of the pattern, both of which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(nlogm) time algorithm and optimize it further to obtain O(n+mlogm) time. For the multiple pattern case, we give an O(nlogm) time algorithm. 2014 Journal Article http://hdl.handle.net/20.500.11937/13024 10.1016/j.tcs.2013.10.006 Elsevier restricted |
| spellingShingle | Kim, J. Eades, P. Fleischer, R. Hong, S. Iliopoulos, Costas Park, K. Puglisi, Simon Tokuyama, T. Order-preserving matching |
| title | Order-preserving matching |
| title_full | Order-preserving matching |
| title_fullStr | Order-preserving matching |
| title_full_unstemmed | Order-preserving matching |
| title_short | Order-preserving matching |
| title_sort | order-preserving matching |
| url | http://hdl.handle.net/20.500.11937/13024 |