{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:38Z","timestamp":1725600338174},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_14","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T05:20:39Z","timestamp":1313126439000},"page":"158-170","source":"Crossref","is-referenced-by-count":3,"title":["Periodicity and Cyclic Shifts via Linear Sketches"],"prefix":"10.1007","author":[{"given":"Michael S.","family":"Crouch","sequence":"first","affiliation":[]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"14_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci.\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: The count-min sketch and its applications. J. Algorithms\u00a055, 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"14_CR3","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":"14_CR4","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., Saglam, M.: Periodicity in streams. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010, LNCS, vol.\u00a06302, pp. 545\u2013559. Springer, Heidelberg (2010)"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Muthukrishnan, S., Sahinalp, S.C.: Periodicity testing with sublinear samples and space. ACM Transactions on Algorithms\u00a06(2) (2010)","DOI":"10.1145\/1721837.1721859"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse fourier representations via sampling. In: STOC, pp. 152\u2013161 (2002)","DOI":"10.1145\/509907.509933"},{"key":"14_CR7","volume-title":"An Introduction to The Theory of Numbers (Fourth Edition)","author":"G.H. Hardy","year":"1960","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to The Theory of Numbers (Fourth Edition). Oxford University Press, Oxford (1960)"},{"issue":"3","key":"14_CR8","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":"14_CR9","unstructured":"Indyk, P., Koudas, N., Muthukrishnan, S.: Identifying representative trends in massive time series data sets using sketches. In: VLDB, pp. 363\u2013372 (2000)"},{"key":"14_CR10","unstructured":"Indyk, P., McGregor, A.: Declaring independence via the sketching of sketches. In: SODA, pp. 737\u2013745 (2008)"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: On the exact space complexity of sketching and streaming small norms. In: SODA, pp. 1161\u20131178 (2010)","DOI":"10.1137\/1.9781611973075.93"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: PODS, pp. 41\u201352 (2010)","DOI":"10.1145\/1807085.1807094"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Monemizadeh, M., Woodruff, D.P.: 1-pass relative-error $\\text{L}_p$ -sampling with applications. In: SODA (2010)","DOI":"10.1137\/1.9781611973075.92"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science\u00a01(2) (2005)","DOI":"10.1561\/0400000002"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012, 449\u2013461 (1992)","journal-title":"Combinatorica"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: FOCS, pp. 315\u2013323 (2009)","DOI":"10.1109\/FOCS.2009.11"},{"issue":"5","key":"14_CR17","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput.\u00a026(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."}],"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-22935-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T14:00:43Z","timestamp":1686232843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}