2016年 第53卷 第2期
摘要：
随着互联网的快速普及与发展，互联网数据以惊人的速度在全世界范围内呈现出指数级增长的态势。而数据作为客观世界在信息世界中的抽象表达，其必然带有普遍的关联性。如何从海量的异构数据中挖掘实体及其语义关联和属性，并进行知识的融合，进而构建大规模的知识图谱，为语义搜索、深度问答、文本理解等应用提供有力支撑,已成为数据管理、数据挖掘和信息抽取等领域的一个重要研究方向。相比于传统的数据集成，在面向大规模的数据和知识融合过程中，融合算法的效率、多源数据的数据质量评估和基于语义的数据和知识融合等都给现有的数据集成和知识融合技术带来了巨大的挑战。2016年《计算机研究与发展》数据融合和知识融合专题侧重大规模数据和知识的抽取、融合及应用等诸多方面，涉及到数据管理、信息抽取和知识工程等多个交叉学科领域，研究主题包括数据与知识抽取技术、歧义性消除、数据与知识融合技术、数据与知识建模、关联知识库的应用等。本期专题经过公开征文收到43篇投稿，并最终收录了7篇论文，内容涉及实体抽取、实体链接、数据融合与溯源、短文本理解、数据查询、知识表示等主题，为相关领域的研究者探讨面向大数据的数据融合和知识融合的基础理论研究及其应用、讨论该领域内最新的突破性进展、交流新的学术思想和新方法以及展望未来的发展趋势提供了很好的沟通和交流机会。
随着互联网的快速普及与发展，互联网数据以惊人的速度在全世界范围内呈现出指数级增长的态势。而数据作为客观世界在信息世界中的抽象表达，其必然带有普遍的关联性。如何从海量的异构数据中挖掘实体及其语义关联和属性，并进行知识的融合，进而构建大规模的知识图谱，为语义搜索、深度问答、文本理解等应用提供有力支撑,已成为数据管理、数据挖掘和信息抽取等领域的一个重要研究方向。相比于传统的数据集成，在面向大规模的数据和知识融合过程中，融合算法的效率、多源数据的数据质量评估和基于语义的数据和知识融合等都给现有的数据集成和知识融合技术带来了巨大的挑战。2016年《计算机研究与发展》数据融合和知识融合专题侧重大规模数据和知识的抽取、融合及应用等诸多方面，涉及到数据管理、信息抽取和知识工程等多个交叉学科领域，研究主题包括数据与知识抽取技术、歧义性消除、数据与知识融合技术、数据与知识建模、关联知识库的应用等。本期专题经过公开征文收到43篇投稿，并最终收录了7篇论文，内容涉及实体抽取、实体链接、数据融合与溯源、短文本理解、数据查询、知识表示等主题，为相关领域的研究者探讨面向大数据的数据融合和知识融合的基础理论研究及其应用、讨论该领域内最新的突破性进展、交流新的学术思想和新方法以及展望未来的发展趋势提供了很好的沟通和交流机会。
2016, 53(2): 231-246.
DOI: 10.7544/issn1000-1239.2016.20150874
摘要：
随着大规模数据的关联和交叉，数据特征和现实需求都发生了变化.以大规模、多源异构、跨领域、跨媒体、跨语言、动态演化、普适化为主要特征的数据发挥着更重要的作用，相应的数据存储、分析和理解也面临着重大挑战.当下亟待解决的问题是如何利用数据的关联、交叉和融合实现大数据的价值最大化.认为解决这一问题的关键在于数据的融合，所以提出了大数据融合的概念.首先以Web数据、科学数据和商业数据的融合作为案例分析了大数据融合的需求和必要性，并提出了大数据融合的新任务；然后，总结分析了现有融合技术；最后针对大数据融合问题可能面临的挑战和大数据融合带来的问题进行了分析.
随着大规模数据的关联和交叉，数据特征和现实需求都发生了变化.以大规模、多源异构、跨领域、跨媒体、跨语言、动态演化、普适化为主要特征的数据发挥着更重要的作用，相应的数据存储、分析和理解也面临着重大挑战.当下亟待解决的问题是如何利用数据的关联、交叉和融合实现大数据的价值最大化.认为解决这一问题的关键在于数据的融合，所以提出了大数据融合的概念.首先以Web数据、科学数据和商业数据的融合作为案例分析了大数据融合的需求和必要性，并提出了大数据融合的新任务；然后，总结分析了现有融合技术；最后针对大数据融合问题可能面临的挑战和大数据融合带来的问题进行了分析.
2016, 53(2): 247-261.
DOI: 10.7544/issn1000-1239.2016.20160020
摘要：
人们构建的知识库通常被表示为网络形式，节点代表实体，连边代表实体间的关系.在网络表示形式下，人们需要设计专门的图算法存储和利用知识库，存在费时费力的缺点，并受到数据稀疏问题的困扰.最近，以深度学习为代表的表示学习技术受到广泛关注.表示学习旨在将研究对象的语义信息表示为稠密低维实值向量，知识表示学习则面向知识库中的实体和关系进行表示学习.该技术可以在低维空间中高效计算实体和关系的语义联系，有效解决数据稀疏问题，使知识获取、融合和推理的性能得到显著提升.介绍知识表示学习的最新进展，总结该技术面临的主要挑战和可能解决方案，并展望该技术的未来发展方向与前景.
人们构建的知识库通常被表示为网络形式，节点代表实体，连边代表实体间的关系.在网络表示形式下，人们需要设计专门的图算法存储和利用知识库，存在费时费力的缺点，并受到数据稀疏问题的困扰.最近，以深度学习为代表的表示学习技术受到广泛关注.表示学习旨在将研究对象的语义信息表示为稠密低维实值向量，知识表示学习则面向知识库中的实体和关系进行表示学习.该技术可以在低维空间中高效计算实体和关系的语义联系，有效解决数据稀疏问题，使知识获取、融合和推理的性能得到显著提升.介绍知识表示学习的最新进展，总结该技术面临的主要挑战和可能解决方案，并展望该技术的未来发展方向与前景.
2016, 53(2): 262-269.
DOI: 10.7544/issn1000-1239.2016.20150742
摘要：
短文本理解是一项对于机器智能至关重要但又充满挑战的任务.这项任务有益于众多应用场景，如搜索引擎、自动问答、广告和推荐系统.完成这些应用的首要步骤是将输入文本转化为机器可以诠释的形式，即帮助机器“理解”短文本的含义.基于这一目标，许多方法利用外来知识源来解决短文本中语境信息不足的问题.通过总结短文本理解领域的相关工作，介绍了基于向量的短文本理解框架.同时，探讨了短文本理解领域未来的研究方向.
短文本理解是一项对于机器智能至关重要但又充满挑战的任务.这项任务有益于众多应用场景，如搜索引擎、自动问答、广告和推荐系统.完成这些应用的首要步骤是将输入文本转化为机器可以诠释的形式，即帮助机器“理解”短文本的含义.基于这一目标，许多方法利用外来知识源来解决短文本中语境信息不足的问题.通过总结短文本理解领域的相关工作，介绍了基于向量的短文本理解框架.同时，探讨了短文本理解领域未来的研究方向.
2016, 53(2): 270-283.
DOI: 10.7544/issn1000-1239.2016.20150832
摘要：
实体链接(entity linking)是知识库扩容的核心关键技术，传统的实体链接方法通常受制于本地知识库的知识水平，而且忽略共现实体间的语义相关性.提出了一种基于图的中文集成实体链接方法，不仅能够充分利用知识库中实体间的结构化关系，而且能够通过增量证据挖掘获取外部知识，从而实现对同一文本中出现的多个歧义实体的批量实体链接.在开放域公开测试语料上的实验结果表明，所提出的实体相关图构造方法、增量证据挖掘方法和实体语义一致性判据是有效的，算法整体性能一致且显著地优于当前的主流算法.
实体链接(entity linking)是知识库扩容的核心关键技术，传统的实体链接方法通常受制于本地知识库的知识水平，而且忽略共现实体间的语义相关性.提出了一种基于图的中文集成实体链接方法，不仅能够充分利用知识库中实体间的结构化关系，而且能够通过增量证据挖掘获取外部知识，从而实现对同一文本中出现的多个歧义实体的批量实体链接.在开放域公开测试语料上的实验结果表明，所提出的实体相关图构造方法、增量证据挖掘方法和实体语义一致性判据是有效的，算法整体性能一致且显著地优于当前的主流算法.
2016, 53(2): 284-302.
DOI: 10.7544/issn1000-1239.2016.20150842
摘要：
作为语义网络和本体的基础，实体关系抽取已被广泛应用于信息检索、机器翻译和自动问答系统中.实体关系抽取的核心问题在于实体关系特征的选择和提取.中文长句的句式较复杂，经常包含多个实体的特点以及数据稀疏问题，给中文关系探测和关系抽取任务带了挑战.为了解决上述问题，提出了一种基于句法语义特征的实体关系抽取方法.通过将2个实体各自的依存句法关系进行组合，获取依存句法关系组合特征，利用依存句法分析和词性标注选择最近句法依赖动词特征.将这2个新特征加入到基于特征的关系探测和关系抽取中，使用支持向量机(support vector machine, SVM)方法，以真实旅游领域文本作为语料进行实验.实验表明，从句法和语义上提取的2个特征能够有效地提高实体关系探测和关系抽取的性能，其准确率、召回率和F1值均优于已有方法.此外，最近句法依赖动词特征非常有效，尤其对数据稀疏的关系类型贡献最大，在关系探测和关系抽取上的性能均优于当前经典的基于动词特征方法.
作为语义网络和本体的基础，实体关系抽取已被广泛应用于信息检索、机器翻译和自动问答系统中.实体关系抽取的核心问题在于实体关系特征的选择和提取.中文长句的句式较复杂，经常包含多个实体的特点以及数据稀疏问题，给中文关系探测和关系抽取任务带了挑战.为了解决上述问题，提出了一种基于句法语义特征的实体关系抽取方法.通过将2个实体各自的依存句法关系进行组合，获取依存句法关系组合特征，利用依存句法分析和词性标注选择最近句法依赖动词特征.将这2个新特征加入到基于特征的关系探测和关系抽取中，使用支持向量机(support vector machine, SVM)方法，以真实旅游领域文本作为语料进行实验.实验表明，从句法和语义上提取的2个特征能够有效地提高实体关系探测和关系抽取的性能，其准确率、召回率和F1值均优于已有方法.此外，最近句法依赖动词特征非常有效，尤其对数据稀疏的关系类型贡献最大，在关系探测和关系抽取上的性能均优于当前经典的基于动词特征方法.
2016, 53(2): 303-315.
DOI: 10.7544/issn1000-1239.2016.20150839
摘要：
本体在演变的过程中常出现不一致性问题，这将导致经典的推理模式失效. 不一致容忍语义能有效地解决推理失效的问题，但各类不一致容忍语义或者需要耗费大量计算，或者丢弃了本体中有效的信息.为此，一种针对IAR-语义和ICAR-语义的变种被用以解决上述的缺陷.新定义的IPAR-语义能够避免计算整个ABox关于TBox的封闭，在减少计算量的同时尽可能地保留了本体中的信息.在IPAR-语义下实现了基于图的查询应答方法，新方法将本体和查询以不同的规则构建成图，避免了传统重写导致的查询冗余的问题.最后，通过实验对比新的查询应答方法与ICAR-语义下的查询应答方法，实验结果表明：基于图的一致性查询方法执行效率要优于ICAR-语义下的查询方法；在本体规模不断增加的情况下，新方法具有更好的稳定性.
本体在演变的过程中常出现不一致性问题，这将导致经典的推理模式失效. 不一致容忍语义能有效地解决推理失效的问题，但各类不一致容忍语义或者需要耗费大量计算，或者丢弃了本体中有效的信息.为此，一种针对IAR-语义和ICAR-语义的变种被用以解决上述的缺陷.新定义的IPAR-语义能够避免计算整个ABox关于TBox的封闭，在减少计算量的同时尽可能地保留了本体中的信息.在IPAR-语义下实现了基于图的查询应答方法，新方法将本体和查询以不同的规则构建成图，避免了传统重写导致的查询冗余的问题.最后，通过实验对比新的查询应答方法与ICAR-语义下的查询应答方法，实验结果表明：基于图的一致性查询方法执行效率要优于ICAR-语义下的查询方法；在本体规模不断增加的情况下，新方法具有更好的稳定性.
2016, 53(2): 316-325.
DOI: 10.7544/issn1000-1239.2016.20150872
摘要：
数据融合是集成数据的质量保证和分析挖掘的前提条件；然而，数据融合作为一个整体对于用户来讲是一个黑盒过程，使得当前数据融合过程缺乏可解释性和可调试性.为了便于数据融合过程中有效的冲突检测和调试，需要利用数据溯源技术建立数据融合的可回溯机制.数据溯源描述了数据产生并随着时间推移而演变的整个过程，半环溯源模型作为一种经典的数据溯源表示形式,不仅能表示结果数据是由哪些数据派生的，而且还能够描述这些数据以什么方式进行派生.主要研究用于数据融合的半环溯源的计算问题.用于数据融合的半环溯源计算是一个pay as you go的模式，计算数据的溯源信息是一个非常耗时的过程.首先，提出一种基于Kleene序列的近似迭代方法，并证明了该方法与半环溯源的派生树定义的关系，从而证明了该方法的正确性.然后，提出了一种类牛顿序列，这种方法比Kleene序列有更好的收敛性.由于递归的引入可能会导致这2种迭代算法无法终止，通过分析结果元组的半环多项式溯源的特点，证明这2种近似算法最坏可在n次迭代后终止.最后，通过实验说明了本文提出的方法是可行和有效的.
数据融合是集成数据的质量保证和分析挖掘的前提条件；然而，数据融合作为一个整体对于用户来讲是一个黑盒过程，使得当前数据融合过程缺乏可解释性和可调试性.为了便于数据融合过程中有效的冲突检测和调试，需要利用数据溯源技术建立数据融合的可回溯机制.数据溯源描述了数据产生并随着时间推移而演变的整个过程，半环溯源模型作为一种经典的数据溯源表示形式,不仅能表示结果数据是由哪些数据派生的，而且还能够描述这些数据以什么方式进行派生.主要研究用于数据融合的半环溯源的计算问题.用于数据融合的半环溯源计算是一个pay as you go的模式，计算数据的溯源信息是一个非常耗时的过程.首先，提出一种基于Kleene序列的近似迭代方法，并证明了该方法与半环溯源的派生树定义的关系，从而证明了该方法的正确性.然后，提出了一种类牛顿序列，这种方法比Kleene序列有更好的收敛性.由于递归的引入可能会导致这2种迭代算法无法终止，通过分析结果元组的半环多项式溯源的特点，证明这2种近似算法最坏可在n次迭代后终止.最后，通过实验说明了本文提出的方法是可行和有效的.
2016, 53(2): 326-340.
DOI: 10.7544/issn1000-1239.2016.20150296
摘要：
如今的数据中心严重受限于其功耗预算和碳排放配额.面对与日俱增的能耗开支和节能减排压力，学术界和工业界不约而同地开始关注非传统的绿色数据中心设计.最近，能源存储设备(energy storage system, ESS)逐渐成为数据中心中一种新兴的关键使能元件,它能够极大提升数据中心的能效和可持续性.一方面，ESS使得数据中心可以通过削减由不规则负载带来的短暂峰值功耗来降低运营成本;另一方面，它还能够方便新能源在数据中心中的融合，从而极大降低对环境的不良影响.介绍ESS在新型数据中心设计中的系统结构，并重点分析了ESS在管理功耗尖峰和供电波动两大方面发挥的重要作用.对比多项前沿研究并探讨ESS的关键设计点如成本、能效、可靠性等，同时分析了ESS未来发展所面临的其他机遇和挑战.
如今的数据中心严重受限于其功耗预算和碳排放配额.面对与日俱增的能耗开支和节能减排压力，学术界和工业界不约而同地开始关注非传统的绿色数据中心设计.最近，能源存储设备(energy storage system, ESS)逐渐成为数据中心中一种新兴的关键使能元件,它能够极大提升数据中心的能效和可持续性.一方面，ESS使得数据中心可以通过削减由不规则负载带来的短暂峰值功耗来降低运营成本;另一方面，它还能够方便新能源在数据中心中的融合，从而极大降低对环境的不良影响.介绍ESS在新型数据中心设计中的系统结构，并重点分析了ESS在管理功耗尖峰和供电波动两大方面发挥的重要作用.对比多项前沿研究并探讨ESS的关键设计点如成本、能效、可靠性等，同时分析了ESS未来发展所面临的其他机遇和挑战.
2016, 53(2): 341-353.
DOI: 10.7544/issn1000-1239.2016.20148436
摘要：
片上网络(networks-on-chip, NoC)是3维集成电路的主要通信技术之一.其中，路由器是3维片上网络的重要组成部件.现有的面向3维片上网络中路由器的容错技术，通常采取路由器整体冗余技术或者直接舍弃失效路由器的方法，这导致网络资源损失较为严重.提出一种面向3维片上网络的轻量级细粒度容错机制，充分利用故障路由器中仍能正常运行的有效资源，保障系统通信.提出的容错机制包括一种高可靠性路由器微体系结构设计和一种与之匹配的容错路由机制.通过实验对比和分析，相比较于已有的3维片上网络容错机制，提出的细粒度容错机制具备较高的通信性能和可靠性，同时面积和功耗开销较小.
片上网络(networks-on-chip, NoC)是3维集成电路的主要通信技术之一.其中，路由器是3维片上网络的重要组成部件.现有的面向3维片上网络中路由器的容错技术，通常采取路由器整体冗余技术或者直接舍弃失效路由器的方法，这导致网络资源损失较为严重.提出一种面向3维片上网络的轻量级细粒度容错机制，充分利用故障路由器中仍能正常运行的有效资源，保障系统通信.提出的容错机制包括一种高可靠性路由器微体系结构设计和一种与之匹配的容错路由机制.通过实验对比和分析，相比较于已有的3维片上网络容错机制，提出的细粒度容错机制具备较高的通信性能和可靠性，同时面积和功耗开销较小.
2016, 53(2): 354-361.
DOI: 10.7544/issn1000-1239.2016.20148380
摘要：
在主副版本机制的全局容错调度中，副版本运行窗口短，采用优先级继承策略的副版本响应时间长，容易错失截止期.针对副版本实时性差的问题，提出基于优先级提升策略的全局容错调度算法(fault tolerant global scheduling with backup priority promotion, FTGS-BPP)，通过赋予副版本比主版本高的优先级，减少副版本在运行过程中受到的干扰，缩短了副版本的响应时间，改善了副版本的实时性，从而减少了实现容错所需的额外处理器资源.仿真结果表明，和采用优先级继承策略的全局容错调度算法相比，FTGS-BPP在调度相同的任务集时明显降低了处理器资源需求.
在主副版本机制的全局容错调度中，副版本运行窗口短，采用优先级继承策略的副版本响应时间长，容易错失截止期.针对副版本实时性差的问题，提出基于优先级提升策略的全局容错调度算法(fault tolerant global scheduling with backup priority promotion, FTGS-BPP)，通过赋予副版本比主版本高的优先级，减少副版本在运行过程中受到的干扰，缩短了副版本的响应时间，改善了副版本的实时性，从而减少了实现容错所需的额外处理器资源.仿真结果表明，和采用优先级继承策略的全局容错调度算法相比，FTGS-BPP在调度相同的任务集时明显降低了处理器资源需求.
2016, 53(2): 362-373.
DOI: 10.7544/issn1000-1239.2016.20148246
摘要：
排序是计算机科学中最基本的问题之一，随着众核处理器结构的不断发展，设计众核结构上的高效排序算法具有重要意义.众核处理器的一个重要方向是阵列众核处理器，根据阵列众核处理器的结构特点，提出了2种面向阵列众核结构的高效归并排序算法，通过利用DMA(direct memory access)多缓冲机制提高访存效率、深度平衡归并策略保持众多核心之间的负载均衡、SIMD(single instruction multiple data)归并方法提高归并计算效率以及片上交换归并策略提高片上数据重用率，大幅度提高了阵列众核处理器的排序性能.在异构融合阵列众核处理器DFMC(deeply-fused many-core)原型系统的实验结果表明，算法排序速度达647 MKeys/s(million keys per second)，其排序效率(排序速度/峰值性能)是NVIDIA GPU上最快的归并排序算法(GTX580平台)的3.3倍，是Intel Xeon Phi上最快的归并排序算法的2.7倍.最后，建立了阵列众核处理器上归并排序算法的性能分析模型，利用该模型分析了主要结构参数与算法性能的关系，对阵列众核处理器的研究有一定的指导意义.
排序是计算机科学中最基本的问题之一，随着众核处理器结构的不断发展，设计众核结构上的高效排序算法具有重要意义.众核处理器的一个重要方向是阵列众核处理器，根据阵列众核处理器的结构特点，提出了2种面向阵列众核结构的高效归并排序算法，通过利用DMA(direct memory access)多缓冲机制提高访存效率、深度平衡归并策略保持众多核心之间的负载均衡、SIMD(single instruction multiple data)归并方法提高归并计算效率以及片上交换归并策略提高片上数据重用率，大幅度提高了阵列众核处理器的排序性能.在异构融合阵列众核处理器DFMC(deeply-fused many-core)原型系统的实验结果表明，算法排序速度达647 MKeys/s(million keys per second)，其排序效率(排序速度/峰值性能)是NVIDIA GPU上最快的归并排序算法(GTX580平台)的3.3倍，是Intel Xeon Phi上最快的归并排序算法的2.7倍.最后，建立了阵列众核处理器上归并排序算法的性能分析模型，利用该模型分析了主要结构参数与算法性能的关系，对阵列众核处理器的研究有一定的指导意义.
2016, 53(2): 374-389.
DOI: 10.7544/issn1000-1239.2016.20148277
摘要：
为了弥补从大数据技术到行业应用之间的鸿沟,针对当前行业用户对大数据处理平台的持续扩展、一体化和多样性需求，提出了大数据一体机的可扩展性、可定制性和多类型处理模型，并基于此设计了云海大数据一体机.该一体机采用兼顾横向和纵向可扩展的体系结构，并采用硬件可定制化设计和混合型软件架构支持多种大数据应用类型. 在此基础上，针对HDFS元数据服务瓶颈问题、MapReduce负载倾斜问题、HBase的跨域问题，介绍了在云海大数据一体机中采用的多元数据服务、负载均衡和跨数据中心大表技术.在电信、金融和环保行业实际案例中的应用和测试表明，上述体系结构和关键技术是可行和有效的.
为了弥补从大数据技术到行业应用之间的鸿沟,针对当前行业用户对大数据处理平台的持续扩展、一体化和多样性需求，提出了大数据一体机的可扩展性、可定制性和多类型处理模型，并基于此设计了云海大数据一体机.该一体机采用兼顾横向和纵向可扩展的体系结构，并采用硬件可定制化设计和混合型软件架构支持多种大数据应用类型. 在此基础上，针对HDFS元数据服务瓶颈问题、MapReduce负载倾斜问题、HBase的跨域问题，介绍了在云海大数据一体机中采用的多元数据服务、负载均衡和跨数据中心大表技术.在电信、金融和环保行业实际案例中的应用和测试表明，上述体系结构和关键技术是可行和有效的.
2016, 53(2): 390-398.
DOI: 10.7544/issn1000-1239.2016.20148039
摘要：
当前在大规模并行计算机中，多数并行程序的用户习惯于使用虚拟地址进行编程.因此，虚拟地址与物理地址之间的转换效率直接影响了并行程序的执行性能，而cache能够有效地提高虚实地址转换的效率并降低延迟.提出了一种在大规模并行计算机互连网络中的地址转换cache.它采用了嵌入式DRAM(embedded dynamic random access memory, eDRAM)存储器，容纳更多的地址转换表项，从而提高命中率.并设计一种eDRAM刷新机制，隐藏了刷新操作，避免刷新导致的性能损失.ATC(address translation cache)中实现了诸如纠错码与旁路机制等多种可靠性设计.在32个计算结点上运行业界公认的NPB测试程序，结果显示32个结点中ATC的平均命中率达到了95.3%，表明ATC设计的正确性与高性能.并且通过与3种传统SRAM(static random access memory)实现的cache进行对比实验，说明了cache容量是提高命中率的关键因素.
当前在大规模并行计算机中，多数并行程序的用户习惯于使用虚拟地址进行编程.因此，虚拟地址与物理地址之间的转换效率直接影响了并行程序的执行性能，而cache能够有效地提高虚实地址转换的效率并降低延迟.提出了一种在大规模并行计算机互连网络中的地址转换cache.它采用了嵌入式DRAM(embedded dynamic random access memory, eDRAM)存储器，容纳更多的地址转换表项，从而提高命中率.并设计一种eDRAM刷新机制，隐藏了刷新操作，避免刷新导致的性能损失.ATC(address translation cache)中实现了诸如纠错码与旁路机制等多种可靠性设计.在32个计算结点上运行业界公认的NPB测试程序，结果显示32个结点中ATC的平均命中率达到了95.3%，表明ATC设计的正确性与高性能.并且通过与3种传统SRAM(static random access memory)实现的cache进行对比实验，说明了cache容量是提高命中率的关键因素.
2016, 53(2): 399-415.
DOI: 10.7544/issn1000-1239.2015.20148358
摘要：
随着非易失存储器的出现和广泛使用，存储体系结构正在发生根本改变.传统数据库系统与文件系统事务处理技术大多基于磁盘设备，设计之初并未考虑非易失存储器特性.为了充分利用非易失存储器特性，缩小计算机系统的I/O性能与CPU处理性能之间的差距，基于非易失存储器的事务存储系统与技术成为了研究热点.首先讨论了软件层事务处理技术的现状，分别介绍了传统数据库系统与文件系统事务处理常用技术；然后依据闪存和相变内存进行划分，对现有基于非易失存储器的事务存储系统与技术进行了讨论；最后给出了基于非易失存储器的事务存储系统研究展望.在基于闪存的事务存储相关研究中，首先分析了使用传统设备接口闪存设备加速事务处理的系统设计，然后重点分析了基于专用事务接口的事务闪存存储系统研究，并对基于闪存的事务存储系统不同研究进行了比较.在基于相变内存的事务存储相关研究中，分别分析并比较了相变内存在主存环境和外存环境提供事务处理的技术，重点讨论了日志与缓存融合技术、细粒度日志技术等关键问题.
随着非易失存储器的出现和广泛使用，存储体系结构正在发生根本改变.传统数据库系统与文件系统事务处理技术大多基于磁盘设备，设计之初并未考虑非易失存储器特性.为了充分利用非易失存储器特性，缩小计算机系统的I/O性能与CPU处理性能之间的差距，基于非易失存储器的事务存储系统与技术成为了研究热点.首先讨论了软件层事务处理技术的现状，分别介绍了传统数据库系统与文件系统事务处理常用技术；然后依据闪存和相变内存进行划分，对现有基于非易失存储器的事务存储系统与技术进行了讨论；最后给出了基于非易失存储器的事务存储系统研究展望.在基于闪存的事务存储相关研究中，首先分析了使用传统设备接口闪存设备加速事务处理的系统设计，然后重点分析了基于专用事务接口的事务闪存存储系统研究，并对基于闪存的事务存储系统不同研究进行了比较.在基于相变内存的事务存储相关研究中，分别分析并比较了相变内存在主存环境和外存环境提供事务处理的技术，重点讨论了日志与缓存融合技术、细粒度日志技术等关键问题.
2016, 53(2): 416-430.
DOI: 10.7544/issn1000-1239.2016.20148360
摘要：
动态随机存储器(DRAM)具有速度快、密度高、成本低的优势，被广泛应用于计算机的主存.DRAM采用电容作为存储单元，电容电荷的多少表示数字“0”或“1”.由于存在漏电现象，电容里的电荷会缓慢流失，造成数据丢失.为保证数据正确性，DRAM采用周期性的刷新操作，在数据丢失前，把数据读出然后重新写入存储单元.刷新操作会阻碍正常访存的执行，造成性能上的开销；同时刷新操作会消耗额外的功耗，带来功耗上的开销.刷新的开销与DRAM密度相关：在过去，当DRAM密度较小时，需要刷新的存储单元数较少，刷新开销很小，并未引起关注；但是，随着摩尔定律的发展，DRAM密度越来越大，目前已发展到千兆比特级别，其刷新周期并没有改善，单位时间内需要刷新的存储单元数越来越多，从而使刷新带来的性能和功耗开销越来越严重.刷新问题目前得到了工业界和学术界的广泛关注.首先介绍了目前DRAM的刷新方式和开销，以及工业界已经实现的一些改进；然后把工业界和学术界提出的众多优化方法分为“减轻刷新操作对访存的阻塞”和“减少不必要的刷新操作”两大类，分别进行了分析和总结；最后给出了关于智能刷新管理的总结和展望.
动态随机存储器(DRAM)具有速度快、密度高、成本低的优势，被广泛应用于计算机的主存.DRAM采用电容作为存储单元，电容电荷的多少表示数字“0”或“1”.由于存在漏电现象，电容里的电荷会缓慢流失，造成数据丢失.为保证数据正确性，DRAM采用周期性的刷新操作，在数据丢失前，把数据读出然后重新写入存储单元.刷新操作会阻碍正常访存的执行，造成性能上的开销；同时刷新操作会消耗额外的功耗，带来功耗上的开销.刷新的开销与DRAM密度相关：在过去，当DRAM密度较小时，需要刷新的存储单元数较少，刷新开销很小，并未引起关注；但是，随着摩尔定律的发展，DRAM密度越来越大，目前已发展到千兆比特级别，其刷新周期并没有改善，单位时间内需要刷新的存储单元数越来越多，从而使刷新带来的性能和功耗开销越来越严重.刷新问题目前得到了工业界和学术界的广泛关注.首先介绍了目前DRAM的刷新方式和开销，以及工业界已经实现的一些改进；然后把工业界和学术界提出的众多优化方法分为“减轻刷新操作对访存的阻塞”和“减少不必要的刷新操作”两大类，分别进行了分析和总结；最后给出了关于智能刷新管理的总结和展望.
2016, 53(2): 431-442.
DOI: 10.7544/issn1000-1239.2016.20148327
摘要：
在大规模分布式存储系统的容错技术中，数据副本管理是一种重要机制.针对网络环境中的动态副本管理需求，建立一种文件支持度指标及其动态计算模型.该模型通过周期性数据采集，利用文件支持度的自相关性，结合文件上一采集周期访问量、访问量占比、被访问数据量以及文件级别等参数，构建了能够较准确描述文件的动态副本需求状态模型.通过动态适应性的参数调整以适应变化的负载状态，使副本管理决策尽可能反映系统实际状态.在此基础上设计了数据结点负载均衡、副本调整、副本清理等相关算法，实现了动态副本管理的目标.通过实验验证了所设计的动态副本管理机制的有效性.
在大规模分布式存储系统的容错技术中，数据副本管理是一种重要机制.针对网络环境中的动态副本管理需求，建立一种文件支持度指标及其动态计算模型.该模型通过周期性数据采集，利用文件支持度的自相关性，结合文件上一采集周期访问量、访问量占比、被访问数据量以及文件级别等参数，构建了能够较准确描述文件的动态副本需求状态模型.通过动态适应性的参数调整以适应变化的负载状态，使副本管理决策尽可能反映系统实际状态.在此基础上设计了数据结点负载均衡、副本调整、副本清理等相关算法，实现了动态副本管理的目标.通过实验验证了所设计的动态副本管理机制的有效性.
2016, 53(2): 443-448.
DOI: 10.7544/issn1000-1239.2016.20148040
摘要：
预取作为一种提升存储系统性能的有效手段被广泛使用，然而传统的预取算法大多基于顺序性访问特征的探测，这使得它们在非顺序数据访问环境下很难奏效，甚至可能因为预取准确率较低而对存储系统的性能带来负面影响.而基于频繁序列挖掘的预取算法则能够通过分析数据的访问行为找出潜在规律，从而能在非顺序访问模式下也取得一定的性能提升.同时，为了应对某些缓存受限的应用场景，如嵌入式系统，预取算法通过提高分析的准确率减少预取可能对缓存带来的不利影响.新提出的预取算法基于频繁序列挖掘技术，并使用字典树组织预取规则，通过多步匹配和子树分割技术精细地控制规则的使用，提升预取的准确率，从而使得预取算法能够有效提升存储系统的性能.
预取作为一种提升存储系统性能的有效手段被广泛使用，然而传统的预取算法大多基于顺序性访问特征的探测，这使得它们在非顺序数据访问环境下很难奏效，甚至可能因为预取准确率较低而对存储系统的性能带来负面影响.而基于频繁序列挖掘的预取算法则能够通过分析数据的访问行为找出潜在规律，从而能在非顺序访问模式下也取得一定的性能提升.同时，为了应对某些缓存受限的应用场景，如嵌入式系统，预取算法通过提高分析的准确率减少预取可能对缓存带来的不利影响.新提出的预取算法基于频繁序列挖掘技术，并使用字典树组织预取规则，通过多步匹配和子树分割技术精细地控制规则的使用，提升预取的准确率，从而使得预取算法能够有效提升存储系统的性能.
2016, 53(2): 449-458.
DOI: 10.7544/issn1000-1239.2016.20148275
摘要：
大数据集成是提供高质量数据以进行决策的基础.集成的一个关键环节是根据实体在数据库中的不同元组确定其准确属性值.最新的R-topK方法在数据上实施人工设计的规则确定属性值间的准确程度，得到了相对准确的属性值.然而这种方法在处理多个可能的准确值或设计的规则存在冲突等情况下需要较多人工交互.为此提出基于权重规则的WR(weighted-rule)方法确定大数据集成中数据的准确属性值.该方法为属性值间准确程度的判断规则扩充了权重，在准确值发生冲突时避免了R-topK方法中人工交互干预.基于追逐过程设计了约束条件推理算法，并证明它能够在O(n\+2)内推导出每对属性值间的带权重的准确程度，形成推导准确属性值的约束条件.面对约束条件中可能的冲突，提出了目标求解算法，在O(n)时间内从所有属性值组合中搜索最可能的准确属性值.在真实和合成数据集中进行了充分的实验，验证了WR方法的效果和效率.WR方法较R-topK方法在性能上提高了3~15倍，在效果上提升7%~80%.
大数据集成是提供高质量数据以进行决策的基础.集成的一个关键环节是根据实体在数据库中的不同元组确定其准确属性值.最新的R-topK方法在数据上实施人工设计的规则确定属性值间的准确程度，得到了相对准确的属性值.然而这种方法在处理多个可能的准确值或设计的规则存在冲突等情况下需要较多人工交互.为此提出基于权重规则的WR(weighted-rule)方法确定大数据集成中数据的准确属性值.该方法为属性值间准确程度的判断规则扩充了权重，在准确值发生冲突时避免了R-topK方法中人工交互干预.基于追逐过程设计了约束条件推理算法，并证明它能够在O(n\+2)内推导出每对属性值间的带权重的准确程度，形成推导准确属性值的约束条件.面对约束条件中可能的冲突，提出了目标求解算法，在O(n)时间内从所有属性值组合中搜索最可能的准确属性值.在真实和合成数据集中进行了充分的实验，验证了WR方法的效果和效率.WR方法较R-topK方法在性能上提高了3~15倍，在效果上提升7%~80%.
2016, 53(2): 459-466.
DOI: 10.7544/issn1000-1239.2016.20148284
摘要：
异构信息网络中包含多类实体和关系.随着数据规模增大时，不同类实体规模增长不平衡，异构关系数据也变得异常稀疏，导致聚类算法的时间复杂度高、准确率低.针对上述问题，提出了一种基于关联矩阵分解的2阶段联合聚类算法FNMTF-CM.第1阶段,抽取规模较小的一类实体中的关联关系构建关联矩阵，通过对称非负矩阵分解得到划分指示矩阵.与原始关系矩阵相比，关联矩阵的稠密度更高，规模更小.第2阶段,将划分指示矩阵作为关系矩阵三分解的输入，进而快速求解另一类实体的划分指示矩阵.在标准测试数据集和异构关系数据集上的实验表明，算法准确率和性能整体优于传统的基于非负矩阵分解的联合聚类算法.
异构信息网络中包含多类实体和关系.随着数据规模增大时，不同类实体规模增长不平衡，异构关系数据也变得异常稀疏，导致聚类算法的时间复杂度高、准确率低.针对上述问题，提出了一种基于关联矩阵分解的2阶段联合聚类算法FNMTF-CM.第1阶段,抽取规模较小的一类实体中的关联关系构建关联矩阵，通过对称非负矩阵分解得到划分指示矩阵.与原始关系矩阵相比，关联矩阵的稠密度更高，规模更小.第2阶段,将划分指示矩阵作为关系矩阵三分解的输入，进而快速求解另一类实体的划分指示矩阵.在标准测试数据集和异构关系数据集上的实验表明，算法准确率和性能整体优于传统的基于非负矩阵分解的联合聚类算法.
2016, 53(2): 467-478.
DOI: 10.7544/issn1000-1239.2016.20148281
摘要：
多元连接是数据分析最常用的操作之一，MapReduce是广泛用于大规模数据分析处理的编程模型，它给多元连接优化带来新的挑战：传统的优化方法不能简单地适用到MapReduce中；MapReduce连接执行算法尚存优化空间.针对前者，考虑到I/O代价是连接运算的主要代价，首先以降低I/O代价为目标提出一种启发式算法确定多元连接执行顺序，并在此基础上进一步优化，最后针对MapReduce设计一种并行执行策略提高多元连接的整体性能.针对后者，考虑到负载均衡能够有效减少MapReduce的“木桶效应”，通过任务公平分配算法提高连接内部的并行度，并在此基础上给出Reduce任务个数的确定方法.最后，通过实验验证本文提出的执行计划确定方法以及负载均衡算法的优化效果.该研究对大数据环境下MapReduce多元连接的应用具有指导意义，可以优化如OLAP分析中的星型连接、社交网络中社团发现的链式连接等应用的性能.
多元连接是数据分析最常用的操作之一，MapReduce是广泛用于大规模数据分析处理的编程模型，它给多元连接优化带来新的挑战：传统的优化方法不能简单地适用到MapReduce中；MapReduce连接执行算法尚存优化空间.针对前者，考虑到I/O代价是连接运算的主要代价，首先以降低I/O代价为目标提出一种启发式算法确定多元连接执行顺序，并在此基础上进一步优化，最后针对MapReduce设计一种并行执行策略提高多元连接的整体性能.针对后者，考虑到负载均衡能够有效减少MapReduce的“木桶效应”，通过任务公平分配算法提高连接内部的并行度，并在此基础上给出Reduce任务个数的确定方法.最后，通过实验验证本文提出的执行计划确定方法以及负载均衡算法的优化效果.该研究对大数据环境下MapReduce多元连接的应用具有指导意义，可以优化如OLAP分析中的星型连接、社交网络中社团发现的链式连接等应用的性能.
2016, 53(2): 479-491.
DOI: 10.7544/issn1000-1239.2016.20148274
摘要：
随着图数据规模的爆炸式增长，其形式也越来越复杂.异构信息网可建模成包含多种类型的顶点和多种类型的边的图.例如，文献数据库、在线购物网站等.首次研究异构信息网上的可达性查询问题.利用不同类型顶点之间的关系，查询2个顶点满足路径模式的可达性，该问题的时间复杂度是多项式的.然而在大规模的网络上，每次查询遍历一遍网络的时间开销也是不能容忍的.现有的可达性查询问题主要分为2类: k跳可达性查询和带有标签约束的可达性查询.但是这2种问题的算法都不能用于解决异构信息网上的可达性查询问题.因此，为了实现高效的在线查询，提出一种新的索引结构，通过路径模式的分解，预先计算部分路径模式的可达信息.当在线查询到来时，在路径模式的偏序图上，快速找到索引结构中存在的路径子模式，高效地计算查询结果.在真实和人工数据集上进行了大量实验，验证了算法的有效性.
随着图数据规模的爆炸式增长，其形式也越来越复杂.异构信息网可建模成包含多种类型的顶点和多种类型的边的图.例如，文献数据库、在线购物网站等.首次研究异构信息网上的可达性查询问题.利用不同类型顶点之间的关系，查询2个顶点满足路径模式的可达性，该问题的时间复杂度是多项式的.然而在大规模的网络上，每次查询遍历一遍网络的时间开销也是不能容忍的.现有的可达性查询问题主要分为2类: k跳可达性查询和带有标签约束的可达性查询.但是这2种问题的算法都不能用于解决异构信息网上的可达性查询问题.因此，为了实现高效的在线查询，提出一种新的索引结构，通过路径模式的分解，预先计算部分路径模式的可达信息.当在线查询到来时，在路径模式的偏序图上，快速找到索引结构中存在的路径子模式，高效地计算查询结果.在真实和人工数据集上进行了大量实验，验证了算法的有效性.
2016, 53(2): 492-502.
DOI: 10.7544/issn1000-1239.2016.20148283
摘要：
网络大数据时代的到来使得知识网络中时空信息越来越丰富.现有的知识网络描述模型对知识的时空信息刻画不足.研究证明，利用网络中知识的时空信息以及相关性，能够提高网络中知识间的关联推理的准确率.针对以上问题，首先提出了一种包含时空信息的演化知识网络表示模型，然后研究在该网络模型上的关联推理问题，提出了一种基于背包问题的知识间关联推理方法.在多个数据集上的实验证明了所提出的关联推理方法的有效性以及对大规模知识网络的适应性.
网络大数据时代的到来使得知识网络中时空信息越来越丰富.现有的知识网络描述模型对知识的时空信息刻画不足.研究证明，利用网络中知识的时空信息以及相关性，能够提高网络中知识间的关联推理的准确率.针对以上问题，首先提出了一种包含时空信息的演化知识网络表示模型，然后研究在该网络模型上的关联推理问题，提出了一种基于背包问题的知识间关联推理方法.在多个数据集上的实验证明了所提出的关联推理方法的有效性以及对大规模知识网络的适应性.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
