{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:21Z","timestamp":1759638621654,"version":"3.41.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319905297"},{"type":"electronic","value":"9783319905303"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-90530-3_9","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"90-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Periodicity in Data Streams with Wildcards"],"prefix":"10.1007","author":[{"given":"Funda","family":"Erg\u00fcn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erfan","family":"Sadeqi Azer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-17517-6_5","volume-title":"Algorithms and Computation","author":"A Amir","year":"2010","unstructured":"Amir, A., Eisenberg, E., Levy, A.: Approximate periodicity. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol. 6506, pp. 25\u201336. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17517-6_5"},{"volume-title":"Pattern Matching Algorithms","year":"1997","key":"9_CR2","unstructured":"Apostolico, A., Galil, Z. (eds.): Pattern Matching Algorithms. Oxford University Press, Oxford (1997)"},{"issue":"3","key":"9_CR3","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013940 (2013)","DOI":"10.1145\/2488608.2488726"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-21458-5_15","volume-title":"Combinatorial Pattern Matching","author":"D Breslauer","year":"2011","unstructured":"Breslauer, D., Galil, Z.: Real-time streaming string-matching. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 162\u2013172. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_15"},{"key":"9_CR6","series-title":"Discrete Mathematics and its Applications","volume-title":"Algorithmic Combinatorics on Partial Words","author":"F Blanchet-Sadri","year":"2008","unstructured":"Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Discrete Mathematics and its Applications. CRC Press, Boca Raton (2008)"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2012.03.034","volume":"443","author":"F Blanchet-Sadri","year":"2012","unstructured":"Blanchet-Sadri, F., Mercas, R., Rashin, A., Willett, E.: Periodicity algorithms and a conjecture on overlaps in partial words. Theor. Comput. Sci. 443, 35\u201345 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.ipl.2006.08.002","volume":"101","author":"P Clifford","year":"2007","unstructured":"Clifford, P., Clifford, R.: Simple deterministic wildcard matching. Inf. Process. Lett. 101(2), 53\u201354 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1137\/1.9781611973068.85","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Rapha\u00ebl Clifford","year":"2009","unstructured":"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\u2013784 (2009)"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-662-48350-3_31","volume-title":"Algorithms - ESA 2015","author":"R Clifford","year":"2015","unstructured":"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\u2013372. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_31"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"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\u20132052 (2016)","DOI":"10.1137\/1.9781611974331.ch142"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013601 (2002)","DOI":"10.1145\/509907.509992"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2012.06.012","volume":"483","author":"R Clifford","year":"2013","unstructured":"Clifford, R., Jalsenius, M., Porat, E., Sach, B.: Space lower bounds for online pattern matching. Theor. Comput. Sci. 483, 68\u201374 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR14","unstructured":"Clifford, R., Kociumaka, T., Porat, E.: The streaming k-mismatch problem. CoRR, abs\/1708.05223 (2017)"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-22935-0_14","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"MS Crouch","year":"2011","unstructured":"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\u2013170. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22935-0_14"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"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\u2013199 (2006)","DOI":"10.1109\/ICDM.2006.153"},{"key":"9_CR17","unstructured":"Erg\u00fcn, 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\u201342:21 (2017)"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-319-90530-3_9","volume-title":"Computer Science \u2013 Theory and Applications","author":"Funda Erg\u00fcn","year":"2018","unstructured":"Erg\u00fcn, F., Grigorescu, E., Azer, E.S., Zhou, S.: Periodicity in data streams with wildcards. CoRR, abs\/1802.07375 (2018)"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/978-3-642-15369-3_41","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"F Erg\u00fcn","year":"2010","unstructured":"Erg\u00fcn, F., Jowhari, H., Sa\u011flam, M.: Periodicity in streams. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX\/RANDOM -2010. LNCS, vol. 6302, pp. 545\u2013559. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15369-3_41"},{"issue":"2","key":"9_CR20","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/1721837.1721859","volume":"6","author":"F Erg\u00fcn","year":"2010","unstructured":"Erg\u00fcn, F., Muthukrishnan, S., Sahinalp, S.C.: Periodicity testing with sublinear samples and space. ACM Trans. Algorithms 6(2), 43:1\u201343:14 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"9_CR21","first-page":"25","volume":"9","author":"P Gawrychowski","year":"2013","unstructured":"Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. ACM Trans. Algorithms (TALG) 9(3), 25 (2013)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9_CR22","unstructured":"Golan, S., Kopelowitz, T., Porat, E.: Streaming pattern matching with d wildcards. In: 24th Annual European Symposium on Algorithms, pp. 44:1\u201344:16 (2016)"},{"key":"9_CR23","unstructured":"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\u201318:13 (2016)"},{"issue":"3","key":"9_CR24","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","volume":"26","author":"Z Galil","year":"1983","unstructured":"Galil, Z., Seiferas, J.: Time-space-optimal string matching. J. Comput. Syst. Sci. 26(3), 280\u2013294 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR25","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-319-07566-2_15","volume-title":"Combinatorial Pattern Matching","author":"Danny Hermelin","year":"2014","unstructured":"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\u2013149 (2014)"},{"key":"9_CR26","unstructured":"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\u2013372 (2000)"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Faster algorithms for string matching problems: matching the convolution bound. In: 39th Annual Symposium on Foundations of Computer Science, FOCS, pp. 166\u2013173 (1998)","DOI":"10.1109\/SFCS.1998.743440"},{"key":"9_CR28","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 655\u2013656 (2002)"},{"issue":"2","key":"9_CR29","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9_CR30","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"9_CR31","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s00453-009-9351-y","volume":"60","author":"O Lachish","year":"2011","unstructured":"Lachish, O., Newman, I.: Testing periodicity. Algorithmica 60(2), 401\u2013420 (2011)","journal-title":"Algorithmica"},{"key":"9_CR32","unstructured":"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\u2013517 (2014)"},{"key":"9_CR33","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.dam.2014.07.017","volume":"179","author":"F Manea","year":"2014","unstructured":"Manea, F., Mercas, R., Tiseanu, C.: An algorithmic toolbox for periodic partial words. Discret. Appl. Math. 179, 174\u2013192 (2014)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"9_CR34","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1006\/inco.1995.1144","volume":"122","author":"S Muthukrishnan","year":"1995","unstructured":"Muthukrishnan, S., Ramesh, H.: String matching under a general matching relation. Inf. Comput. 122(1), 140\u2013148 (1995)","journal-title":"Inf. Comput."},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-73437-6_19","volume-title":"Combinatorial Pattern Matching","author":"E Porat","year":"2007","unstructured":"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\u2013182. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_19"},{"key":"9_CR36","doi-asserted-by":"crossref","unstructured":"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\u2013323 (2009)","DOI":"10.1109\/FOCS.2009.11"},{"key":"9_CR37","doi-asserted-by":"crossref","unstructured":"Radoszewski, J., Starikovskaya, T.A.: Streaming k-mismatch with error correcting and applications. In: 2017 Data Compression Conference, DCC, pp. 290\u2013299 (2017)","DOI":"10.1109\/DCC.2017.14"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-90530-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:09:51Z","timestamp":1751580591000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}