软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2017年第03期杂志 文档列表

软件学报杂志大数据管理技术专刊

大数据管理技术专刊前言473-475

摘要：大数据管理及处理能力已经成为引领网络时代IT发展的关键,获取大量运行数据并建立对其进行动态高效处理的能力,已经成为产业竞争力的体现.从2012年美国政府宣布“大数据研究计划（Big Data Initiative）”和我国的《“十二五”国家科技计划信息技术领域项目》将大数据研究列在首位以来,大数据管理分析技术得到了学术界和工业界空前的关注.2016年5月,美国又进一步了《联邦大数据研究与开发战略计划》.然而,

集群数据库系统的日志复制和故障恢复476-489

摘要：互联网、社交、购物、金融等各类应用直接面临海量用户的高并发访问,传统的单点数据库逐渐成为这些应用系统的瓶颈,而众多互联网应用能够良好运行的主要原因是使用了基于集群环境的数据管理系统作支撑.与传统数据库系统相比,基于集群环境的数据库系统具有更好的扩展性和可用性,而日志复制是保证这些特性的核心组件.传统的主备架构的日志复制在异常情况下对未决事务日志处理不佳,导致数据副本之间存在不一致的风险.另外,分布式系统领域的一致性算法缺乏对事务一致性的处理,而且在选主时存在活锁、多主和频繁选主的问题,无法直接适用于事务日志复制.提出了一种集群环境下的事务日志复制策略和恢复机制,能够有效处理未提交日志,提供了强弱两种读一致性,并且提出一种轻量级的选主算法,可以避免出现以上的选主问题.在开源Ocean Base分布式数据库系统中实现了上述机制,并使用基准测试工具对系统进行测试,通过一系列实验验证了系统的扩展性和可用性.

面向MIC协处理器的OLAP外键连接算法490-501

摘要：众核架构协处理器Xeon Phi成为新兴的主流高性能计算平台.对于数据库应用而言,内存分析处理是一种计算密集型负载,其性能主要取决于大事实表与维表之间的内存外键连接性能.关注于一种相对于缓存相关的分区哈希连接算法和缓存不相关的无分区哈希连接算法的缓存友好型外键连接算法,以适应Xeon Phi协处理器较小的LLC和高并发线程的特点.通过挖掘OLAP模式中的键特征,基于键值匹配的哈希探测操作,可以进一步简化为事实表与维表之间基于主-外键参照完整性约束的键参照访问,因此,复杂的哈希表和CPU代价较高的哈希探测操作可以简化为通过映射外键值为键向量内存偏移地址的方法对向量直接访问.基于向量参照访问的外键连接算法,能够简单并高效地应用于Xeon Phi协处理器平台,通过更多的核心和高并发线程来掩盖内存访问延迟.实验中,对传统的哈希连接算法（无分区哈希连接算法和基数分区哈希连接算法）和基于向量参照技术的外键连接算法在Xeon E5-2650 v3 10核处理器平台和Xeon Phi 5110P 60核协处理器平台进行性能测试和比较,实验结果给出了主流的内存外键连接算法在不同数据集和不同平台上全面的性能特征.

一种面向HDFS的多层索引技术502-513

摘要：SOH（SQL over HDFS）系统通常将数据存储于分布式文件系统HDFS（Hadoop distributed file system）中,采用Map/Reduce或分布式查询引擎来处理查询任务.得益于HDFS以及Map/Reduce的容错能力和可扩展性,SOH系统可以很好地应对数据规模的飞速增长,完成分析型查询处理.然而,在处理选择型查询或交互式查询时,这类系统暴露出了性能上的缺陷.提出一种通用的索引技术,可以应用于SOH系统中,以提高其查询处理的效率.分析了SOH系统访问HDFS文件的过程,指出了其中影响数据加载时间的关键因素.提出了split层和split内部双层索引机制;设计并实现了聚集索引和非聚集索引;最后,在标准数据集上进行了大量实验,并与现有基于HDFS的索引技术进行了比较.实验结果表明,所提出的索引技术可以有效地提高查询处理的效率.

MapReduce大数据处理平台与算法研究进展514-543

