计算机学报杂志

发表咨询:400-808-1731

订阅咨询:400-808-1751

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

Chinese Journal of Computers

  • 11-1826/TP 国内刊号
  • 0254-4164 国际刊号
  • 3.18 影响因子
  • 1-3个月下单 审稿周期
计算机学报是中国计算机学会;中国科学院计算技术研究所主办的一本学术期刊,主要刊载该领域内的原创性研究论文、综述和评论等。杂志于1978年创刊,目前已被数学文摘、上海图书馆馆藏等知名数据库收录,是中国科学院主管的国家重点学术期刊之一。计算机学报在学术界享有很高的声誉和影响力,该期刊发表的文章具有较高的学术水平和实践价值,为读者提供更多的实践案例和行业信息,得到了广大读者的广泛关注和引用。
栏目设置:研究论文与技术报告、短文、学术通信、学术活动、中国计算机学会学术动态

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

计算机学报杂志数据科学与工程
一种基于离群点检测的自动实体匹配方法2197-2211

摘要:实体匹配也叫记录匹配,是数据集成与数据清洗过程中的一项关键技术.其典型用例包括不同网站之间的商品匹配以及DBLP(Digital Bibliorgrophy&Library Project)与Scholar文献数据库之间的文献实体匹配.真实数据中广泛存在的数据质量缺陷,如错误值、缺失值和数据表达形式多样性等数据质量问题,使得实体匹配问题很具挑战性.目前流行的实体匹配算法可划分为三大类:基于规则的、基于概率的和基于学习的.电商数据中,对同一商品的描述可能差异巨大.对于这类充满表达多样性的实体匹配问题,通常并不存在简洁高效的匹配规则,训练精准的分类模型也很困难.针对这个问题,文中提出了一种基于离群点检测(Outlier Detection)的自动实体匹配方法,记为ODetec算法.首先计算记录序偶在匹配属性上的相似度,并将序偶映射为特征空间上的点;接着在特征空间中估算每个序偶的离群距离;最后根据离群距离和匹配约束,抽取匹配序偶.另外,ODetec算法采用主成分分析方法将多个存在相关性的匹配特征变换为彼此正交的主成分,突破了Fellegi-Sunter模型中属性之间须满足条件独立假设的限制,具备了更好的匹配效果和更为广泛的适用性.实验结论证实了ODetec方法的有效性.

Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统2212-2230

摘要:随着互联网应用的迅猛发展和语义网技术研究的深入,语义数据呈现出爆炸性增长趋势.一方面,对于语义数据实现高效存储和查询是语义网应用的重要基础,越来越多的语义应用可以依赖于此以提供更好的服务;另一方面,语义数据的爆炸性增长,对大数据环境下的语义数据的存储与查询技术提出了新的挑战.传统的基于关系型数据库的语义数据与查询系统已难以满足大规模语义数据的存储与查询需求.该文针对大规模RDF数据的存储与查询问题,以OpenRDF Sesame框架为基础,采用分布式分层式存储架构,提出并实现了属性表存储结构来进行语义数据的存储.在此基础上,针对布尔矩阵分解算法在对大规模语义数据构造属性表较慢的问题,基于Spark分布式计算框架提出并实现了并行化频繁项集挖掘算法求解大规模矩阵分解,以加速属性表的构造过程.并且,在查询层增加了基于哈希转换等查询优化.最后,基于该文所提出的索引结构和优化方法设计实现了原型系统Goldfish,并在大规模合成和真实数据集上进行了实验对比.结果表明,Goldfish原型系统比Rainbow系统查询性能平均提升约6倍,比Jena-HBase查询性能平均提升约500倍,比基于MapReduce的RDF查询系统SHARD性能平均提升约1200倍.

不确定数据基于密度的局部异常点检测2231-2244

摘要:不确定数据作为一种新型的数据模型,被广泛应用于金融、基于位置的服务、移动物体监测、传感器网络等许多类型应用领域.近年来出现的面向不确定数据的分析处理技术已成为数据库、数据挖掘等领域的研究热点.许多传统的数据挖掘技术已经被扩展并应用到不确定数据的分析和管理,异常点检测是数据挖掘领域重要的技术,用来发现行为或特征不同于其他对象的数据对象.当数据对象的性质和行为明显区别于它的近邻时,则被为视为异常点.异常点检测在许多方面有着广泛的应用,如网络入侵检测、信用卡诈骗、环境监测等.该文研究不确定数据基于密度的局部异常点检测,每个不确定数据由几个离散的可能实例组成.首先,提出了基于特定不确定数据模型的局部异常点定义.为了能够快速地检测局部异常点,在不展开可能世界的前提下,提出了基础算法UDOL(Uncertain Density-based Local Outlier).然后,又提出在不精确计算概率的情况下,通过估计局部异常点因子的检测算法PUDOL(Pruning on Uncertain Density-based Local Outlier),可以有效地减少计算量.最后,通过大量的实验验证该文提出算法的性能.实验结果证明,该文所提出的算法是解决不确定数据基于密度的局部异常点检测的有效方法.

云环境下数据库机密性保护技术研究综述2245-2270

摘要:随着云计算的迅猛发展,越来越多的企业和个人把数据外包到位于公有云的数据库系统上管理.然而,数据安全和隐私保护方面的顾虑已经成为阻碍用户更广泛采用云计算和云数据库的一大因素.在云数据外包业务和云数据安全需求的强力驱动下,云环境下数据库的机密性保护成为了重要的研究课题.该综述首先提出了云数据库机密性保护的五级安全模型,使得该文中涉及的众多跨领域、跨问题的安全技术得以在统一的框架中讨论;然后,针对该安全模型中的3级至5级的机密性威胁(云环境下的新型威胁),系统性地总结和分析了对其相应的三项机密性保护的关键技术——密文查询(3级),可信硬件(4级)和访问模式保护(5级);进而在此基础上,介绍和比较了目前最先进的安全云数据库系统;最后,展望了云数据库机密性保护技术的研究趋势,指出了若干研究方向.

面向时间不确定事件流的嵌套查询处理技术2271-2285

摘要:随着复杂事件处理(Complex Event Processing,CEP)技术的发展,该技术已经在多个领域中得到了应用,例如供应链管理和智能跟踪与监控.由于嵌套查询能够满足这些应用领域里更高层次的需求,因此嵌套查询成为了CEP研究的关键问题之一,得到了广泛关注.但是,已有嵌套查询的对象都是发生时间确定的事件,并未考虑现实应用中事件的发生时间是未知的或是不精确的,而这种情况下通常需要概率的方法来表示事件的发生时间.因此文中旨在解决发生时间不确定事件流上的嵌套查询问题.首先,针对基于可能世界的基本处理方法存在的低效问题,文中提出了一种基于迭代的处理方法;进一步,在迭代处理方法的基础上,提出基于子查询长度的剪枝优化技术和基于共享子表达式的缓存优化技术,特别地,基于缓存优化技术提出了查询结果发生概率计算的剪枝方法;最后,通过实验验证了文中提出方法可有效地进行发生时间不确定事件流上的嵌套查询,并能够通过对方法的优化有效地降低处理代价,提高查询处理效率.

基于Web信息的关系型信息错误自动检测与修复技术研究综述2286-2304

摘要:信息质量已经成为诸多应用领域所面临的一个重要问题,自动检测和修复信息系统中的信息错误是改善信息质量的有效手段.利用Web对关系数据库中的信息进行扩展以助于信息错误的自动检测与修复具有对待检测与修复的信息本身依赖少、信息质量规则更灵活、适用性更广以及信息修复相对更准确等优势,可以有效克服现有的基于规则、基于扩展信息和基于人机交互的信息错误检测与修复技术的不足.文中详细分析了基于Web信息的信息错误自动检测与修复技术的优势及所面临的挑战,提出了基于Web信息的信息错误自动检测与修复技术框架.该框架包括:Web信息自动拓展模型、基于Web信息的信息错误自动检测算法、基于Web信息的信息错误自动修复算法和基于Web信息的信息错误自动检测与修复算法的可靠性评估模型.基于上述框架,文中系统总结了基于Web信息的信息错误自动检测技术、信息错误自动修复技术以及信息扩展核心技术三个方面的研究进展,提炼出了基于Web信息的信息错误自动检测与修复技术需要解决的关键科学问题,对未来的研究方向进行了展望并且讨论了初步的研究思路.

