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

来源：计算机研究与发展杂志2016年第8期北京时间：

作者：张奋翔,陈华辉,钱江波,董一鸿,

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

关键词：流次模最大化, 分层模型, 流水并行, 数据摘要, Spark分布式平台,