张奋翔　陈华辉　钱江波　董一鸿

(宁波大学信息科学与工程学院　浙江宁波　315211)



HSSM:一种流数据分层次模最大化方法

张奋翔陈华辉钱江波董一鸿

(宁波大学信息科学与工程学院浙江宁波315211)

(zhang_fenxiang@163.com)

从大规模数据中“摘要”出最能满足效用函数收益的有限个数据对象，可以被归纳为次模函数最大化问题.并行过滤算法在满足流数据访问次数限制与实时响应的条件下，通过分布式筛选的方式实现次规模最大化，但在提升摘要速率时效用函数收益损失较大.提出一种流数据分层次模最大化算法HSSM，在仅访问一次数据集的条件下，采用流水并行的分布式处理框架得到接近于标准贪心算法的次模函数收益，同时改进HSSM通过累积摘要的压缩存储、分层过滤低增益对象提升摘要速率.该方法在数据摘要问题的相关领域具有广泛的应用性，如文档集中代表性文章的选取、数据集中心点选取等.实验结果显示，分布式算法Spark-HSSM+对比于传统的算法在运行速率上达到与摘要规模k成k2正比例关系的提升.而相对于其他分布式算法，其实验效用收益与理论最差收益都更接近于贪心算法.

流次模最大化；分层模型；流水并行；数据摘要；Spark分布式平台

在信息飞速增长的时代，经常需要从海量数据或仅能访问一次的流数据中“摘要”出一个较小的且具有代表性的数据集[1-2]，例如，热点文章及热门微博推荐[3-4]、文档中概要语句提取[5]、数据集中心点选取[6]、数据集中噪声的查……