位置敏感的社交网中最小种集选取算法研究2305-2319

摘要:最小种子集合选取问题(J-MIN-Seed问题)的目标是选择一个种子集合S,在影响传播结束后,它不仅需要影响一定数量的用户(如J个用户),同时S是最小的集合.虽然该问题得到了广泛的研究,但是现有工作却忽略了一个重要事实,即地理位置信息对于J-MIN-Seed问题是非常重要的.在许多真实的应用中,例如位置敏感的口碑营销,都有地理位置的需求.因此,该文将地理位置因素融入到J-MIN-Seed问题中,提出了位置敏感的J-MINSeed问题,并证明了该问题是NP-hard问题.该问题的一个挑战是如何高效且有效地计算给定区域的影响范围.为了解决这个挑战,该文对现有的树模型进行扩展,设计出一种高效且有效的近似模型.基于此模型,该文首先提出了朴素的贪心算法MS-Greedy.MS-Greedy虽然有近似保证,但其计算量太大.为满足在线查询的需求,该文又提出了另外两种高效的算法Bound-based和Partition-Assembly-based.大量真实数据的实验结果表明:文中算法能有效地解决位置敏感的J-MIN-Seed问题.

基于多核的细粒度并行的集合相似连接2320-2337

摘要:相似连接是指在给定的两个数据集中,根据给定的相似性度量函数来计算数据之间的相似度,并找出所有相似度不小于给定阈值的数据对的操作.相似连接作为一个基本的操作,被广泛地应用于各种领域.随着网络和移动应用等信息技术的不断发展,数据呈现爆炸式增长,海量数据的分析需要强大的计算能力.为了满足不断增长的计算需求,提高计算效率和计算性能,计算机的体系结构也不断升级,出现了多核多处理器架构.为了提高相似连接的效率和计算资源的利用率,文中提出了基于多核的并行相似连接方法.相似连接操作与传统关系数据库中结构化数据之间的连接操作不同,相似连接处理的是异构数据,每一条数据处理的代价与其结构有关.为了实现多核处理器之间的任务均衡,文中提出了适合相似连接操作特点的数据长度均衡的数据划分方法.根据相似连接操作遵循Filter-Refine两阶段框架的特点,结合现代计算机体系结构的多核特性,提出了基于共享索引的任务分解方法和基于独立索引的任务分解方法.文中利用提出的数据划分方法和任务分解方法,实现了基于多核的并行化相似连接算法,包括自连接和R-S连接.文中对两种不同的实现方式的时间代价进行了分析,其中包括索引更新、索引扫描以及集合交运算的代价,从理论分析的角度证明了数据长度均衡划分和独立索引的实现方式在执行效率上具有优势.文中实验部分利用不同的数据集在多核多处理器平台上对并行相似连接的不同实现方式的执行效率和可扩展性进行了验证.实验结果证明,文中提出的数据长度均衡的数据划分方法以及基于独立索引的任务分解方法可以有效地提高并行相似连接的执行效率,在16核平台上使用16个线程在DBLP数据集上执行并行的相似自连接以及在CiteSeer和DBLP两个数据集上执行并行的R

云存储中支持失效文件快速查询的批量审计方法2338-2351

摘要:云存储服务中,批量审计是高效验证云端数据完整性的关键技术.批量审计容易遭受“失效文件”攻击,并且查询失效文件代价高、速度慢,严重影响着批量审计方案的可用性和效率.针对该问题,提出一种支持失效文件快速查询的批量审计方法,该方法通过建立批量审计过程的关联性,改变了二分查询树中右孩子节点的计算方式,减少了整个查找过程的批量审计次数;并在批量审计过程中执行幂指测试,通过一次审计就可完成含有单个失效文件的子树查找过程,有效缩短了子树的查找长度;采用混合型查询方法,根据历史查询信息设置幂指测试的深度,降低了“失效文件聚集处”的查询开销.安全分析和性能表明,该方法能够快速完成失效文件定位,有效抵抗“失效文件”攻击,保证了批量审计方案的可用性和效率.在少量文件失效的情景下,相较于简单二分查找方法,文中方法耗费的批量审计次数减少了30%.

