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

Periodicity in Data Streams with Wildcards

  • Conference paper
  • First Online:
Computer Science – Theory and Applications (CSR 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10846))

Included in the following conference series:

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 S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the length \(n-p\) prefix equals the length \(n-p\) suffix. We present a two-pass streaming algorithm that computes wildcard-periods of S using \(\mathcal {O}\left( k^3\,{{\mathsf {polylog}}} \,n\right) \) bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We then 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}\left( k^3\log ^9 n\right) \) space.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Although wildcard characters are usually denoted with ‘?’, we use \(\bot \) to differentiate from compilation errors - the equivalent of wildcard characters.

References

  1. Amir, A., Eisenberg, E., Levy, A.: Approximate periodicity. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol. 6506, pp. 25–36. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17517-6_5

    Chapter  Google Scholar 

  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)

    Google Scholar 

  5. Breslauer, D., Galil, Z.: Real-time streaming string-matching. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 162–172. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21458-5_15

    Chapter  MATH  Google Scholar 

  6. Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Discrete Mathematics and its Applications. CRC Press, Boca Raton (2008)

    MATH  Google Scholar 

  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  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  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)

    Chapter  Google Scholar 

  10. Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.: Dictionary matching in a stream. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 361–372. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48350-3_31

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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  MATH  Google Scholar 

  14. Clifford, R., Kociumaka, T., Porat, E.: The streaming k-mismatch problem. CoRR, abs/1708.05223 (2017)

    Google Scholar 

  15. Crouch, M.S., McGregor, A.: Periodicity and cyclic shifts via linear sketches. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX/RANDOM -2011. LNCS, vol. 6845, pp. 158–170. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22935-0_14

    Chapter  MATH  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)

    Google Scholar 

  17. Ergü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)

    Google Scholar 

  18. Ergün, F., Grigorescu, E., Azer, E.S., Zhou, S.: Periodicity in data streams with wildcards. CoRR, abs/1802.07375 (2018)

    Chapter  Google Scholar 

  19. Ergün, F., Jowhari, H., Sağlam, M.: Periodicity in streams. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX/RANDOM -2010. LNCS, vol. 6302, pp. 545–559. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15369-3_41

    Chapter  Google Scholar 

  20. Ergün, F., Muthukrishnan, S., Sahinalp, S.C.: Periodicity testing with sublinear samples and space. ACM Trans. Algorithms 6(2), 43:1–43:14 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  21. Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. ACM Trans. Algorithms (TALG) 9(3), 25 (2013)

    MathSciNet  MATH  Google Scholar 

  22. 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)

    Google Scholar 

  23. Gawrychowski, P., Merkurev, O., Shur, A.M., Uznanski, P.: Tight tradeoffs for real-time approximation of longest palindromes in streams. In: 27th Annual Symposium on Combinatorial Pattern Matching, CPM, pp. 18:1–18:13 (2016)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  25. 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)

    Google Scholar 

  26. 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)

    Google Scholar 

  27. 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)

    Google Scholar 

  28. 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)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  32. 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)

    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  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  35. Porat, E., Lipsky, O.: Improved sketching of hamming distance with error correcting. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 173–182. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73437-6_19

    Chapter  Google Scholar 

  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)

    Google Scholar 

  37. Radoszewski, J., Starikovskaya, T.A.: Streaming k-mismatch with error correcting and applications. In: 2017 Data Compression Conference, DCC, pp. 290–299 (2017)

    Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous reviewers for their helpful comments. The work was supported by the National Science Foundation under NSF Awards #1649515 and #1619081.

Author information

Authors and Affiliations

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

    Funda Ergün & Erfan Sadeqi Azer

  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 Samson Zhou .

Editor information

Editors and Affiliations

  1. Department of Informatics, University of Bergen, Bergen, Norway

    Fedor V. Fomin

  2. Steklov Mathematical Institute, Moscow, Russia

    Vladimir V. Podolskii

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ergün, F., Grigorescu, E., Sadeqi Azer, E., Zhou, S. (2018). Periodicity in Data Streams with Wildcards. In: Fomin, F., Podolskii, V. (eds) Computer Science – Theory and Applications. CSR 2018. Lecture Notes in Computer Science(), vol 10846. Springer, Cham. https://doi.org/10.1007/978-3-319-90530-3_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-90530-3_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-90529-7

  • Online ISBN: 978-3-319-90530-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation