IEICE TRANSACTIONS on Information
A Simple Heuristic for Order-Preserving Matching
Summary :
Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.
- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.3 pp.502-504
- Publication Date
- 2019/03/01
- Publicized
- 2018/10/30
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018FCL0004
- Type of Manuscript
- Special Section LETTER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
- Category
Authors
Joong Chae NA
Sejong University
Inbok LEE
Korea Aerospace University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Joong Chae NA, Inbok LEE, "A Simple Heuristic for Order-Preserving Matching" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 3, pp. 502-504, March 2019, doi: 10.1587/transinf.2018FCL0004.
Abstract: Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018FCL0004/_p
Copy
@ARTICLE{e102-d_3_502,
author={Joong Chae NA, Inbok LEE, },
journal={IEICE TRANSACTIONS on Information},
title={A Simple Heuristic for Order-Preserving Matching},
year={2019},
volume={E102-D},
number={3},
pages={502-504},
abstract={Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.},
keywords={},
doi={10.1587/transinf.2018FCL0004},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - A Simple Heuristic for Order-Preserving Matching
T2 - IEICE TRANSACTIONS on Information
SP - 502
EP - 504
AU - Joong Chae NA
AU - Inbok LEE
PY - 2019
DO - 10.1587/transinf.2018FCL0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2019
AB - Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.
ER -
English
