{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:18:11Z","timestamp":1773886691859,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>\n            In this article, we propose a new multiscale sliding window model which differentiates data items in different time periods of the data stream, based on a reasonable monotonicity of resolution assumption. Our model, as a well-motivated extension of the sliding window model, stands halfway between the traditional all-history and time-decaying models. We also present algorithms for estimating two significant data stream statistics---\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            and Jacard's similarity coefficient---with reasonable accuracies under the new model. Our algorithms use space logarithmic in the data stream size and linear in the number of windows; they support update time logarithmic in the number of windows and independent of the accuracy required. Our algorithms are easy to implement. Experimental results demonstrate the efficiencies of our algorithms. Our techniques apply to scenarios in which universe sampling is used.\n          <\/jats:p>","DOI":"10.1145\/1189769.1189773","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1305-1334","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Maintaining stream statistics over multiscale sliding windows"],"prefix":"10.1145","volume":"31","author":[{"given":"Yishan","family":"Jiao","sequence":"first","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences and Graduate School, Chinese Academy of Sciences, Zhongguancun, Beijing, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315460"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 30th International Conference on Very Large Databases","author":"Arasu A.","unstructured":"Arasu , A. and Widom , J . 2004. Resource sharing in continuous sliding-window aggregates . In Proceedings of the 30th International Conference on Very Large Databases . Toronto, Canada, Morgan Kaufmann, 336--347. Arasu, A. and Widom, J. 2004. Resource sharing in continuous sliding-window aggregates. In Proceedings of the 30th International Conference on Very Large Databases. Toronto, Canada, Morgan Kaufmann, 336--347."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773176"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 6th International Workshop on Randomization and Approximation Techniques","author":"Bar-Yossef Z.","unstructured":"Bar-Yossef , Z. , Jayram , T. , Kumar , R. , Sivakumar , D. , and Trevisan , L . 2002. Counting distinct elements in a data stream . In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques . Cambridge, MA, Springer, 1--10. Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D., and Trevisan, L. 2002. Counting distinct elements in a data stream. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques. Cambridge, MA, Springer, 1--10."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008992.1009048"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322095"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908981"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773175"},{"key":"e_1_2_1_12_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.55"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142389"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies","author":"Cormode G.","unstructured":"Cormode , G. and Muthukrishnan , S . 2004. What's new: Finding significant differences in network data streams . In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies . Hong Kong, China, IEEE, 1534--1545. Cormode, G. and Muthukrishnan, S. 2004. What's new: Finding significant differences in network data streams. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong, China, IEEE, 1534--1545."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms","author":"Datar M.","unstructured":"Datar , M. and Muthukrishnan , S . 2002. Estimating rarity and similarity over data stream windows . In Proceedings of the 10th Annual European Symposium on Algorithms . Rome, Italy, Springer, 323--334. Datar, M. and Muthukrishnan, S. 2002. Estimating rarity and similarity over data stream windows. In Proceedings of the 10th Annual European Symposium on Algorithms. Rome, Italy, Springer, 323--334."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2003 ACM SIGMOD Workshop on Management and Processing of Data Streams","author":"Dong G.","unstructured":"Dong , G. , Han , J. , Lakshmanan , L. V. , Pei , J. , Wang , H. , and Yu , P. S . 2003. Online mining of changes from data streams: Research problems and preliminary results . In Proceedings of the 2003 ACM SIGMOD Workshop on Management and Processing of Data Streams . San Diego, CA, ACM. Dong, G., Han, J., Lakshmanan, L. V., Pei, J., Wang, H., and Yu, P. S. 2003. Online mining of changes from data streams: Research problems and preliminary results. In Proceedings of the 2003 ACM SIGMOD Workshop on Management and Processing of Data Streams. San Diego, CA, ACM."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 11th Annual European Symposium on Algorithms","author":"Durand M.","unstructured":"Durand , M. and Flajolet , P . 2003. Loglog counting of large cardinalities (extended abstract) . In Proceedings of the 11th Annual European Symposium on Algorithms . Budapest, Hungary, Springer, 605--617. Durand, M. and Flajolet, P. 2003. Loglog counting of large cardinalities (extended abstract). In Proceedings of the 11th Annual European Symposium on Algorithms. Budapest, Hungary, Springer, 605--617."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 24th Symposium on Foundations of Computer Science","author":"Flajolet P.","unstructured":"Flajolet , P. and Martin , G. N . 1983. Probabilistic counting . In Proceedings of the 24th Symposium on Foundations of Computer Science . Tucson, AZ, IEEE Computer Society, 76--82. Flajolet, P. and Martin, G. N. 1983. Probabilistic counting. In Proceedings of the 24th Symposium on Foundations of Computer Science. Tucson, AZ, IEEE Computer Society, 76--82."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564880"},{"key":"e_1_2_1_24_1","volume-title":"The Art of Programming","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1973. The Art of Programming . Addison-Wesley , Reading, MA . Knuth, D. E. 1973. The Art of Programming. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering","author":"Lin X.","unstructured":"Lin , X. , Lu , H. , Xu , J. , and Yu , J. X . 2004. Continuously maintaining quantile summaries of the most recent n elements over a data stream . In Proceedings of the 20th International Conference on Data Engineering . Boston, MA, IEEE Computer Society, 362--374. Lin, X., Lu, H., Xu, J., and Yu, J. X. 2004. Continuously maintaining quantile summaries of the most recent n elements over a data stream. In Proceedings of the 20th International Conference on Data Engineering. Boston, MA, IEEE Computer Society, 362--374."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.137"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081895"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Muthukrishnan S.","year":"2003","unstructured":"Muthukrishnan , S. 2003 . Data streams: algorithms and applications . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms . Baltimore, MD, ACM\/SIAM, 413--413. Muthukrishnan, S. 2003. Data streams: algorithms and applications. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Baltimore, MD, ACM\/SIAM, 413--413."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies","author":"Papagiannaki K.","unstructured":"Papagiannaki , K. , Taft , N. , and Diot , C . 2004. Impact of flow dynamics on traffic engineering design principles . In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies . Hong Kong, China, 2295--2306. Papagiannaki, K., Taft, N., and Diot, C. 2004. Impact of flow dynamics on traffic engineering design principles. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong, China, 2295--2306."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:09:43Z","timestamp":1672261783000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189773"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189773","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}