基于随机游走的实体类型补全方法2352-2366

摘要:伴随着大数据的大量涌现以及开放链接数据(LOD)等项目的开展,语义网知识库的数量激增,语义网知识库正在引起学术界和工业界越来越多的关注,在信息检索系统中起着重要的作用,如实体搜索和问答系统等.实体类型信息在信息检索中扮演着重要的角色,例如,查询“汤姆·汉克斯所出演的电影”,该查询限定了返回的实体类型是“电影”,这对提高查询结果的精度具有重要作用.然而,知识库中实体类型信息的缺失是十分严重的,影响了知识库在信息检索等领域中使用的正确性和广泛性.据统计,在DBpedia2014中,8%的实体没有任何类型信息,28%的实体只有高度抽象的类型信息(比如类型为“Thing”),因此对于实体类型补全的研究尤其是实体细粒度类型的补全是十分重要的.目前已有的方法包括基于概率模型和表示学习两类.以基于概率模型的SDType算法为例.首先,SDType为每个谓词计算对各个类型的区分能力得分,然后,在为实体做类型补全时,累加该实体所具有的谓词对各个类型的得分.此类方法没有考虑谓词与谓词之间的相互增强作用,在存在知识缺失的情况下会影响补全效果.以表示学习的类型补全方法TransE为例,此方法对于简单的关系(1-1的关系)补全是可以的,但是对于补全实体类型这种复杂的关系效果并不理想,另外,表示学习的训练集尤其是负例难以获得.由于模型需要学量的参数,在大数据量的背景下,性能也是一个问题.文中提出一种基于谓词-类型推理图的随机游走方法来补全缺失的实体类型.首先对知识库中已有知识进行统计,包括具有某个谓词的实体数目、属于某个类型的实体数目以及属于某个类型并且具有某个谓词的实体数目.其次,基于得到的统计信息构建结点由谓词和类型组成的有向推理图,推理图的边包括谓词-谓词和谓词-类型两种.在构�

一种新的用于跨领域推荐的迁移学习模型2367-2380

摘要:协同过滤是一种简单常用的推荐方法,但是当目标数据非常稀疏时,其性能会严重退化,借助与目标数据跨域关联的辅助数据进行跨领域推荐是解决此问题的一种有效途径.已有的跨领域推荐模型大多假设不同领域完全共享一个评分模式,忽略了领域特有评分模式,可能导致推荐性能退化.此外,许多模型基于单一桥梁迁移跨领域信息,正迁移不足.特别是在考虑领域特有被评分模式的前提下,据作者所知目前还没有模型利用项目的共享被评分模式进行跨领域推荐.因此,该文提出一种新的三元桥迁移学习模型,用于跨领域推荐.首先通过评分矩阵的集合分解提取用户的潜在因子和共享评分模式,以及项目的潜在因子和共享被评分模式,在此过程中考虑了领域特有模式,并对潜在因子施加相似性约束;然后利用潜在因子中的聚类信息构造邻接图;最后通过用户端和项目端的基于共享模式、潜在因子和邻接图的三元桥迁移学习联合预测缺失评分.在三个公开的真实数据集上进行的大量实验表明,该模型的推荐精度优于一些目前最先进的推荐模型.

一种滑动窗口下数据流Disjoint查询的增量处理算法2381-2403

摘要:对于滑动窗口下不具有全局约束机制的数据流Disjoint查询精确处理问题进行了研究,在现有FSM算法基础上提出了一种具有增量计算特征的查询处理算法DQPIC.该算法使用FSM算法处理第一个窗口中的数据流成员,同时保留了该窗口上的查询结果和窗口所对应STWM的最后一个列向量,除此之外还需要保留窗口STWM中所有列向量第curbound.highest个成员DTW路径的起始位置、距离值以及该成员在STWM中对应列向量的dmin值和候选查询结果这些信息.从第二个窗口开始,继续使用FSM算法处理窗口成员,同时也保留和第一个窗口一样的信息.在这个过程中,当处理相邻窗口中相同数据流成员时,通过比较该成员在前后两个窗口中分别对应的保留信息是否相同,可以确定算法有无继续处理剩余相同数据流成员的必要,能够在前一个窗口查询结果基础上增量地获得当前窗口查询结果.基于公用数据样本SST与Maskedchirp的仿真实验验证了该算法的有效性.提出的算法与现有其他算法执行结果相同,在空间开销增加1.12~3.27倍情况下,可以实现时间效率2.5~25倍的提高,对于与大窗口下的Disjoint查询相关应用场景,具有更好的时间效果.

ALFHJ:一种面向众核协处理器的自适应无锁哈希连接算法2404-2420

摘要:众核协处理器因其良好的并行计算能力和能源效率,正成为当前高性能计算普遍采用的加速设备.无划分哈希连接算法是多核平台上一种简单高效的连接算法,但随着众核上并发线程数的增加,其共享哈希表的锁同步问题正成为算法并行化的瓶颈.为解决上述问题,该文提出一种面向众核协处理器的自适应无锁哈希连接算法ALFHJ.该算法通过评估数据集的潜在冲突度动态调整算法参数及处理流程,支持基于CAS(比较与交换)原子操作的无锁共享哈希表构建,并利用SIMD指令进行哈希表探测.同时,该文进行了热点代码分析,讨论了一致性问题、ABA问题以及收敛性问题.在Xeon Phi上的实验结果表明,相比最新的基于锁同步的NPO(优化的无分区哈希连接)算法,ALFHJ算法有以下两点优势:(1)在提高哈希表空间利用率的同时,更能保持性能的相对稳定;(2)并行执行时间对于均匀数据集减少约10%,对于倾斜数据集减少约30%~50%.

计算机学报杂志科学与工程论坛
基于迁移鲁棒稀疏编码的图像表示方法2421-2432

摘要:图像表示是图像处理和图像理解研究中的关键问题之一.在图像的低层表示上有很多重要的研究工作,例如HOG,SIFT等.然而在图像的低层表示和高层语义间仍然存在着巨大的鸿沟.因而,很多机器学习的方法被用来学习图像的高层表示,例如主成分分析,稀疏编码,非负矩阵分解以及低秩表示等.传统机器学习假设标记图像和未标记图像服从同一分布,图像表示的误差服从高斯分布.然而现实中图像数据更新速度快,而且图像生成环境存在差异性,导致未标记图像与已标记图像不服从同一分布,因而需要重新标记数据和训练模型.并且图像数据容易出现异常,例如遮挡、腐蚀等等,从而不能再用高斯分布来估计误差.迁移学习允许标记图像(训练数据)和未标记图像(测试数据)服从不同的分布.基于迁移学习的图像表示方法学习一个新的好的特征空间.在这个新的特征空间下,可以较好地描述标记图像和未标记图像的语义信息.并且在这个新的特征空间下,从训练集中标记图像上学习到的统计模型(例如分类模型),可以较好地迁移到测试集中未标记图像上,从而充分利用已标记图像,将学习到的知识迁移到未标记的图像集上.该文提出了一种基于迁移鲁棒稀疏编码的图像表示方法,引入权值矩阵削弱异常点对分类的干扰,使用稀疏编码获得数据的高级语义,利用最小化最大均值差异缩小源域和目标域图像集之间的分布差异以及图拉普拉斯项保留图像集的几何特性.该文的主要贡献在于:一是通过权值矩阵泛化残差分布,使得所提出的基于迁移鲁棒稀疏编码的图像表示方法能大大减少异常点对编码和字典学习的影响;二是在鲁棒字典学习过程中,采用正则化参数代替迁移稀疏编码中的字典约束,从而将其转化为无约束优化问题,避免了拉格朗日求解法的复杂性.在几个通用迁