{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T16:02:06Z","timestamp":1782316926352,"version":"3.54.5"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"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. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            The streams where multiple transactions are associated with the same key are prevalent in practice, e.g., a customer has multiple shopping records arriving at different time. Itemset frequency estimation on such streams is very challenging since sampling based methods, such as the popularly used reservoir sampling, cannot be used. In this article, we propose a novel\n            <jats:italic>k<\/jats:italic>\n            -Minimum Value (KMV) synopsis based method to estimate the frequency of itemsets over multi-transaction streams. First, we extract the KMV synopses for each item from the stream. Then, we propose a novel estimator to estimate the frequency of an itemset over the KMV synopses. Comparing to the existing estimator, our method is not only more accurate and efficient to calculate but also follows the downward-closure property. These properties enable the incorporation of our new estimator with existing frequent itemset mining (FIM) algorithm (e.g., FP-Growth) to mine frequent itemsets over multi-transaction streams. To demonstrate this, we implement a KMV synopsis based FIM algorithm by integrating our estimator into existing FIM algorithms, and we prove it is capable of guaranteeing the accuracy of FIM with a bounded size of KMV synopsis. Experimental results on massive streams show our estimator can significantly improve on the accuracy for both estimating itemset frequency and FIM compared to the existing estimators.\n          <\/jats:p>","DOI":"10.1145\/3465238","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T21:25:55Z","timestamp":1626902755000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Synopsis Based Approach for Itemset Frequency Estimation over Massive Multi-Transaction Stream"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2766-0917","authenticated-orcid":false,"given":"Guangtao","family":"Wang","sequence":"first","affiliation":[{"name":"University of Michigan and JD AI Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gao","family":"Cong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology, Ultimo, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhen","family":"Hai","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research, A*STAR, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jieping","family":"Ye","sequence":"additional","affiliation":[{"name":"University of Michigan, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Data Streams","author":"Aggarwal Charu C.","unstructured":"Charu C. Aggarwal and S. Yu Philip . 2007. A survey of synopsis construction in data streams . In Data Streams . Springer , 169\u2013207. Charu C. Aggarwal and S. Yu Philip. 2007. A survey of synopsis construction in data streams. In Data Streams. Springer, 169\u2013207."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645920.672836"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3002498"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2019.03.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jretconser.2007.02.003"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514927"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956967"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956807"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-013-0265-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2012.05.007"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032649.1033437"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783279"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562789"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061325"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57529-2_50"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00163"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1207"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13748-011-0002-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258013"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bdr.2020.100146"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0059-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/360402.360421"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956918"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487617"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2007.11.061"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 1st International Workshop on Knowledge Discovery in Data Streams. 1\u201310","author":"Li Hua-Fu","year":"2004","unstructured":"Hua-Fu Li , Suh-Yin Lee , and Man-Kwan Shan . 2004 . An efficient algorithm for mining frequent itemsets over the entire history of data streams . In Proceedings of the 1st International Workshop on Knowledge Discovery in Data Streams. 1\u201310 . Hua-Fu Li, Suh-Yin Lee, and Man-Kwan Shan. 2004. An efficient algorithm for mining frequent itemsets over the entire history of data streams. In Proceedings of the 1st International Workshop on Knowledge Discovery in Data Streams. 1\u201310."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1453729.1453732"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1045-1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.7"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924513.1924516"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.11.001"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1053724.1054115"},{"key":"e_1_2_1_41_1","volume-title":"Frequent Itemset Mining over Data Streams","author":"Manku Gurmeet Singh","unstructured":"Gurmeet Singh Manku . 2016. Frequent Itemset Mining over Data Streams . Springer , 209\u2013219. Gurmeet Singh Manku. 2016. Frequent Itemset Mining over Data Streams. Springer, 209\u2013219."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287400"},{"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.1109\/ICDE.2008.4497426"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.82"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629586"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783265"},{"key":"e_1_2_1_48_1","volume-title":"A Modern Course on Statistical Distributions in Scientific Work","author":"Shaked Moshe","unstructured":"Moshe Shaked . 1975. On the distribution of the minimum and of the maximum of a random number of iid random variables . In A Modern Course on Statistical Distributions in Scientific Work . Springer , 363\u2013380. Moshe Shaked. 1975. On the distribution of the minimum and of the maximum of a random number of iid random variables. In A Modern Course on Statistical Distributions in Scientific Work. Springer, 363\u2013380."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1774088.1774436"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the International Conference on Advanced Machine Learning Technologies and Applications. Springer, 337\u2013348","author":"Srivastava Saurabh Ranjan","year":"2020","unstructured":"Saurabh Ranjan Srivastava , Yogesh Kumar Meena , and Girdhari Singh . 2020 . Itemset mining based episode profiling of terrorist attacks using weighted ontology . In Proceedings of the International Conference on Advanced Machine Learning Technologies and Applications. Springer, 337\u2013348 . Saurabh Ranjan Srivastava, Yogesh Kumar Meena, and Girdhari Singh. 2020. Itemset mining based episode profiling of terrorist attacks using weighted ontology. In Proceedings of the International Conference on Advanced Machine Learning Technologies and Applications. Springer, 337\u2013348."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 2006 SIAM International Conference on Data Mining.","author":"Sun Xingzhi","year":"2006","unstructured":"Xingzhi Sun , Maria E. Orlowska , and Xue Li . 2006 . Finding frequent itemsets in high-speed data streams . In Proceedings of the 2006 SIAM International Conference on Data Mining. Xingzhi Sun, Maria E. Orlowska, and Xue Li. 2006. Finding frequent itemsets in high-speed data streams. In Proceedings of the 2006 SIAM International Conference on Data Mining."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2009.07.012"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43946-4_7"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67786-6_18"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-019-05827-w"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2013.10.002"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449726.3463165"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609548"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2578330"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0042-x"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316709"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.11.023"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287401"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465238","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:11Z","timestamp":1750191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3465238"],"URL":"https:\/\/doi.org\/10.1145\/3465238","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}