Document Open Access Logo

String Periods in the Order-Preserving Model

Authors Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur, Tomasz Walen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.38.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Garance Gourdel
Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Arseny Shur
Tomasz Walen

Cite As Get BibTex

Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur, and Tomasz Walen. String Periods in the Order-Preserving Model. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.38

Abstract

The order-preserving model (op-model, in short) was introduced quite recently but 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(n log log n), O(n log^2 log n/log log log n), O(n log n) depending on the type of periodicity. In the most general variant the number of different periods can be as big as Omega(n^2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of such periods.

Subject Classification

Keywords
  • order-preserving pattern matching
  • period
  • efficient algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Tom M. Apostol. Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics, Springer, 1976. Google Scholar
  2. Alberto Apostolico and Raffaele Giancarlo. Periodicity and repetitions in parameterized strings. Discrete Applied Mathematics, 156(9):1389-1398, 2008. URL: http://dx.doi.org/10.1016/j.dam.2006.11.017.
  3. Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot, and Stéphane Vialette. Single and multiple consecutive permutation motif search. In Leizhen Cai, Siu-Wing Cheng, and Tak Wah Lam, editors, Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, volume 8283 of Lecture Notes in Computer Science, pages 66-77. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45030-3_7.
  4. Jean Berstel and Luc Boasson. Partial words and a theorem of fine and wilf. Theor. Comput. Sci., 218(1):135-141, 1999. URL: http://dx.doi.org/10.1016/S0304-3975(98)00255-2.
  5. Francine Blanchet-Sadri, Deepak Bal, and Gautam Sisodia. Graph connectivity, partial words, and a theorem of fine and wilf. Inf. Comput., 206(5):676-693, 2008. URL: http://dx.doi.org/10.1016/j.ic.2007.11.007.
  6. Francine Blanchet-Sadri and Robert A. Hegstrom. Partial words and a theorem of fine and wilf revisited. Theor. Comput. Sci., 270(1-2):401-419, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(00)00407-2.
  7. Francine Blanchet-Sadri, Sean Simmons, Amelia Tebbe, and Amy Veprauskas. Abelian periods, partial words, and an extension of a theorem of fine and wilf. RAIRO - Theor. Inf. and Applic., 47(3):215-234, 2013. URL: http://dx.doi.org/10.1051/ita/2013034.
  8. Domenico Cantone, Simone Faro, and M. Oguzhan Külekci. An efficient skip-search approach to the order-preserving pattern matching problem. In Jan Holub and Jan Zdárek, editors, Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015, pages 22-35. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, 2015. URL: http://www.stringology.org/event/2015/p04.html.
  9. Maria Gabriella Castelli, Filippo Mignosi, and Antonio Restivo. Fine and wilf’s theorem for three periods and a generalization of sturmian words. Theor. Comput. Sci., 218(1):83-94, 1999. URL: http://dx.doi.org/10.1016/S0304-3975(98)00251-5.
  10. Tamanna Chhabra, Simone Faro, M. Oguzhan Külekci, and Jorma Tarhio. Engineering order-preserving pattern matching with SIMD parallelism. Softw., Pract. Exper., 47(5):731-739, 2017. URL: http://dx.doi.org/10.1002/spe.2433.
  11. Tamanna Chhabra, Emanuele Giaquinta, and Jorma Tarhio. Filtration algorithms for approximate order-preserving matching. In Costas S. Iliopoulos, Simon J. Puglisi, and Emine Yilmaz, editors, String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings, volume 9309 of Lecture Notes in Computer Science, pages 177-187. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23826-5_18.
  12. Tamanna Chhabra, M. Oguzhan Külekci, and Jorma Tarhio. Alternative algorithms for order-preserving matching. In Jan Holub and Jan Zdárek, editors, Proceedings of the Prague Stringology Conference 2015, Prague, Czech Republic, August 24-26, 2015, pages 36-46. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, 2015. URL: http://www.stringology.org/event/2015/p05.html.
  13. Tamanna Chhabra and Jorma Tarhio. A filtration method for order-preserving matching. Inf. Process. Lett., 116(2):71-74, 2016. URL: http://dx.doi.org/10.1016/j.ipl.2015.10.005.
  14. Sukhyeun Cho, Joong Chae Na, Kunsoo Park, and Jeong Seop Sim. A fast algorithm for order-preserving pattern matching. Inf. Process. Lett., 115(2):397-402, 2015. URL: http://dx.doi.org/10.1016/j.ipl.2014.10.018.
  15. Sorin Constantinescu and Lucian Ilie. Fine and Wilf’s theorem for Abelian periods. Bulletin of the EATCS, 89:167-170, 2006. Google Scholar
  16. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  17. Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. Algorithms on strings. Cambridge University Press, 2007. Google Scholar
  18. Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Order-preserving indexing. Theor. Comput. Sci., 638:122-135, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.06.050.
  19. Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczynski, and Tomasz Walen. A note on efficient computation of all abelian periods in a string. Inf. Process. Lett., 113(3):74-77, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2012.11.001.
  20. Maxime Crochemore and Wojciech Rytter. Jewels of Stringology. World Scientific, 2003. Google Scholar
  21. Gianni Decaroli, Travis Gagie, and Giovanni Manzini. A compact index for order-preserving pattern matching. In Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagristà, and James A. Storer, editors, 2017 Data Compression Conference, DCC 2017, Snowbird, UT, USA, April 4-7, 2017, pages 72-81. IEEE, 2017. URL: http://dx.doi.org/10.1109/DCC.2017.35.
  22. Sergi Elizalde and Marc Noy. Consecutive patterns in permutations. Advances in Applied Mathematics, 30(1):110-125, 2003. URL: http://dx.doi.org/10.1016/S0196-8858(02)00527-4.
  23. Simone Faro and M. Oguzhan Külekci. Efficient algorithms for the order preserving pattern matching problem. In Riccardo Dondi, Guillaume Fertin, and Giancarlo Mauri, editors, Algorithmic Aspects in Information and Management - 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, volume 9778 of Lecture Notes in Computer Science, pages 185-196. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-41168-2_16.
  24. Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, and Élise Prieur-Gaston. Algorithms for computing abelian periods of words. Discrete Applied Mathematics, 163:287-297, 2014. URL: http://dx.doi.org/10.1016/j.dam.2013.08.021.
  25. Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, Élise Prieur-Gaston, and William F. Smyth. A note on easy and efficient computation of full abelian periods of a word. Discrete Applied Mathematics, 212:88-95, 2016. URL: http://dx.doi.org/10.1016/j.dam.2015.09.024.
  26. Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc., 16:109-114, 1965. Google Scholar
  27. Travis Gagie, Giovanni Manzini, and Rossano Venturini. An encoding for order-preserving matching. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 38:1-38:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.38.
  28. Pawel Gawrychowski and Przemyslaw Uznanski. Order-preserving pattern matching with k mismatches. Theor. Comput. Sci., 638:136-144, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.08.022.
  29. Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur, and Tomasz Waleń. String periods in the order-preserving model. ArXiv preprint. URL: https://arxiv.org/abs/1801.01404.
  30. Lidia A. Idiatulina and Arseny M. Shur. Periodic partial words and random bipartite graphs. Fundam. Inform., 132(1):15-31, 2014. URL: http://dx.doi.org/10.3233/FI-2014-1030.
  31. Jacques Justin. On a paper by castelli, mignosi, restivo. ITA, 34(5):373-377, 2000. URL: http://dx.doi.org/10.1051/ita:2000122.
  32. Jinil Kim, Peter Eades, Rudolf Fleischer, Seok-Hee Hong, Costas S. Iliopoulos, Kunsoo Park, Simon J. Puglisi, and Takeshi Tokuyama. Order-preserving matching. Theor. Comput. Sci., 525:68-79, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.006.
  33. Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Fast algorithms for abelian periods in words and greatest common divisor queries. In Natacha Portier and Thomas Wilke, editors, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, volume 20 of LIPIcs, pages 245-256. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.245.
  34. Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Fast algorithms for abelian periods in words and greatest common divisor queries. J. Comput. Syst. Sci., 84:205-218, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.09.003.
  35. Tomasz Kociumaka, Jakub Radoszewski, and Bartlomiej Wisniewski. Subquadratic-time algorithms for abelian stringology problems. In Ilias S. Kotsireas, Siegfried M. Rump, and Chee K. Yap, editors, Mathematical Aspects of Computer and Information Sciences - 6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers, volume 9582 of Lecture Notes in Computer Science, pages 320-334. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-32859-1_27.
  36. Marcin Kubica, Tomasz Kulczynski, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett., 113(12):430-433, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.03.015.
  37. Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Generalized pattern matching and periodicity under substring consistent equivalence relations. Theor. Comput. Sci., 656:225-233, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.02.017.
  38. Arseny M. Shur and Yulia V. Gamzova. Partial words and the interaction property of periods. Izvestiya: Mathematics, 68:405-428, 2004. URL: http://stacks.iop.org/1064-5632/68/i=2/a=A09.
  39. Arseny M. Shur and Yulia V. Konovalova. On the periods of partial words. In Jirí Sgall, Ales Pultr, and Petr Kolman, editors, Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings, volume 2136 of Lecture Notes in Computer Science, pages 657-665. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-44683-4_57.
  40. Robert Tijdeman and Luca Zamboni. Fine and Wilf words for any periods. Indag. Math., 14(1):135-147, 2003. URL: http://dx.doi.org/10.1016/S0019-3577(03)90076-0.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact