{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T03:19:15Z","timestamp":1771125555471,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["LO 748\/13-1"],"award-info":[{"award-number":["LO 748\/13-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the sliding window streaming model the goal is to compute an output value that only depends on the last<jats:italic>n<\/jats:italic>symbols from the data stream. Thereby, only space sublinear in the window size<jats:italic>n<\/jats:italic>should be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instant<jats:italic>t<\/jats:italic>, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called \u201cstrict correctness\u201d in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption.<\/jats:p>","DOI":"10.1007\/s00224-020-10000-1","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T12:05:02Z","timestamp":1597406702000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Derandomization for Sliding Window Algorithms with Strict Correctness\u2217"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0775-7781","authenticated-orcid":false,"given":"Moses","family":"Ganardi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hucke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"10000_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, C.C.: Data streams - models and algorithms springer (2007)","DOI":"10.1007\/978-0-387-47534-9"},{"issue":"1","key":"10000_CR2","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. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"10000_CR3","doi-asserted-by":"crossref","unstructured":"Andrade, H.C.M., Gedik, B., Turaga, D.S.: Fundamentals of stream processing: application design, systems, and analytics cambridge university press (2014)","DOI":"10.1017\/CBO9781139058940"},{"key":"10000_CR4","doi-asserted-by":"crossref","unstructured":"Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows (2004)","DOI":"10.1145\/1055558.1055598"},{"key":"10000_CR5","doi-asserted-by":"crossref","unstructured":"Babcock, B., Datar, M., Motwani, R., O\u2019Callaghan, L.: Maintaining variance and k-medians over data stream windows. In: Proceedings of PODS 2003, pages 234\u2013243 ACM (2003)","DOI":"10.1145\/773153.773176"},{"key":"10000_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2012.12.028","volume":"494","author":"A Babu","year":"2013","unstructured":"Babu, A., Limaye, N., Radhakrishnan, J., Varma, G.: Streaming algorithms for language recognition problems. Theor. Comput. Sci. 494, 13\u201323 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10000_CR7","doi-asserted-by":"publisher","first-page":"2072","DOI":"10.1007\/s00453-018-0524-4","volume":"81","author":"R Ben-Basat","year":"2019","unstructured":"Ben-Basat, R., Einziger, G., Friedman, R., Kassner, Y.: Succinct summing over sliding windows. Algorithmica 81(5), 2072\u20132091 (2019)","journal-title":"Algorithmica"},{"key":"10000_CR8","doi-asserted-by":"crossref","unstructured":"Braverman, V., Sliding window algorithms. In: Encyclopedia of Algorithms, pages 2006\u20132011. Springer (2016)","DOI":"10.1007\/978-1-4939-2864-4_797"},{"issue":"1","key":"10000_CR9","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.jcss.2011.04.004","volume":"78","author":"V Braverman","year":"2012","unstructured":"Braverman, V., Ostrovsky, R., Zaniolo, C.: Optimal sampling from sliding windows. J. Comput. Syst. Sci. 78(1), 260\u2013272 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"10000_CR10","doi-asserted-by":"crossref","unstructured":"Chan, H., Lam, T.W., Lee, L., Pan, J., Ting, H., Zhang, Q.: Edit distance to monotonicity in sliding windows. In: Proceedings of ISAAC 2011, volume 7074 of Lecture Notes in Computer Science, pages 564\u2013573 Springer (2011)","DOI":"10.1007\/978-3-642-25591-5_58"},{"key":"10000_CR11","doi-asserted-by":"crossref","unstructured":"Crouch, M.S., McGregor, A., Stubbsm, D.: Dynamic graphs in the sliding-window model. In: Proceedings of ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 337\u2013348 Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_29"},{"issue":"6","key":"10000_CR12","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM Journal on Computing 31(6), 1794\u20131813 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"10000_CR13","unstructured":"Ganardi, M., Hucke, D., K\u00f6nig, D., Lohrey, M., Mamouras, K.: Automata theory on sliding windows. In: Proceedings of STACS 2018, volume 96 of LIPIcs, pages 31:1\u201331:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. to appear (2018)"},{"key":"10000_CR14","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Querying regular languages over sliding windows. In: Proceedings of FSTTCS 2016, volume 65 of LIPIcs, pages 18:1\u201318:14 Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)","DOI":"10.1007\/s00224-020-10000-1"},{"key":"10000_CR15","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Randomized sliding window algorithms for regular languages. In: Proceedings of ICALP 2018, volume 107 of LIPIcs, pages 127:1\u2013127:13 Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"10000_CR16","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Sliding windows over context-free languages (2018)"},{"key":"10000_CR17","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Derandomization for Sliding Window Algorithms with Strict Correctness. In: Proceedings of CSR 2019, volume 11532 of Lecture Notes in Computer Science, pages 237\u2013249 Springer International Publishing (2019)","DOI":"10.1007\/978-3-030-19955-5_21"},{"key":"10000_CR18","doi-asserted-by":"crossref","unstructured":"Golab, L., O\u0307zsu, M.T.: Processing sliding window multi-joins in continuous queries over data streams. In: Proceedings of VLDB 2003, pages 500\u2013511 Morgan Kaufmann (2003)","DOI":"10.1016\/B978-012722442-8\/50051-3"},{"issue":"1","key":"10000_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Comput. Complex. 8(1), 21\u201349 (1999)","journal-title":"Comput. Complex."},{"key":"10000_CR20","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"10000_CR21","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. In: Proceedings of STOC 1995, pages 103\u2013111 ACM (1995)","DOI":"10.1145\/225058.225093"},{"key":"10000_CR22","unstructured":"Paz, A.: Introduction to probabilistic automata academic press (1971)"},{"issue":"3","key":"10000_CR23","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"MO Rabin","year":"1963","unstructured":"Rabin, M. O.: Probabilistic automata. Inf. Control. 6(3), 230\u2013245 (1963)","journal-title":"Inf. Control."},{"key":"10000_CR24","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: Toward a unified measure of complexity. In: Proceedings of FOCS 1977, pages 222\u2013227 IEEE Computer Society (1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"10000_CR25","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Lower Bounds by Probabilistic Arguments (Extended Abstract). In: Proceedings of FOCS 1983, pages 420\u2013428 IEEE Computer Society (1983)","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10000-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10000-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10000-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T23:03:58Z","timestamp":1667775838000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10000-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10000"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10000-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,14]]},"assertion":[{"value":"14 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}