{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:36Z","timestamp":1740109416502,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00224-019-09950-y","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T12:02:56Z","timestamp":1576843376000},"page":"177-197","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","volume":"64","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8288-5698","authenticated-orcid":false,"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"key":"9950_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Eisenberg, E., Levy, A.: Approximate periodicity. Algorithms and Computation \u2013 21st International Symposium, ISAAC Proceedings, Part I, 25\u201336 (2010)","DOI":"10.1007\/978-3-642-17517-6_5"},{"volume-title":"Pattern Matching Algorithms","year":"1997","key":"9950_CR2","unstructured":"Apostolico, A., Galil, Z. (eds.): Pattern Matching Algorithms. Oxford University Press, Oxford (1997)"},{"issue":"3","key":"9950_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":"9950_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":"9950_CR5","doi-asserted-by":"crossref","unstructured":"Breslauer, D., Galil, Z.: Real-Time Streaming String-Matching. In: Combinatorial Pattern Matching, pp. 162\u2013172. Springer (2011)","DOI":"10.1007\/978-3-642-21458-5_15"},{"key":"9950_CR6","doi-asserted-by":"crossref","unstructured":"Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Discrete mathematics and its applications. CRC Press (2008)","DOI":"10.1201\/9781420060935"},{"key":"9950_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":"9950_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":"9950_CR9","doi-asserted-by":"crossref","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)","DOI":"10.1137\/1.9781611973068.85"},{"key":"9950_CR10","doi-asserted-by":"crossref","unstructured":"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\u2013372 (2015)","DOI":"10.1007\/978-3-662-48350-3_31"},{"key":"9950_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":"9950_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":"9950_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":"9950_CR14","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1137\/1.9781611975482.68","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Raphael Clifford","year":"2019","unstructured":"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\u20131125 (2019)"},{"key":"9950_CR15","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":"Michael S. Crouch","year":"2011","unstructured":"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\u2013170 (2011)"},{"key":"9950_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":"9950_CR17","unstructured":"Ergu\u0307n, 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":"9950_CR18","doi-asserted-by":"crossref","unstructured":"Ergu\u0307n, 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\u2013559 (2010)","DOI":"10.1007\/978-3-642-15369-3_41"},{"issue":"2","key":"9950_CR19","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/1721837.1721859","volume":"6","author":"F Ergu\u0307n","year":"2010","unstructured":"Ergu\u0307n, F., Muthukrishnan, S., Sahinalp, S.C.: Periodicity testing with sublinear samples and space. ACM Trans. Algorithm. 6(2), 43:1\u201343:14 (2010)","journal-title":"ACM Trans. Algorithm."},{"issue":"3","key":"9950_CR20","first-page":"25","volume":"9","author":"P Gawrychowski","year":"2013","unstructured":"Gawrychowski, P.: Optimal pattern matching in lzw compressed strings. ACM Trans. Algorithm. (TALG) 9(3), 25 (2013)","journal-title":"ACM Trans. Algorithm. (TALG)"},{"key":"9950_CR21","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)"},{"issue":"3","key":"9950_CR22","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":"9950_CR23","doi-asserted-by":"publisher","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":"9950_CR24","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":"9950_CR25","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)"},{"key":"9950_CR26","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":"9950_CR27","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H. Jr, Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"9950_CR28","doi-asserted-by":"crossref","unstructured":"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\u201352 (2010)","DOI":"10.1145\/1807085.1807094"},{"issue":"2","key":"9950_CR29","first-page":"249","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":"J. Res. Dev."},{"issue":"2","key":"9950_CR30","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":"9950_CR31","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)"},{"issue":"2","key":"9950_CR32","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J Misra","year":"1982","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Program. 2 (2), 143\u2013152 (1982)","journal-title":"Sci. Comput. Program."},{"key":"9950_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":"9950_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":"9950_CR35","doi-asserted-by":"crossref","unstructured":"Porat, E., Lipsky, O.: Improved Sketching of Hamming Distance with Error Correcting. In: Annual Symposium on Combinatorial Pattern Matching, pp. 173\u2013182 (2007)","DOI":"10.1007\/978-3-540-73437-6_19"},{"key":"9950_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":"9950_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":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09950-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09950-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09950-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T00:39:56Z","timestamp":1608338396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09950-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9950"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09950-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"assertion":[{"value":"20 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}