2020年 第57卷 第6期
2020, 57(6): 1123-1124.
DOI: 10.7544/issn1000-1239.2020.qy0601
摘要：
我们高兴地向读者推出本刊“计算机体系结构前沿技术”专题！本专题收录的6篇文章既包含不同技术领域和方向的综述，也包含了具体技术的发明和介绍.
我们高兴地向读者推出本刊“计算机体系结构前沿技术”专题！本专题收录的6篇文章既包含不同技术领域和方向的综述，也包含了具体技术的发明和介绍.
2020, 57(6): 1125-1139.
DOI: 10.7544/issn1000-1239.2020.20200010
摘要：
新兴的非易失存储器STT-RAM具有低泄漏功率、高密度和快速读取速度、高写入能量等特点；而SRAM具有高泄漏功率、低密度、快速读取写入速度、低写入能量等特点.SRAM和STT-RAM相结合组成的混合缓存充分发挥了两者的性能，提供了比SRAM更低的泄漏功率和更高的单元密度，比STT-RAM更高的写入速度和更低的写入能量.混合缓存结构主要是通过把写密集数据放入SRAM中、读密集型数据放入STT-RAM中发挥这2种存储器的性能.因此如何识别并分配读写密集型数据是混合缓存设计的关键挑战.利用缓存访问请求的写入强度和重用信息，提出一种基于强化学习的缓存管理方法，设计缓存分配策略优化能耗.关键思想是使用强化学习对得到的缓存行(cache line)集合的能耗进行学习，得到该集合分配到SRAM或者STT-RAM的权重，将集合中的缓存行分配到权重大的区域.实验评估表明：提出的策略与以前的策略相比，在单核(四核)系统中能耗平均降低了16.9％(9.7％).
新兴的非易失存储器STT-RAM具有低泄漏功率、高密度和快速读取速度、高写入能量等特点；而SRAM具有高泄漏功率、低密度、快速读取写入速度、低写入能量等特点.SRAM和STT-RAM相结合组成的混合缓存充分发挥了两者的性能，提供了比SRAM更低的泄漏功率和更高的单元密度，比STT-RAM更高的写入速度和更低的写入能量.混合缓存结构主要是通过把写密集数据放入SRAM中、读密集型数据放入STT-RAM中发挥这2种存储器的性能.因此如何识别并分配读写密集型数据是混合缓存设计的关键挑战.利用缓存访问请求的写入强度和重用信息，提出一种基于强化学习的缓存管理方法，设计缓存分配策略优化能耗.关键思想是使用强化学习对得到的缓存行(cache line)集合的能耗进行学习，得到该集合分配到SRAM或者STT-RAM的权重，将集合中的缓存行分配到权重大的区域.实验评估表明：提出的策略与以前的策略相比，在单核(四核)系统中能耗平均降低了16.9％(9.7％).
2020, 57(6): 1140-1151.
DOI: 10.7544/issn1000-1239.2020.20200107
摘要：
随着深度学习的快速发展，卷积神经网络已广泛应用于计算机视觉、自然语言处理等人工智能领域中.Winograd快速卷积算法因能有效降低卷积神经网络中卷积操作的计算复杂度而受到广泛关注.随着国防科技大学自主研制的飞腾多核处理器在智能领域的推广应用，对面向飞腾多核处理器的高性能卷积实现提出了强烈需求.针对飞腾多核处理器的体系结构特征与Wingorad快速卷积算法的计算特点，提出了一种高性能并行Winograd快速卷积算法.该算法不依赖通用矩阵乘库函数，由卷积核转换、输入特征图转换、逐元素乘、输出特征图逆变换等4个部分构成，融合设计了4个部分的数据操作，并设计了与之配套的数据布局、多级并行数据转换算法与多级并行矩阵乘算法，实现访存性能以及算法整体性能的提升.在两款飞腾多核处理器上的测试结果显示，与开源库ACL和NNPACK中的Winograd快速卷积实现相比，该算法分别能获得1.05~16.11倍与1.66~16.90倍的性能加速；集成到开源框架Mxnet后，该算法使得VGG16网络的前向计算获得了3.01~6.79倍的性能加速.
随着深度学习的快速发展，卷积神经网络已广泛应用于计算机视觉、自然语言处理等人工智能领域中.Winograd快速卷积算法因能有效降低卷积神经网络中卷积操作的计算复杂度而受到广泛关注.随着国防科技大学自主研制的飞腾多核处理器在智能领域的推广应用，对面向飞腾多核处理器的高性能卷积实现提出了强烈需求.针对飞腾多核处理器的体系结构特征与Wingorad快速卷积算法的计算特点，提出了一种高性能并行Winograd快速卷积算法.该算法不依赖通用矩阵乘库函数，由卷积核转换、输入特征图转换、逐元素乘、输出特征图逆变换等4个部分构成，融合设计了4个部分的数据操作，并设计了与之配套的数据布局、多级并行数据转换算法与多级并行矩阵乘算法，实现访存性能以及算法整体性能的提升.在两款飞腾多核处理器上的测试结果显示，与开源库ACL和NNPACK中的Winograd快速卷积实现相比，该算法分别能获得1.05~16.11倍与1.66~16.90倍的性能加速；集成到开源框架Mxnet后，该算法使得VGG16网络的前向计算获得了3.01~6.79倍的性能加速.
2020, 57(6): 1152-1163.
DOI: 10.7544/issn1000-1239.2020.20200115
摘要：
随着互联网技术的蓬勃发展，图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法，也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构，具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上，BFS算法的优化已取得一系列进展，首先对现有的优化技术进行系统的介绍，并在此基础上提出2种面向高通量计算机的优化手段，通过减少冗余访存和提高缓存局部性，有效提高了算法的访存效率.通过这些优化手段，在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为230的Kronecker图(顶点数为230，边数为234)，优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比，单节点具有1.18倍的性能优势.在性能功耗比方面，高通量计算机的结果为181.04 MTEPS/W.在2019年6月份的Green Graph500面向大数据集的排行榜上取得第2名的成绩.综上，高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.
随着互联网技术的蓬勃发展，图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法，也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构，具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上，BFS算法的优化已取得一系列进展，首先对现有的优化技术进行系统的介绍，并在此基础上提出2种面向高通量计算机的优化手段，通过减少冗余访存和提高缓存局部性，有效提高了算法的访存效率.通过这些优化手段，在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为230的Kronecker图(顶点数为230，边数为234)，优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比，单节点具有1.18倍的性能优势.在性能功耗比方面，高通量计算机的结果为181.04 MTEPS/W.在2019年6月份的Green Graph500面向大数据集的排行榜上取得第2名的成绩.综上，高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.
2020, 57(6): 1164-1178.
DOI: 10.7544/issn1000-1239.2020.20200106
摘要：
基于新型可重构架构FPGA(field programmable gate array)的图计算加速器同时具备着性能和能效的优势，满足复杂性高、数据规模大和基本操作多变的图计算的性能需求.但高效底层硬件代码的设计需要很长的设计周期，而已有的通用编程与开发环境虽满足功能要求，但性能差距较大.因此，编程墙的问题是影响应用开发与加速器性能的重要阻碍之一.设计良好的编程与开发环境是图计算加速器进一步提升性能且降低开发周期的最重要环节.高效的编程与开发环境需要提供便利的应用程序接口、扩展性强的编程模型、高效的高层次综合工具、能够融合软硬件特性的领域特定语言以及生成高性能硬件代码.对FPGA图计算的编程与开发环境做出系统性探索，主要就编程模型、高层次综合、编程语言以及应用程序开发进行介绍与分析.此外还对国内外相关技术的发展进行总结与分析，并针对本领域相关开放问题与挑战提供了未来思考.
基于新型可重构架构FPGA(field programmable gate array)的图计算加速器同时具备着性能和能效的优势，满足复杂性高、数据规模大和基本操作多变的图计算的性能需求.但高效底层硬件代码的设计需要很长的设计周期，而已有的通用编程与开发环境虽满足功能要求，但性能差距较大.因此，编程墙的问题是影响应用开发与加速器性能的重要阻碍之一.设计良好的编程与开发环境是图计算加速器进一步提升性能且降低开发周期的最重要环节.高效的编程与开发环境需要提供便利的应用程序接口、扩展性强的编程模型、高效的高层次综合工具、能够融合软硬件特性的领域特定语言以及生成高性能硬件代码.对FPGA图计算的编程与开发环境做出系统性探索，主要就编程模型、高层次综合、编程语言以及应用程序开发进行介绍与分析.此外还对国内外相关技术的发展进行总结与分析，并针对本领域相关开放问题与挑战提供了未来思考.
2020, 57(6): 1179-1190.
DOI: 10.7544/issn1000-1239.2020.20200109
摘要：
大数据时代的到来为信息处理带来了新的挑战，内存计算方式的Spark显著提高了数据处理的性能.Spark的性能优化和分析可以在应用层、系统层和硬件层开展，然而现有工作都只局限在某一层，使得Spark语义与底层动作脱离，如操作系统参数对Spark应用层的性能影响的缺失将使得大量灵活的操作系统配置参数无法发挥作用.针对上述问题，设计了Spark存储系统分析工具SMTT,打通了Spark层、JVM层和OS层，建立了上层应用程序的语义与底层物理内存信息的联系.SMTT针对Spark内存特点，分别设计了针对执行内存和存储内存的追踪方式.基于SMTT工具完成了对Spark迭代计算过程内存使用，以及跨越Spark，JVM和OS层的执行/存储内存使用过程的分析，并以RDD为例通过SMTT分析了单节点和多节点情况下Spark中读和写操作比例，结果表明该工作为Spark内存系统的性能分析和优化提供了有力的支持.
大数据时代的到来为信息处理带来了新的挑战，内存计算方式的Spark显著提高了数据处理的性能.Spark的性能优化和分析可以在应用层、系统层和硬件层开展，然而现有工作都只局限在某一层，使得Spark语义与底层动作脱离，如操作系统参数对Spark应用层的性能影响的缺失将使得大量灵活的操作系统配置参数无法发挥作用.针对上述问题，设计了Spark存储系统分析工具SMTT,打通了Spark层、JVM层和OS层，建立了上层应用程序的语义与底层物理内存信息的联系.SMTT针对Spark内存特点，分别设计了针对执行内存和存储内存的追踪方式.基于SMTT工具完成了对Spark迭代计算过程内存使用，以及跨越Spark，JVM和OS层的执行/存储内存使用过程的分析，并以RDD为例通过SMTT分析了单节点和多节点情况下Spark中读和写操作比例，结果表明该工作为Spark内存系统的性能分析和优化提供了有力的支持.
2020, 57(6): 1191-1207.
DOI: 10.7544/issn1000-1239.2020.20200113
摘要：
随着工艺和制程技术的不断发展以及体系架构的日趋完善，通用图形处理器(general purpose graphics processing units, GPGPU)的并行计算能力得到了很大的提升，其在高性能、高吞吐量等通用计算应用场景的使用越来越广泛.GPGPU通过支持大量线程的并发执行，可以较好地隐藏长延时访存操作，从而获得高并行计算能力.然而，GPGPU在处理计算和访存不规则的应用时，其存储子系统的效率受到很大影响，尤其是片上缓存的争用情况尤为突出，难以及时提供计算操作所需的数据，使得GPGPU的高并行计算能力不能得到充分发挥.解决片上缓存的争用问题、优化缓存子系统的性能，是优化GPGPU性能的主要解决方案之一，也是目前研究GPGPU性能优化的主要热点之一.目前，针对GPGPU缓存子系统的性能优化研究主要集中在线程级并行度(thread level parallelism, TLP)调节、访存顺序调节、数据通量增强、最后一级缓存(last level cache, LLC)优化和基于非易失性存储(non-volatile memory, NVM)的GPGPU缓存新架构设计等5个方面.也从这5个方面重点分析讨论了目前主要的GPGPU缓存子系统性能优化方法，并在最后指出了未来GPGPU缓存子系统优化需要进一步探讨的问题，对GPGPU缓存子系统性能优化的研究有重要意义.
随着工艺和制程技术的不断发展以及体系架构的日趋完善，通用图形处理器(general purpose graphics processing units, GPGPU)的并行计算能力得到了很大的提升，其在高性能、高吞吐量等通用计算应用场景的使用越来越广泛.GPGPU通过支持大量线程的并发执行，可以较好地隐藏长延时访存操作，从而获得高并行计算能力.然而，GPGPU在处理计算和访存不规则的应用时，其存储子系统的效率受到很大影响，尤其是片上缓存的争用情况尤为突出，难以及时提供计算操作所需的数据，使得GPGPU的高并行计算能力不能得到充分发挥.解决片上缓存的争用问题、优化缓存子系统的性能，是优化GPGPU性能的主要解决方案之一，也是目前研究GPGPU性能优化的主要热点之一.目前，针对GPGPU缓存子系统的性能优化研究主要集中在线程级并行度(thread level parallelism, TLP)调节、访存顺序调节、数据通量增强、最后一级缓存(last level cache, LLC)优化和基于非易失性存储(non-volatile memory, NVM)的GPGPU缓存新架构设计等5个方面.也从这5个方面重点分析讨论了目前主要的GPGPU缓存子系统性能优化方法，并在最后指出了未来GPGPU缓存子系统优化需要进一步探讨的问题，对GPGPU缓存子系统性能优化的研究有重要意义.
2020, 57(6): 1208-1217.
DOI: 10.7544/issn1000-1239.2020.20190485
摘要：
深度学习的可解释性研究是人工智能、机器学习、认知心理学、逻辑学等众多学科的交叉研究课题，其在信息推送、医疗研究、金融、信息安全等领域具有重要的理论研究意义和实际应用价值.从深度学习可解释性研究起源、研究探索期、模型构建期3方面回顾了深度学习可解释性研究历史，从可视化分析、鲁棒性扰动分析、敏感性分析3方面展现了深度学习现有模型可解释性分析研究现状，从模型代理、逻辑推理、网络节点关联分析、传统机器学习模型改进4方面剖析了可解释性深度学习模型构建研究，同时对当前该领域研究存在的不足作出了分析，展示了可解释性深度学习的典型应用，并对未来可能的研究方向作出了展望.
深度学习的可解释性研究是人工智能、机器学习、认知心理学、逻辑学等众多学科的交叉研究课题，其在信息推送、医疗研究、金融、信息安全等领域具有重要的理论研究意义和实际应用价值.从深度学习可解释性研究起源、研究探索期、模型构建期3方面回顾了深度学习可解释性研究历史，从可视化分析、鲁棒性扰动分析、敏感性分析3方面展现了深度学习现有模型可解释性分析研究现状，从模型代理、逻辑推理、网络节点关联分析、传统机器学习模型改进4方面剖析了可解释性深度学习模型构建研究，同时对当前该领域研究存在的不足作出了分析，展示了可解释性深度学习的典型应用，并对未来可能的研究方向作出了展望.
2020, 57(6): 1218-1226.
DOI: 10.7544/issn1000-1239.2020.20190578
摘要：
对于智能机器人来说，正确地理解环境是一项非常重要且充满挑战性的能力，从而成为机器人学领域一个关键问题.随着服务机器人进入家庭成为趋势，让机器人能够依靠自身搭载的传感器和场景理解算法，以自主、可靠的方式感知并理解其所处的环境，识别环境中的各类物体及其相互关系，并建立环境模型，成为自主完成任务和实现人-机器人智能交互的前提.在规模较大的室内空间中，由于机器人常用的RGB-D(RGB depth)视觉传感器(同时获取彩色图像和深度信息)视野有限，使之难以直接获取包含整个区域的单帧图像，但机器人能够运动到不同位置，采集多种视角的图像数据，这些数据总体上能够覆盖整个场景.在此背景下，提出了基于多视角RGB-D图像帧信息融合的室内场景理解算法，在单帧RGB-D图像上进行物体检测和物体关系提取，在多帧RGB-D图像上进行物体实例检测，同时构建对应整个场景的物体关系拓扑图模型.通过对RGB-D图像帧进行划分，提取图像单元的颜色直方图特征，并提出基于最长公共子序列的跨帧物体实例检测方法，确定多帧图像之间的物体对应关联，解决了RGB-D摄像机视角变化影响图像帧融合的问题.最后，在NYUv2(NYU depth dataset v2)数据集上验证了本文算法的有效性.
对于智能机器人来说，正确地理解环境是一项非常重要且充满挑战性的能力，从而成为机器人学领域一个关键问题.随着服务机器人进入家庭成为趋势，让机器人能够依靠自身搭载的传感器和场景理解算法，以自主、可靠的方式感知并理解其所处的环境，识别环境中的各类物体及其相互关系，并建立环境模型，成为自主完成任务和实现人-机器人智能交互的前提.在规模较大的室内空间中，由于机器人常用的RGB-D(RGB depth)视觉传感器(同时获取彩色图像和深度信息)视野有限，使之难以直接获取包含整个区域的单帧图像，但机器人能够运动到不同位置，采集多种视角的图像数据，这些数据总体上能够覆盖整个场景.在此背景下，提出了基于多视角RGB-D图像帧信息融合的室内场景理解算法，在单帧RGB-D图像上进行物体检测和物体关系提取，在多帧RGB-D图像上进行物体实例检测，同时构建对应整个场景的物体关系拓扑图模型.通过对RGB-D图像帧进行划分，提取图像单元的颜色直方图特征，并提出基于最长公共子序列的跨帧物体实例检测方法，确定多帧图像之间的物体对应关联，解决了RGB-D摄像机视角变化影响图像帧融合的问题.最后，在NYUv2(NYU depth dataset v2)数据集上验证了本文算法的有效性.
2020, 57(6): 1227-1238.
DOI: 10.7544/issn1000-1239.2020.20190403
摘要：
信任推荐系统是以社交网络为基础的一种重要推荐系统应用，其结合用户之间的信任关系对用户进行项目推荐.但之前的研究一般假定用户之间的信任值固定，无法对用户信任及偏好的动态变化做出及时响应，进而影响推荐效果.实际上，用户接受推荐后，当实际评价高于心理预期时，体验用户对推荐者的信任将增加，反之则下降.针对此问题，并且重点考虑用户间信任变化过程及信任的动态性，提出了一种结合强化学习的用户信任增强方法.因此，使用最小均方误差算法研究评价差值对用户信任的动态影响，利用强化学习方法deep q-learning(DQN)模拟推荐者在推荐过程中学习用户偏好进而提升信任值的过程，并且提出了一个多项式级别的算法来计算信任值和推荐，可激励推荐者学习用户的偏好，并使用户对推荐者的信任始终保持在较高程度.实验表明，方法可快速响应用户偏好的动态变化，当其应用于推荐系统时，相较于其他方法，可为用户提供更及时、更准确的推荐结果.
信任推荐系统是以社交网络为基础的一种重要推荐系统应用，其结合用户之间的信任关系对用户进行项目推荐.但之前的研究一般假定用户之间的信任值固定，无法对用户信任及偏好的动态变化做出及时响应，进而影响推荐效果.实际上，用户接受推荐后，当实际评价高于心理预期时，体验用户对推荐者的信任将增加，反之则下降.针对此问题，并且重点考虑用户间信任变化过程及信任的动态性，提出了一种结合强化学习的用户信任增强方法.因此，使用最小均方误差算法研究评价差值对用户信任的动态影响，利用强化学习方法deep q-learning(DQN)模拟推荐者在推荐过程中学习用户偏好进而提升信任值的过程，并且提出了一个多项式级别的算法来计算信任值和推荐，可激励推荐者学习用户的偏好，并使用户对推荐者的信任始终保持在较高程度.实验表明，方法可快速响应用户偏好的动态变化，当其应用于推荐系统时，相较于其他方法，可为用户提供更及时、更准确的推荐结果.
2020, 57(6): 1239-1251.
DOI: 10.7544/issn1000-1239.2020.20190253
摘要：
知识表示学习是知识获取与应用的基础，是贯穿知识图谱构建与应用全过程的重要问题，伴随含有时间标签的大型知识图谱的发展，近几年时间感知的知识表示学习成为该领域研究热点之一.针对传统方法不能有效学习知识持续时长分布规律的问题，融合超平面和有效持续时间建模，提出一种时间感知知识表示学习方法Duration-HyTE.首先，将元事实按照有效持续时间分类，对知识有效持续时间进行建模，提出知识有效可信度的计算方法，将其作用于训练过程评价函数和损失函数的计算，最后在含有时间标签的数据集Wikidata12K、YAGO11K和新建立的持续型关系数据集上进行对比实验，结果表明与其他同类方法相比，Duration-HyTE方法在实体和关系的链接预测和时间预测上性能得到有效提升，尤其在Wikidata12K数据集上，经Duration-HyTE训练得到的知识表示模型对于头尾实体的预测效果比当前最优的表示方法分别提升了25.7%和35.8%，有效提高了链接预测准确率.
知识表示学习是知识获取与应用的基础，是贯穿知识图谱构建与应用全过程的重要问题，伴随含有时间标签的大型知识图谱的发展，近几年时间感知的知识表示学习成为该领域研究热点之一.针对传统方法不能有效学习知识持续时长分布规律的问题，融合超平面和有效持续时间建模，提出一种时间感知知识表示学习方法Duration-HyTE.首先，将元事实按照有效持续时间分类，对知识有效持续时间进行建模，提出知识有效可信度的计算方法，将其作用于训练过程评价函数和损失函数的计算，最后在含有时间标签的数据集Wikidata12K、YAGO11K和新建立的持续型关系数据集上进行对比实验，结果表明与其他同类方法相比，Duration-HyTE方法在实体和关系的链接预测和时间预测上性能得到有效提升，尤其在Wikidata12K数据集上，经Duration-HyTE训练得到的知识表示模型对于头尾实体的预测效果比当前最优的表示方法分别提升了25.7%和35.8%，有效提高了链接预测准确率.
2020, 57(6): 1252-1268.
DOI: 10.7544/issn1000-1239.2020.20190641
摘要：
古诗词是中国宝贵的文化遗产.利用计算机对诗词进行辅助研究，对语言、文学、传承普及中华文化，具有重要意义.然而，关于诗词的知识是高度碎片化的，原因是互联网上的诗词知识，不仅存在于诗词本身，还分布于诗词的各种解读资料，比如诗词的注释、译文、赏析等.若以知识图谱的方式，捕捉古诗词中词语之间潜在的语义联系并将它们以知识的方式关联起来，能够将诗词碎片化的知识有条理地整合在一起，从而更好地对古诗词知识进行推理和分析.基于此，提出了一种古诗词知识图谱的构建方法.构建图谱的节点时，首先利用改进的Apriori算法产生诗词中的候选词，然后检验候选词是否出现在诗词注释和中文词典中，从而判断其是否构成图谱节点.构建图谱的边时，首先利用注释信息在词语之间建立语义联系，然后用人工构建的诗词分类体系在抽象的语义之间建立联系.最终得到一个内容覆盖全面且包含多层词语语义联系的古诗词图谱.古诗词图谱可用于对诗词各种不同维度的分析研究，相比于基于字的数据分析，利用古诗词图谱能够从语义的角度更加深入具体地辅助文学研究.以唐诗为例，说明了古诗词图谱在诗词分析中的必要性.此外，古诗词图谱还适用于各种关于诗词的推理和分析任务，以判定诗词题材和分析诗词情感这2个任务为例，证明了古诗词图谱的有效性和应用价值.
古诗词是中国宝贵的文化遗产.利用计算机对诗词进行辅助研究，对语言、文学、传承普及中华文化，具有重要意义.然而，关于诗词的知识是高度碎片化的，原因是互联网上的诗词知识，不仅存在于诗词本身，还分布于诗词的各种解读资料，比如诗词的注释、译文、赏析等.若以知识图谱的方式，捕捉古诗词中词语之间潜在的语义联系并将它们以知识的方式关联起来，能够将诗词碎片化的知识有条理地整合在一起，从而更好地对古诗词知识进行推理和分析.基于此，提出了一种古诗词知识图谱的构建方法.构建图谱的节点时，首先利用改进的Apriori算法产生诗词中的候选词，然后检验候选词是否出现在诗词注释和中文词典中，从而判断其是否构成图谱节点.构建图谱的边时，首先利用注释信息在词语之间建立语义联系，然后用人工构建的诗词分类体系在抽象的语义之间建立联系.最终得到一个内容覆盖全面且包含多层词语语义联系的古诗词图谱.古诗词图谱可用于对诗词各种不同维度的分析研究，相比于基于字的数据分析，利用古诗词图谱能够从语义的角度更加深入具体地辅助文学研究.以唐诗为例，说明了古诗词图谱在诗词分析中的必要性.此外，古诗词图谱还适用于各种关于诗词的推理和分析任务，以判定诗词题材和分析诗词情感这2个任务为例，证明了古诗词图谱的有效性和应用价值.
2020, 57(6): 1269-1283.
DOI: 10.7544/issn1000-1239.2020.20190484
摘要：
车辆共乘旨在通过降低车辆空载率以提升运输效率、缓解交通拥堵、降低环境污染并节省出行资源. 首先针对即时车辆共乘问题构建了数学模型,以共享路程比率和绕行距离约束为手段对车辆合乘中车主资源的利用效率进行评估.然后提出离散排列问题的解空间图理论并对其原理进行了阐述和分析，继而基于此理论构建一种多策略解空间图搜索算法.该算法以并行化结构生成价值矩阵显著提升了传统方法的效率，并以多种控制策略操纵结合离散排列问题特点设计的不同搜索算子，指导搜索过程在解空间图中向更高价值方向移动以高效获取高质量的匹配方案.实验结果表明，该算法的求解质量可达最优解的95%以上，且求解效率明显优于对比实验中的其他算法.
车辆共乘旨在通过降低车辆空载率以提升运输效率、缓解交通拥堵、降低环境污染并节省出行资源. 首先针对即时车辆共乘问题构建了数学模型,以共享路程比率和绕行距离约束为手段对车辆合乘中车主资源的利用效率进行评估.然后提出离散排列问题的解空间图理论并对其原理进行了阐述和分析，继而基于此理论构建一种多策略解空间图搜索算法.该算法以并行化结构生成价值矩阵显著提升了传统方法的效率，并以多种控制策略操纵结合离散排列问题特点设计的不同搜索算子，指导搜索过程在解空间图中向更高价值方向移动以高效获取高质量的匹配方案.实验结果表明，该算法的求解质量可达最优解的95%以上，且求解效率明显优于对比实验中的其他算法.
2020, 57(6): 1284-1291.
DOI: 10.7544/issn1000-1239.2020.20190587
摘要：
针对无线传感网中分布式数据收集及应用，采用分布式压缩感知理论中的JSM-1 (joint sparse model-1)模型，提出了一种基于Jacobi ADMM (alternating direction method of multipliers)的分布式压缩感知数据重构算法.该算法通过在簇头节点间交换公共信息以挖掘关联数据集的公共部分，并在各个簇头节点内部更新各自的独立部分，从而实现无线传感网中相关感知数据的分布式压缩重构.首先，将无线传感网中的数据收集问题抽象为一个分布式优化问题.然后，为了能够有效地解决分布式计算过程中产生的不收敛问题，在优化目标函数中引入了近似项，从而使得子优化问题具有严格凸性，并利用交替方向乘子法求解压缩感知数据的重构问题.最后，分别利用合成数据集和真实数据集进行验证.实验结果表明：与现有其他数据重构算法相比，基于Jacobi ADMM的分布式压缩感知数据重构算法具有更高的数据重构精度.
针对无线传感网中分布式数据收集及应用，采用分布式压缩感知理论中的JSM-1 (joint sparse model-1)模型，提出了一种基于Jacobi ADMM (alternating direction method of multipliers)的分布式压缩感知数据重构算法.该算法通过在簇头节点间交换公共信息以挖掘关联数据集的公共部分，并在各个簇头节点内部更新各自的独立部分，从而实现无线传感网中相关感知数据的分布式压缩重构.首先，将无线传感网中的数据收集问题抽象为一个分布式优化问题.然后，为了能够有效地解决分布式计算过程中产生的不收敛问题，在优化目标函数中引入了近似项，从而使得子优化问题具有严格凸性，并利用交替方向乘子法求解压缩感知数据的重构问题.最后，分别利用合成数据集和真实数据集进行验证.实验结果表明：与现有其他数据重构算法相比，基于Jacobi ADMM的分布式压缩感知数据重构算法具有更高的数据重构精度.
2020, 57(6): 1292-1301.
DOI: 10.7544/issn1000-1239.2020.20190692
摘要：
近年来，随着通信技术和网络传输能力的大幅度提升，应用需求呈现多元化的增长态势(视频会议、在线游戏等交互式应用要求低时延、低抖动，而软件更新等应用则要求高吞吐).为满足时延不敏感的数据传输并保证高效的瓶颈带宽利用率，低优先级拥塞控制算法(如LEDBAT(low extra delay background transport))受到广泛关注.该类算法能在链路空闲时占用未被使用的带宽，而在链路负载较高时释放占用的带宽以保证时延敏感数据的传输.然而，当中间路由器部署主动队列管理算法时，低优先级拥塞控制算法存在优先级反转问题，即链路高负载时无法释放占用的带宽，使其退化为普通拥塞控制算法.为解决该问题，针对LEDBAT中的固定时延阈值造成的优先级反转，提出启发式的动态阈值调整算法，其在运行时动态搜索最优的动态时延阈值，确保LEDBAT与主动队列管理算法共存时仍能保持低优先级特性，同时不降低链路的利用率.为验证算法的有效性，在网络模拟NS2中建立了不同网络场景并对算法进行大量的评估.实验结果表明：与已有低优先拥塞控制算法相比，新算法能够有效解决优先级反转的问题，同时保证链路的带宽利用率.
近年来，随着通信技术和网络传输能力的大幅度提升，应用需求呈现多元化的增长态势(视频会议、在线游戏等交互式应用要求低时延、低抖动，而软件更新等应用则要求高吞吐).为满足时延不敏感的数据传输并保证高效的瓶颈带宽利用率，低优先级拥塞控制算法(如LEDBAT(low extra delay background transport))受到广泛关注.该类算法能在链路空闲时占用未被使用的带宽，而在链路负载较高时释放占用的带宽以保证时延敏感数据的传输.然而，当中间路由器部署主动队列管理算法时，低优先级拥塞控制算法存在优先级反转问题，即链路高负载时无法释放占用的带宽，使其退化为普通拥塞控制算法.为解决该问题，针对LEDBAT中的固定时延阈值造成的优先级反转，提出启发式的动态阈值调整算法，其在运行时动态搜索最优的动态时延阈值，确保LEDBAT与主动队列管理算法共存时仍能保持低优先级特性，同时不降低链路的利用率.为验证算法的有效性，在网络模拟NS2中建立了不同网络场景并对算法进行大量的评估.实验结果表明：与已有低优先拥塞控制算法相比，新算法能够有效解决优先级反转的问题，同时保证链路的带宽利用率.
2020, 57(6): 1302-1311.
DOI: 10.7544/issn1000-1239.2020.20190572
摘要：
复杂网络社区挖掘作为近年的研究热点，重叠社区检测有重要的现实意义.传统社区发现方法将所有节点精确地划分到每一个子类中，形成非重叠划分.但硬划分方法较难处理含有不确定信息和噪声信息的复杂情况.而目前采用网络嵌入的方法进行重叠社区发现的研究较少，针对社区漂移和边界不确定的问题，提出了一种结合粗糙粒化的网络嵌入社区发现方法.通过网络嵌入获得融合结构信息和属性信息的节点表示，并将相似的节点映射到距离相近的低维连续的向量空间.然后，结合粗糙粒化的思想，考虑网络结构和节点上的多层次信息来处理社区边界上的不确定性区域，最终生成重叠社区.在网络公开数据集和人工数据集的实验结果都表明，提出的粗糙粒化的网络嵌入(network embedding based on rough granulation, RGNE)社区发现方法具有更高的精度，并可有效地处理不确定性网络的社区发现问题.最后，对影响实验效果的参数设置进行了详细讨论分析.
复杂网络社区挖掘作为近年的研究热点，重叠社区检测有重要的现实意义.传统社区发现方法将所有节点精确地划分到每一个子类中，形成非重叠划分.但硬划分方法较难处理含有不确定信息和噪声信息的复杂情况.而目前采用网络嵌入的方法进行重叠社区发现的研究较少，针对社区漂移和边界不确定的问题，提出了一种结合粗糙粒化的网络嵌入社区发现方法.通过网络嵌入获得融合结构信息和属性信息的节点表示，并将相似的节点映射到距离相近的低维连续的向量空间.然后，结合粗糙粒化的思想，考虑网络结构和节点上的多层次信息来处理社区边界上的不确定性区域，最终生成重叠社区.在网络公开数据集和人工数据集的实验结果都表明，提出的粗糙粒化的网络嵌入(network embedding based on rough granulation, RGNE)社区发现方法具有更高的精度，并可有效地处理不确定性网络的社区发现问题.最后，对影响实验效果的参数设置进行了详细讨论分析.
2020, 57(6): 1312-1322.
DOI: 10.7544/issn1000-1239.2020.20190584
摘要：
准确预测社交网络中消息的传播范围是舆情分析的重要内容，该问题受到了数据挖掘领域的广泛关注.目前的大部分研究主要利用社交网络拓扑结构和用户的动作日志来预测社交消息的传播范围.在实际应用中用户的动作日志中通常容易获得，但是社交网络的拓扑结构(例如用户之间的朋友关系)并不容易获得，因此无拓扑结构的社交消息预测具有更广泛的应用前景.提出了一种新的社交消息传播范围预测方法NT-EP，该方法由4部分构成：1)利用消息传播随时间衰减的特性为消息构造加权传播图，使用随机游走策略获取多条传播路径；2)把目标消息的传播路径输入到Bi-GRU(bidirectional gated recurrent unite)，结合注意力机制计算出目标消息的传播特征向量；3)使用梯度下降方法计算出其他消息的影响向量；4)将目标消息的传播特征向量和其他消息的影响向量结合在一起，预测目标消息的传播范围.在Sina微博和Flixster数据集上的实验结果表明：NT-EP方法在均方误差(mean squared error, MSE)，F1-score等多个指标上都优于现有的社交消息预测方法.
准确预测社交网络中消息的传播范围是舆情分析的重要内容，该问题受到了数据挖掘领域的广泛关注.目前的大部分研究主要利用社交网络拓扑结构和用户的动作日志来预测社交消息的传播范围.在实际应用中用户的动作日志中通常容易获得，但是社交网络的拓扑结构(例如用户之间的朋友关系)并不容易获得，因此无拓扑结构的社交消息预测具有更广泛的应用前景.提出了一种新的社交消息传播范围预测方法NT-EP，该方法由4部分构成：1)利用消息传播随时间衰减的特性为消息构造加权传播图，使用随机游走策略获取多条传播路径；2)把目标消息的传播路径输入到Bi-GRU(bidirectional gated recurrent unite)，结合注意力机制计算出目标消息的传播特征向量；3)使用梯度下降方法计算出其他消息的影响向量；4)将目标消息的传播特征向量和其他消息的影响向量结合在一起，预测目标消息的传播范围.在Sina微博和Flixster数据集上的实验结果表明：NT-EP方法在均方误差(mean squared error, MSE)，F1-score等多个指标上都优于现有的社交消息预测方法.
2020, 57(6): 1323-1334.
DOI: 10.7544/issn1000-1239.2020.20190207
摘要：
作为智慧物联的重要技术支撑，无线射频识别 (radio frequency identification, RFID)技术，已广泛用于供应链等物品追溯及实时监控领域.为提高基于RFID供应链环境中标签对象路径追溯查询效率，须对RFID时空数据进行有效编码.考虑到RFID供应链数据具有海量性、存在环路、更新频繁等特点，在2个向量之间可以插入无限个向量的思想基础上，提出了一种偏增向量路径编码策略.该策略以时空数据结点为编码对象，利用向量加法给结点分配唯一1对向量，实现对每个结点时空信息的统一编码.同时，针对码值过大导致的溢出问题提出了优化方案，并进行了正确性证明.实验结果表明：所提出的偏增向量路径编码策略及其优化策略能满足不同类型追溯查询需求，且具有编码速度快、码值溢出速度慢、更新效率高和支持环路等优点.
作为智慧物联的重要技术支撑，无线射频识别 (radio frequency identification, RFID)技术，已广泛用于供应链等物品追溯及实时监控领域.为提高基于RFID供应链环境中标签对象路径追溯查询效率，须对RFID时空数据进行有效编码.考虑到RFID供应链数据具有海量性、存在环路、更新频繁等特点，在2个向量之间可以插入无限个向量的思想基础上，提出了一种偏增向量路径编码策略.该策略以时空数据结点为编码对象，利用向量加法给结点分配唯一1对向量，实现对每个结点时空信息的统一编码.同时，针对码值过大导致的溢出问题提出了优化方案，并进行了正确性证明.实验结果表明：所提出的偏增向量路径编码策略及其优化策略能满足不同类型追溯查询需求，且具有编码速度快、码值溢出速度慢、更新效率高和支持环路等优点.
2020, 57(6): 1335-1346.
DOI: 10.7544/issn1000-1239.2020.20190470
摘要：
为了提高反最近邻问题的查询效率，首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义，提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor, MBDNN-tree)，该索引结构运用了R-树中分割空间数据的思想，将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance)，利用多种序关系对原始点集进行划分，从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析，给出了MBDNN-树的性质.在此基础上，给出了MBDNN-树进行反最近邻查询的剪枝规则，进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性，有效地减少了结点的访问数量，从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明：基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.
为了提高反最近邻问题的查询效率，首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义，提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor, MBDNN-tree)，该索引结构运用了R-树中分割空间数据的思想，将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance)，利用多种序关系对原始点集进行划分，从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析，给出了MBDNN-树的性质.在此基础上，给出了MBDNN-树进行反最近邻查询的剪枝规则，进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性，有效地减少了结点的访问数量，从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明：基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
