资源描述：
《一种有效的挖掘数据流近似频繁项算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.18,No.4,April2007,pp.884−892http://www.jos.org.cnDOI:10.1360/jos180884Tel/Fax:+86-10-62562563©2007byJournalofSoftware.Allrightsreserved.∗一种有效的挖掘数据流近似频繁项算法1+1,211,2王伟平,李建中,张冬冬,郭龙江1(哈尔滨工业大学计算机科学与技术
2、学院,黑龙江哈尔滨150001)2(黑龙江大学计算机科学与技术学院,黑龙江哈尔滨150080)AnEfficientAlgorithmforMiningApproximateFrequentItemoverDataStreams1+1,211,2WANGWei-Ping,LIJian-Zhong,ZHANGDong-Dong,GUOLong-Jiang1(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)2
3、(SchoolofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080,China)+Correspondingauthor:Phn:+86-451-6415872,E-mail:wpwang@hit.edu.cn,http://www.hit.edu.cnWangWP,LiJZ,ZhangDD,GuoLJ.Anefficientalgorithmforminingapproximatefrequentitemoverdatastreams.Jou
4、rnalofSoftware,2007,18(4):884−892.http://www.jos.org.cn/1000-9825/18/884.htmAbstract:Afrequentitemofadatastreamisadatapointwhoseoccurrencefrequencyisaboveagiventhreshold.Findingfrequentitemofdatastreamhaswideapplicationsinvariousfields,suchasnetworktrafficmonitor,
5、datastreamOLAPanddatastreammining,etc.Indatastreammodel,thealgorithmcanonlyscanthedatainonepassandtheavailablememoryspaceisverylimitedrelativetothevolumeofadatastream,thereforeitisusuallyunabletofindalltheaccuratefrequentitemsofadatastream.Thispaperproposesanovela
6、lgorithmtofindε-approximate−1frequentitemsofadatastream,itsspacecomplexityisO(ε)andtheprocessingtimeforeachitemisO(1)inaverage.Moreover,thefrequencyerrorboundoftheresultsreturnedbytheproposedalgorithmisε(1−s+ε)N.Amongalltheexistedapproaches,thismethodisthebest.Key
7、words:datastream;datamining;frequentitem;ε-approximate摘要:数据流频繁项是指在数据流中出现频率超出指定阈值的数据项.查找数据流频繁项在网络故障监测、流数据分析以及流数据挖掘等多个领域有着广泛的应用.在数据流模型下,算法只能一遍扫描数据,并且可用的存储空间远远小于数据流的规模,因此,挖掘出所有准确的数据流频繁项通常是不可能的.提出一种新的挖掘数据流近似频−1繁项的算法.该算法的空间复杂性为O(ε),每个数据项的平均处理时间为O(1),输出结果的频率误差界限为ε(1−s+ε
8、)N,在目前已有的同类算法中均为最优.关键词:数据流;数据挖掘;频繁项;ε-近似中图法分类号:TP311文献标识码:A∗SupportedbytheKeyProgramoftheNationalNaturalScienceFoundationofChinaunderGrantNo.60533110(国家
