流数据Top-K关键字查询算法.pdf

第43卷 第 8期 计 算 机 科 学 Vo1．43No．8 2016年 8月 Computer Science Aug2016 流数据 Top—K关键字查询算法 郑诗敏 秦小麟 刘 亮 周 倩 (南京航空航天大学计算机科学与技术学院 南京210016) 摘 要 基于SparkStreaming计算框架的分布式Top-K关键字查询是统计流数据 中所有关键字的热点研究问题。 多数研究通过限定存储空间来实现Top-K关键字查询，并假设关键字集合已知。针对这个问题，提出一种可应用于 关键字集合未知情况的分布式Top-K关键字查询算法，根据监测到的关键字动态地调整存储空间，通过更新策略的 优化提升其精度。实验结果表明，该算法的性能在关键字集合未知的情况下比现有算法更优。 关键词 Top-K关键字查询，流数据，云计算，SparkStreaming 中图法分类号 TP311 文献标识码 A DOI 10．11896／j．issn．1002—137x．2016．8．030 Algorithm forTop-KKeywordQueryinDataStreams ZHENGShi-min Q1NXiao-lin LIULiang ZHOUQian (CollegeofComputerScienceandTechnology，NanjingUniversityofAeronauticsandAstronautics，Nanjing210016，China) Abstract DistributedTop-Kkeywordquerybasedontheframewo~ ofSparkStreamingisahotresearchissue．Itis usedtocountallkeywordsindatastreams．MoststudiesofTop-K keywordquerylimitstoragespaceandassumethat thekeywordssetisknown．Tosolvethisproblem，wepresentedadistributedTop-K keywordqueryalgorithm which canbeusedincaseswherethekeywordssetisunknown．Thisalgorithm dynamicallyadjuststhesizeofstoragespace accordingot monitoredkeywordsandoptimizestheupdatedstrategytoimproveprecision．Experimentalresultsshow thattheproposedalgorithm undertheconditionofunknownkeywordssethasbetterperformance． Keywords Top-K keywordquery，Datastreams，Cloudcomputing，Sparkstreaming 关键字集合未知的情况下，算法的精度和性能还不尽如人意。 1 引言 流数据中关键字集合的大小是影响精度和性能的主要因素之 随着互联网技术的飞速发展及新闻、博客、社交网络的兴 一 。 经典ToFK关键字查询算法_3“使用 固定大小的存储空 起，网络给人们生活带来方便的同时，也带来了数据的爆炸式 间来进行频数的统计和更新，每监测到一个新词时，如果其在 增长。信息时代的到来，尤其在社交应用的普及之后 ，每个人 存储结构中已经存在，则进行增量操作；反之，则根据不同的 每天都在生产数据。在海量数据的时代背景下，人们更关注 策略替换已有的关键字。由于存储空间的限定，