计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2017年第01期杂志 文档列表

面向网络大数据的知识融合方法综述1-27

摘要：网络大数据是指“人、机、物”三元世界在网络空间中交互、融合所产生并在互联网上可获得的大数据.网络大数据中蕴含丰富的知识资源,包括描述特定事物的实体、刻画实体逻辑联系的关系、用于语义标注实体的分类等.知识自身呈现出异质性、多元性和碎片化等特点.如何在网络大数据环境下海量碎片化的数据中提取出能够用于解决问题的知识,并对知识进行有效的融合计算,将从网络大数据中获得的知识有效组织起来是知识库构建亟待解决的技术难点和当前研究的热点.该文从知识融合的定义出发,介绍近年来的可用于知识融合的技术和算法的最新进展,通过分类和总结现有技术,为进一步的研究工作提供可选方案.文中首先介绍了在知识融合中用于判断知识真伪的知识评估的若干研究和评估方法;然后基于知识评估的结果,从实体扩充、关系扩充和分类扩充3个方面详细总结了知识融合中各种可用的知识扩充方法和研究进展;探讨了应用于网络大数据的知识融合的总体框架;基于这些讨论,总结面向网络大数据的知识融合面临的主要挑战和可能解决方案,并展望了该技术未来的发展方向与前景.

基于用户签到行为的兴趣点推荐28-51

摘要：随着大数据技术的快速发展,推荐系统成为大数据领域里的一个重要的研究方向.随着基于位置社交网络(Location-Based Social Networks,LBSN)的快速发展,兴趣点(Point-Of-Interest,POI)推荐成为一个重要的研究热点,帮助人们发现有趣的并吸引人的位置,特别是当用户在异地旅行的时候.由于用户的签到行为具有高稀疏性,为兴趣点推荐带来很大的挑战.为处理用户签到数据的稀疏性问题,越来越多的研究结合地理影响、时间效应、社会相关性、内容信息和流行度影响这些方面的因素为提高兴趣点推荐的性能.然而,目前的研究缺乏一种综合分析上述所有因素共同作用的方法来处理兴趣点的数据稀疏问题,特别是异地推荐场景被目前大多数研究工作所忽略.针对以上所述的挑战,文中提出一种联合概率生成模型,称为GTSCP,模拟用户签到行为的决策过程,该模型有效地融合上述因素来处理数据稀疏性,特别是异地推荐场景.文章所提的兴趣点推荐方法包含离线模型和在线推荐两个部分.文中所提的GTSCP联合模型支持本地和异地两种推荐场景.文章在多个真实LBSNs的大规模签到数据集上进行实验,结果表明该算法相比其它先进的兴趣点推荐算法具有更好的推荐效果.

一种基于自适应结构概要的有向标签图子图匹配查询算法52-71

摘要：有向标签图作为重要的数据表示模型,广泛应用于社交网络、语义网分析等信息技术相关的研究领域,子图匹配查询是图数据管理的重要研究问题,引起了研究者的广泛关注.有向标签图的子图同构和子图模拟匹配查询由于代价极高,不适用于大规模图数据的查询处理.本文针对有向标签图,研究基于自适应结构概要的子图匹配查询算法.首先基于图压缩的思想,提出一种满足顶点“局部双拟”关系且具有自适应更新特性的有向标签图结构概要模型,在缩小数据图规模的基础上,适应查询图的结构;然后采用图模拟方式,提出基于自适应结构概要模型的子图匹配查询算法,根据查询图顶点的标签,对与其匹配的结构概要顶点按照其中包含数据图顶点的数量由小到大排序,根据查询图顶点之间的rank差值在结构概要模型中实现顶点匹配;最后在真实数据集和模拟数据集上进行实验,结果表明:(1)自适应结构概要模型可根据查询图结构,实现对数据图的最大压缩;(2)可在O(|E|log|V|)的总体时间复杂度内实现结构概要的自适应更新以及基于图模拟方式的子图匹配查询.

大数据访问控制研究72-91

