{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T11:10:30Z","timestamp":1790161830695,"version":"4.1.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>\n            We propose an approximate integrated approach for solving both problems of finding the most popular\n            <jats:italic>k<\/jats:italic>\n            elements, and finding frequent elements in a data stream coming from a large domain. Our solution is space efficient and reports both frequent and top-\n            <jats:italic>k<\/jats:italic>\n            elements with tight guarantees on errors. For general data distributions, our top-\n            <jats:italic>k<\/jats:italic>\n            algorithm returns\n            <jats:italic>k<\/jats:italic>\n            elements that have roughly the highest frequencies; and it uses limited space for calculating frequent elements. For realistic Zipfian data, the space requirement of the proposed algorithm for solving the exact frequent elements problem decreases dramatically with the parameter of the distribution; and for top-\n            <jats:italic>k<\/jats:italic>\n            queries, the analysis ensures that only the top-\n            <jats:italic>k<\/jats:italic>\n            elements, in the correct order, are reported. The experiments, using real and synthetic data sets, show space reductions with hardly any loss in accuracy. Having proved the effectiveness of the proposed approach through both analysis and experiments, we extend it to be able to answer continuous queries about frequent and top-\n            <jats:italic>k<\/jats:italic>\n            elements. Although the problems of incremental reporting of frequent and top-\n            <jats:italic>k<\/jats:italic>\n            elements are useful in many applications, to the best of our knowledge, no solution has been proposed.\n          <\/jats:p>","DOI":"10.1145\/1166074.1166084","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"1095-1133","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":145,"title":["An integrated efficient solution for computing frequent and top-\n            <i>k<\/i>\n            elements in data streams"],"prefix":"10.1145","volume":"31","author":[{"given":"Ahmed","family":"Metwally","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amr El","family":"Abbadi","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 9th DBPL International Conference on Data Base and Programming Languages. 1--11","author":"Arasu A."},{"key":"e_1_2_1_3_1","unstructured":"Arasu A. Babu S. and Widom J. 2003b. The CQL Continuous Query Language: Semantic foundations and query execution. Tech. rep. 2002-67. Stanford University Stanford CA.]]  Arasu A. Babu S. and Widom J. 2003b. The CQL Continuous Query Language: Semantic foundations and query execution. Tech. rep. 2002-67. Stanford University Stanford CA.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 2nd IEEE MDM International Conference on Mobile Data Management. 3--14","author":"Bonnet P."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 10th SIROCCO International Colloquium on Structural Information and Communication Complexity. 33--42","author":"Bose P."},{"key":"e_1_2_1_9_1","unstructured":"Boyer R. and Moore J. 1981. A fast majority vote algorithm. Tech. rep. 1981-32. Institute for Computing Science University of Texas Austin Austin TX.]]  Boyer R. and Moore J. 1981. A fast majority vote algorithm. Tech. rep. 1981-32. Institute for Computing Science University of Texas Austin Austin TX.]]"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 29th ICALP International Colloquium on Automata, Languages and Programming. 693--703","author":"Charikar M."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335432"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 29th VLDB International Conference on Very Large Data Bases. 464--475","author":"Cormode G."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007588"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773182"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347094"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 13th ACM SIAM Symposium on Discrete Algorithms. 635--644","author":"Datar M."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 10th ESA Annual European Symposium on Algorithms. 348--360","author":"Demaine E."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 24th VLDB International Conference on Very Large Data Bases. 299--310","author":"Fang M."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of 40th FOCS Annual Symposium on Foundations of Computer Science. 501--511","author":"Feigenbaum J."},{"key":"e_1_2_1_21_1","first-page":"376","article-title":"Finding a majority among N votes: Solution to problem 81-5","volume":"3","author":"Fischer M.","year":"1982","journal-title":"J. Algorith."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375665"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276334"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 27th VLDB International Conference on Very Large Data Bases. 79--88","author":"Gilbert A."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948227"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 29th ICALP International Colloquium on Automata, Languages and Programming. 681--692","author":"Guha S."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380841"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956815"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316217"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 21st VLDB International Conference on Very Large Data Bases. 311--322","author":"Haas P."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956918"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2%3C143::AID-RSA7%3E3.0.CO;2-V"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 20th IEEE ICDE International Conference on Data Engineering. 362--374","author":"Lin X."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 28th VLDB International Conference on Very Large Data Bases. 346--357","author":"Manku G."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304204"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 26th VLDB International Conference on Very Large Data Bases. 101--110","author":"Matias Y."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060753"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 28th VLDB International Conference on Very Large Data Bases. 358--369","author":"Zhu Y."},{"key":"e_1_2_1_47_1","unstructured":"Zipf G. 1949. Human Behavior and The Principle of Least Effort. Addison-Wesley Reading MA.]]  Zipf G. 1949. Human Behavior and The Principle of Least Effort. Addison-Wesley Reading MA.]]"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1166074.1166084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:19:23Z","timestamp":1672262363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1166074.1166084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1166074.1166084"],"URL":"https:\/\/doi.org\/10.1145\/1166074.1166084","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}