{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:05Z","timestamp":1787340485580,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>In the streaming model, elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and nontrivial task in this model. These tasks become even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. In their pioneering paper, Datar et al. [SIAM J. Comput., 31 (2002), pp. 1794\u20131813] presented the exponential histogram, an effective method for estimating statistics on sliding windows. In this paper we present a novel smooth histogram method that is more general and achieves stronger bounds than the exponential histogram. In particular, the smooth histogram method improves the approximation error rate obtained via exponential histograms. Furthermore, the smooth histogram method not only captures and improves multiple previous results on sliding windows but also extends the class of functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: $L_p$ norms, frequency moments, the length of the increasing subsequence, and the geometric mean.<\/jats:p>","DOI":"10.1137\/090749281","type":"journal-article","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T18:21:00Z","timestamp":1268418060000},"page":"2113-2131","source":"Crossref","is-referenced-by-count":7,"title":["Effective Computations on Sliding Windows"],"prefix":"10.1137","volume":"39","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,3,12]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan,\n                      Geometric Approximation via Coresets\n                      , in Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ. 52, Cambridge University Press, Cambridge, UK, 2005, pp. 1\u201330.","DOI":"10.1017\/9781009701259.002"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"C. C. Aggarwal,\n                      Data Streams: Models and Algorithms (Advances in Database Systems)\n                      , Springer-Verlag, New York, 2006.","DOI":"10.1007\/978-0-387-47534-9"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Arasu and G. S. Manku,\n                      Approximate counts and quantiles over sliding windows\n                      , in Proceedings of the 23rd ACM SIGMOD-SIGART Symposium on Principles of Database Systems, Paris, 2004, pp. 286\u2013296.","DOI":"10.1145\/1055558.1055598"},{"key":"R5","unstructured":"B. Babcock, M. Datar, and R. Motwani,\n                      Sampling from a moving window over streaming data\n                      , in Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 2002, pp. 633\u2013634."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"B. Babcock, M. Datar, R. Motwani, and L. O'Callaghan,\n                      Maintaining variance and k-medians over data stream windows\n                      , in Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, San Diego, 2003, pp. 234\u2013243.","DOI":"10.1145\/773153.773176"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. Bhuvanagiri, S. Ganguly, D. Kesh, and C. Saha,\n                      Simpler algorithm for estimating frequency moments of data streams\n                      , in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, 2006, pp. 708\u2013713.","DOI":"10.1145\/1109557.1109634"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"V. Braverman, R. Ostrovsky, and C. Zaniolo,\n                      Optimal sampling from sliding windows\n                      , in Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Providence, 2009, pp. 147\u2013156.","DOI":"10.1145\/1559795.1559818"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, S. Khot, and X. Sun,\n                      Near-optimal lower bounds on the multi-party communication complexity of set disjointness\n                      , in Proceedings of the 18th IEEE Conference on Computational Complexity, Aarhus, Denmark, 2003, pp. 107\u2013117.","DOI":"10.1109\/CCC.2003.1214414"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195906001975"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.032"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Y. Chi, H. Wang, P. S. Yu, and R. R. Muntz,\n                      Moment: Maintaining closed frequent itemsets over a stream sliding window\n                      , in Proceedings of the Fourth IEEE International Conference on Data Mining, Brighton, UK, 2004, pp. 59\u201366.","DOI":"10.1109\/ICDM.2004.10084"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-036X.1996.tb00036.x"},{"key":"R15","unstructured":"D. Coppersmith and R. Kumar,\n                      An improved data stream algorithm for frequency moments\n                      , in Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 2004, pp. 151\u2013156."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"G. Cormode, S. Tirthapura, and B. Xu,\n                      Time-decaying sketches for sensor data aggregation\n                      , in Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Beijing, 2007, pp. 215\u2013224.","DOI":"10.1145\/1281100.1281132"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Datar and S. Muthukrishnan,\n                      Estimating rarity and similarity over data stream windows\n                      , in Proceedings of the 10th European Symposium on Algorithms, Rome, 2002, pp. 323\u2013334.","DOI":"10.1007\/3-540-45749-6_31"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1105-2"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"S. Ganguly,\n                      Estimating frequency moments of data streams using random linear combinations\n                      , in Proceedings of the APPROX-RANDOM 2004, Cambridge, MA, 2004, pp. 369\u2013380.","DOI":"10.1007\/978-3-540-27821-4_33"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons and S. Tirthapura,\n                      Distributed streams algorithms for sliding windows\n                      , in Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures, Winnipeg, Manitoba, Canada, 2002, pp. 63\u201372.","DOI":"10.1145\/564870.564880"},{"key":"R22","unstructured":"P. Gopalan, T. S. Jayram, R. Krauthgamer, and R. Kumar,\n                      Estimating the sortedness of a data stream\n                      , in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms 2007, New Orleans, pp. 318\u2013327."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"S. Guha, D. Gunopulos, and N. Koudas,\n                      Correlating synchronous and asynchronous data streams\n                      , in Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, 2003, pp. 529\u2013534.","DOI":"10.1145\/956750.956814"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"D. Gusfield,\n                      Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology\n                      , Cambridge University Press, Cambridge, UK, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"P. Indyk and D. Woodruff,\n                      Optimal approximations of the frequency moments of data streams\n                      , in Proceedings of the 37th ACM Symposium on Theory of Computing, Baltimore, 2005, pp. 202\u2013208.","DOI":"10.1145\/1060590.1060621"},{"key":"R27","unstructured":"D. M. Kane, J. Nelson, and D. P. Woodruff,\n                      Revisiting Norm Estimation in Data Streams\n                      , http:\/\/www.mit.edu\/~minilek\/papers\/norms.pdf (2008)."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"L. K. Lee and H. F. Ting,\n                      Maintaining significant stream statistics over sliding windows\n                      , in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, 2006, pp. 724\u2013732.","DOI":"10.1145\/1109557.1109636"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"L. K. Lee and H. F. Ting,\n                      A simpler and more efficient deterministic scheme for finding frequent items over sliding windows\n                      , in Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Chicago, 2006, pp. 290\u2013297.","DOI":"10.1145\/1142351.1142393"},{"key":"R30","first-page":"2006","volume":"11","author":"Liben-Nowell D.","year":"2003","journal-title":"J. Comb. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1382-6905","issn-type":"print"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"P. A. Pevzner,\n                      Computational Molecular Biology\n                      , MIT Press, Cambridge, MA, 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"R33","unstructured":"X. Sun and D. P. Woodruff,\n                      The communication and streaming complexity of computing the longest common and increasing subsequences\n                      , in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 2007, pp. 336\u2013345."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"S. Tirthapura, B. Xu, and C. Busch,\n                      Sketching asynchronous streams over a sliding window\n                      , in Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, Denver, 2006, pp. 82\u201391.","DOI":"10.1145\/1146381.1146397"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090749281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:25Z","timestamp":1787337385000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090749281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090749281"],"URL":"https:\/\/doi.org\/10.1137\/090749281","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}