Order-Preserving Indexing
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 86514892
- Type
- D - Journal article
- DOI
-
10.1016/j.tcs.2015.06.050
- Title of journal
- Theoretical Computer Science
- Article number
- -
- First page
- 122
- Volume
- 638
- Issue
- -
- ISSN
- 0304-3975
- Open access status
- Out of scope for open access requirements
- Month of publication
- July
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
8
- Research group(s)
-
-
- Citation count
- 10
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Order preserved matching (shaped pattern matching) plays a central role in computational finance, music analysis, graphics etc. In real life problems, the shapes are defined over general alphabets. This paper introduced a novel data structure for indexing, independent of the alphabet. Additionally, it presented fast/optimal, deterministic and randomised algorithms for finding “shaped patterns”. The paper was the first to introduce the topic and its solution and was followed with extensions and applications (e.g., Gawrychowski and Uznanski, TCS 638; Amir and Kondratovsky, CPM 2019; Ganguly, Hon, Sadakane et al. TCS 854).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -