2015年 第52卷 第1期
摘要：
国家自然科学基金优秀青年基金是基金委近年来新设的一个项目，促进创新型青年人才的快速成长，主要支持具备5～10年的科研经历并取得一定科研成就的青年科学技术人员。这一期的计算机研究与发展邀请了中科院计算所陈云霁、清华大学朱军、北京大学马思伟、中国科学技术大学刘利刚、华中科技大学廖小飞、天津大学胡清华等6位优秀青年基金获得者来介绍他们近来的工作。这些工作一定程度上体现了我国计算机领域青年科研人员锐意进取、开拓创新的风貌。
国家自然科学基金优秀青年基金是基金委近年来新设的一个项目，促进创新型青年人才的快速成长，主要支持具备5～10年的科研经历并取得一定科研成就的青年科学技术人员。这一期的计算机研究与发展邀请了中科院计算所陈云霁、清华大学朱军、北京大学马思伟、中国科学技术大学刘利刚、华中科技大学廖小飞、天津大学胡清华等6位优秀青年基金获得者来介绍他们近来的工作。这些工作一定程度上体现了我国计算机领域青年科研人员锐意进取、开拓创新的风貌。
2015, 52(1): 3-15.
DOI: 10.7544/issn1000-1239.2015.20140104
摘要：
计算机系统模拟器已经成为计算机系统结构领域研究中不可或缺的工具，真实计算机系统的不断发展对模拟器的性能要求也越来越高，模拟器的性能提升也促进了真实计算机结构和性能上的进步.为了提升性能，模拟器的发展经历了从串行单线程模拟到多处理单元并行模拟的发展趋势.串行模拟器和并行模拟器分别针对各自的模拟目标和模拟过程提出了各种优化方案，串行模拟器研究者提出了交织码、二进制翻译、FPGA加速、模拟分离等加速技术，而并行模拟器在串行模拟器基础上针对自己特有的支撑架构以及负载均衡、同步机制和通信机制等问题提出了各种解决方案.
计算机系统模拟器已经成为计算机系统结构领域研究中不可或缺的工具，真实计算机系统的不断发展对模拟器的性能要求也越来越高，模拟器的性能提升也促进了真实计算机结构和性能上的进步.为了提升性能，模拟器的发展经历了从串行单线程模拟到多处理单元并行模拟的发展趋势.串行模拟器和并行模拟器分别针对各自的模拟目标和模拟过程提出了各种优化方案，串行模拟器研究者提出了交织码、二进制翻译、FPGA加速、模拟分离等加速技术，而并行模拟器在串行模拟器基础上针对自己特有的支撑架构以及负载均衡、同步机制和通信机制等问题提出了各种解决方案.
2015, 52(1): 16-26.
DOI: 10.7544/issn1000-1239.2015.20140107
摘要：
随着大数据的快速发展，以概率统计为基础的机器学习在近年来受到工业界和学术界的极大关注，并在视觉、语音、自然语言、生物等领域获得很多重要的成功应用，其中贝叶斯方法在过去20多年也得到了快速发展,成为非常重要的一类机器学习方法.总结了贝叶斯方法在机器学习中的最新进展，具体内容包括贝叶斯机器学习的基础理论与方法、非参数贝叶斯方法及常用的推理方法、正则化贝叶斯方法等. 最后，还针对大规模贝叶斯学习问题进行了简要的介绍和展望，对其发展趋势作了总结和展望.
随着大数据的快速发展，以概率统计为基础的机器学习在近年来受到工业界和学术界的极大关注，并在视觉、语音、自然语言、生物等领域获得很多重要的成功应用，其中贝叶斯方法在过去20多年也得到了快速发展,成为非常重要的一类机器学习方法.总结了贝叶斯方法在机器学习中的最新进展，具体内容包括贝叶斯机器学习的基础理论与方法、非参数贝叶斯方法及常用的推理方法、正则化贝叶斯方法等. 最后，还针对大规模贝叶斯学习问题进行了简要的介绍和展望，对其发展趋势作了总结和展望.
2015, 52(1): 27-37.
DOI: 10.7544/issn1000-1239.2015.20140106
摘要：
AVS(audio video coding standard)工作组是“数字音视频编解码技术标准”工作组的简称，由国家原信息产业部科学技术司于2002年6月批准成立.工作组的任务是制(修)订数字音视频的压缩、解压缩、处理和表示等共性技术标准，为数字音视频设备与系统提供高效经济的编解码技术.经过10多年的努力，AVS已经成功制定一系列标准，如AVS1，AVS+和AVS2.其中AVS1和AVS2的说法源于AVS第1阶段和第2阶段的工作或第1代、第2代标准.AVS+是工作组专门为高清数字电视广播制定的一个标准.目前AVS1和AVS+标准已经制定完成并成功应用于许多行业中，AVS2也即将完成.将对AVS的AVS视频标准12年来的技术发展过程给以概述，并简单介绍目前最新一代视频编码标准AVS2关键技术，最后对视频编码技术的未来发展方向予以展望.
AVS(audio video coding standard)工作组是“数字音视频编解码技术标准”工作组的简称，由国家原信息产业部科学技术司于2002年6月批准成立.工作组的任务是制(修)订数字音视频的压缩、解压缩、处理和表示等共性技术标准，为数字音视频设备与系统提供高效经济的编解码技术.经过10多年的努力，AVS已经成功制定一系列标准，如AVS1，AVS+和AVS2.其中AVS1和AVS2的说法源于AVS第1阶段和第2阶段的工作或第1代、第2代标准.AVS+是工作组专门为高清数字电视广播制定的一个标准.目前AVS1和AVS+标准已经制定完成并成功应用于许多行业中，AVS2也即将完成.将对AVS的AVS视频标准12年来的技术发展过程给以概述，并简单介绍目前最新一代视频编码标准AVS2关键技术，最后对视频编码技术的未来发展方向予以展望.
2015, 52(1): 38-44.
DOI: 10.7544/issn1000-1239.2015.20140108
摘要：
与传统制造所生产的产品相比，3D打印产品的成本仍相对较高.因此，如何能在不牺牲打印物体表面质量的前提下通过模型优化来减少打印材料消耗，对于降低打印成本至关重要.针对这一问题，借鉴传统渐进结构优化方法，结合Von Mises应力计算，给出一种面向3D打印体积极小的拓扑优化算法.该算法通过模型力学计算所得的最大Von Mises应力与材料允许应力之比来引导模型体积减小进化，直至最大Von Mises应力达到允许应力值为止.同时，引入多分辨率技术，由粗网格再到细网格进行优化计算，有效地提高了计算效率.与现有其他给定结构模式的方法相比，该优化结果能更好地体现模型荷载受力的传递路径.
与传统制造所生产的产品相比，3D打印产品的成本仍相对较高.因此，如何能在不牺牲打印物体表面质量的前提下通过模型优化来减少打印材料消耗，对于降低打印成本至关重要.针对这一问题，借鉴传统渐进结构优化方法，结合Von Mises应力计算，给出一种面向3D打印体积极小的拓扑优化算法.该算法通过模型力学计算所得的最大Von Mises应力与材料允许应力之比来引导模型体积减小进化，直至最大Von Mises应力达到允许应力值为止.同时，引入多分辨率技术，由粗网格再到细网格进行优化计算，有效地提高了计算效率.与现有其他给定结构模式的方法相比，该优化结果能更好地体现模型荷载受力的传递路径.
2015, 52(1): 45-55.
DOI: 10.7544/issn1000-1239.2015.20140105
摘要：
近年来,多线程程序中性能bug问题越来越突出.传统用于检测并发错误的记录/重放系统存在重放开销和执行时间不精确等问题,因此不适于对性能bug的研究.针对上述问题,提出了一种可用于多线程程序性能分析的重放系统——PerfPlay.首先,分析了用于程序性能分析时必要的程序信息；其次,基于程序执行轨迹,探讨了不同的重放策略，并提出了基于程序调度的重放策略，以保证重放系统的性能保真度；最后,基于提出的性能重放系统,进一步研究了经典的“线程间不必要锁竞争”所造成的性能问题.通过与传统的重放策略作比较,PerfPlay保证了重放系统的性能保证度.并经过案例研究,发现并进一步验证了若干真实的多线程程序性能问题.
近年来,多线程程序中性能bug问题越来越突出.传统用于检测并发错误的记录/重放系统存在重放开销和执行时间不精确等问题,因此不适于对性能bug的研究.针对上述问题,提出了一种可用于多线程程序性能分析的重放系统——PerfPlay.首先,分析了用于程序性能分析时必要的程序信息；其次,基于程序执行轨迹,探讨了不同的重放策略，并提出了基于程序调度的重放策略，以保证重放系统的性能保真度；最后,基于提出的性能重放系统,进一步研究了经典的“线程间不必要锁竞争”所造成的性能问题.通过与传统的重放策略作比较,PerfPlay保证了重放系统的性能保证度.并经过案例研究,发现并进一步验证了若干真实的多线程程序性能问题.
2015, 52(1): 56-65.
DOI: 10.7544/issn1000-1239.2015.20140544
摘要：
多标记学习是一类复杂的决策任务，同一个对象可能同时属于多个类别.此类任务在文本分类、图像识别、基因功能分析等领域广泛存在.多标记分类任务往往由高维特征描述，存在大量无关和冗余的信息.目前已经提出了大量的单标记特征选择算法以应对维数灾难问题，但对于多标记的属性约简和特征选择却鲜有研究.将粗糙集应用于多标记数据的特征选择中，针对多标记分类任务，重新定义了邻域粗糙集的下近似和依赖度计算方法，探讨了这一模型的性质，进而构造了基于邻域粗糙集的多标记分类任务的特征选择算法，并给出了在公开数据上的实验结果.实验分析证明算法的有效性.
多标记学习是一类复杂的决策任务，同一个对象可能同时属于多个类别.此类任务在文本分类、图像识别、基因功能分析等领域广泛存在.多标记分类任务往往由高维特征描述，存在大量无关和冗余的信息.目前已经提出了大量的单标记特征选择算法以应对维数灾难问题，但对于多标记的属性约简和特征选择却鲜有研究.将粗糙集应用于多标记数据的特征选择中，针对多标记分类任务，重新定义了邻域粗糙集的下近似和依赖度计算方法，探讨了这一模型的性质，进而构造了基于邻域粗糙集的多标记分类任务的特征选择算法，并给出了在公开数据上的实验结果.实验分析证明算法的有效性.
2015, 52(1): 66-82.
DOI: 10.7544/issn1000-1239.2015.20130970
摘要：
解释器广泛应用于Java虚拟机、JavaScript执行引擎等托管运行环境中.解释器通常使用间接转移指令实现字节码分派.在现代多发射多级流水的微处理器中，间接转移预测失效严重制约解释器的性能.针对解释器提出了一种字节码指针引导的间接转移预测技术，其核心思想是使用解释器特有的字节码指针值区分不同的间接转移场景.该技术使用软硬件协同的方式，解释器中插入专门的引导指令以标记字节码指针，预测器在运行时刻使用字节码指针值预测转移目标地址.实验结果表明，该技术与常用的转移目标缓冲预测器相比，能提升Java解释器的性能达34.7%，能提升JavaScript解释器的性能达8.3%，与专用的硬件间接转移预测器TTC(tagged target cache)相比，也能提升Java解释器的性能达21.9%.
解释器广泛应用于Java虚拟机、JavaScript执行引擎等托管运行环境中.解释器通常使用间接转移指令实现字节码分派.在现代多发射多级流水的微处理器中，间接转移预测失效严重制约解释器的性能.针对解释器提出了一种字节码指针引导的间接转移预测技术，其核心思想是使用解释器特有的字节码指针值区分不同的间接转移场景.该技术使用软硬件协同的方式，解释器中插入专门的引导指令以标记字节码指针，预测器在运行时刻使用字节码指针值预测转移目标地址.实验结果表明，该技术与常用的转移目标缓冲预测器相比，能提升Java解释器的性能达34.7%，能提升JavaScript解释器的性能达8.3%，与专用的硬件间接转移预测器TTC(tagged target cache)相比，也能提升Java解释器的性能达21.9%.
2015, 52(1): 83-93.
DOI: 10.7544/issn1000-1239.2015.20131182
摘要：
虚拟化技术在为现代数据中心提供高效的服务器整合能力和灵活的应用部署能力的同时，也对数据中心服务器的I/O系统设计提出了新的需求，现有I/O资源与服务器紧密绑定的I/O体系架构将产生成本上升、资源冗余、I/O连线复杂化等一系列问题.针对上述问题，提出了一种基于单根I/O虚拟化协议(single root I/O virtualization, SR-IOV)的多根I/O资源池化方法：基于硬件的多根域间地址和ID映射机制，实现了多个物理服务器对同一I/O设备的共享复用，有效减少单体服务器所需的设备数量和连线数量，并进一步提高服务器密度；同时提出虚拟I/O设备热插拔技术和多根共享管理机制，实现了虚拟I/O资源在服务器间的实时动态分配，提高资源的利用效率.提出的方法在可编程逻辑器件(fieid-programmable gate array, FPGA)原型系统中进行了验证，其评测表明，方法能够在实现多根I/O虚拟化共享的同时，保证各个根节点服务器获得近乎本地直连设备的I/O性能.
虚拟化技术在为现代数据中心提供高效的服务器整合能力和灵活的应用部署能力的同时，也对数据中心服务器的I/O系统设计提出了新的需求，现有I/O资源与服务器紧密绑定的I/O体系架构将产生成本上升、资源冗余、I/O连线复杂化等一系列问题.针对上述问题，提出了一种基于单根I/O虚拟化协议(single root I/O virtualization, SR-IOV)的多根I/O资源池化方法：基于硬件的多根域间地址和ID映射机制，实现了多个物理服务器对同一I/O设备的共享复用，有效减少单体服务器所需的设备数量和连线数量，并进一步提高服务器密度；同时提出虚拟I/O设备热插拔技术和多根共享管理机制，实现了虚拟I/O资源在服务器间的实时动态分配，提高资源的利用效率.提出的方法在可编程逻辑器件(fieid-programmable gate array, FPGA)原型系统中进行了验证，其评测表明，方法能够在实现多根I/O虚拟化共享的同时，保证各个根节点服务器获得近乎本地直连设备的I/O性能.
2015, 52(1): 94-104.
DOI: 10.7544/issn1000-1239.2015.20140485
摘要：
能耗和资源等绿色需求是嵌入式系统发展不容忽视的因素.数据分配作为编译后端的重要优化手段，对能耗以及资源的利用率有着重要影响.为提高资源和能源的有效利用率，构建了数据分配过程的绿色评估模型，并以此为指导，提出了一种迭代式多目标分配优化方法，从能源消耗和资源的均衡使用度2个方面出发，利用可交换类指令重排优化和寄存器重分配优化，对总线和存储系统的绿色指标进行改进.模拟实验表明，该方法相对于GCC编译器，能够获得23%左右的绿色指标提升值，为满足更高的绿色需求提供了保障.
能耗和资源等绿色需求是嵌入式系统发展不容忽视的因素.数据分配作为编译后端的重要优化手段，对能耗以及资源的利用率有着重要影响.为提高资源和能源的有效利用率，构建了数据分配过程的绿色评估模型，并以此为指导，提出了一种迭代式多目标分配优化方法，从能源消耗和资源的均衡使用度2个方面出发，利用可交换类指令重排优化和寄存器重分配优化，对总线和存储系统的绿色指标进行改进.模拟实验表明，该方法相对于GCC编译器，能够获得23%左右的绿色指标提升值，为满足更高的绿色需求提供了保障.
2015, 52(1): 105-115.
DOI: 10.7544/issn1000-1239.2015.20131195
摘要：
在大规模流数据实时处理领域中图形处理器(graphics processing unit, GPU)集群是一种重要的并行计算系统，对计算速度、能耗和可靠性3项指标都有较高要求.然而各指标互相约束，在实时计算中需要动态寻找最优均衡点，因此GPU集群中多项性能指标实时优化成为一个具有挑战性的问题.为综合考虑计算速度、能耗和可靠性3项指标，利用极大熵函数法把多项指标转化为一个综合性能评价指标，再以模型预测控制理论为基础构造一个自适应强的控制模型，该模型能够依据计算负载的变化动态调整集群内节点的能耗状态，在保证计算速度和可靠性的前提下消减冗余计算能耗.与未考虑可靠性的基准控制模型进行对比实验，结果表明所提出的模型具有较好的控制稳定性和鲁棒性，适合应用到GPU集群节能管理中.
在大规模流数据实时处理领域中图形处理器(graphics processing unit, GPU)集群是一种重要的并行计算系统，对计算速度、能耗和可靠性3项指标都有较高要求.然而各指标互相约束，在实时计算中需要动态寻找最优均衡点，因此GPU集群中多项性能指标实时优化成为一个具有挑战性的问题.为综合考虑计算速度、能耗和可靠性3项指标，利用极大熵函数法把多项指标转化为一个综合性能评价指标，再以模型预测控制理论为基础构造一个自适应强的控制模型，该模型能够依据计算负载的变化动态调整集群内节点的能耗状态，在保证计算速度和可靠性的前提下消减冗余计算能耗.与未考虑可靠性的基准控制模型进行对比实验，结果表明所提出的模型具有较好的控制稳定性和鲁棒性，适合应用到GPU集群节能管理中.
2015, 52(1): 116-129.
DOI: 10.7544/issn1000-1239.2015.20131567
摘要：
随着社交网络、生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时，利用深度优先遍历(depth-first search, DFS)或可达性传递闭包可以很容易处理可达性查询.但是，随着图的规模越变越大，由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大，这2种方法不再适用.因此，许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域，如软件工程、 编程语言、分布式计算、社交网络分析、 生物网络分析、XML和RDF数据库、路由规划等领域.此外，可达性索引还可用于加速其他图算法，如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着，依据支持的数据规模、数据类型以及查询类别，将现有可达性索引工作进行了分类，并对代表性工作进行分类比较；最后，讨论了现有的大规模图数据可达性索引方法存在的问题，并指出了未来的研究方向.
随着社交网络、生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时，利用深度优先遍历(depth-first search, DFS)或可达性传递闭包可以很容易处理可达性查询.但是，随着图的规模越变越大，由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大，这2种方法不再适用.因此，许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域，如软件工程、 编程语言、分布式计算、社交网络分析、 生物网络分析、XML和RDF数据库、路由规划等领域.此外，可达性索引还可用于加速其他图算法，如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着，依据支持的数据规模、数据类型以及查询类别，将现有可达性索引工作进行了分类，并对代表性工作进行分类比较；最后，讨论了现有的大规模图数据可达性索引方法存在的问题，并指出了未来的研究方向.
2015, 52(1): 130-140.
DOI: 10.7544/issn1000-1239.2015.20130691
摘要：
扩展条件函数依赖(extended conditional functional dependency, eCFD)是一种描述数据一致性的语义规则，是条件函数依赖(conditional functional dependency, CFD)的扩展.相比于CFD，eCFD能够描述更多的模式从而表达更丰富的语义信息.然而，关注eCFD的研究工作并不多.从给定数据中发现eCFD规则是一个重要问题，据笔者所知，目前还没有这方面的工作.该问题的难点在于，给定数据中所有合法的eCFD规则之间存在不一致的情况，且包含大量冗余，而CFD和传统的函数依赖规则并没有这样的问题.为避免不一致，同时尽可能地消除冗余，定义了“强合法eCFD”和“近似无冗余eCFD”.基于这些概念给出了eCFD发现问题的形式化定义，并给出了MeCFD算法.利用划分属性的方法，MeCFD首先生成所有的基本eCFD，然后，通过合并基本eCFD来构造“组合eCFD”.使用先深序来搜索候选空间，使得MeCFD仅用常数的存储空间来维护数据划分，节省了大量的空间开销，有效的剪枝策略被用来改进MeCFD的性能.真实数据集上的实验结果显示出MeCFD良好的可扩展性以及剪枝策略和优化方法的有效性.
扩展条件函数依赖(extended conditional functional dependency, eCFD)是一种描述数据一致性的语义规则，是条件函数依赖(conditional functional dependency, CFD)的扩展.相比于CFD，eCFD能够描述更多的模式从而表达更丰富的语义信息.然而，关注eCFD的研究工作并不多.从给定数据中发现eCFD规则是一个重要问题，据笔者所知，目前还没有这方面的工作.该问题的难点在于，给定数据中所有合法的eCFD规则之间存在不一致的情况，且包含大量冗余，而CFD和传统的函数依赖规则并没有这样的问题.为避免不一致，同时尽可能地消除冗余，定义了“强合法eCFD”和“近似无冗余eCFD”.基于这些概念给出了eCFD发现问题的形式化定义，并给出了MeCFD算法.利用划分属性的方法，MeCFD首先生成所有的基本eCFD，然后，通过合并基本eCFD来构造“组合eCFD”.使用先深序来搜索候选空间，使得MeCFD仅用常数的存储空间来维护数据划分，节省了大量的空间开销，有效的剪枝策略被用来改进MeCFD的性能.真实数据集上的实验结果显示出MeCFD良好的可扩展性以及剪枝策略和优化方法的有效性.
2015, 52(1): 141-155.
DOI: 10.7544/issn1000-1239.2015.20131166
摘要：
Java本地调用接口(Java native interface, JNI)机制被广泛应用在移动应用开发领域.JNI机制中JNI接口函数被用于在本地代码中解析和转换Java端的数据类型和Java对象.然而，JNI接口函数的调用开销影响了程序运行的效率，其复杂的使用规范也是集成与复用第三方本地组件时的主要障碍.提出一种基于跨语言对象迁移策略的复合本地对象模型，能够实现有效减少本地调用程序中的JNI接口函数调用开销和有效利用已有本地组件的目的.详细讨论了复合本地对象的语言特性及其具体实现，并给出跨语言对象迁移规范以及开发实例.在Dalvik虚拟机中实现了该模型，通过实验证明该策略和模型能够有效改善JNI机制的不足.
Java本地调用接口(Java native interface, JNI)机制被广泛应用在移动应用开发领域.JNI机制中JNI接口函数被用于在本地代码中解析和转换Java端的数据类型和Java对象.然而，JNI接口函数的调用开销影响了程序运行的效率，其复杂的使用规范也是集成与复用第三方本地组件时的主要障碍.提出一种基于跨语言对象迁移策略的复合本地对象模型，能够实现有效减少本地调用程序中的JNI接口函数调用开销和有效利用已有本地组件的目的.详细讨论了复合本地对象的语言特性及其具体实现，并给出跨语言对象迁移规范以及开发实例.在Dalvik虚拟机中实现了该模型，通过实验证明该策略和模型能够有效改善JNI机制的不足.
2015, 52(1): 156-166.
DOI: 10.7544/issn1000-1239.2015.20130915
摘要：
随着在线社会网络的快速发展，越来越多的人开始利用微博或Twitter来传播信息或分享观点.研究社会网络中的信息传播规律对于意见领袖挖掘、舆情监控、品牌营销等有着重要意义.虽然有关社会网络中的信息传播模型已经得到广泛研究，但是影响网络中节点之间信息传播的因素有哪些，以及如何刻画信息传播过程，仍然是一个有待深入研究的重要内容.传统的传播模型及其扩展模型更多地从网络结构出发研究信息传播，很大程度上忽视了节点属性和信息内容的影响.从多个维度提取信息传播的特征，包括节点属性特征和信息内容特征，对节点间传播概率和传播延迟进行建模，提出一个细粒度的在线社会网络信息传播模型.利用随机梯度下降算法学习模型中的各个特征的权重.另外，针对模型的传播预测功能，在新浪微博真实数据集上进行了实验，结果表明，在预测准确率方面，所提出的模型要优于其他同类模型，如异步独立级联模型、NetRate模型.
随着在线社会网络的快速发展，越来越多的人开始利用微博或Twitter来传播信息或分享观点.研究社会网络中的信息传播规律对于意见领袖挖掘、舆情监控、品牌营销等有着重要意义.虽然有关社会网络中的信息传播模型已经得到广泛研究，但是影响网络中节点之间信息传播的因素有哪些，以及如何刻画信息传播过程，仍然是一个有待深入研究的重要内容.传统的传播模型及其扩展模型更多地从网络结构出发研究信息传播，很大程度上忽视了节点属性和信息内容的影响.从多个维度提取信息传播的特征，包括节点属性特征和信息内容特征，对节点间传播概率和传播延迟进行建模，提出一个细粒度的在线社会网络信息传播模型.利用随机梯度下降算法学习模型中的各个特征的权重.另外，针对模型的传播预测功能，在新浪微博真实数据集上进行了实验，结果表明，在预测准确率方面，所提出的模型要优于其他同类模型，如异步独立级联模型、NetRate模型.
2015, 52(1): 167-176.
DOI: 10.7544/issn1000-1239.2015.20130722
摘要：
针对嵌入式系统体系结构分析设计语言(architecture analysis and design language, AADL)分级调度模型的分析问题,提出了基于模型检验的可调度性分析和验证方法.基于时间自动机理论，将AADL分级调度模型转换为时间自动机网络，将待验证性质描述为时序逻辑公式，通过模型检验工具对可调度性进行分析和验证.研究结果表明，使用模型检验方法来分析AADL分级调度模型的可调度性是可行的.相对其他方法而言,该方法利用了形式化方法的穷举性来分析系统的性质,分析结果更加精确.
针对嵌入式系统体系结构分析设计语言(architecture analysis and design language, AADL)分级调度模型的分析问题,提出了基于模型检验的可调度性分析和验证方法.基于时间自动机理论，将AADL分级调度模型转换为时间自动机网络，将待验证性质描述为时序逻辑公式，通过模型检验工具对可调度性进行分析和验证.研究结果表明，使用模型检验方法来分析AADL分级调度模型的可调度性是可行的.相对其他方法而言,该方法利用了形式化方法的穷举性来分析系统的性质,分析结果更加精确.
2015, 52(1): 177-190.
DOI: 10.7544/issn1000-1239.2015.20130995
摘要：
视频跟踪是机器视觉领域中的热点研究问题，在过去的几十年内得到了广泛研究.为了获得鲁棒的跟踪效果，设计能够适应跟踪目标外观变化的外观模型成为算法研究中的一种重要内容.近年来，将机器学习理论引入外观模型设计中的思想大大推动了视频跟踪研究的发展.为了使读者能够快速了解其发展的趋势并且掌握基于外观模型学习跟踪算法研究的技术，在介绍外观模型学习跟踪算法原理和机制的基础上，重点综述了外观模型学习跟踪方法的研究进展，包括目标特征描述和3类主要目标外观建模方式及其各自研究过程中跟踪方法的对比与分析，进而总结了外观模型学习跟踪算法在理论及应用方面的研究现状，最后提出进一步研究的主要发展内容和趋势.
视频跟踪是机器视觉领域中的热点研究问题，在过去的几十年内得到了广泛研究.为了获得鲁棒的跟踪效果，设计能够适应跟踪目标外观变化的外观模型成为算法研究中的一种重要内容.近年来，将机器学习理论引入外观模型设计中的思想大大推动了视频跟踪研究的发展.为了使读者能够快速了解其发展的趋势并且掌握基于外观模型学习跟踪算法研究的技术，在介绍外观模型学习跟踪算法原理和机制的基础上，重点综述了外观模型学习跟踪方法的研究进展，包括目标特征描述和3类主要目标外观建模方式及其各自研究过程中跟踪方法的对比与分析，进而总结了外观模型学习跟踪算法在理论及应用方面的研究现状，最后提出进一步研究的主要发展内容和趋势.
2015, 52(1): 191-199.
DOI: 10.7544/issn1000-1239.2015.20131113
摘要：
隐藏主题变量图模型是一种用节点表示潜在主题或者潜在主题变化的概率图模型.针对当前隐藏主题变量图模型只能提取单层主题节点的缺陷，提出一种基于深度学习框架的提取多层主题节点的概率图模型.该模型在隐藏主题变量图模型的底层增加预处理结构层，即引入自组织映射层，可以有效地提取不同层次的主题状态.另外，隐藏主题变量图模型使用了隐马尔可夫网络和条件随机场的相结合的模型.针对条件随机场，提出了一阶逻辑子句定义的特征函数.弥补了长距离依存特性的缺失.在此基础上提出了一种分层次提取主题状态的新深度学习算法.在国际通用的亚马逊情感分析数据、Tripadvisor情感分析数据上的实验表明，新算法可以提升情感分析的准确率.同时实验结果也表明，提取多层主题状态可以更好地挖掘宏观主题分布信息和评论的局部主题信息.
隐藏主题变量图模型是一种用节点表示潜在主题或者潜在主题变化的概率图模型.针对当前隐藏主题变量图模型只能提取单层主题节点的缺陷，提出一种基于深度学习框架的提取多层主题节点的概率图模型.该模型在隐藏主题变量图模型的底层增加预处理结构层，即引入自组织映射层，可以有效地提取不同层次的主题状态.另外，隐藏主题变量图模型使用了隐马尔可夫网络和条件随机场的相结合的模型.针对条件随机场，提出了一阶逻辑子句定义的特征函数.弥补了长距离依存特性的缺失.在此基础上提出了一种分层次提取主题状态的新深度学习算法.在国际通用的亚马逊情感分析数据、Tripadvisor情感分析数据上的实验表明，新算法可以提升情感分析的准确率.同时实验结果也表明，提取多层主题状态可以更好地挖掘宏观主题分布信息和评论的局部主题信息.
2015, 52(1): 200-210.
DOI: 10.7544/issn1000-1239.2015.20130493
摘要：
在实际应用中，包含多种特征空间信息的高阶异构数据广泛出现.由于高阶联合聚类算法能够有效融合多种特征空间信息提高聚类效果，近年来逐渐成为研究热点.目前高阶联合聚类算法多数为非层次聚类算法.然而，高阶异构数据内部往往隐藏着层次聚簇结构，为了更有效地挖掘数据内部隐藏的层次聚簇模式，提出了一种高阶层次联合聚类算法(high-order hierarchical co-clustering algorithm, HHCC).该算法利用变量相关性度量指标Goodman-Kruskal τ衡量对象变量和特征变量的相关性，将相关性较强的对象划分到同一个对象聚簇中，同时将相关性较强的特征划分到同一个特征聚簇中.HHCC算法采用自顶向下的分层聚类策略，利用指标Goodman-Kruskal τ评估每层对象和特征的聚类质量，利用局部搜索方法优化指标Goodman-Kruskal τ，自动确定聚簇数目，获得每层的聚类结果，最终形成树状聚簇结构.实验结果表明HHCC算法的聚类效果优于4种经典的同构层次聚类算法和5种已有的非层次高阶联合聚类算法.
在实际应用中，包含多种特征空间信息的高阶异构数据广泛出现.由于高阶联合聚类算法能够有效融合多种特征空间信息提高聚类效果，近年来逐渐成为研究热点.目前高阶联合聚类算法多数为非层次聚类算法.然而，高阶异构数据内部往往隐藏着层次聚簇结构，为了更有效地挖掘数据内部隐藏的层次聚簇模式，提出了一种高阶层次联合聚类算法(high-order hierarchical co-clustering algorithm, HHCC).该算法利用变量相关性度量指标Goodman-Kruskal τ衡量对象变量和特征变量的相关性，将相关性较强的对象划分到同一个对象聚簇中，同时将相关性较强的特征划分到同一个特征聚簇中.HHCC算法采用自顶向下的分层聚类策略，利用指标Goodman-Kruskal τ评估每层对象和特征的聚类质量，利用局部搜索方法优化指标Goodman-Kruskal τ，自动确定聚簇数目，获得每层的聚类结果，最终形成树状聚簇结构.实验结果表明HHCC算法的聚类效果优于4种经典的同构层次聚类算法和5种已有的非层次高阶联合聚类算法.
2015, 52(1): 211-220.
DOI: 10.7544/issn1000-1239.2015.20131016
摘要：
为提高神经网络的逼近能力,提出一种基于受控Hadamard门设计的量子神经网络模型及算法.该模型输入为多维离散序列，可用矩阵描述，行数为输入节点数，列数为序列长度.模型为3层结构，隐层为量子神经元，输出层为普通神经元.量子神经元由量子旋转门和多位受控Hadamard门组成，利用多位受控Hadamard门中目标量子位的输出向输入端的反馈，实现对输入序列的整体记忆，利用受控Hadamard门中控制位和目标位之间的受控关系获得量子神经元的输出.基于量子计算理论设计了该模型的学习算法.该模型可高效地获取输入序列的特征.实验结果表明，当输入节点数和序列长度满足一定关系时，该模型明显优于普通BP神经网络.
为提高神经网络的逼近能力,提出一种基于受控Hadamard门设计的量子神经网络模型及算法.该模型输入为多维离散序列，可用矩阵描述，行数为输入节点数，列数为序列长度.模型为3层结构，隐层为量子神经元，输出层为普通神经元.量子神经元由量子旋转门和多位受控Hadamard门组成，利用多位受控Hadamard门中目标量子位的输出向输入端的反馈，实现对输入序列的整体记忆，利用受控Hadamard门中控制位和目标位之间的受控关系获得量子神经元的输出.基于量子计算理论设计了该模型的学习算法.该模型可高效地获取输入序列的特征.实验结果表明，当输入节点数和序列长度满足一定关系时，该模型明显优于普通BP神经网络.
2015, 52(1): 221-228.
DOI: 10.7544/issn1000-1239.2015.20131135
摘要：
本体作为知识库表示知识已经成为计算机理论与应用的研究热点.在描述逻辑中,将本体看作一个逻辑理论,一个本体被形式化为给定的描述逻辑系统的一个Tbox.本体是动态的实体，为了适应新领域的发展，需要对原始本体进行扩充.但是扩充后的本体与原始本体是否保持逻辑一致性是目前研究者们所关注的焦点.在Lutz等人研究的基础上探究FL0的保守扩充问题.首先构建了FL0的典范模型,将包含推理问题转换为典范模型的模拟问题；其次由典范模型之间的最大模拟是多项式时间复杂的,证明了FL0的包含推理是多项式时间复杂的;最后给出描述逻辑FL0的保守扩充及其判定算法，证明了FL0的保守扩充的判定算法是指数时间复杂的.
本体作为知识库表示知识已经成为计算机理论与应用的研究热点.在描述逻辑中,将本体看作一个逻辑理论,一个本体被形式化为给定的描述逻辑系统的一个Tbox.本体是动态的实体，为了适应新领域的发展，需要对原始本体进行扩充.但是扩充后的本体与原始本体是否保持逻辑一致性是目前研究者们所关注的焦点.在Lutz等人研究的基础上探究FL0的保守扩充问题.首先构建了FL0的典范模型,将包含推理问题转换为典范模型的模拟问题；其次由典范模型之间的最大模拟是多项式时间复杂的,证明了FL0的包含推理是多项式时间复杂的;最后给出描述逻辑FL0的保守扩充及其判定算法，证明了FL0的保守扩充的判定算法是指数时间复杂的.
2015, 52(1): 229-247.
DOI: 10.7544/issn1000-1239.2015.20131340
摘要：
随着信息技术的发展，以Web2.0技术为基础的博客、微博、社交网络等新兴服务和物联网以前所未有的发展速度产生了类型繁多的数据，而云计算为数据的存储提供了基础平台，这一切造就了大数据时代的正式到来.大数据中蕴藏着巨大的价值，是企业的宝贵财富.但大数据同时也带来了巨大的挑战，个人隐私保护问题就是其中之一.迅速发展的互联网已经成为人们生活中不可或缺的一部分，人们在网络上留下了许多数据足迹，这些数据足迹具有累积性和关联性，将多处数据足迹聚集在一起，就可以发现个人的隐私信息.恶意分子利用这些信息进行欺诈等行为，给个人的生活带来了许多麻烦或经济损失，因此大数据的个人隐私问题引起了工业界和学术界的广泛关注.首先介绍了大数据时代个人隐私保护的相关概念，讨论了个人隐私保护面临的挑战和研究问题；然后从数据层、应用层以及数据展示层叙述了个人隐私保护所使用的技术，探讨了个人隐私保护的相关法律以及行业规范的几个重要方面；最后提出了大数据个人隐私保护的进一步研究方向.
随着信息技术的发展，以Web2.0技术为基础的博客、微博、社交网络等新兴服务和物联网以前所未有的发展速度产生了类型繁多的数据，而云计算为数据的存储提供了基础平台，这一切造就了大数据时代的正式到来.大数据中蕴藏着巨大的价值，是企业的宝贵财富.但大数据同时也带来了巨大的挑战，个人隐私保护问题就是其中之一.迅速发展的互联网已经成为人们生活中不可或缺的一部分，人们在网络上留下了许多数据足迹，这些数据足迹具有累积性和关联性，将多处数据足迹聚集在一起，就可以发现个人的隐私信息.恶意分子利用这些信息进行欺诈等行为，给个人的生活带来了许多麻烦或经济损失，因此大数据的个人隐私问题引起了工业界和学术界的广泛关注.首先介绍了大数据时代个人隐私保护的相关概念，讨论了个人隐私保护面临的挑战和研究问题；然后从数据层、应用层以及数据展示层叙述了个人隐私保护所使用的技术，探讨了个人隐私保护的相关法律以及行业规范的几个重要方面；最后提出了大数据个人隐私保护的进一步研究方向.
2015, 52(1): 248-258.
DOI: 10.7544/issn1000-1239.2015.20130544
摘要：
随着云计算服务的广泛应用，为了节省磁盘空间和带宽，出现了一种新技术：客户端去重复化.但近期发现了一种针对该技术的新型攻击：攻击者只需获得原始文件的一个摘要信息，即文件的散列值，即可从服务器端获得全部原始文件.为了解决上述安全问题，提出了一个密码学安全的、高效的证明方案来支持多客户端加密文件的去重复删除场景.通过抽样检测、动态系数和随机选择的原始文件检索值使方案达到安全与高效的目标；同时，还提出了一种巧妙的分布式捎带技术，将文件加密密钥的分发过程与所有权证明过程同步实施.最后，对所提方案进行了严格的安全性证明和深入的性能分析与仿真，结果表明，所提的方案不仅能达到可证明的安全级别，而且执行效率较高，尤其在减少客户端计算负载方面.
随着云计算服务的广泛应用，为了节省磁盘空间和带宽，出现了一种新技术：客户端去重复化.但近期发现了一种针对该技术的新型攻击：攻击者只需获得原始文件的一个摘要信息，即文件的散列值，即可从服务器端获得全部原始文件.为了解决上述安全问题，提出了一个密码学安全的、高效的证明方案来支持多客户端加密文件的去重复删除场景.通过抽样检测、动态系数和随机选择的原始文件检索值使方案达到安全与高效的目标；同时，还提出了一种巧妙的分布式捎带技术，将文件加密密钥的分发过程与所有权证明过程同步实施.最后，对所提方案进行了严格的安全性证明和深入的性能分析与仿真，结果表明，所提的方案不仅能达到可证明的安全级别，而且执行效率较高，尤其在减少客户端计算负载方面.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
