{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:12:25Z","timestamp":1761973945123,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_56","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T04:31:28Z","timestamp":1368765088000},"page":"638-650","source":"Crossref","is-referenced-by-count":6,"title":["How to Catch L 2-Heavy-Hitters on Sliding Windows"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Gelles","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"56_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-47534-9","volume-title":"Data streams: models and algorithms","author":"C.C. Aggarwal","year":"2007","unstructured":"Aggarwal, C.C.: Data streams: models and algorithms. Springer, New York (2007)"},{"issue":"1","key":"56_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. Journal of Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"56_CR3","doi-asserted-by":"crossref","unstructured":"Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: PODS 2004, pp. 286\u2013296 (2004)","DOI":"10.1145\/1055558.1055598"},{"key":"56_CR4","doi-asserted-by":"crossref","unstructured":"Bandi, N., Agrawal, D., Abbadi, A.E.: Fast algorithms for heavy distinct hitters using associative memories. In: ICDSC 2007, p. 6 (2007)","DOI":"10.1109\/ICDCS.2007.110"},{"key":"56_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45726-7_1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., Trevisan, L.: Counting distinct elements in a data stream. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 1\u201310. Springer, Heidelberg (2002)"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: FOCS 2002, pp. 209\u2013218 (2002)","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"56_CR7","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA 2002, pp. 623\u2013632 (2002)"},{"key":"56_CR8","doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: SODA 2006, pp. 708\u2013713 (2006)","DOI":"10.1145\/1109557.1109634"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R.: Smooth histograms for sliding windows. In: FOCS 2007, pp. 283\u2013293 (2007)","DOI":"10.1109\/FOCS.2007.4389500"},{"key":"56_CR10","unstructured":"Braverman, V., Gelles, R., Ostrovsky, R.: How to catch L 2-heavy-hitters on sliding windows (2010), http:\/\/arxiv.org\/abs\/1012.3130"},{"issue":"3","key":"56_CR11","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"A.Z. Broder","year":"2000","unstructured":"Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. Journal of Computer and System Sciences\u00a060(3), 630\u2013659 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"8-13","key":"56_CR12","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1016\/S0169-7552(97)00031-7","volume":"29","author":"A.Z. Broder","year":"1997","unstructured":"Broder, A.Z., Glassman, S.C., Manasse, M.S., Zweig, G.: Syntactic clustering of the web. Computer Networks and ISDN Systems\u00a029(8-13), 1157\u20131166 (1997)","journal-title":"Computer Networks and ISDN Systems"},{"key":"56_CR13","unstructured":"Broder, A.: On the resemblance and containment of documents. In: Proceedings of the Compression and Complexity of Sequences 1997, pp. 21\u201329 (1997)"},{"key":"56_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 693\u2013703. Springer, Heidelberg (2002)"},{"issue":"3","key":"56_CR15","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences\u00a055(3), 441\u2013453 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"56_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jalgor.2005.01.006","volume":"59","author":"E. Cohen","year":"2006","unstructured":"Cohen, E., Strauss, M.J.: Maintaining time-decaying stream aggregates. Journal of Algorithms\u00a059(1), 19\u201336 (2006)","journal-title":"Journal of Algorithms"},{"key":"56_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-24698-5_7","volume-title":"LATIN 2004: Theoretical Informatics","author":"G. Cormode","year":"2004","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: The count-min sketch and its applications. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 29\u201338. Springer, Heidelberg (2004)"},{"issue":"2","key":"56_CR18","doi-asserted-by":"crossref","first-page":"1530","DOI":"10.14778\/1454159.1454225","volume":"1","author":"G. Cormode","year":"2008","unstructured":"Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. Proc. VLDB Endow.\u00a01(2), 1530\u20131541 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"56_CR19","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Finding hierarchical heavy hitters in data streams. In: VLDB 2003, pp. 464\u2013475 (2003)","DOI":"10.1016\/B978-012722442-8\/50048-3"},{"issue":"1","key":"56_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1145\/1061318.1061325","volume":"30","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: What\u2019s hot and what\u2019s not: tracking most frequent items dynamically. ACM Trans. Database Syst.\u00a030(1), 249\u2013278 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"56_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/3-540-45749-6_31","volume-title":"Algorithms - ESA 2002","author":"M. Datar","year":"2002","unstructured":"Datar, M., Muthukrishnan, S.: Estimating rarity and similarity over data stream windows. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 323\u2013334. Springer, Heidelberg (2002)"},{"key":"56_CR22","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows (extended abstract). In: SODA 2002, pp. 635\u2013644 (2002)"},{"key":"56_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-45749-6_33","volume-title":"Algorithms - ESA 2002","author":"E.D. Demaine","year":"2002","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 348\u2013360. Springer, Heidelberg (2002)"},{"issue":"3","key":"56_CR24","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1145\/859716.859719","volume":"21","author":"C. Estan","year":"2003","unstructured":"Estan, C., Varghese, G.: New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Trans. Comput. Syst.\u00a021(3), 270\u2013313 (2003)","journal-title":"ACM Trans. Comput. Syst."},{"key":"56_CR25","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting. In: FOCS 1983, pp. 76\u201382 (1983)","DOI":"10.1109\/SFCS.1983.46"},{"key":"56_CR26","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B., Tirthapura, S.: Estimating simple functions on the union of data streams. In: SPAA 2001, pp. 281\u2013291 (2001)","DOI":"10.1145\/378580.378687"},{"key":"56_CR27","doi-asserted-by":"crossref","unstructured":"Golab, L., DeHaan, D., Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Identifying frequent items in sliding windows over on-line packet streams. In: IMC 2003, pp. 173\u2013178 (2003)","DOI":"10.1145\/948205.948227"},{"key":"56_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/978-3-540-78773-0_60","volume-title":"LATIN 2008: Theoretical Informatics","author":"R.Y.S. Hung","year":"2008","unstructured":"Hung, R.Y.S., Ting, H.F.: Finding heavy hitters over the sliding window of a weighted data stream. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 699\u2013710. Springer, Heidelberg (2008)"},{"issue":"7","key":"56_CR29","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.ipl.2009.01.027","volume":"110","author":"R.Y. Hung","year":"2010","unstructured":"Hung, R.Y., Lee, L.K., Ting, H.: Finding frequent items over sliding windows with constant update time. Information Processing Letters\u00a0110(7), 257\u2013260 (2010)","journal-title":"Information Processing Letters"},{"key":"56_CR30","unstructured":"Indyk, P.: A small approximately min-wise independent family of hash functions. In: SODA 1999, pp. 454\u2013456 (1999)"},{"key":"56_CR31","unstructured":"Indyk, P.: Heavy hitters and sparse approximations, lecture notes (2009), http:\/\/people.csail.mit.edu\/indyk\/Rice\/lec4.pdf"},{"key":"56_CR32","doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.: Optimal approximations of the frequency moments of data streams. In: STOC 2005, pp. 202\u2013208 (2005)","DOI":"10.1145\/1060590.1060621"},{"key":"56_CR33","doi-asserted-by":"crossref","unstructured":"Jin, C., Qian, W., Sha, C., Yu, J.X., Zhou, A.: Dynamically maintaining frequent items over a data stream. In: CIKM 2003, pp. 287\u2013294 (2003)","DOI":"10.1145\/956915.956918"},{"key":"56_CR34","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: PODS 2010, pp. 41\u201352 (2010)","DOI":"10.1145\/1807085.1807094"},{"key":"56_CR35","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"R.M. Karp","year":"2003","unstructured":"Karp, R.M., Shenker, S., Papadimitriou, C.H.: 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":"56_CR36","doi-asserted-by":"crossref","unstructured":"Lee, L.K., Ting, H.F.: A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In: PODS 2006, pp. 290\u2013297 (2006)","DOI":"10.1145\/1142351.1142393"},{"key":"56_CR37","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Motwani, R.: Approximate frequency counts over data streams. In: VLDB 2002, pp. 346\u2013357 (2002)","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"56_CR38","unstructured":"Open problems in data streams and related topics. IITK Workshop on Algrithms for Data Streams 2006 (2006), compiled and edited by McGregor, A."},{"key":"56_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-540-30570-5_27","volume-title":"Database Theory - ICDT 2005","author":"A. Metwally","year":"2005","unstructured":"Metwally, A., Agrawal, D., El Abbadi, A.: Efficient computation of frequent and top-k elements in data streams. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, pp. 398\u2013412. Springer, Heidelberg (2005)"},{"key":"56_CR40","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Now Publishers Inc. (2005)","DOI":"10.1561\/0400000002"},{"key":"56_CR41","unstructured":"Nie, G., Lu, Z.: Approximate frequency counts in sliding window over data stream. In: Canadian Conference on Electrical and Computer Engineering, pp. 2232\u20132236 (2005)"},{"key":"56_CR42","doi-asserted-by":"crossref","unstructured":"Saks, M., Sun, X.: Space lower bounds for distance approximation in the data stream model. In: STOC 2002, pp. 360\u2013369 (2002)","DOI":"10.1145\/509961.509963"},{"key":"56_CR43","doi-asserted-by":"crossref","unstructured":"Sen, S., Wang, J.: Analyzing peer-to-peer traffic across large networks. In: IMW 2002, pp. 137\u2013150. ACM (2002)","DOI":"10.1145\/637201.637222"},{"key":"56_CR44","doi-asserted-by":"crossref","unstructured":"Tirthapura, S., Woodruff, D.P.: A general method for estimating correlated aggregates over a data stream. In: International Conference on Data Engineering, pp. 162\u2013173 (2012)","DOI":"10.1109\/ICDE.2012.62"},{"key":"56_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, L., Guan, Y.: Frequency estimation over sliding windows. In: International Conference on Data Engineering, pp. 1385\u20131387 (2008)","DOI":"10.1109\/ICDE.2008.4497564"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_56","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T10:26:28Z","timestamp":1746008788000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}