{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:44Z","timestamp":1773481904995,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00778-009-0172-z","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T15:26:04Z","timestamp":1259594764000},"page":"3-20","source":"Crossref","is-referenced-by-count":129,"title":["Methods for finding frequent items in data streams"],"prefix":"10.1007","volume":"19","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marios","family":"Hadjieleftheriou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,1]]},"reference":[{"key":"172_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: ACM Symposium on Theory of Computing, pp. 20\u201329, 1996. Journal version in Journal of Computer and System Sciences 58, 137\u2013147 (1999)","DOI":"10.1006\/jcss.1997.1545"},{"key":"172_CR2","doi-asserted-by":"crossref","unstructured":"Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: ACM Principles of Database Systems (2004)","DOI":"10.1145\/1055558.1055598"},{"key":"172_CR3","doi-asserted-by":"crossref","unstructured":"Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: ACM Principles of Database Systems, pp. 1\u201316 (2002)","DOI":"10.1145\/543613.543615"},{"key":"172_CR4","doi-asserted-by":"crossref","unstructured":"Bandi, N., Metwally, A., Agrawal, D., Abbadi, A.E.: Fast data stream algorithms using associative memories. In: ACM SIGMOD International Conference on Management of Data (2007)","DOI":"10.1145\/1247480.1247510"},{"key":"172_CR5","unstructured":"Bhattacharrya, S., Madeira, A., Muthukrishnan, S., Ye, T.: How to scalably skip past streams. In: Scalable Stream Processing Systems (SSPS) Workshop with ICDE (2007)"},{"key":"172_CR6","doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: ACM-SIAM Symposium on Discrete Algorithms (2006)","DOI":"10.1145\/1109557.1109634"},{"key":"172_CR7","unstructured":"Blum, A., Gibbons, P., Song, D., Venkataraman, S.: New streaming algorithms for fast detection of superspreaders. Technical Report IRP-TR-04-23, Intel Research (2004)"},{"key":"172_CR8","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Bounds for frequency estimation of packet streams. In: SIROCCO (2003)"},{"key":"172_CR9","unstructured":"Boyer, R.S., Moore, J.: A fast majority vote algorithm. Technical Report ICSCA-CMP-32, Institute for Computer Science, University of Texas (1981)"},{"key":"172_CR10","doi-asserted-by":"crossref","unstructured":"Boyer, R.S., Moore, J.S.: MJRTY\u2014a fast majority vote algorithm. In: Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, pp. 105\u2013117. Kluwer, Dordrecht (1991)","DOI":"10.1007\/978-94-011-3488-0_5"},{"key":"172_CR11","doi-asserted-by":"crossref","unstructured":"Bu, T., Cao, J., Chen, A., Lee, P.P.C.: A fast and compact method for unveiling significant patterns in high speed networks. In: IEEE INFOCOMM (2007)","DOI":"10.1109\/INFCOM.2007.220"},{"key":"172_CR12","unstructured":"Cand\u00e8s, E., Tao, T.: Near optimal signal recovery from random projections and universal encoding strategies. Technical Report math.CA\/0410542, arXiv. http:\/\/arxiv.org\/abs\/math.CA\/0410542 (2004)"},{"key":"172_CR13","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A.: A near-optimal algorithm for computing the entropy of a stream. In: ACM-SIAM Symposium on Discrete Algorithms (2007)"},{"key":"172_CR14","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Procedings of the International Colloquium on Automata, Languages and Programming (ICALP) (2002)","DOI":"10.1007\/3-540-45465-9_59"},{"key":"172_CR15","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Johnson, T., Spatscheck, O., Srivastava, D.: Holistic UDAFs at streaming speeds. In: ACM SIGMOD International Conference on Management of Data, pp. 35\u201346 (2004)","DOI":"10.1145\/1007568.1007575"},{"key":"172_CR16","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Space- and time-efficient deterministic algorithms for biased quantiles over data streams. In: ACM Principles of Database Systems (2006)","DOI":"10.1145\/1142351.1142389"},{"key":"172_CR17","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Tirthapura, S.: Exponentially decayed aggregates on data streams. In: IEEE International Conference on Data Engineering (2008)","DOI":"10.1109\/ICDE.2008.4497562"},{"key":"172_CR18","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: What\u2019s new: Finding significant differences in network data streams. In: Proceedings of IEEE Infocom (2004)","DOI":"10.1109\/TNET.2005.860096"},{"issue":"1","key":"172_CR19","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode G., Muthukrishnan S.: An improved data stream summary: the count-\u00a0min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"172_CR20","doi-asserted-by":"crossref","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. In: ACM-SIAM Symposium on Discrete Algorithms (2002)","DOI":"10.1137\/S0097539701398363"},{"key":"172_CR21","doi-asserted-by":"crossref","unstructured":"Demaine, E., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: European Symposium on Algorithms (ESA) (2002)","DOI":"10.1007\/3-540-45749-6_33"},{"key":"172_CR22","unstructured":"Dobra, A., Rusu, F.: Statistical analysis of sketch estimators. In: ACM SIGMOD International Conference on Management of Data (2007)"},{"key":"172_CR23","unstructured":"Donoho, D.: Compressed sensing. http:\/\/www-stat.stanford.edu\/~donoho\/Reports\/2004\/CompressedSensing091604.pdf , Unpublished Manuscript (2004)"},{"issue":"4","key":"172_CR24","first-page":"376","volume":"3","author":"M. Fischer","year":"1982","unstructured":"Fischer M., Salzburg S.: Finding a majority among n votes: solution to problem 81-5. J. Algorithms 3(4), 376\u2013379 (1982)","journal-title":"J. Algorithms"},{"key":"172_CR25","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.: How to summarize the universe: dynamic maintenance of quantiles. In: International Conference on Very Large Data Bases, pp. 454\u2013465 (2002)","DOI":"10.1016\/B978-155860869-6\/50047-0"},{"key":"172_CR26","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. In: ACM SIGMOD International Conference on Management of Data (2001)","DOI":"10.1145\/375663.375670"},{"issue":"1","key":"172_CR27","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/15427951.2004.10129079","volume":"1","author":"M. Henzinger","year":"2003","unstructured":"Henzinger M.: Algorithmic challenges in search engines. Internet Math. 1(1), 115\u2013126 (2003)","journal-title":"Internet Math."},{"key":"172_CR28","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Shrivastava, N., Suri, S., Toth, C.: Adaptive spatial partitioning for multidimensional data streams. In: ISAAC (2004)","DOI":"10.1007\/978-3-540-30551-4_46"},{"key":"172_CR29","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., McGregor, A., Muthukrishnan, S., Vee, E.: Estimating statistical aggregates on probabilistic data streams. In: ACM Principles of Database Systems (2007)","DOI":"10.1145\/1265530.1265565"},{"key":"172_CR30","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"R. Karp","year":"2003","unstructured":"Karp R., Papadimitriou C., Shenker S.: A simple algorithm for finding frequent elements in sets and bags. ACM Trans. Database Syst. 28, 51\u201355 (2003)","journal-title":"ACM Trans. Database Syst."},{"key":"172_CR31","unstructured":"Kollios, G., Byers, J., Considine, J., Hadjieleftheriou, M., Li, F.: Robust aggregation in sensor networks. IEEE Data Engineering Bulletin 28(1) (2005)"},{"key":"172_CR32","doi-asserted-by":"crossref","unstructured":"Lee, L., Ting, H.: A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In: ACM Principles of Database Systems (2006)","DOI":"10.1145\/1142351.1142393"},{"key":"172_CR33","doi-asserted-by":"crossref","unstructured":"Manku, G., Motwani, R.: Approximate frequency counts over data streams. In: International Conference on Very Large Data Bases, pp. 346\u2013357 (2002)","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"172_CR34","unstructured":"Manku, G.S.: Frequency counts over data streams. http:\/\/www.cse.ust.hk\/vldb2002\/VLDB2002-proceedings\/slides\/S10P03slides.pdf (2002)"},{"key":"172_CR35","doi-asserted-by":"crossref","unstructured":"Metwally, A., Agrawal, D., Abbadi, A.E.: Efficient computation of frequent and top-k elements in data streams. In: International Conference on Database Theory (2005)","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"172_CR36","doi-asserted-by":"crossref","unstructured":"Metwally, A., Agrawal, D., Abbadi, A.E.: Why go logarithmic if we can go linear?: towards effective distinct counting of search traffic. In: International Conference on Extending Database Technology (2008)","DOI":"10.1145\/1353343.1353418"},{"key":"172_CR37","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J. Misra","year":"1982","unstructured":"Misra J., Gries D.: Finding repeated elements. Sci Comput Program 2, 143\u2013152 (1982)","journal-title":"Sci Comput Program"},{"key":"172_CR38","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. In: ACM-SIAM Symposium on Discrete Algorithms (2003)"},{"issue":"4","key":"172_CR39","first-page":"277","volume":"13","author":"R. Pike","year":"2005","unstructured":"Pike R., Dorward S., Griesemer R., Quinlan S.: Interpreting the data: parallel analysis with sawzall. Dyn. Grids Worldw. Comput. 13(4), 277\u2013298 (2005)","journal-title":"Dyn. Grids Worldw. Comput."},{"issue":"5","key":"172_CR40","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1109\/TNET.2007.896150","volume":"15","author":"R. Schweller","year":"2007","unstructured":"Schweller R., Li Z., Chen Y., Gao Y., Gupta A., Zhang Y., Dinda P.A., Kao M.-Y., Memik G.: Reversible sketches: enabling monitoring and analysis over high-speed data streams. IEEE Trans. Netw. 15(5), 1059\u20131072 (2007)","journal-title":"IEEE Trans. Netw."},{"key":"172_CR41","doi-asserted-by":"crossref","unstructured":"Shrivastava, N., Buragohain, C., Agrawal, D., Suri, S.: Medians and beyond: new aggregation techniques for sensor networks. In: ACM SenSys (2004)","DOI":"10.1145\/1031495.1031524"},{"key":"172_CR42","unstructured":"Thorup, M.: Even strongly universal hashing is pretty fast. In: ACM-SIAM Symposium on Discrete Algorithms (2000)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-009-0172-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-009-0172-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-009-0172-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T14:26:01Z","timestamp":1739456761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-009-0172-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["172"],"URL":"https:\/\/doi.org\/10.1007\/s00778-009-0172-z","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,1]]}}}