摘要：综述了近年来基于MapReduce编程模型的大数据处理平台与算法的研究进展.首先介绍了12个典型的基于MapReduce的大数据处理平台,分析对比它们的实现原理和适用场景,抽象其共性;随后介绍基于MapReduce的大数据分析算法,包括搜索算法、数据清洗/变换算法、聚集算法、连接算法、排序算法、偏好查询、最优化算法、图算法、数据挖掘算法,将这些算法按照MapReduce实现方式分类,分析影响算法性能的因素;最后,将大数据处理算法抽象为外存算法,并对外存算法的特征加以梳理,提出了普适的外存算法性能优化方法的研究思路和问题,以供研究人员参考.具体包括优化外存算法的磁盘I/O、优化外存算法的局部性以及设计增量式迭代算法.现有的大数据处理平台和算法研究多集中在基于资源分配和任务调度的平台动态性能优化、特定算法并行化、特定算法性能优化等领域,所提出的外存算法性能优化属于静态优化方法,是现有研究的良好补充,为研究人员提供了广阔的研究空间.

面向多源大数据云端处理的成本最小化方法544-562

摘要：云计算为大数据处理提供了一种强大而高效的解决方案.在此模式下,数据管理者（data manager,简称DM）可以租用多个数据中心实时处理地理分散的数据.然而,由于数据产生的动态性以及资源价格的波动性,将数据迁移至哪些数据中心并提供合适的计算资源来处理它们,成为DM低成本处理多源数据的一大问题.首先,将以上问题转换成联合随机优化问题;然后,利用李雅普诺夫（Lyapunov）优化框架将原问题分解成两个独立的子问题进行求解;最后,基于求解结果设计在线算法.理论分析结果表明：所提算法可不断趋近线下最优解,并能够保证数据处理时延.在WorldCup98和Youtube数据集上的实验验证了理论分析结果的正确性以及该方法的优越性.

分布式数据流上的高性能分发策略563-578

摘要：随着大数据应用的普及,高效可扩展的数据流操作在实时分析处理中扮演着越来越重要的角色.分布式并行处理架构是应对大流量、低延时数据流处理任务的一种有效解决方案.然而在Key-based分组并行处理中,由于数据的倾斜分布及数据流本身的实时、动态和数据规模不可预知等特性,使得数据流分布并行处理系统存在持续且动态负载不均衡现象,这会造成系统时效性降低、硬件资源浪费等问题.现有的研究工作处理均衡负载有两种方案：（1）基于key粒度的迁移,使得并行处理节点负载达到均衡;（2）基于元组粒度级别的拆分,采用随机分发使系统均衡.前者将系统调整至给定的均衡容忍范围内,类似于一维装箱的NP问题;后者对key的拆分势必带来新的为维护Key-based操作的正确性而增加的额外代价,如内存及网络通信成本.综合两种方法,提出对key按需拆分、尽量合并的方法,通过轻量级均衡调整算法以及保证Key-based操作特性的拆分方法,使系统既能达到后者的均衡,又能减少细粒度均衡所带来的额外代价.

一种云环境中数据流的高效多目标调度方法579-597

摘要：在分布式系统中,云计算作为一种新的服务提供模式出现,其执行科学应用数据流时的优势和缺点得到越来越多的关注,其主要特点为拥有大量同质和并发的任务包,并构成了性能瓶颈的主要因素.在云数据流中调度大规模任务是已被证实的NP难问题.专注于解决优化云数据流中的调度过程,并受现实世界启发,从不同角度将优化目标分别划分为用户指标（完工时间和经济成本）和云系统指标（网络带宽、存储约束和系统公平度）,并将该调度问题制定成为一个新的连续的合作博弈,设计出快速收敛的高效Muliti-Objective Game（MOG）调度算法,在优化用户指标的同时,实现系统指标的约束,并保证云资源的效率和公平度.通过综合实验,证实该方法与其他相关算法相比,在算法复杂度O（l？K？M）（明显改进数量级）、结果质量（一些情况下最佳）、系统级别公平性上具有明显的优越性.

基于最小费用最大流的大规模资源调度方法598-610

