{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:49:58Z","timestamp":1787496598462,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540291183","type":"print"},{"value":"9783540319511","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_66","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T08:46:24Z","timestamp":1128588384000},"page":"746-757","source":"Crossref","is-referenced-by-count":2,"title":["Finding Frequent Patterns in a String in Sublinear Time"],"prefix":"10.1007","author":[{"given":"Petra","family":"Berenbrink","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Funda","family":"Ergun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom","family":"Friedetzky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"66_CR1","doi-asserted-by":"crossref","unstructured":"Batu, T., Ergun, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A sublinear algorithm for weakly approximating edit distance. In: STOC 2003, pp. 316\u2013324 (2003)","DOI":"10.1145\/780542.780590"},{"key":"66_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"issue":"4","key":"66_CR3","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"key":"66_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1989","unstructured":"Hagerup, T., R\u00fcb, C.: A Guided Tour of Chernoff Bounds. Information Processing Letters\u00a033, 305\u2013308 (1989)","journal-title":"Information Processing Letters"},{"key":"66_CR5","unstructured":"Indyk, P., Koudas, N., Muthukrishnan, S.: Identifying Representative Trends in Massive Time Series Data Sets Using Sketches. In: Proc. VLDB 2000, pp. 363\u2013372 (2000)"},{"key":"66_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"R. Karp","year":"2003","unstructured":"Karp, R., Shenker, S., Papadimitriou, C.: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst.\u00a028, 51\u201355 (2003)","journal-title":"ACM Trans. Database Syst."},{"key":"66_CR7","doi-asserted-by":"crossref","unstructured":"Lachish, O., Newman, I.: Periodicity Testing. In: Proc. RANDOM 2005 (2005) (to appear)","DOI":"10.1007\/11538462_31"},{"key":"66_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"66_CR9","doi-asserted-by":"crossref","unstructured":"Ron, D.: Property Testing (A Tutorial). Handbook of Randomization (2000)","DOI":"10.1007\/978-1-4615-0013-1_15"},{"issue":"2","key":"66_CR10","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust Characterization of Polynomials with Applications to Program Testing. SIAM Journal of Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_66.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:50:49Z","timestamp":1605624649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/11561071_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}