{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T16:28:54Z","timestamp":1781368134651,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642153686","type":"print"},{"value":"9783642153693","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_41","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T00:01:36Z","timestamp":1282867296000},"page":"545-559","source":"Crossref","is-referenced-by-count":16,"title":["Periodicity in Streams"],"prefix":"10.1007","author":[{"given":"Funda","family":"Ergun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hossein","family":"Jowhari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mert","family":"Sa\u011flam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: Space complexity of approximating the frequency moments. In: STOC 1996 (1996)","DOI":"10.1145\/237814.237823"},{"key":"41_CR2","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. In: SODA 2000 (2000)"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Sampling algorithms: lower bounds and applications. In: CCC 2002 (2002)","DOI":"10.1145\/380752.380810"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"Berinde, R., Cormode, G., Indyk, P., Strauss, M.: Space-optimal heavy hitters with strong error bounds. In: PODS 2009 (2009)","DOI":"10.1145\/1559795.1559819"},{"key":"41_CR5","doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: SODA 2006 (2006)","DOI":"10.1145\/1109557.1109634"},{"key":"41_CR6","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Bounds for frequency estimation of packet streams. In: Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (2003)"},{"issue":"1","key":"41_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theor. Comput. Sci.\u00a0312(1), 3\u201315 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"41_CR8","unstructured":"Cole, R., Hariharan, R.: Approximate String Matching: A Simpler Faster Algorithm. In: SODA 1998 (1998)"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: Space efficient mining of multigraph streams. In: PODS 2005, pp. 271\u2013282 (2005)","DOI":"10.1145\/1065167.1065201"},{"key":"41_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/3-540-45123-4_34","volume-title":"Combinatorial Pattern Matching","author":"A. Czumaj","year":"2000","unstructured":"Czumaj, A., G\u0105sieniec, L.: On the complexity of determining the period of a string. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 412\u2013422. Springer, Heidelberg (2000)"},{"key":"41_CR11","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: ICDM 2006 (2006)","DOI":"10.1109\/ICDM.2006.153"},{"key":"41_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-24698-5_6","volume-title":"LATIN 2004: Theoretical Informatics","author":"F. Ergun","year":"2004","unstructured":"Ergun, F., Muthukrishnan, S., Sahinalp, C.: Sublinear methods for detecting periodic trends in data streams. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 16\u201328. Springer, Heidelberg (2004)"},{"key":"41_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/11590156_24","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"S. Ganguly","year":"2005","unstructured":"Ganguly, S., Kesh, D., Saha, C.: Practical algorithms for tracking database join sizes. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 297\u2013309. Springer, Heidelberg (2005)"},{"issue":"3","key":"41_CR14","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P. Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM\u00a053(3), 307\u2013323 (2006)","journal-title":"J. ACM"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.: Optimal approximations of the frequency moments of data streams. In: STOC 2005 (2005)","DOI":"10.1145\/1060590.1060621"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Woodruff, D.: The data stream space complexity of cascaded norms. In: FOCS 2009 (2009)","DOI":"10.1109\/FOCS.2009.82"},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.: An optimal algorithm for the distinct elements problem. In: PODS 2010 (2010)","DOI":"10.1145\/1807085.1807094"},{"key":"41_CR18","first-page":"260","volume":"249","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern matching algorithms. IBM Journal of Res. and Dev.\u00a0249, 260 (1987)","journal-title":"IBM Journal of Res. and Dev."},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comp.\u00a06, 323\u2013350 (1977)","journal-title":"SIAM J. Comp."},{"key":"41_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/11538462_31","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"O. Lachish","year":"2005","unstructured":"Lachish, O., Newman, I.: Testing periodicity. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 366\u2013377. Springer, Heidelberg (2005)"},{"key":"41_CR21","series-title":"Lecture Notes in Computer Science","first-page":"173","volume-title":"Combinatorial Pattern Matching","author":"O. Lipsky","year":"2007","unstructured":"Lipsky, O., Porat, E.: Improved sketching of hamming distance with error correcting. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 173\u2013182. Springer, Heidelberg (2007)"},{"key":"41_CR22","doi-asserted-by":"crossref","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Technical Report, Cornell University (1982)","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"41_CR23","doi-asserted-by":"crossref","unstructured":"Monemizadeh, M., Woodruff, D.: 1-Pass relative-error Lp-sampling with applications. In: SODA 2010 (2010)","DOI":"10.1137\/1.9781611973075.92"},{"key":"41_CR24","unstructured":"Muthukrishnan, S.: Data stream algorithms. In: The Barbados Workshop on Computational Complexity (2009)"},{"key":"41_CR25","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: FOCS 2009 (2009)","DOI":"10.1109\/FOCS.2009.11"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:05:30Z","timestamp":1606169130000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}