摘要：并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模,仅能满足局部最优解且只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束这3种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构,使其具备适应性调整能力;其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法;最后,实验对比公平性、优先级和放置约束这3种资源调度典型系统,验证了该方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真,验证了万级规模下,基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%.

空间众包环境下的3类对象在线任务分配611-630

摘要：随着移动互联网技术与O2O（offline-to-online）商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足：（1）现有工作通常假设基于静态场景,即,全部众包任务和众包工人的时空信息在任务分配前已完整获知,但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此,现存研究结果在实际应用中缺乏可行性;（2）现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,提出了一类新型动态任务分配问题,即,空间众包环境下的3类对象在线任务分配.该问题不但囊括了任务分配中的3类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.进而设计了随机阈值算法,给出了该算法在最差情况下的竞争比分析.采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终通过在真实数据集和具有不同分布人造数据集上进行的大量实验,验证了算法的效果与性能.

复杂网络大数据中重叠社区检测算法631-647

摘要：提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（detecting overlapping communities over complex network big data）,时间复杂度为O（nlog2（n））,算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.

基于深度稀疏自动编码器的社区发现算法648-662

摘要：社区结构是复杂网络的重要特征之一,社区发现对研究网络结构有重要的应用价值.k-均值等经典聚类算法是解决社区发现问题的一类基本方法.然而,在处理网络的高维矩阵时,使用这些经典聚类方法得到的社区往往不够准确.提出一种基于深度稀疏自动编码器的社区发现算法CoDDA（a community detection algorithm based on deep sparse autoencoder）,尝试提高使用这些经典方法处理高维邻接矩阵进行社区发现的准确性.首先,提出基于跳数的处理方法,对稀疏的邻接矩阵进行优化处理,得到的相似度矩阵不仅能够反映网络拓扑结构中相连节点间的相似关系,同时还反映了不相连节点间的相似关系.然后,基于无监督深度学习方法构建深度稀疏自动编码器,对相似度矩阵进行特征提取,得到低维的特征矩阵.与邻接矩阵相比,特征矩阵对网络拓扑结构有更强的特征表达能力.最后,使用k-均值算法对低维特征矩阵聚类得到社区结构.实验结果显示：与6种典型的社区发现算法相比,Co DDA算法能够发现更准确的社区结构.同时,参数实验结果显示,Co DDA算法发现的社区结构比直接使用高维邻接矩阵的基本k-均值算法发现的社区结构更为准确.

动态信息网络中基于角色的结构演化与预测663-675

摘要：动态信息网络是当前复杂网络领域中一个极具挑战的问题,其动态的演化过程具有时序、复杂、多变的特点.结构是网络最基本的特征,也是进行网络建模和分析的基础,研究网络结构的演化过程,对全面认识复杂系统的行为倾向具有重要意义.使用角色来量化动态网络的结构,得到动态网络的角色模型,应用并改进多类标分类问题的问题转换思想,将动态网络的角色预测问题视为多目标回归问题,以历史网络数据作为训练数据构建模型,预测未来时刻网络可能的角色分布情况,提出基于多目标回归思想的动态网络角色预测方法 MTR-RP（multi-target regression based role prediction）.该方法不仅克服了基于转移矩阵方法忽略时间因素的不足,还考虑了多个预测目标之间可能存在的依赖关系.实验结果表明,提出的MTR-RP方法具有更准确且更稳定的预测效果.

基于语义约束LDA的商品特征和情感词提取676-693

摘要：随着网络购物的发展,Web上产生了大量的商品评论文本数据,其中蕴含着丰富的评价知识.如何从这些海量评论文本中有效地提取商品特征和情感词,进而获取特征级别的情感倾向,是进行商品评论细粒度情感分析的关键.根据中文商品评论文本的特点,从句法分析、词义理解和语境相关等多角度获取词语间的语义关系,然后将其作为约束知识嵌入到主题模型,提出语义关系约束的主题模型SRC-LDA（semantic relation constrained LDA）,用来实现语义指导下LDA的细粒度主题词提取.由于SRC-LDA改善了标准LDA对于主题词的语义理解和识别能力,从而提高了相同主题下主题词分配的关联度和不同主题下主题词分配的区分度,可以更多地发现细粒度特征词、情感词及其之间的语义关联性.实验结果表明,SRC-LDA对于细粒度特征和情感词的发现和提取具有较好的效果.