摘要：大数据时代的到来,使得数据成为了重要的经济资产.为了更好地利用它们,有偿或无偿的共享数据将是一种趋势.作为确保大数据安全分享重要技术之一的访问控制技术也将在大数据时挥重要作用.该文首先对大数据及大数据应用的新特点进行分析,并提炼出这些新特点为访问控制领域带来的五个迫切需要解决的新问题:授权管理问题、细粒度访问控制问题、访问控制策略描述问题、个人隐私保护问题,以及访问控制在分布式架构中的实施问题.接着对相关访问控制关键技术的研究现状进行了梳理,包括角色访问控制、风险访问控制、半/非结构化数据的访问控制、针对隐私保护的访问控制、世系数据相关的访问控制、基于密码学的访问控制等.虽然这些现有技术不一定能直接应用于大数据场景,但是它们都可以被大数据访问控制的研究所借鉴,以解决大数据带来的上述访问控制的新问题.在此基础上,总结并提炼了若干大数据访问控制所呈现的新特点:判定依据多元化、判定结果模糊化、多种访问控制技术融合化.最后,对未来大数据访问控制的研究进行了展望,给出了一些有待研究的问题.该文认为大数据应用的发展将为访问控制技术的研究提出许多新的挑战,同时也将带来巨大的机遇,这必将引起访问控制技术的一次重大变革.

基于关联数据的一致性和时效性清洗方法92-106

摘要：数据一致性和数据时效性是大数据质量管理所关注的两个重要内容.条件函数依赖（CFDs）和时效约束（CCs）分别是用于分析数据一致性和数据时效性的有效技术手段.现实生活中的数据会夹杂一些关于一致性和时效性的潜在错误,这些错误又无法为CFDs和CCs检测和修复,最终影响数据的整体质量.值得一提的是,这些数据通常是相互关联的,这种关联关系可以用来发现数据中的潜在错误.文中使用了一种条件合并的函数依赖（CCFDs）将关联数据放在一起进行处理.基于此,该文提出了一种基于关联数据的一致性和时效性清洗方法.在数据清洗过程中,数据的检测和修复是两个相互影响的过程.所以,该文设计了一种新的自动清洗框架,迭代地进行数据检测和数据修复.其次,该文对关联数据的一致性和时效性清洗的相关问题进行了分析,并且证明了关于CCFDs和CCs的最小代价修复问题是一个Σp2完全(NPNP)问题.进而,该文采用一种启发式的修复方法对错误进行修复.为了提高修复的准确性,该文还提出了一种修复序列图的概念.最后,通过在两组真实数据上进行实验,验证了方法的实用性和高效性.

基于云计算的流数据集成与服务107-125

摘要：当前,大数据的管理和处理是云基础设施的重点用武之地,而服务是落实云计算环境中各类资源及能力交付和使用模式的主要方式.随着感知设备的普及,系统规模急剧扩张,数据多元异构复杂性提升,流数据并发数量及速度剧增,传统的流数据系统在处理能力、可扩展性、容错性等方面面临瓶颈问题,而云计算技术依靠其良好的可伸缩性、数据的并行化处理能力、对服务使用模式的支持、容错性等特点,可作为流数据管理与处理的基础.基于云计算对来自不同类型设备的大规模流数据进行集成、处理及服务化正是文中关注的焦点所在.从应用需求出发,该文对大规模流数据集成和实时处理及服务的概念框架、集成方法、流数据查询处理、定制化服务、可伸缩性保障和可靠性保障以及相关评测基准等要点进行了剖析,归纳了大规模流数据的集成与服务研究面临的挑战,探讨了云计算环境下求解相关问题的思路.

个人数据银行——一种基于银行架构的个人大数据资产管理与增值服务的新模式126-143

摘要：随着移动互联网的不断深入发展,个人大数据呈现指数级增长,却面临着产权模糊、管理散乱和流通困难等问题,严重影响个人大数据市场的有序发展.文中基于银行个人货币资产管理的模式及架构,以保护个人数据产权、知情权、隐私权和收益权为核心,提出了一种个人大数据资产管理与增值服务系统——个人数据银行,包括数据确权、汇聚、管理、交易和增值服务等功能,以个人为主体对象组织数据,有效连接人与数据,使得个人数据可授权访问且有序流通.文中对个人大数据资产管理与增值服务平台面临的问题进行了讨论,明确了个人数据银行定义,探讨了个人数据银行平台的组成架构和关键技术,并研发了一种个人数据银行平台——数汇宝,从理论和实践两个方面分析了个人数据银行建设的可行性,为个人数据资产化管理奠定了基础.

分布式大数据多函数依赖冲突检测144-160

