{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T04:51:56Z","timestamp":1778647916978,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T00:00:00Z","timestamp":1109635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:p>Most database management systems maintain statistics on the underlying relation. One of the important statistics is that of the \u201chot items\u201d in the relation: those that appear many times (most frequently, or more than some threshold). For example, end-biased histograms keep the hot items as part of the histogram and are used in selectivity estimation. Hot items are used as simple outliers in data mining, and in anomaly detection in many applications.We present new methods for dynamically determining the hot items at any time in a relation which is undergoing deletion operations as well as inserts. Our methods maintain small space data structures that monitor the transactions on the relation, and, when required, quickly output all hot items without rescanning the relation in the database. With user-specified probability, all hot items are correctly reported. Our methods rely on ideas from \u201cgroup testing.\u201d They are simple to implement, and have provable quality, space, and time guarantees. Previously known algorithms for this problem that make similar quality and performance guarantees cannot handle deletions, and those that handle deletions cannot make similar guarantees without rescanning the database. Our experiments with real and synthetic data show that our algorithms are accurate in dynamically tracking the hot items independent of the rate of insertions and deletions.<\/jats:p>","DOI":"10.1145\/1061318.1061325","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"249-278","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":192,"title":["What's hot and what's not: tracking most frequent items dynamically"],"prefix":"10.1145","volume":"30","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"Rutgers University, Murray Hill, NJ"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}]}],"member":"320","published-online":{"date-parts":[[2005,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1987. Data structures and algorithms. Addison-Wesley Reading MA.   Aho A. V. Hopcroft J. E. and Ullman J. D. 1987. Data structures and algorithms. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303978"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the First SIAM International Conference on Data Mining.","author":"Barbara D.","unstructured":"Barbara , D. , Wu , N. , and Jajodia , S . 2001. Detecting novel network intrusions using Bayes estimators . In Proceedings of the First SIAM International Conference on Data Mining. Barbara, D., Wu, N., and Jajodia, S. 2001. Detecting novel network intrusions using Bayes estimators. In Proceedings of the First SIAM International Conference on Data Mining."},{"key":"e_1_2_1_6_1","volume-title":"Tech. Rep. 35. Institute for Computer Science","author":"Boyer B.","year":"1982","unstructured":"Boyer , B. and Moore , J . 1982 . A fast majority vote algorithm. Tech. Rep. 35. Institute for Computer Science , University of Texas, at Austin, Austin, TX. Boyer, B. and Moore, J. 1982. A fast majority vote algorithm. Tech. Rep. 35. Institute for Computer Science, University of Texas, at Austin, Austin, TX."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Charikar M. Chen K. and Farach-Colton M. 2002. Finding frequent items in data streams. In Procedings of the International Colloquium on Automata Languages and Programming (ICALP). 693--703.   Charikar M. Chen K. and Farach-Colton M. 2002. Finding frequent items in data streams. In Procedings of the International Colloquium on Automata Languages and Programming (ICALP). 693--703.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773182"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of IEEE Infocom.","author":"Cormode G.","unstructured":"Cormode , G. and Muthukrishnan , S . 2004b. What's new: Finding significant differences in network data streams . In Proceedings of IEEE Infocom. Cormode, G. and Muthukrishnan, S. 2004b. What's new: Finding significant differences in network data streams. In Proceedings of IEEE Infocom."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms. Lecture Notes in Computer Science","volume":"2461","author":"Demaine E.","unstructured":"Demaine , E. , L\u00f3pez-Ortiz , A. , and Munro , J. I . 2002. Frequency estimation of Internet packet streams with limited space . In Proceedings of the 10th Annual European Symposium on Algorithms. Lecture Notes in Computer Science , vol. 2461 . Springer, Berlin, Germany, 348--360. Demaine, E., L\u00f3pez-Ortiz, A., and Munro, J. I. 2002. Frequency estimation of Internet packet streams with limited space. In Proceedings of the 10th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2461. Springer, Berlin, Germany, 348--360."},{"key":"e_1_2_1_13_1","volume-title":"Combinatorial Group Testing and Its Applications. Series on Applied Mathematics","volume":"3","author":"Du D.-Z.","unstructured":"Du , D.-Z. and Hwang , F . 1993 . Combinatorial Group Testing and Its Applications. Series on Applied Mathematics , vol. 3 . World Scientific, Singapore. Du, D.-Z. and Hwang, F. 1993. Combinatorial Group Testing and Its Applications. Series on Applied Mathematics, vol. 3. World Scientific, Singapore."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/964725.633056"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 299--310","author":"Fang M.","unstructured":"Fang , M. , Shivakumar , N. , Garcia-Molina , H. , Motwani , R. , and Ullman , J. D . 1998. Computing iceberg queries efficiently . In Proceedings of the International Conference on Very Large Data Bases. 299--310 . Fang, M., Shivakumar, N., Garcia-Molina, H., Motwani, R., and Ullman, J. D. 1998. Computing iceberg queries efficiently. In Proceedings of the International Conference on Very Large Data Bases. 299--310."},{"key":"e_1_2_1_16_1","first-page":"376","article-title":"Finding a majority among n votes: Solution to problem 81-5","volume":"3","author":"Fischer M.","year":"1982","unstructured":"Fischer , M. and Salzberg , S. 1982 . Finding a majority among n votes: Solution to problem 81-5 . J. Algorith. 3 , 4, 376 -- 379 . Fischer, M. and Salzberg, S. 1982. Finding a majority among n votes: Solution to problem 81-5. J. Algorith. 3, 4, 376--379.","journal-title":"J. Algorith."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564794"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276334"},{"key":"e_1_2_1_19_1","unstructured":"Gibbons P. and Matias Y. 1999. Synopsis structures for massive data sets. DIMACS Series in Discrete Mathematics and Theoretical Computer Science A.   Gibbons P. and Matias Y. 1999. Synopsis structures for massive data sets. DIMACS Series in Discrete Mathematics and Theoretical Computer Science A."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 466--475","author":"Gibbons P. B.","unstructured":"Gibbons , P. B. , Matias , Y. , and Poosala , V . 1997. Fast incremental maintenance of approximate histograms . In Proceedings of the International Conference on Very Large Data Bases. 466--475 . Gibbons, P. B., Matias, Y., and Poosala, V. 1997. Fast incremental maintenance of approximate histograms. In Proceedings of the International Conference on Very Large Data Bases. 466--475."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509966"},{"key":"e_1_2_1_22_1","unstructured":"Gilbert A. Kotidis Y. Muthukrishnan S. and Strauss M. 2001. QuickSAND: Quick summary and analysis of network data. DIMACS Tech. Rep. 2001--43 Available online at http:\/\/dimacs. crutgers.edu\/Techniclts.  Gilbert A. Kotidis Y. Muthukrishnan S. and Strauss M. 2001. QuickSAND: Quick summary and analysis of network data. DIMACS Tech. Rep. 2001--43 Available online at http:\/\/dimacs. crutgers.edu\/Techniclts."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 454--465","author":"Gilbert A. C.","unstructured":"Gilbert , A. C. , Kotidis , Y. , Muthukrishnan , S. , and Strauss , M . 2002b. How to summarize the universe: Dynamic maintenance of quantiles . In Proceedings of the International Conference on Very Large Data Bases. 454--465 . Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. 2002b. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the International Conference on Very Large Data Bases. 454--465."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/169725.169708"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223841"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge U.K.   Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 346--357","author":"Manku G.","unstructured":"Manku , G. and Motwani , R . 2002. Approximate frequency counts over data streams . In Proceedings of the International Conference on Very Large Data Bases. 346--357 . Manku, G. and Motwani, R. 2002. Approximate frequency counts over data streams. In Proceedings of the International Conference on Very Large Data Bases. 346--357."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge U.K.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Available online at http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps.","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. Available online at http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps. Muthukrishnan, S. 2003. Data streams: Algorithms and applications. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Available online at http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. 496--497","author":"Thorup M.","year":"2000","unstructured":"Thorup , M. 2000 . Even strongly universal hashing is pretty fast . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. 496--497 . Thorup, M. 2000. Even strongly universal hashing is pretty fast. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. 496--497."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 16th International Conference on Data Engineering (ICDE' 00)","author":"Yi B.-K.","unstructured":"Yi , B.-K. , Sidiropoulos , N. , Johnson , T. , Jagadish , H. , Faloutsos , C. , and Biliris , A . 2000. Online data mining for co-evolving time sequences . In Proceedings of the 16th International Conference on Data Engineering (ICDE' 00) . 13--22. Yi, B.-K., Sidiropoulos, N., Johnson, T., Jagadish, H., Faloutsos, C., and Biliris, A. 2000. Online data mining for co-evolving time sequences. In Proceedings of the 16th International Conference on Data Engineering (ICDE' 00). 13--22."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1061318.1061325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1061318.1061325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:36:56Z","timestamp":1750282616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1061318.1061325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1145\/1061318.1061325"],"URL":"https:\/\/doi.org\/10.1145\/1061318.1061325","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]},"assertion":[{"value":"2005-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}