基于社交关系的微博主题情感挖掘694-707

摘要：微博情感分析是社交媒体挖掘中的重要任务之一,在个性化推荐、舆情分析等方面具有重要的理论和应用价值.挖掘性能良好且可同步进行文档主题分析与情感分析的主题情感模型,近年来在以微博为代表的社交媒体情感分析中备受关注.然而,绝大多数现有主题情感模型都只简单地假设不同微博的情感极性是互相独立的,这与微博生态的现实状况不相一致,从而导致这些模型无法对用户的真实情感进行有效建模.基于此,综合考虑了微博用户相互关联的事实,提出了基于LDA和微博用户关系的主题情感模型SRTSM（social relation topic sentiment model）.该模型在LDA中加入情感层与微博用户关系参数,利用微博用户关系与微博主题学习微博的情感极性.针对新浪微博真实数据集上的大量实验结果表明：与代表性算法JST,Sentiment-LDA及DPLDA相比较,SRTSM模型能够对用户真实情感与讨论主题进行更加有效的分析建模.

融合主题模型和协同过滤的多样化移动应用推荐708-720

摘要：随着移动应用的急速增长,手机助手等移动应用获取平台也面临着信息过载的问题.面对大量的移动应用,用户很难找到最适合的;而另一方面,长尾应用淹没在资源池中不易被人所知.已有推荐方法多注重推荐准确率,忽视了多样性,推荐结果中多是下载量高的应用,使得推荐系统的数据积累越来越偏向于热门应用,导致长期的推荐效果越来越差.针对这一问题,首先改进了两种推荐方法,提出了将用户的主题模型和应用的主题模型与MF相结合的LDA_MF模型,以及将应用的标签信息和用户行为数据同时加以考虑的LDA_CF算法.为了结合不同算法的优点,在保证推荐准确率的条件下提升推荐结果的多样性,提出了融合LDA_MF,LDA_CF以及经典的基于物品的协同过滤模型的混合推荐算法.使用真实的大数据评测所提推荐算法,结果显示,所提推荐方法能够得到推荐多样性更好且准确率更高的结果.

社交网络环境下基于信任的推荐算法721-731

摘要：现有的基于信任的推荐算法通常假设用户是单一和同质的,没有充分挖掘信任关系信息,且相似关系和信任关系的融合缺乏高效的模型,极大地影响了推荐的准确性和可靠性.提出一种基于信任的推荐算法.首先,结合全局信任和局部信任,并利用信任的传播性质对信任关系进行建模;然后,设置推荐权重,综合考虑相似度和信任度来构建用户间的偏好关系,筛选出邻居;最后,将基于记忆的协同过滤思想和社交网络的信任关系融入概率矩阵分解模型,同时使用自适应权重动态决定各部分的影响程度,形成高效、统一的可信推荐模型Trust-PMF.该算法在FilmTrust,Epinions这两个数据集上与相关算法做了对比验证,结果证实了该算法的高效性.

透析计算：面向OLGP的InfoNetCube高效物化732-743

摘要：信息网络数据立方（InfoNetCube）的计算是进行信息网络在线分析处理的基础.然而,不同于传统的数据立方,信息网络数据立方由多个子方体格组成,每个方体格中任意方体（cuboid）的任意单元格都包含一个主题图（或称图度量）,因而空间开销较传统数据立方大2个数量级以上.如何快速、高效地进行信息网络数据立方的部分物化,是极具挑战的研究课题.提出了基于透析计算思想的信息网络立方物化策略,通过主题图度量在信息维和拓扑维上反单调性运用,提出了基于透析计算的空间剪枝算法,快速透析掉不可能命中的子图度量、方体单元、方体乃至方体格.实验结果表明,所提出的基于透析计算的部分物化策略可以对信息网络方体进行有效剪枝,算法较基于基本方体的部分物化策略运行时间平均降低75%.