2020年 第57卷 第1期
摘要:
我们高兴地向读者推出本期“优青专题”——专门介绍2018年国家自然科学基金优秀青年基金(优青基金)项目获得者(及其合作者)的研究成果的专题.优秀青年基金是国家自然科学基金委员会2012年起设立的一类人才项目,主要支持取得较好科研成就的青年科学技术人员进行开拓创新的基础研究,旨在促进创新型青年科学技术人才的快速成长,培养一批有望进入世界科技前沿的优秀学术骨干.《计算机研究与发展》自2015年以来刊出了“优青专题”系列,集中介绍这些优秀青年学者(及其合作者)的研究成果.本期是该系列的第5个专题,共收录3篇文章.
我们高兴地向读者推出本期“优青专题”——专门介绍2018年国家自然科学基金优秀青年基金(优青基金)项目获得者(及其合作者)的研究成果的专题.优秀青年基金是国家自然科学基金委员会2012年起设立的一类人才项目,主要支持取得较好科研成就的青年科学技术人员进行开拓创新的基础研究,旨在促进创新型青年科学技术人才的快速成长,培养一批有望进入世界科技前沿的优秀学术骨干.《计算机研究与发展》自2015年以来刊出了“优青专题”系列,集中介绍这些优秀青年学者(及其合作者)的研究成果.本期是该系列的第5个专题,共收录3篇文章.
2020, 57(1): 3-16.
DOI: 10.7544/issn1000-1239.2020.20190233
摘要:
在传统基于关键词集合的可搜索对称加密技术中,关键词集合通常由关键词提取算法生成,使得其关键词的内容和数量受到关键词提取算法的限制.因此,在基于关键词的加密搜索系统中,除了初始化系统生成的关键词集,用户无法搜索其他相关内容导致限制了加密搜索技术的应用.针对以上问题,提出了支持灵活精度可控的可搜索对称加密方案(flexible accuracy-controllable searchable symmetric encryption, FASSE),通过在系统运行过程中灵活地生成关键词和文档摘要生成的索引,从而减少对关键词集合的依赖,从而有效提高了加密搜索技术灵活性.FASSE提供3种基本搜索,分别是一次命中搜索、增强搜索和过滤搜索,它们分别对应着用户只用一次就在字典中找到关键词记录、没有在字典中找到关键词记录而只用一次就在摘要中找到记录或者多次在字典和摘要中查找到关键词记录的这3种搜索情况.同时,系统也结合3种搜索设计了一种模糊增强搜索进一步增强系统的实用性.FASSE方案的具体实现语言是Java编程开发语言,并且最终实验得出FASSE在https://eprint.iacr.org/complete/的论文数据集中平均搜索完每一篇论文的时间为114.26 ms.
在传统基于关键词集合的可搜索对称加密技术中,关键词集合通常由关键词提取算法生成,使得其关键词的内容和数量受到关键词提取算法的限制.因此,在基于关键词的加密搜索系统中,除了初始化系统生成的关键词集,用户无法搜索其他相关内容导致限制了加密搜索技术的应用.针对以上问题,提出了支持灵活精度可控的可搜索对称加密方案(flexible accuracy-controllable searchable symmetric encryption, FASSE),通过在系统运行过程中灵活地生成关键词和文档摘要生成的索引,从而减少对关键词集合的依赖,从而有效提高了加密搜索技术灵活性.FASSE提供3种基本搜索,分别是一次命中搜索、增强搜索和过滤搜索,它们分别对应着用户只用一次就在字典中找到关键词记录、没有在字典中找到关键词记录而只用一次就在摘要中找到记录或者多次在字典和摘要中查找到关键词记录的这3种搜索情况.同时,系统也结合3种搜索设计了一种模糊增强搜索进一步增强系统的实用性.FASSE方案的具体实现语言是Java编程开发语言,并且最终实验得出FASSE在https://eprint.iacr.org/complete/的论文数据集中平均搜索完每一篇论文的时间为114.26 ms.
2020, 57(1): 17-31.
DOI: 10.7544/issn1000-1239.2020.20190208
摘要:
多光源场景绘制一直是计算机图形学中的重要研究问题,是实现全局光照效果的重要手段之一,也是游戏、影视、动画等应用领域的重要需求.无论在离线绘制领域还是实时绘制领域,多光源场景的高效绘制仍然是一个巨大的挑战.回顾了近年来图形学在多光源场景绘制方面的主要进展,如何提高多光源绘制的效率是所有相关方法的主要研究问题.在离线绘制领域,首先介绍了如何通过加快可见性测试来提高单个光源的平均计算效率;然后,讨论了光源聚类算法,介绍了基于光源聚类的加速绘制方法,并讨论了不同的光源聚类策略,包括基于层次结构的策略和基于矩阵分析的策略;之后,介绍了基于光源聚类的重要性采样方法.在实时绘制领域,介绍了多种光源剔除绘制方法.对比和分析了各种方法的优缺点,并总结了多光源绘制的研究趋势以及面临的挑战.
多光源场景绘制一直是计算机图形学中的重要研究问题,是实现全局光照效果的重要手段之一,也是游戏、影视、动画等应用领域的重要需求.无论在离线绘制领域还是实时绘制领域,多光源场景的高效绘制仍然是一个巨大的挑战.回顾了近年来图形学在多光源场景绘制方面的主要进展,如何提高多光源绘制的效率是所有相关方法的主要研究问题.在离线绘制领域,首先介绍了如何通过加快可见性测试来提高单个光源的平均计算效率;然后,讨论了光源聚类算法,介绍了基于光源聚类的加速绘制方法,并讨论了不同的光源聚类策略,包括基于层次结构的策略和基于矩阵分析的策略;之后,介绍了基于光源聚类的重要性采样方法.在实时绘制领域,介绍了多种光源剔除绘制方法.对比和分析了各种方法的优缺点,并总结了多光源绘制的研究趋势以及面临的挑战.
2020, 57(1): 32-52.
DOI: 10.7544/issn1000-1239.2020.20190239
摘要:
随着共享经济的发展,拼车这一由多位乘客协商共同乘坐同一辆车并分担费用的共享出行模式正得到广泛应用.在移动互联网与普适计算的推动下,拼车体现出数据量大、动态性强、目标多样、应用范围广等新特点.这些新特点使得求解大规模拼车问题的难度大大增加,并催生了众多大规模拼车算法的学术研究.拼车中各类关于社会影响因素的实际问题也成为新型研究热点.为了面向大规模拼车算法进行系统性介绍,首先介绍了拼车问题的概念定义与工作流程.随后,对大规模拼车系统的核心算法问题,即路线规划问题进行了系统地分类、介绍与分析,并进一步详细讨论了大规模拼车涉及的激励机制、隐私保护、安全保障等社会影响因素.最后,分析展望了该领域未来的潜在研究方向,为从事拼车算法的相关研究人员和从业者提供参考和帮助.
随着共享经济的发展,拼车这一由多位乘客协商共同乘坐同一辆车并分担费用的共享出行模式正得到广泛应用.在移动互联网与普适计算的推动下,拼车体现出数据量大、动态性强、目标多样、应用范围广等新特点.这些新特点使得求解大规模拼车问题的难度大大增加,并催生了众多大规模拼车算法的学术研究.拼车中各类关于社会影响因素的实际问题也成为新型研究热点.为了面向大规模拼车算法进行系统性介绍,首先介绍了拼车问题的概念定义与工作流程.随后,对大规模拼车系统的核心算法问题,即路线规划问题进行了系统地分类、介绍与分析,并进一步详细讨论了大规模拼车涉及的激励机制、隐私保护、安全保障等社会影响因素.最后,分析展望了该领域未来的潜在研究方向,为从事拼车算法的相关研究人员和从业者提供参考和帮助.
2020, 57(1): 53-73.
DOI: 10.7544/issn1000-1239.2020.20190002
摘要:
智慧健康是基于物联网的环境感知网络和传感基础设施的实时的、智能的、无处不在的医疗保健服务.得益于云计算、雾计算以及物联网等相关技术的快速发展,关于智慧健康的相关研究也逐渐步入正轨.近年来对于智慧健康的相关研究,主要从云端和边缘这2个主要方向展开,其中包含了云、雾计算,物联网传感器,区块链以及隐私和安全等相关技术.目前,在云和智慧健康的研究中,关注点在于如何利用云去完成海量健康数据的挑战和提升服务性能,具体包括健康大数据在云中的存储、检索和计算等相关问题.而在边缘,研究重点转变为健康数据的采集、传输和计算,具体包括用于采集健康数据的各类传感器和可穿戴设备、各类无线传感器技术以及如何在边缘处理健康数据并提升服务性能等.最后,对典型的智慧健康应用案例、区块链在智慧健康中的应用以及相关隐私和安全问题进行了讨论,并提出了智慧健康服务在未来的挑战和机遇.
智慧健康是基于物联网的环境感知网络和传感基础设施的实时的、智能的、无处不在的医疗保健服务.得益于云计算、雾计算以及物联网等相关技术的快速发展,关于智慧健康的相关研究也逐渐步入正轨.近年来对于智慧健康的相关研究,主要从云端和边缘这2个主要方向展开,其中包含了云、雾计算,物联网传感器,区块链以及隐私和安全等相关技术.目前,在云和智慧健康的研究中,关注点在于如何利用云去完成海量健康数据的挑战和提升服务性能,具体包括健康大数据在云中的存储、检索和计算等相关问题.而在边缘,研究重点转变为健康数据的采集、传输和计算,具体包括用于采集健康数据的各类传感器和可穿戴设备、各类无线传感器技术以及如何在边缘处理健康数据并提升服务性能等.最后,对典型的智慧健康应用案例、区块链在智慧健康中的应用以及相关隐私和安全问题进行了讨论,并提出了智慧健康服务在未来的挑战和机遇.
2020, 57(1): 74-84.
DOI: 10.7544/issn1000-1239.2020.20190519
摘要:
近10年来,在盛行的网络应用(如搜索、在线零售和云计算等)的需求驱动下,数据中心在全球范围内以前所未有的速度和规模发展建立起来.特别地,数据中心网络引起了学术界和工业界的广泛关注.在这样的背景下,调研了数据中心网络的一个核心方面——传输层协议.虽然传输协议在因特网上已经有很长的历史,它却直到2010年才在数据中心网络环境下被系统性地探索.数据中心网络有着和因特网不一样的特点(如单一控制域和同构网络架构),这给数据中心网络上的传输协议设计同时带来了机遇和挑战.在这驱使下,一系列的传输协议被设计提出.将早期(2010—2015年)数据中心网络传输设计方面的工作分成3类——基于端主机的拥塞控制、网络仲裁机制和交换机优先级调度,对这3类工作的优缺点作深入讨论.最后,分析近年来数据中心网络传输设计的研究趋势——接收端驱动的主动拥塞控制和RDMA传输协议设计.
近10年来,在盛行的网络应用(如搜索、在线零售和云计算等)的需求驱动下,数据中心在全球范围内以前所未有的速度和规模发展建立起来.特别地,数据中心网络引起了学术界和工业界的广泛关注.在这样的背景下,调研了数据中心网络的一个核心方面——传输层协议.虽然传输协议在因特网上已经有很长的历史,它却直到2010年才在数据中心网络环境下被系统性地探索.数据中心网络有着和因特网不一样的特点(如单一控制域和同构网络架构),这给数据中心网络上的传输协议设计同时带来了机遇和挑战.在这驱使下,一系列的传输协议被设计提出.将早期(2010—2015年)数据中心网络传输设计方面的工作分成3类——基于端主机的拥塞控制、网络仲裁机制和交换机优先级调度,对这3类工作的优缺点作深入讨论.最后,分析近年来数据中心网络传输设计的研究趋势——接收端驱动的主动拥塞控制和RDMA传输协议设计.
2020, 57(1): 85-101.
DOI: 10.7544/issn1000-1239.2020.20190062
摘要:
随着DRAM技术面临密度扩展瓶颈以及高泄漏功耗问题,新型非易失内存(non-volatile memory, NVM)因其非易失、高密度、字节寻址和低静态功耗等特性,已经得到学术界和工业界的广泛关注.新型非易失内存如相变内存(phase change memory, PCM)很可能替代DRAM或与DRAM混合作为系统主内存.然而,由于NVM的非易失特性,存储在NVM的数据在面临系统故障时可能由于部分更新或内存控制器写重排序而产生不一致性的问题.为了保证NVM中数据的一致性,确保对NVM写操作的顺序化和持久化是基本要求.NVM有着内在缺陷如有限的写耐久性以及较高的写延迟,在保证NVM数据一致性的前提下,减少NVM写次数有助于延长NVM的寿命并提高NVM系统的性能.重点讨论了基于NVM构建的持久索引、文件系统以及持久性事务等数据一致性研究,以便为实现低开销的数据一致性提供更好的解决方案或思路.最后给出了基于NVM的数据一致性研究展望.
随着DRAM技术面临密度扩展瓶颈以及高泄漏功耗问题,新型非易失内存(non-volatile memory, NVM)因其非易失、高密度、字节寻址和低静态功耗等特性,已经得到学术界和工业界的广泛关注.新型非易失内存如相变内存(phase change memory, PCM)很可能替代DRAM或与DRAM混合作为系统主内存.然而,由于NVM的非易失特性,存储在NVM的数据在面临系统故障时可能由于部分更新或内存控制器写重排序而产生不一致性的问题.为了保证NVM中数据的一致性,确保对NVM写操作的顺序化和持久化是基本要求.NVM有着内在缺陷如有限的写耐久性以及较高的写延迟,在保证NVM数据一致性的前提下,减少NVM写次数有助于延长NVM的寿命并提高NVM系统的性能.重点讨论了基于NVM构建的持久索引、文件系统以及持久性事务等数据一致性研究,以便为实现低开销的数据一致性提供更好的解决方案或思路.最后给出了基于NVM的数据一致性研究展望.
2020, 57(1): 102-123.
DOI: 10.7544/issn1000-1239.2020.20180675
摘要:
云计算作为一种新型计算模式,已经受到了学术界和工业界的广泛关注.基于资源虚拟化技术,云计算能够以按需使用、按使用量付费的方式为用户提供基础设施、平台、软件等服务.因此,越来越多的企业和组织选择云计算来部署他们的科学或商业应用.然而,随着用户数量的不断增加,数据中心的规模在迅速扩大、架构变得日益复杂,导致云计算系统的运行故障频繁发生,造成了巨大的损失.因此在规模巨大、架构复杂的云计算系统中,如何保障系统的可靠性已经成为一个极具挑战性的问题.针对云计算可靠性问题,概述了云计算系统中常见的各种故障,并详细描述了目前云计算中提高可靠性关键的故障管理技术;由于故障管理技术的应用会不可避免地增加系统的能耗,因此介绍了云计算中可靠性与能耗权衡问题的研究现状;最后列举了当前云计算可靠性研究中存在的主要挑战.
云计算作为一种新型计算模式,已经受到了学术界和工业界的广泛关注.基于资源虚拟化技术,云计算能够以按需使用、按使用量付费的方式为用户提供基础设施、平台、软件等服务.因此,越来越多的企业和组织选择云计算来部署他们的科学或商业应用.然而,随着用户数量的不断增加,数据中心的规模在迅速扩大、架构变得日益复杂,导致云计算系统的运行故障频繁发生,造成了巨大的损失.因此在规模巨大、架构复杂的云计算系统中,如何保障系统的可靠性已经成为一个极具挑战性的问题.针对云计算可靠性问题,概述了云计算系统中常见的各种故障,并详细描述了目前云计算中提高可靠性关键的故障管理技术;由于故障管理技术的应用会不可避免地增加系统的能耗,因此介绍了云计算中可靠性与能耗权衡问题的研究现状;最后列举了当前云计算可靠性研究中存在的主要挑战.
2020, 57(1): 124-135.
DOI: 10.7544/issn1000-1239.2020.20190166
摘要:
提出一种新颖精巧的用户期望值提取模型,据此建立基于用户偏好的个性化模糊量词.首先给定一组多属性样本信息,仅要求用户根据自己的态度偏好或主观评判,提供一个关于样本方案的优劣排序.根据这个排序序列,基于有序加权平均(ordered weighted averaging, OWA)思想并利用理想解法(technique for order preference by similarity to ideal solution, TOPSIS)方法,构造用户期望值提取模型,获取用户关于样本信息的期望值,再从中抽取偏好、态度等个性特征信息,建立针对此用户的个性化量词.最后利用所得量词对新产品进行OWA数据集成,实现个性化产品推荐.案例研究及实验分析表明,所提模型及方法能够很好地捕获并反映主体的偏好及态度等个性特征,在实际应用中可面向不同层次水平、不同知识结构的用户,理性快捷地向其推荐相应态度偏好下的“最满意方案”而非一般意义下的“最优方案”,相比同类方法具有更大的实用性和灵活性.
提出一种新颖精巧的用户期望值提取模型,据此建立基于用户偏好的个性化模糊量词.首先给定一组多属性样本信息,仅要求用户根据自己的态度偏好或主观评判,提供一个关于样本方案的优劣排序.根据这个排序序列,基于有序加权平均(ordered weighted averaging, OWA)思想并利用理想解法(technique for order preference by similarity to ideal solution, TOPSIS)方法,构造用户期望值提取模型,获取用户关于样本信息的期望值,再从中抽取偏好、态度等个性特征信息,建立针对此用户的个性化量词.最后利用所得量词对新产品进行OWA数据集成,实现个性化产品推荐.案例研究及实验分析表明,所提模型及方法能够很好地捕获并反映主体的偏好及态度等个性特征,在实际应用中可面向不同层次水平、不同知识结构的用户,理性快捷地向其推荐相应态度偏好下的“最满意方案”而非一般意义下的“最优方案”,相比同类方法具有更大的实用性和灵活性.
2020, 57(1): 136-144.
DOI: 10.7544/issn1000-1239.2020.20190204
摘要:
变分自编码(variational autoencoder, VAE)是一种基于连续隐向量的生成模型,通过变分近似构建目标函数,其中的生成模型及变分推理模型均采用神经网络结构.传统变分自编码模型中的变分识别模型假设多维隐变量之间是相互独立的,这种假设简化了推理过程,但是这使得变分下界过于松弛,同时限制了隐向量空间的表示能力.提出混合变分自编码(mixture of variational autoencoder, MVAE)模型,它通过多个变分自编码组件生成样本数据,丰富了变分识别模型结构,同时扩展了隐向量表示空间.该模型以连续型隐向量作为模型的隐层表示,其先验分布为高斯分布;以离散型隐向量作为各组件的指示向量,其先验分布为多项式分布.对于MVAE模型的变分优化目标,采用重参策略和折棍参数化策略处理目标函数,并用随机梯度下降方法求解模型参数.MVAE采用混合组件的方法可以增强隐变量空间的表示能力,提高近似推理精度,重参策略和折棍参数化策略可以有效求解对应的优化问题.最后在MNIST和OMNIGLOT数据集上设计了对比实验,验证了MVAE模型较高的推理精度及较强的隐变量空间表示能力.
变分自编码(variational autoencoder, VAE)是一种基于连续隐向量的生成模型,通过变分近似构建目标函数,其中的生成模型及变分推理模型均采用神经网络结构.传统变分自编码模型中的变分识别模型假设多维隐变量之间是相互独立的,这种假设简化了推理过程,但是这使得变分下界过于松弛,同时限制了隐向量空间的表示能力.提出混合变分自编码(mixture of variational autoencoder, MVAE)模型,它通过多个变分自编码组件生成样本数据,丰富了变分识别模型结构,同时扩展了隐向量表示空间.该模型以连续型隐向量作为模型的隐层表示,其先验分布为高斯分布;以离散型隐向量作为各组件的指示向量,其先验分布为多项式分布.对于MVAE模型的变分优化目标,采用重参策略和折棍参数化策略处理目标函数,并用随机梯度下降方法求解模型参数.MVAE采用混合组件的方法可以增强隐变量空间的表示能力,提高近似推理精度,重参策略和折棍参数化策略可以有效求解对应的优化问题.最后在MNIST和OMNIGLOT数据集上设计了对比实验,验证了MVAE模型较高的推理精度及较强的隐变量空间表示能力.
2020, 57(1): 145-158.
DOI: 10.7544/issn1000-1239.2020.20190180
摘要:
行为识别是当今计算机视觉领域的一个研究热点,是一项具有挑战性的任务.行为识别分析与其网络输入数据类型、网络结构、特征融合环节具有密切联系.目前,主流的行为识别网络输入数据为RGB图像和光流图像,网络结构主要以双流和3D卷积为主;而特征选择直接影响到识别的效率,多层次的特征融合工作还有很多问题有待解决.针对主流的双流卷积网络输入数据为RGB图像和光流图像的局限,利用低秩空间中稀疏特征能够有效捕捉视频中运动物体信息的特点,对网络输入数据进行补充.同时,针对网络中缺乏信息交互的特点,将深度网络中高层语义信息和低层细节信息结合起来共同识别行为动作,使时序分割网络性能更具优势.在行为识别数据集UCF101和HMDB51上取得了97.1%和76.7%的识别效果,较目前主流算法有了较大的提升.实验结果表明,该方法能够有效地提高行为识别的识别率.
行为识别是当今计算机视觉领域的一个研究热点,是一项具有挑战性的任务.行为识别分析与其网络输入数据类型、网络结构、特征融合环节具有密切联系.目前,主流的行为识别网络输入数据为RGB图像和光流图像,网络结构主要以双流和3D卷积为主;而特征选择直接影响到识别的效率,多层次的特征融合工作还有很多问题有待解决.针对主流的双流卷积网络输入数据为RGB图像和光流图像的局限,利用低秩空间中稀疏特征能够有效捕捉视频中运动物体信息的特点,对网络输入数据进行补充.同时,针对网络中缺乏信息交互的特点,将深度网络中高层语义信息和低层细节信息结合起来共同识别行为动作,使时序分割网络性能更具优势.在行为识别数据集UCF101和HMDB51上取得了97.1%和76.7%的识别效果,较目前主流算法有了较大的提升.实验结果表明,该方法能够有效地提高行为识别的识别率.
2020, 57(1): 159-174.
DOI: 10.7544/issn1000-1239.2020.20190042
摘要:
因果关系作为一种重要的关系类型在关系推理等许多领域中起着至关重要的作用,因此对因果关系进行抽取是文本挖掘中的一项基本任务.与传统文本分类方法或关系抽取不同,采用序列标注的方法可以抽取文本中的因果实体并确定因果关系方向,不需要依赖特征工程或因果背景知识.主要贡献有:1)拓展句法依存树到句法依存图,将图注意力网络应用到自然语言处理中,引入了基于句法依存图的图注意力网络的概念;2)提出Bi-LSTM+CRF+S-GAT因果关系抽取模型,根据输入的词向量生成句子中每个词的因果标签;3)对SemEval数据集进行修正与拓展,针对其存在的缺陷制定规则重新标注实验数据.在拓展后的SemEval数据集上进行了大量的实验,结果表明:该模型在预测准确率上比现有最优模型Bi-LSTM+CRF+self-ATT提高了0.064.
因果关系作为一种重要的关系类型在关系推理等许多领域中起着至关重要的作用,因此对因果关系进行抽取是文本挖掘中的一项基本任务.与传统文本分类方法或关系抽取不同,采用序列标注的方法可以抽取文本中的因果实体并确定因果关系方向,不需要依赖特征工程或因果背景知识.主要贡献有:1)拓展句法依存树到句法依存图,将图注意力网络应用到自然语言处理中,引入了基于句法依存图的图注意力网络的概念;2)提出Bi-LSTM+CRF+S-GAT因果关系抽取模型,根据输入的词向量生成句子中每个词的因果标签;3)对SemEval数据集进行修正与拓展,针对其存在的缺陷制定规则重新标注实验数据.在拓展后的SemEval数据集上进行了大量的实验,结果表明:该模型在预测准确率上比现有最优模型Bi-LSTM+CRF+self-ATT提高了0.064.
2020, 57(1): 175-187.
DOI: 10.7544/issn1000-1239.2020.20180691
摘要:
实体解析(entity resolution, ER)是数据集成和清洗系统的关键基础问题.尽管有大量实体解析方法提出,但这些方法依赖隐式或显式的假设或采用不同的解析策略.对相同的实体解析任务进行处理后,它们的结论存在冲突,产生了大量的不一致记录对.在没有给定标记数据的情况下,进行这类记录对的消歧处理具有很大的挑战:一方面当标签数据缺失时,评估现存方法的解析效果并选出最优的不可行,另一方面尽管可选的方法是协调这些冲突结果以得到一致的标记方案,但有效且融合所有提示信息的消歧策略还有待研究.为此,提出了一种基于因子图的不一致记录对消歧方法.该方法首先对某给定的实体解析任务使用现存的实体解析技术进行实体解析,得到一致或不一致的记录对;接着,用核密度估计、匹配信息传递等方法输出与不一致记录对是否匹配相关的特征,并把这些建模为因子图的因子函数,该因子图是一个带因子权重的联合概率分布;最后基于最大似然估计方法估计出各因子的权重,并基于该分布对不一致记录对进行消歧处理.实验结果表明:在真实的数据集合,该方法有效且优于现存最好的方法.
实体解析(entity resolution, ER)是数据集成和清洗系统的关键基础问题.尽管有大量实体解析方法提出,但这些方法依赖隐式或显式的假设或采用不同的解析策略.对相同的实体解析任务进行处理后,它们的结论存在冲突,产生了大量的不一致记录对.在没有给定标记数据的情况下,进行这类记录对的消歧处理具有很大的挑战:一方面当标签数据缺失时,评估现存方法的解析效果并选出最优的不可行,另一方面尽管可选的方法是协调这些冲突结果以得到一致的标记方案,但有效且融合所有提示信息的消歧策略还有待研究.为此,提出了一种基于因子图的不一致记录对消歧方法.该方法首先对某给定的实体解析任务使用现存的实体解析技术进行实体解析,得到一致或不一致的记录对;接着,用核密度估计、匹配信息传递等方法输出与不一致记录对是否匹配相关的特征,并把这些建模为因子图的因子函数,该因子图是一个带因子权重的联合概率分布;最后基于最大似然估计方法估计出各因子的权重,并基于该分布对不一致记录对进行消歧处理.实验结果表明:在真实的数据集合,该方法有效且优于现存最好的方法.
2020, 57(1): 188-201.
DOI: 10.7544/issn1000-1239.2020.20190079
摘要:
组件化服务化软件系统由松耦合的异构服务组件构成,每个服务组件都包含着大量可高度灵活配置的配置项.服务组件之间存在着复杂的依赖关系,导致其配置项相互关联,使得系统部署、更新或迁移易于出错.对于相互关联的配置项,更改一个配置项就需要修改与之关联的其他配置项,否则将违反约束条件,导致系统出现故障.因而,分析配置项关联性对于保障系统可靠性至关重要,但需要跨产品的领域知识.提出了一种基于关联挖掘的服务一致化配置方法.该方法爬取配置文件样本数据以将搜索范围缩小到频繁改变的配置项,根据配置项的名称、取值和类型的相似性计算,为配置项对生成关联系数,使用定义的过滤规则确定候选关联配置项对集合,输出排序的配置项关联性列表以供查询.基于该方法部署了典型应用系统进行实验和评估,实验结果表明:该方法能够准确检测配置项的关联性.
组件化服务化软件系统由松耦合的异构服务组件构成,每个服务组件都包含着大量可高度灵活配置的配置项.服务组件之间存在着复杂的依赖关系,导致其配置项相互关联,使得系统部署、更新或迁移易于出错.对于相互关联的配置项,更改一个配置项就需要修改与之关联的其他配置项,否则将违反约束条件,导致系统出现故障.因而,分析配置项关联性对于保障系统可靠性至关重要,但需要跨产品的领域知识.提出了一种基于关联挖掘的服务一致化配置方法.该方法爬取配置文件样本数据以将搜索范围缩小到频繁改变的配置项,根据配置项的名称、取值和类型的相似性计算,为配置项对生成关联系数,使用定义的过滤规则确定候选关联配置项对集合,输出排序的配置项关联性列表以供查询.基于该方法部署了典型应用系统进行实验和评估,实验结果表明:该方法能够准确检测配置项的关联性.
2020, 57(1): 202-213.
DOI: 10.7544/issn1000-1239.2020.20180871
摘要:
软件动态胎记技术是实现混淆对抗的软件抄袭检测的有效手段之一.然而,多线程程序中线程交织的不确定性对其造成了不可忽视的影响;极端情况下,传统动态胎记技术甚至会判定同一个程序与其自身不存在抄袭关系.对此,提出从多线程程序在同一输入下的多条执行轨迹中进行相似部分的识别,并从中抽象出不易受线程交织影响的行为motifs来实现多线程程序的抄袭检测.该方法捕捉程序的动态执行轨迹,经过轨迹修剪、gram匹配以及扩展和抽象,从中提取motifs胎记建模多线程程序的行为;最终,通过衡量motifs胎记的相似性实现程序间潜在抄袭的判定.在一个包含234个不同版本多线程程序的公共数据集上开展的实验表明,motifs胎记是一种可靠的线程感知胎记方法,不仅可有效对抗当下主流的代码混淆技术,相比现有的2种多线程程序抄袭检测方法TreSB(thread-related system call birthmark)和TOB(thread-oblivious birthmark),也体现出更优秀的检测能力.
软件动态胎记技术是实现混淆对抗的软件抄袭检测的有效手段之一.然而,多线程程序中线程交织的不确定性对其造成了不可忽视的影响;极端情况下,传统动态胎记技术甚至会判定同一个程序与其自身不存在抄袭关系.对此,提出从多线程程序在同一输入下的多条执行轨迹中进行相似部分的识别,并从中抽象出不易受线程交织影响的行为motifs来实现多线程程序的抄袭检测.该方法捕捉程序的动态执行轨迹,经过轨迹修剪、gram匹配以及扩展和抽象,从中提取motifs胎记建模多线程程序的行为;最终,通过衡量motifs胎记的相似性实现程序间潜在抄袭的判定.在一个包含234个不同版本多线程程序的公共数据集上开展的实验表明,motifs胎记是一种可靠的线程感知胎记方法,不仅可有效对抗当下主流的代码混淆技术,相比现有的2种多线程程序抄袭检测方法TreSB(thread-related system call birthmark)和TOB(thread-oblivious birthmark),也体现出更优秀的检测能力.
2020, 57(1): 214-226.
DOI: 10.7544/issn1000-1239.2020.20190052
摘要:
时间自动机为实时系统进行建模时,通常会因不同的时间度量而产生大量状态片段,精确加速技术可以有效解决这一类片段问题.精确加速中的关键技术是可加速环窗口的计算,但其计算方法均为人工推演.通过对精确加速计算原理的分析,提出了一种精确加速中可加速环窗口的计算算法,可以选择环中任意入边有环时钟复位的节点作为起始,对识别出的可加速环进行进一步精准压缩.首先,识别出时间自动机中所有可加速环,选取1个未处理的可加速环检测环时钟复位的节点出边是否有环时钟复位;然后,将所记录的节点按照记录顺序连接成1个新环,并重新计算新环各边的边界约束;最后,计算可加速环的窗口.算法根据窗口计算原理,获取影响窗口大小的位置不变式、边界约束、时钟复位等数据,并对无用数据和节点进行约减,压缩了可加速环规模,提高了计算效率.算法为研发精确加速自动检测程序奠定了基础.
时间自动机为实时系统进行建模时,通常会因不同的时间度量而产生大量状态片段,精确加速技术可以有效解决这一类片段问题.精确加速中的关键技术是可加速环窗口的计算,但其计算方法均为人工推演.通过对精确加速计算原理的分析,提出了一种精确加速中可加速环窗口的计算算法,可以选择环中任意入边有环时钟复位的节点作为起始,对识别出的可加速环进行进一步精准压缩.首先,识别出时间自动机中所有可加速环,选取1个未处理的可加速环检测环时钟复位的节点出边是否有环时钟复位;然后,将所记录的节点按照记录顺序连接成1个新环,并重新计算新环各边的边界约束;最后,计算可加速环的窗口.算法根据窗口计算原理,获取影响窗口大小的位置不变式、边界约束、时钟复位等数据,并对无用数据和节点进行约减,压缩了可加速环规模,提高了计算效率.算法为研发精确加速自动检测程序奠定了基础.
2020, 57(1): 227-239.
DOI: 10.7544/issn1000-1239.2020.20190026
摘要:
为了弥补已有的研究成果无法直接处理道路网环境下K-支配空间Skyline查询问题的不足,提出了基于网络Voronoi图的道路网环境下K-支配空间Skyline查询方法.该方法将K-支配应用到道路网Skyline查询中以处理多属性数据对象,在实际应用中可以用来解决道路网环境下多目标查询和决策问题.方法主要包括道路网中约减数据集过程和K-支配检查过程.首先基于空间数据点构建网络Voronoi图,并对查询点建立查询凸包,通过网络Voronoi图的性质与查询区域的位置关系对数据集约减,从而优化数据集并且有效地减少查询点重复搜索的现象;然后对候选集的非空间属性进行K-支配检查得到道路网精炼集合;最后对精炼集合进行支配检查得到最终的空间Skyline集合.理论研究和实验表明所提出的方法具有较高的效率,可较好地处理道路网环境下K-支配空间Skyline查询问题.
为了弥补已有的研究成果无法直接处理道路网环境下K-支配空间Skyline查询问题的不足,提出了基于网络Voronoi图的道路网环境下K-支配空间Skyline查询方法.该方法将K-支配应用到道路网Skyline查询中以处理多属性数据对象,在实际应用中可以用来解决道路网环境下多目标查询和决策问题.方法主要包括道路网中约减数据集过程和K-支配检查过程.首先基于空间数据点构建网络Voronoi图,并对查询点建立查询凸包,通过网络Voronoi图的性质与查询区域的位置关系对数据集约减,从而优化数据集并且有效地减少查询点重复搜索的现象;然后对候选集的非空间属性进行K-支配检查得到道路网精炼集合;最后对精炼集合进行支配检查得到最终的空间Skyline集合.理论研究和实验表明所提出的方法具有较高的效率,可较好地处理道路网环境下K-支配空间Skyline查询问题.