摘要：关系数据库数据质量的一个主要问题是存在数据不一致现象.为找出不一致数据,需要进行函数依赖冲突检测.集中式数据库中可以通过SQL技术检测不一致情况,而分布式环境下的函数依赖冲突检测更富有挑战性,特别是大数据背景下,这个问题尤为突出.分布式环境下的函数依赖冲突检测通常需要进行数据迁移,而且不同的数据迁移方法会对检测效率产生一定的影响.该文提出了一种基于等价类的分布式环境多个函数依赖冲突检测的方法,给出了冲突检测的响应时间代价模型.由于分布式环境函数依赖冲突检测问题的任务分配问题为NP-难问题,多项式时间内难以得到最优解,该文将不一致性检测响应时间最小化问题转化为整数规划问题,并给出了近似最优解.针对集群规模和函数依赖个数大小不同的情况,分别给出了不同的任务分配策略,并在检测过程中实现了动态负载均衡,有效提高了负载均衡度和检测效率.在真实和人工数据集上的实验表明,相对于集中式检测方法以及基于Hadoop的naive方法,该文提出的多函数依赖冲突检测方法检测效率有明显的提升,且在数据规模、节点个数和函数依赖个数等方面扩展性能良好.

基于分布式数据流的大数据分类模型和算法161-175

摘要：大数据是需求驱动的概念.随着数据库系统的普及和因特网服务的扩张,企业或者个人可用的数据正在膨胀,已有的技术很难满足大数据时代的数据分析需求,因此需要探索新的理论和方法来支撑大数据的应用.虽然大数据的4V属性已经被广泛讨论,但是它们大多描述的仍然是大数据的表象,所以很难从中抽象出统一的数据格式,因而进一步寻找可用于数据格式化的技术特征是必要的.面向于以分布式和流动性为主要技术特征的大数据应用需求,文中以分布式数据流为数据表达载体,在此基础上设计对应的大数据分类模型和挖掘算子.同时针对大数据的分类挖掘需要解决的关键问题来构建关键步骤对应的算法.理论上证明了文中给出的微簇合并技术和样本数据重构方法的合理性.实验表明:文中提出的基于分布式数据流的大数据的分类模型及算法不仅能大幅度地减少网络节点间的通讯代价,而且可以获得平均10%左右的全局挖掘精度的提升(对比已有的典型算法DS-means);虽然时间花费略高于DS-means,但是两者在不同的数据容量测试下相差很小、且时间攀升趋势相当.

基于认知诊断的个性化试题推荐方法176-191

摘要：面向学生的个性化试题推荐是智能教育领域重要的研究课题,现有的试题推荐工作大多采用协同过滤的方法或基于认知诊断的方法.然而,协同过滤的试题推荐方法往往忽略了学生的学习状态(知识点掌握情况);基于认知诊断的方法只能建模单个学生的学习状态,不能利用相似学生的共性特征.针对以上问题,文中提出一种基于学生知识点掌握程度的协同过滤试题推荐方法.该推荐方法分为3步:第1步结合认知诊断模型,根据学生已有的答题情况和试题知识点的关联对学生的试题掌握水平进行建模;第2步将学生的试题掌握水平用于概率矩阵分解预测学生的答题情况;第3步根据得分预测和试题难度向学生进行相应的试题推荐.该推荐方法同时考虑了被推荐学生学习的个性和群组学生学习的共性,在保证试题推荐解释性的同时提高了试题推荐的可靠性.最后,文中通过大量对比实验证明了该方法在进行学生试题推荐时能够保持精确性和可解释性.

面向近似近邻查询的分布式哈希学习方法192-206

摘要：近似近邻查询是信息检索领域中的一项重要技术.随着文本、图像、视频等非结构化数据规模的迅速增长,如何对海量高维数据进行快速、准确的查询是处理大规模数据所必须面对的问题.哈希作为近似近邻查询的关键方法之一,能够在保持数据相似性的条件下对高维数据进行大比例压缩.以往所提出的哈希方法往往都是应对集中式存储的数据,因而难以处理分布式存储的数据.该文提出了一种基于乘积量化的分布式哈希学习方法SparkPQ,并在Spark分布式计算框架下实现算法.在传统的乘积量化方法的基础上,该文首先给出了分布式乘积量化模型的形式化定义.然后,作者设计了一种按行列划分的分布式矩阵,采用分布式K-Means算法实现模型求解和码本训练,利用训练出的码本模型对分布式数据进行编码和索引.最终,该文构建了一套完整的近似近邻查询系统,不仅可以大幅降低存储和计算开销,而且在保证高检索准确率的条件下加速查询效率.在较大规模的图像检索数据集上进行的实验验证了方法的正确性和可扩展性.

关系数据中函数依赖检测方法207-222

