Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Periodicity in Data Streams with Wildcards

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We investigate the problem of detecting periodic trends within a string S of length n, arriving in the streaming model, containing at most k wildcard characters, where k = o(n). A wildcard character is a special character that can be assigned any other character. We say that S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the prefix of length n − p equals the suffix of length n − p. We present a two-pass streaming algorithm that computes wildcard-periods of S using \(\mathcal {O}(k^{3} \text {polylog} n)\) bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We also give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S with \(p<\frac {n}{2}\) and no wildcard characters appearing in the last p symbols of S, using \(\mathcal {O}(k^{3}\log ^{9} n)\) space.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Although wildcard characters are usually denoted with ‘?’, we use ⊥ to differentiate from compilation errors - the equivalent of wildcard characters

References

  1. Amir, A., Eisenberg, E., Levy, A.: Approximate periodicity. Algorithms and Computation – 21st International Symposium, ISAAC Proceedings, Part I, 25–36 (2010)

  2. Apostolico, A., Galil, Z. (eds.): Pattern Matching Algorithms. Oxford University Press, Oxford (1997)

    MATH  Google Scholar 

  3. Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403–410 (1990)

    Article  Google Scholar 

  4. Andoni, A., Goldberger, A., McGregor, A., Porat, E.: Homomorphic fingerprints under misalignments: sketching edit and shift distances. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 931–940 (2013)

  5. Breslauer, D., Galil, Z.: Real-Time Streaming String-Matching. In: Combinatorial Pattern Matching, pp. 162–172. Springer (2011)

  6. Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Discrete mathematics and its applications. CRC Press (2008)

  7. Blanchet-Sadri, F., Mercas, R., Rashin, A., Willett, E.: Periodicity algorithms and a conjecture on overlaps in partial words. Theor. Comput. Sci. 443, 35–45 (2012)

    Article  MathSciNet  Google Scholar 

  8. Clifford, P., Clifford, R.: Simple deterministic wildcard matching. Inf. Process. Lett. 101(2), 53–54 (2007)

    Article  MathSciNet  Google Scholar 

  9. Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: From coding theory to efficient pattern matching. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 778–784 (2009)

  10. Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.A.: Dictionary Matching in a Stream. In: Algorithms - ESA 23Rd Annual European Symposium, Proceedings, pp. 361–372 (2015)

  11. Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.A.: The k-mismatch problem revisited. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2039–2052 (2016)

  12. Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 592–601 (2002)

  13. Clifford, R., Jalsenius, M., Porat, E., Sach, B.: Space lower bounds for online pattern matching. Theor. Comput. Sci. 483, 68–74 (2013)

    Article  MathSciNet  Google Scholar 

  14. Clifford, R., Kociumaka, T., Porat, E.: The streaming k-mismatch problem. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1106–1125 (2019)

    Chapter  Google Scholar 

  15. Crouch, M.S., McGregor, A.: Periodicity and Cyclic Shifts via Linear Sketches. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14Th International Workshop, APPROX, and 15th International Workshop, RANDOM. Proceedings, pp. 158–170 (2011)

    Chapter  Google Scholar 

  16. Elfeky, M.G., Aref, W.G., Elmagarmid, A.K.: STAGGER: periodicity mining of data streams using expanding sliding windows. In: Proceedings of the 6th IEEE International Conference on Data Mining (ICDM), pp. 188–199 (2006)

  17. Ergu̇n, F., Grigorescu, E., Azer, E.S., Zhou, S.: Streaming Periodicity with Mismatches. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 42:1–42:21 (2017)

  18. Ergu̇n, F., Jowhari, H., Saglam, M.: Periodicity in Streams. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13Th International Workshop, APPROX 2010, and 14Th International Workshop, RANDOM 2010. Proceedings, pp. 545–559 (2010)

  19. Ergu̇n, F., Muthukrishnan, S., Sahinalp, S.C.: Periodicity testing with sublinear samples and space. ACM Trans. Algorithm. 6(2), 43:1–43:14 (2010)

    Article  MathSciNet  Google Scholar 

  20. Gawrychowski, P.: Optimal pattern matching in lzw compressed strings. ACM Trans. Algorithm. (TALG) 9(3), 25 (2013)

    MathSciNet  MATH  Google Scholar 

  21. Golan, S., Kopelowitz, T., Porat, E.: Streaming Pattern Matching with D Wildcards. In: 24Th Annual European Symposium on Algorithms, pp. 44:1–44:16 (2016)

  22. Galil, Z., Seiferas, J.: Time-space-optimal string matching. J. Comput. Syst. Sci. 26(3), 280–294 (1983)

    Article  MathSciNet  Google Scholar 

  23. Hermelin, D., Rozenberg, L.: Parameterized Complexity Analysis for the Closest String with Wildcards Problem. In: Combinatorial Pattern Matching - 25Th Annual Symposium, CPM Proceedings, pp. 140–149 (2014)

    Chapter  Google Scholar 

  24. Indyk, P., Koudas, N., Muthukrishnan, S.: Identifying representative trends in massive time series data sets using sketches. In: VLDB, Proceedings of 26th International Conference on Very Large Data Bases, pp. 363–372 (2000)

  25. Indyk, P.: Faster algorithms for string matching problems: Matching the Convolution Bound. In: 39Th Annual Symposium on Foundations of Computer Science, FOCS, pp. 166–173 (1998)

  26. Kalai, A.: Efficient pattern-matching with don’t cares. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 655–656 (2002)

  27. Knuth, D.E., Morris, J.H. Jr, Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323–350 (1977)

    Article  MathSciNet  Google Scholar 

  28. Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pp. 41–52 (2010)

  29. Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM. J. Res. Dev. 31(2), 249–260 (1987)

    MATH  Google Scholar 

  30. Lachish, O., Newman, I.: Testing periodicity. Algorithmica 60(2), 401–420 (2011)

    Article  MathSciNet  Google Scholar 

  31. Lewenstein, M., Nekrich, Y., Vitter, J.S.: Space-Efficient String Indexing for Wildcard Pattern Matching. In: 31St International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 506–517 (2014)

  32. Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Program. 2 (2), 143–152 (1982)

    Article  MathSciNet  Google Scholar 

  33. Manea, F., Mercas, R., Tiseanu, C.: An algorithmic toolbox for periodic partial words. Discret. Appl. Math. 179, 174–192 (2014)

    Article  MathSciNet  Google Scholar 

  34. Muthukrishnan, S., Ramesh, H.: String matching under a general matching relation. Inf. Comput. 122(1), 140–148 (1995)

    Article  MathSciNet  Google Scholar 

  35. Porat, E., Lipsky, O.: Improved Sketching of Hamming Distance with Error Correcting. In: Annual Symposium on Combinatorial Pattern Matching, pp. 173–182 (2007)

  36. Porat, B., Porat, E.: Exact and Approximate Pattern Matching in the Streaming Model. In: 50Th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 315–323 (2009)

  37. Radoszewski, J., Starikovskaya, T.A.: Streaming K-Mismatch with Error Correcting and Applications. In: 2017 Data Compression Conference, DCC, pp. 290–299 (2017)

Download references

Acknowledgments

We would like to thank the anonymous reviewers for their helpful comments that improved the presentation. The work was supported by the National Science Foundation under NSF Awards #1649515 and #1619081, as well as by the Indiana University Grand Challenges Program Precision Health Initiative (PHI) Grant.

Author information

Authors and Affiliations

  1. School of Informatics and Computing, Indiana University, Bloomington, IN, USA

    Funda Ergün, Erfan Sadeqi Azer & Samson Zhou

  2. Department of Computer Science, Purdue University, West Lafayette, IN, USA

    Elena Grigorescu & Samson Zhou

Authors
  1. Funda Ergün
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elena Grigorescu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Erfan Sadeqi Azer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Samson Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Funda Ergün.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the Topical Collection on Computer Science Symposium in Russia (2018)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ergün, F., Grigorescu, E., Sadeqi Azer, E. et al. Periodicity in Data Streams with Wildcards. Theory Comput Syst 64, 177–197 (2020). https://doi.org/10.1007/s00224-019-09950-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-019-09950-y

Keywords

Search

Navigation