{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:30:35Z","timestamp":1740105035837,"version":"3.37.3"},"reference-count":42,"publisher":"Wiley","issue":"18","license":[{"start":{"date-parts":[[2013,12,5]],"date-time":"2013-12-05T00:00:00Z","timestamp":1386201600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61103214"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41101059"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Doctoral Fund of Ministry of Education of China","award":["20110031120030"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2014,12,25]]},"abstract":"SUMMARY<\/jats:title>In high\u2010speed network monitoring, the ever\u2010growing traffic calls for a high\u2010performance solution for the computation of frequent items. The increasing number of cores in the current commodity multi\u2010core processors opens up new opportunities in parallelization. In this paper, we present a novel precision integrated framework (PRIF) that exploits the great parallel capability of multi\u2010cores to speed up the famous frequent<\/jats:italic> algorithm. PRIF equally distributes the input data stream into sub\u2010threads that use the optimized weighted frequent<\/jats:italic> algorithm to track local frequent items. The items with frequency increments exceeding a pre\u2010defined threshold are sent to a merging thread which is able to return the global continuous \u03b5<\/jats:italic>\u2010deficient frequent items. The theoretical correctness and complexity analyses are presented. Experiments with real and synthetic traces confirm the theoretical analyses and demonstrate the excellent performance as well as the effects of parameters and data skewness. The results show that PRIF is able to provide continuous frequent items and near\u2010linear speedup at the cost of greater memory use. Copyright \u00a9 2013 John Wiley & Sons, Ltd.<\/jats:p>","DOI":"10.1002\/cpe.3182","type":"journal-article","created":{"date-parts":[[2013,12,5]],"date-time":"2013-12-05T07:50:46Z","timestamp":1386229846000},"page":"2856-2879","source":"Crossref","is-referenced-by-count":17,"title":["An efficient framework for parallel and continuous frequent item monitoring"],"prefix":"10.1002","volume":"26","author":[{"given":"Yu","family":"Zhang","sequence":"first","affiliation":[{"name":"College of Computer and Control Engineering Nankai University No. 94, Weijin Road, Tianjin 300071 China"}]},{"given":"Yue","family":"Sun","sequence":"additional","affiliation":[{"name":"Rice Research Institute Tianjin Academy of Agricultural Sciences No. 268, Baidi Road, Tianjin 300071 China"}]},{"given":"Jianzhong","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Computer and Control Engineering Nankai University No. 94, Weijin Road, Tianjin 300071 China"}]},{"given":"Jingdong","family":"Xu","sequence":"additional","affiliation":[{"name":"College of Computer and Control Engineering Nankai University No. 94, Weijin Road, Tianjin 300071 China"}]},{"given":"Ying","family":"Wu","sequence":"additional","affiliation":[{"name":"College of Computer and Control Engineering Nankai University No. 94, Weijin Road, Tianjin 300071 China"}]}],"member":"311","published-online":{"date-parts":[[2013,12,5]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"crossref","unstructured":"FredSB BonaldT ProutiereA RegnieG RobertsJW.Statistical bandwidth sharing: a study of congestion at flow level.Proceedings of the 2001 SIGCOMM Conference Vol.31 ACM New York NY USA 2001;111\u2013122.","DOI":"10.1145\/964723.383068"},{"key":"e_1_2_8_3_1","unstructured":"MoriT KawaharaR NaitoS GotoS.On the characteristics of internet traffic variability: spikes and elephants.Proceedings of the 2004 International Symposium on Applications and the Internet 2004 Tokyo Japan 2004;99\u2013106."},{"key":"e_1_2_8_4_1","unstructured":"PapagiannakiK TaftN BhattacharyaS ThiranP SalamatianK DiotC.On the feasibility of identifying elephants in internet backbone traffic.Technical Report RR01\u2010ATL\u2010110918 Sprint labs 2001."},{"key":"e_1_2_8_5_1","doi-asserted-by":"crossref","unstructured":"SommerR FeldmannA.Netflow: information loss or win?IMW \u201902: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurment ACM:New York NY USA 2002;173\u2013174.","DOI":"10.1145\/637201.637226"},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633055"},{"key":"e_1_2_8_7_1","unstructured":"FangW PetersonL.Inter\u2010as traffic patterns and their implications.Proceedings of the IEEE GLOBECOM IEEE: Rio de Janeireo 1999;1859\u20131868."},{"key":"e_1_2_8_8_1","unstructured":"MahajanR FloydS WetherallD.Controlling high\u2010bandwidth flows at the congested router.Proceedings of IEEE ICNP 2001 Riverside CA USA 2001;192\u2013201."},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.929850"},{"key":"e_1_2_8_10_1","unstructured":"SinghS EstanC VargheseG SavageS.Automated worm fingerprinting.Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation San Francisco CA USA 2004;45\u201360."},{"key":"e_1_2_8_11_1","doi-asserted-by":"crossref","unstructured":"KumarA SungM XuJJ WangJ.Data streaming algorithms for efficient and accurate estimation of flow size distribution.Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems ACM New York NY USA 2004;177\u2013188.","DOI":"10.1145\/1005686.1005709"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"key":"e_1_2_8_13_1","unstructured":"Sun sparc enterprise t5240 server. (Available from:http:\/\/www.sun.com\/servers\/coolthreads\/t5240\/) [Accessed on 1 April 2011]."},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_33"},{"issue":"1","key":"e_1_2_8_15_1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/762471.762473","article-title":"A simple algorithm for finding frequent elements in streams and bags","volume":"28","author":"Karp RM","year":"2003","journal-title":"ACM Transactions on Database Systems (TODS)"},{"key":"e_1_2_8_16_1","unstructured":"KranakisE MorinP TangY.Bounds for frequency estimation of packet streams.In SIROCCO Ume\u00e5 Sweden 2003;33\u201342."},{"key":"e_1_2_8_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"volume-title":"Multi\u2010core Programming: Increasing Performance Through Software Multi\u2010threading","year":"2006","author":"Akhter S","key":"e_1_2_8_18_1"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"issue":"1","key":"e_1_2_8_20_1","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","article-title":"An improved data stream summary: the count\u2010min sketch and its applications","volume":"55","author":"Cormode G","year":"2005","journal-title":"Journal of Algorithms"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_8_22_1","doi-asserted-by":"crossref","unstructured":"BerindeR CormodeG IndykP StraussMJ.Space\u2010optimal heavy hitters with strong error bounds.Proceedings of the Twenty\u2010Eighth ACM SIGMOD\u2010SIGACT\u2010SIGART Symposium on Principles of Databas Systems ACM Providence Rhode Island USA 2009;157\u2013166.","DOI":"10.1145\/1559795.1559819"},{"key":"e_1_2_8_23_1","doi-asserted-by":"crossref","unstructured":"MankuGS MotwaniR.Approximate frequency counts over data streams.Proceedings of the 28th International Conference on Very Large Data Bases\u2010Volume 28 VLDB Endowment Hong Kong China 2002;346\u2013357.","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"issue":"2","key":"e_1_2_8_24_1","doi-asserted-by":"crossref","first-page":"1530","DOI":"10.14778\/1454159.1454225","article-title":"Finding frequent items in data streams","volume":"1","author":"Cormode G","year":"2008","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_8_25_1","doi-asserted-by":"crossref","unstructured":"TeubnerJ MllerR AlonsoG.Fpga acceleration for the frequent item problem.ICDE IEEE Long Beach California USA 2010;669\u2013680.","DOI":"10.1109\/ICDE.2010.5447856"},{"key":"e_1_2_8_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.216"},{"key":"e_1_2_8_27_1","doi-asserted-by":"crossref","unstructured":"BandiN MetwallyA AgrawalD El\u2009AbbadiA.Fast data stream algorithms using associative memories.Proceedings of the 2007 International Conference on Management of Data ACM: New York 2007;247\u2013256.","DOI":"10.1145\/1247480.1247510"},{"key":"e_1_2_8_28_1","doi-asserted-by":"crossref","unstructured":"DasS AgrawalD El\u2009AbbadiA.CAM conscious integrated answering of frequent elements and top\u2010k queries over data streams.Proceedings of the 4th International Workshop on Data Management on New Hardware ACM:New York 2008;1\u201310.","DOI":"10.1145\/1457150.1457152"},{"key":"e_1_2_8_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2012.04.010"},{"key":"e_1_2_8_30_1","doi-asserted-by":"crossref","unstructured":"GovindarajuNK RaghuvanshiN ManochaD.Fast and approximate stream mining of quantiles and frequencies using graphics processors.Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data ACM Baltimore Maryland USA 2005;611\u2013622.","DOI":"10.1145\/1066157.1066227"},{"key":"e_1_2_8_31_1","doi-asserted-by":"crossref","unstructured":"LaiYK ByrdGT.High\u2010throughput sketch update on a low\u2010power stream processor.Proceedings of the 2006 ACM\/IEEE Symposium on Architecture for Networking and Communications Systems ANCS \u201906 ACM: New York NY USA 2006;123\u2013132. (Available from:http:\/\/doi.acm.org\/10.1145\/1185347.1185364) [Accessed on 25 July 2012].","DOI":"10.1145\/1185347.1185364"},{"key":"e_1_2_8_32_1","unstructured":"CafaroM TempestaP PulimenoM.A paralleld space saving algorithm for frequent items and the riemann\u2013hurwitz zeta distribution.Technical Report CRM\u20103322 CRM (The Centre de Recherches Math\u00e9matiques). (Available from:http:\/\/www.crm.umontreal.ca\/pub\/Rapports\/3300\u20103399\/3322.pdf) [Accessed on 25 July 2012]."},{"key":"e_1_2_8_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1761"},{"key":"e_1_2_8_34_1","doi-asserted-by":"crossref","unstructured":"DasS AntonyS AgrawalD AbbadiAE.CoTS: a scalable framework for parallelizing frequency counting over data streams.ICDE 2009 Shanghai China;1323\u20131326.","DOI":"10.1109\/ICDE.2009.231"},{"issue":"1","key":"e_1_2_8_35_1","first-page":"217","article-title":"Thread cooperation in multicore architectures for frequency counting over multiple data streams","volume":"2","author":"Das S","year":"2009","journal-title":"PVLDB"},{"key":"e_1_2_8_36_1","doi-asserted-by":"crossref","unstructured":"RoyP TeubnerJ AlonsoG.Efficient frequent item counting in multi\u2010core hardware.Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD \u201912 ACM: New York NY USA 2012;1451\u20131459. (Available from:http:\/\/doi.acm.org\/10.1145\/2339530.2339757) [Accessed on 25 July 2012].","DOI":"10.1145\/2339530.2339757"},{"key":"e_1_2_8_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2010.04.026"},{"volume-title":"UNIX Systems Programming: Communication, Concurrency, and Threads","year":"2003","author":"Robbins S","key":"e_1_2_8_38_1"},{"key":"e_1_2_8_39_1","unstructured":"Intel turbo boost technology. (Available from:http:\/\/en.wikipedia.org\/wiki\/Intel_Turbo_Boost) [Accessed on 25 July 2012]."},{"key":"e_1_2_8_40_1","unstructured":"Intel hyper\u2010threading technology. (Available from:http:\/\/en.wikipedia.org\/wiki\/Hyper\u2010threading) [Accessed on 25 July 2012]."},{"key":"e_1_2_8_41_1","unstructured":"CaoZ WangZ.Flow identification for supporting per\u2010flow queueing.Proceedings of the Ninth International Conference on Computer Communications and Networks 2000 Las Vegas NV USA 2000;88\u201393."},{"key":"e_1_2_8_42_1","unstructured":"Caida oc48 traces. (Available from:http:\/\/www.caida.org\/data\/passive\/passive_oc48_dataset.xml) [Accessed on 25 July 2012]."},{"key":"e_1_2_8_43_1","unstructured":"Caida oc192 traces. (Available from:http:\/\/www.caida.org\/data\/passive\/passive_2008_dataset.xml) [Accessed on 25 July 2012]."}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.3182","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.3182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T15:54:25Z","timestamp":1696607665000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.3182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,5]]},"references-count":42,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2014,12,25]]}},"alternative-id":["10.1002\/cpe.3182"],"URL":"https:\/\/doi.org\/10.1002\/cpe.3182","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2013,12,5]]}}}