Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101705
Title: String periods in the order-preserving model
Authors: Gourdel, G.
Kociumaka, T.
Radoszewski, J.
Rytter, W.
Shur, A.
Waleń, T.
Issue Date: 2020
Publisher: Elsevier Inc.
Citation: String periods in the order-preserving model / G. Gourdel, T. Kociumaka, J. Radoszewski, et al. — DOI 10.1016/j.ic.2019.104463 // Information and Computation. — 2020. — Vol. 270. — 104463.
Abstract: In the order-preserving model, two strings match if they share the same relative order between the characters at the corresponding positions. This model is quite recent, but it has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time O(n), O(nlog⁡log⁡n), O(nlog2⁡log⁡n/log⁡log⁡log⁡n), O(nlog⁡n) depending on the type of periodicity. In the most general variant, the number of different op-periods can be as big as Ω(n2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of op-periods. In particular, we characterize the Fine–Wilf property for coprime op-periods. © 2019 Elsevier Inc.
Keywords: EFFICIENT ALGORITHM
ORDER-PRESERVING PATTERN MATCHING
PERIOD
COMPUTATIONAL METHODS
INFORMATION SYSTEMS
COMPACT REPRESENTATION
COPRIME
ITS APPLICATIONS
ORDER PRESERVING
PERIOD
RELATIVE ORDER
PATTERN MATCHING
URI: http://hdl.handle.net/10995/101705
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85072028290
PURE ID: 11901729
bbd4ec15-75f0-45e7-a98a-ca743f77cfe6
ISSN: 8905401
DOI: 10.1016/j.ic.2019.104463
metadata.dc.description.sponsorship: Supported by ISF grants no. 824/17 and 1278/16 and by an ERC grant MPM under the EU's Horizon 2020 Research and Innovation Programme (grant no. 683064).Supported by the Ministry of Science and Higher Education of the Russian Federation, project 1.3253.2017.A part of this work was done during the workshop StringMasters in Warsaw 2017 that was sponsored by the Warsaw Center of Mathematics and Computer Science. The authors thank the participants of the workshop, especially Hideo Bannai and Shunsuke Inenaga, for helpful discussions.
CORDIS project card: 683064
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85072028290.pdf616,22 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.