摘要：在数据质量研究中函数依赖被广泛用于关系数据不一致性的修复.然而,不一致修复问题面临的一个主要挑战是如何从包含有错误的关系数据中自动发现有效的函数依赖(Functional Dependence,FD).目前基于统计度量置信度的FD自动发现方法经常找出大量近似成立但无效的FD.如果直接利用这些FD修复数据,会产生更多错误.针对该问题,文中提出了一种基于数据语义分析的函数依赖检测方法.该方法通过条件概率来分析属性值和元组的数据置信度,进而计算函数依赖成立的置信度.文中同时提出了利用关系数据构建马尔科夫毯贝叶斯网络用以计算数据置信度的方法.最后文中通过实验在模拟数据和真实数据上验证了基于数据语义的置信度计算方法在自动检测中的精确度优于基于统计的计算方法,并且在交互式检测应用场景中数据语义的置信度所需用户工作量少于基于统计的方法.

一种改进的基于BSP的大图计算模型223-235

摘要：伴随大数据的涌现,云存储和计算技术近年得到长足发展.图数据是一种重要而普遍的大数据,在生物信息学、社会网络、化学信息学等领域都有众多应用.因此,大图计算作为大数据分析应用的典型代表,正成为云端负载的重要组成部分.目前,高可扩展性的图计算主要依赖于高性能计算解决方案,需要进行环状(或网状)计算机网络之上的高效全集合通信.然而,在通用计算集群和云计算基础设施上实现基于环状计算机网络的算法时,低效的网络通信将导致巨大的系统延迟.因此,这就要求那些基于云端的大数据计算平台和系统具备十分良好的水平可扩展性.但是,大图的幂律分布和缺乏局部性使得设计一套高度可扩展的大图计算系统变得更具挑战.为此,文中提出了一种面向通用计算集群的可扩展大图计算模型.专注于水平扩展能力,设计了一种新颖的基于分离器-合并器BSP的图计算方法,能够提供原生的负载平衡,仅需很低的通信开销.从而,图数据规模的增大可以通过增加计算节点数量得以解决.最后,在一个图数据通用测试集上,通过大量实验验证了所提模型和方法的有效性和高效性;结果显示,相比经典的以顶点为中心的BSP大图计算模型和其他主流大图计算系统,所提改进的基于BSP的大图计算模型能够提供更好的水平可扩展性.

分布式存储中的纠删码容错技术研究236-255

摘要：大数据规模上体量大和增长速度快的特点对存储系统的性能和可扩展性提出了严峻挑战.使用普通商用服务器构建的分布式存储系统服务能力强、成本低廉且极易扩展,在大数据的存储管理中得到了极为广泛的应用.分布式存储系统庞大的节点数量导致节点失效情况频发,必须采用一定的容错技术来保证数据可靠性.常用的容错技术主要包括多副本技术和纠删码技术两种.与多副本容错技术相比,纠删码容错技术能够以低得多的存储开销提供相同甚至更高的数据可靠性.随着近年来数据规模的爆炸式增长,纠删码容错技术受到了业界的广泛关注.该文综述了分布式存储中纠删码容错技术的研究现状.首先,介绍了纠删码容错技术的基本原理和概念,指出了纠删码容错技术在大规模分布式存储中面临的主要技术挑战;然后,从编码实现、纠删码设计、数据修复和数据更新等方面阐述了分布式存储中纠删码容错技术的研究进展,重点研究分析了各项关键技术的特点和局限性,并依据主要评价指标对现有纠删码的编码性能和修复性能进行了对比和分析;最后,基于最新研究动态指出了分布式存储中纠删容错技术未来的研究方向,包括同步编码实现技术、低冗余再生码设计和数据失效预测技术等.

复杂事件模式检测与CEP测试数据生成算法研究256-272

摘要：随着信息技术的快速发展和广泛应用,大数据正以不可阻挡的气势向我们走来.大数据源于信息技术,同时又向信息技术提出挑战.如何征服大数据给信息技术处理能力上带来的挑战是一个广泛关注的课题.由于采用面向流式数据的处理策略,复杂事件处理(Complex Event Processing,CEP)技术被认为是一种有希望征服大数据挑战的技术之一.然而,当事件流成为大数据时,目前的CEP模型、事件模式检测和CEP系统测试数据生成的方法和技术都存在很多不足.文章针对这一问题讨论了复杂事件建模、模式检测与测试数据的生成方法.提出一种CEP代数模型,用多种事件算子来表达事件之间的关系和事件流模型.在这里,一个创新的思想是把CEP代数模型表达式解释成算术文法产生式,从而可以用词法分析技术解决复杂事件模式检测问题.为了有效地测试复杂事件模式检测的算法,基于CEP代数模型,提出了一个用于支持上述CEP模式检测的大数据事件集的生成算法.并由此生成了不同量级的测试数据,测试了一个RFID物联网中CEP模式检测引擎.实验结果表明了提出的事件模式检测算法和CEP系统测试大数据事件集生成算法的有效性.