Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2017年 第54卷 第12期    出版日期:2017-12-01
综述
2017人工智能应用专题前言
郑庆华
2017, 54(12):  2647-2648. 
摘要 ( 1352 )   HTML ( 8)   PDF (370KB) ( 607 )  
相关文章 | 计量指标
在1956年的美国达特茅斯会议上,包括麦卡锡、明斯基等在内的4位图灵奖获得者与多名学者共同确立了“人工智能”的概念,希望机器能像人那样认知、思考和学习,即用计算机模拟人的智能。近年来,人工智能研究从过去追求计算机模拟人的智能到追求大数据驱动的智能,追求人机融合,追求“互联网-人-机”更加融合的群体智能,这就是提出人工智能2.0(AI2.0)的由来。人工智能研究者结合大数据技术研究智能城市,发展智慧教育、智能医疗、智能交通、智能游戏、无人驾驶、智能制造,形成了一大批新应用。《计算机研究与发展》推出AI2.0新应用研究专题,报导人工智能在新领域中的实际案例,交流学术思想和研究成果,问题导向、应用驱动、以用促研、以研促用,既促进AI2.0的理论研究,又推动应用发展。本期专题得到同行的广泛关注,通过公开征文收到33篇高质量投稿稿件,这些论文在多个应用领域上阐述了AI2.0关键理论与技术的重要研究成果,展示了人工智能与新领域深度融合的发展前景。本专题严格按照期刊审稿的要求进行,特邀编委先后邀请了二十余位相关领域的专家参与评审,历经初审、复审、终审等阶段,最终遴选出4篇高质量的论文入选本专题。内容涵盖了智能医疗、领域知识图谱生成等应用,在一定程度上反映了当前国内学者在AI2.0的代表性新应用。
人工智能
互补学习:一种面向图像应用和噪声标注的深度神经网络训练方法
周彧聪,刘轶,王锐
2017, 54(12):  2649-2659.  doi:10.7544/issn1000-1239.2017.20170637
摘要 ( 841 )   HTML ( 1)   PDF (3210KB) ( 619 )  
相关文章 | 计量指标
近几年来,深度神经网络在图像识别、语音识别、自然语言处理等众多领域取得了突破性的进展.互联网以及移动设备的快速发展极大地推进了图像应用的普及,也为深度神经网络的训练积累了大量数据.其中,大规模人工标注的数据是成功训练深度神经网络的关键.但随着数据规模的快速增长,人工标注图像的成本也越来越高,同时不可避免地产生标注错误,从而影响神经网络的训练.为此,提出了一种称为互补学习的方法,面向图像应用中深度神经网络的训练,将简单样本挖掘和迁移学习的思想相结合,利用少量人工标注的干净数据和大量带有噪声标注的数据,同时训练一主一辅2个深度神经网络模型,在训练过程中采用互补的策略分别选择部分样本进行学习,同时将辅模型的知识迁移给主模型,从而减少噪声标注对训练的影响.实验表明:提出的方法能有效地利用带有噪声标注的数据训练深度神经网络,并对比其他方法有一定的优越性,有较强的应用价值.
基于多网络数据协同矩阵分解预测蛋白质功能
余国先,王可尧,傅广垣,王峻,曾安
2017, 54(12):  2660-2673.  doi:10.7544/issn1000-1239.2017.20170644
摘要 ( 671 )   HTML ( 0)   PDF (2039KB) ( 449 )  
相关文章 | 计量指标
准确预测蛋白质功能是生物信息学的核心任务之一,也是人工智能在生物数据分析中的重要应用点之一.高通量技术的广泛应用产生了大量的生物分子功能关联网络,整合这些网络可更为全面地分析理解蛋白质功能机理,提升蛋白质功能预测精度.已有多种基于数据整合的蛋白质功能预测方法,但它们通常难以应用到较大功能标签空间,未利用标签间关联性和差异性整合多个网络.提出一种基于多网络数据协同矩阵分解的蛋白质功能预测方法(ProCMF).该方法首先利用非负矩阵分解将蛋白质-功能标签关联矩阵分解为2个低秩矩阵,挖掘蛋白质与标签之间的潜在关联.其次,为利用标签间关联关系和多种蛋白质特征数据,ProCMF分别基于上述2个低秩矩阵定义平滑正则性,约束指导低秩矩阵的协同分解.为了差异性地集成多个网络,ProCMF对不同的网络设置不同的权重.最后ProCMF将上述目标统一到一个目标方程中,并用一种交替迭代的方法分别优化求解低秩矩阵和网络权重.在酵母菌、人类和老鼠3个模式物种的多网络数据集上的实验结果表明:ProCMF获得了较其他相关算法更好的预测性能,ProCMF能有效地处理大量的功能标签和区分性地整合多个网络.
EAE:一种酶知识图谱自适应嵌入表示方法
杜治娟,张祎,孟小峰,王秋月
2017, 54(12):  2674-2686.  doi:10.7544/issn1000-1239.2017.20170638
摘要 ( 735 )   HTML ( 1)   PDF (3106KB) ( 461 )  
相关文章 | 计量指标
近年来,构建大规模知识图谱(knowledge graph, KG),并用其解决实际问题已经成为大趋势.KG的嵌入表示方便了机器学习在KG等关系数据上的应用,它可以促进知识分析、推理、融合、补全,甚至决策.最近,开放域知识图谱(open-domain knowledge graph, OKG)的构建和嵌入表示已经得到蓬勃发展,大大促进了开放域中大数据的智能化.与此同时,特定域知识图谱(specific-domain knowledge graph, SKG)也成为了特定领域中智能应用的重要资源.但是,SKG还不发达,其嵌入表示尚处于萌芽阶段.这主要是由于SKG与OKG的数据分布显著不同,更具体地说:1)在OKG中,如WordNet,Freebase,头/尾实体的稀疏度几乎相等;但是在Enzyme,NCI-PID等SKG中不均匀性更受欢迎,例如微生物领域的酶KG中尾实体是头实体的1000倍.2)头实体和尾实体可以在OKG中交换位置,但是它们在SKG中是非交换的,因为大多数关系是属性.例如实体“奥巴马”可以是头实体也可以是尾实体,但是头实体“酶”总是处于头位置.3)关系的广度在OKG中具有小的偏差,而SKG中很不平衡.例如一个酶实体甚至可以链接31809个“x-gene”实体.基于这些观察,提出了一个新方法EAE来处理这3个问题,并在链接预测和元组分类任务上评估了EAE方法.实验结果表明:EAE显著优于Trans(E,H,R,D和TransSparse),达到了最先进的性能.
一种面向临床领域时序知识图谱的链接预测模型
陈德华,殷苏娜,乐嘉锦,王梅,潘乔,朱立峰
2017, 54(12):  2687-2697.  doi:10.7544/issn1000-1239.2017.20170640
摘要 ( 1812 )   HTML ( 11)   PDF (2758KB) ( 805 )  
相关文章 | 计量指标
知识图谱(knowledge graph)链接预测可以解决知识图谱中缺失信息的发现和还原,是目前知识图谱领域的研究热点.传统的知识图谱链接预测方法大多面向静态的数据,并不适用于具有动态变化特性的时序知识图谱.时序知识图谱广泛存在于不同领域中,以临床医学领域为例,糖尿病作为一种典型的慢性病,其病程是一个疾病缓慢发展演化的过程.因此,在临床医学时序知识图谱上进行临床意义的链接预测,比如预测糖尿病的并发症,则需要考虑糖尿病病程发展随时间变化的时序特性,这也为传统的知识图谱链接预测方法带来巨大挑战.为此,结合临床医学事实知识的时序特性,提出一种基于LSTM序列增量学习的临床领域时序知识图谱链接预测模型.该模型结合LSTM长短期记忆单元递归神经网络在序列学习上的优势,通过构建基于LSTM的序列增量学习层,以端到端的方式提取时序知识图谱中的三元组时序特征,从而实现对时序知识图谱的链接预测.通过在糖尿病时序知识图谱上的实验,验证了模型的高效性、可用性及稳定性.
网络技术
基于时间序列启发式信息的室内轨迹跟踪算法
秦俊平,邓庆绪,孙诗文,仁庆道尔吉,佟海滨,苏宪利
2017, 54(12):  2698-2710.  doi:10.7544/issn1000-1239.2017.20160803
摘要 ( 671 )   HTML ( 0)   PDF (4081KB) ( 365 )  
相关文章 | 计量指标
现有的无线传感器网络室内轨迹跟踪算法是通过定位形成轨迹的,没有利用一定空间范围内相邻信标节点RSSI定位信息在一段时间内的启发式信息.提出了基于RSSI时间序列启发式信息的轨迹跟踪算法,该算法构建基于定位信息时空关联特性的轨迹跟踪模型,对定位信息进行一维重构边界时间序列、二维重构区域统计量、移动最小二乘法检测分别得到动态时间窗口及与之匹配的区域信息及边界信息,在此基础上完成受启发式信息约束的动态时间弯曲轨迹跟踪,并对时空关联模型轨迹跟踪算法中定位信息融合处理的原理进行了严谨的数学论证.通过现场实验与仿真实验表明:该算法轨迹光滑、误差不累积、环境适应性好,相比现有方法基于启发式信息有效克服噪声的影响、减小搜索范围,提高轨迹跟踪的准确性.
EasiRCC:面向智能家居的规则匹配与冲突消除方法
黄晓辉,李栋,石海龙,崔莉
2017, 54(12):  2711-2720.  doi:10.7544/issn1000-1239.2017.20160646
摘要 ( 453 )   HTML ( 2)   PDF (2768KB) ( 286 )  
相关文章 | 计量指标
在智能家居中,规则间的冲突问题会直接影响系统的稳定性,针对智能家居的规则冲突问题,提出了一种新型的快速规则匹配和冲突消除方法EasiRCC.解决冲突问题,首先要解决规则的匹配问题,现有的规则匹配方法频发重复匹配现象,造成了系统资源的浪费,针对规则的重复匹配问题,提出了一种基于散列函数寻址方式的快速规则匹配算法EasiRMA,提高了规则匹配效率.其次要解决冲突的消除问题,现有的方法都是采用固定优先级方法来消除冲突,但是却增加了用户制定规则的复杂度,因此提出了一种混合优先级调度机制,使系统可以实时地自适应调整规则的执行优先级.实验结果显示:EasiRCC的规则匹配效率不会随着规则数的增多而变化,其时间复杂度为常数,而传统的匹配方法为O(N),并且在不影响用户正常家居生活的前提下,能够有效地消除规则冲突.
城市车联网V2V链路时延动态预测
王秀峰,崔刚,王春萌
2017, 54(12):  2721-2730.  doi:10.7544/issn1000-1239.2017.20158391
摘要 ( 525 )   HTML ( 5)   PDF (4057KB) ( 362 )  
相关文章 | 计量指标
链路时延是决定车联网(vehicular ad hoc networks, VANETs)许多网络性能的重要标准.现存的VANETs基于节点移动性解决链路时延的问题,但是都没有预测的功能,不适合实际VANETs中动态预测车-车(vehicle to vehicle, V2V)链路时延.提出动态预测任意2车链路时延的数学模型DPLD,考虑2车相对速度分布、相对距离变化、交通密度和城市场景中交通灯因素对2车之间链路时延的影响,因为这些因素在链路连接过程中是变化的.通过考虑相对速度的分布,模型能够实时地调整原则自适应车速变化.通过自动调整2车之间相对距离计算方法,DPLD模型能够自适应2车间相对距离的变化.因此该模型能够有效地预测预期要发生的2车之间的链路时延.这个模型实现取决于相对速度分布参数的估计方法、指数移动平均法对车速异常处理以及交通灯对链路时延影响的概率建模并且详细给出2车遇到不同交通灯的具体链路时延预测方法.仿真结果表明:DPLD模型预测的城市环境的2车之间链路时延准确性很高.
一种基于时间窗口的轻量级实时运动识别算法
董理骅,刘强,陈海明,崔莉
2017, 54(12):  2731-2740.  doi:10.7544/issn1000-1239.2017.20150462
摘要 ( 531 )   HTML ( 0)   PDF (1986KB) ( 364 )  
相关文章 | 计量指标
利用手机或可穿戴设备实时识别人的运动状态,有助于人们及时了解自身状况,进行科学的锻炼.现有高准确度运动识别算法大都具有较高的计算代价和存储代价,难以直接移植到手机和可穿戴设备上,且这些算法难以根据用户习惯校正识别模型.提出了一种基于时间窗口的轻量级实时运动识别算法EasiSports,利用手机或可穿戴设备中的加速度传感器,在多种情况下利用k-means聚类等方法在设备本地建立用户个人运动识别模型,使用SVM分类器实时识别坐、步行、跑步、上楼梯、下楼梯5种状态,计算量较小,适用于手机和可穿戴设备平台.实验表明:该算法对前述5种状态的识别准确度可达到87.45%,识别算法运行时间相较其他算法可获得30%以上的性能提升.
基于智能手机声信号的自标定室内定位系统
林峰,张磊,李贵楠,王智
2017, 54(12):  2741-2751.  doi:10.7544/issn1000-1239.2017.20160727
摘要 ( 634 )   HTML ( 1)   PDF (4645KB) ( 382 )  
相关文章 | 计量指标
随着室内位置信息服务需求的爆发式增长,对室内定位系统的定位精度、与智能手机的兼容性、成本控制、实时性及数据更新速率等提出了新的要求.基于通用智能手机平台,应用声技术提出了一种新的锚节点自标定与用户定位方法,设计并实现了一套室内定位系统:LinLoc.该系统在声技术TPSN测距模型的基础上,利用到达时间(time of arrival, TOA)估计技术,提出一种高实时性的用户定位方法,实现了厘米级别的用户定位,无需时间同步且与智能手机完全兼容,同时提出一种基于TPSN测距的半定规划(semidefinite programming, SDP)锚节点自标定方法,解决了大规模网络中锚节点的坐标标定及后期维护问题.针对LinLoc系统做了充分的仿真及实验,其结果表明:系统性能良好,定位精度可达0.05~0.3m,能够在室内环境中为人们提供精确的位置信息服务.
基于RFID的免携带设备手势识别关键技术研究
王旋,方河川,常俪琼,王举,陈晓江,房鼎益,彭瑶,陈峰
2017, 54(12):  2752-2760.  doi:10.7544/issn1000-1239.2017.20160648
摘要 ( 759 )   HTML ( 4)   PDF (2974KB) ( 407 )  
相关文章 | 计量指标
近年来手势识别作为人机交互的重要组成部分,受到广泛的关注.很多应用受益于手势识别,比如智能手机、智能家居、体感游戏等.与现有基于射频识别(radio frequency identification, RFID)的手势识别系统相比,基于RFID的免携带设备(device free)手势识别方法,不需要用户携带任何设备,因此有更好的用户体验.其主要思想是利用手势动作对信号的干扰信息作为指纹特征,并且利用多径增加匹配难度,从而保证了手势识别的准确度.具体思路为:通过数据分片解决RFID通信在时域上不连续的问题,进而采用雷达中合成孔径雷达(synthetic aperture radar, SAR)算法获取每个手势对应的指纹特征矩阵.最后,借鉴动态时间归整(dynamic time warping, DTW)算法匹配先验手势指纹库,从而完成手势识别.真实环境下的实验结果显示该方法可达到约85%的正确识别率,证明给出方法具有很高的可行性.
信息安全
基于路径与端址跳变的SDN网络主动防御技术
张连成,魏强,唐秀存,房家保
2017, 54(12):  2761-2771.  doi:10.7544/issn1000-1239.2017.20160461
摘要 ( 595 )   HTML ( 2)   PDF (3260KB) ( 387 )  
相关文章 | 计量指标
为解决已有路径跳变技术难以抵御全局截获分析攻击及已有端址跳变技术跳变同步难、部署难度大等问题,提出基于路径与端址跳变的SDN网络主动防御技术.首先,将路径跳变问题建模为约束求解问题,使用可满足性模理论求解器求解获得满足重复约束和容量约束的多条路径,然后,依据特定跳变时隙向所选跳变路径上的所有OpenFlow交换机下发对应的端址跳变流表项,使这些交换机对数据流进行正确转发的同时,更改其端口与地址信息.理论分析与实验结果表明:所提技术可以以较小的通信时延开销与计算开销实现通信双方传输路径与传输路径上端口与地址的随机跳变,且可提升SDN网络对于全局截获分析攻击、拒绝服务攻击与内部威胁的主动防御能力.
强安全的匿名隐式漫游认证与密钥协商方案
陈明
2017, 54(12):  2772-2784.  doi:10.7544/issn1000-1239.2017.20160485
摘要 ( 566 )   HTML ( 1)   PDF (1465KB) ( 365 )  
相关文章 | 计量指标
现有两方漫游认证与密钥协商方案没有考虑抵抗临时秘密泄露的安全性,仅在CK模型下可证明安全.基于椭圆曲线密码体制和基于身份密码系统,采用Schnorr签名算法设计了类似HMQV方案的“挑战-应答”签名,进而构造了一种基于隐式认证技术的、具有强安全性和匿名性的两方漫游认证密钥协商方案.随后,扩展了ID-BJM模型,使之能模拟两方漫游认证与密钥协商方案.在扩展的安全模型下,新方案的安全性被规约为多项式时间敌手求解椭圆曲线上的计算Diffie-Hellman问题,实现了eCK安全.对比分析表明:新方案具有更强的安全性,能抵抗临时秘密泄露攻击,需要实现的密码算法更少,计算、通信和存储开销都相对较低.新方案可应用于移动通信网络、物联网或泛在网络中,为资源约束型移动终端提供安全的漫游接入服务.
基于簇和阈值区间的高效关联规则隐藏算法
牛新征,王崇屹,叶志佳,佘堃
2017, 54(12):  2785-2796.  doi:10.7544/issn1000-1239.2017.20160612
摘要 ( 478 )   HTML ( 1)   PDF (4073KB) ( 317 )  
相关文章 | 计量指标
关联规则隐藏是隐私保护数据挖掘(privacy-preserving data mining, PPDM)的一种重要方法.针对当前的关联规则隐藏算法直接操作事务数据、I/O开销较大的缺陷,提出一种基于FP-tree快速关联规则隐藏的算法FP-DSRRC.算法首先对FP-tree的结构进行改进,增设事务编号索引并建立双向遍历结构,进而利用改进的FP-tree对事务信息进行快速处理,避免了遍历原始数据集产生的大量I/O时间;然后通过建立和维护事务索引表实现对敏感项的快速查找,并基于分簇策略对关联规则处理,以簇为单位进行敏感规则消除,同时采用规则支持度和置信度阈值区间的思想,减少了关联规则隐藏处理对原始数据集的影响;最后通过实验测试证明:相较于传统关联规则隐藏算法,FP-DSRRC算法在保证生成的数据集质量的同时,减少了50%~70%的算法执行时间,并在大规模真实数据集上有较好的可用性.
基于二叉树的非签名认证密钥协商协议
吴福生,张焕国
2017, 54(12):  2797-2804.  doi:10.7544/issn1000-1239.2017.20160791
摘要 ( 629 )   HTML ( 3)   PDF (1466KB) ( 360 )  
相关文章 | 计量指标
协议是网络通信的规范,密码协议是信息安全的关键技术之一,安全的密码协议常常依赖于签名或消息认证技术.签名或消息认证给密钥协商协议通信带来大量计算,不利于计算能力有限设备的网络通信.设计具有计算量小又实用的安全协议是信息安全研究目标之一.故以整数乘法同态映射和二叉树为基础,提出一种新的密钥协商协议,并在开源的OpenSSL环境下实现新协议模拟实验,给出二叉树叶子结点数变化对网络通信影响的模拟实验和实验结果分析.新协议在随机预言模型下可证明安全,即在公钥加密方案中新协议满足选择明文攻击不可区分性的(IND-CPA)安全.新协议与经典的密钥协商协议相比(例如MTI,MQV,HMQV),计算量小、强安全假设少、无需额外的签名与消息认证,且可以在非安全通信信道上进行安全通信.
差分隐私流数据自适应发布算法
吴英杰,张立群,康健,王一蕾
2017, 54(12):  2805-2817.  doi:10.7544/issn1000-1239.2017.20160555
摘要 ( 698 )   HTML ( 4)   PDF (5223KB) ( 402 )  
相关文章 | 计量指标
当前,许多实际应用需要持续地对流数据进行发布,现有关于单条流数据的差分隐私发布研究大多考虑区间的累和发布,而现实应用中往往需要对发布流数据进行任意区间计数查询,同时,用户查询往往存在特定规律,可针对历史查询进行自适应统计与分析,提高发布数据可用性.为此,提出一个基于历史查询的差分隐私流数据自适应发布算法HQ_DPSAP.算法HQ_DPSAP首先结合流数据的特性,利用滑动窗口机制动态构建窗口内流数据对应的差分隐私区间树,而后进一步分析与计算树节点的覆盖概率;接着自底向上计算隐私分配参数,再自顶向下分配隐私预算,并据此对树节点进行异方差加噪;最后根据历史查询规律自适应调整树节点的隐私预算与树结构参数,以实现流数据的自适应发布.实验对算法HQ_DPSAP的可行性及有效性进行比较分析,结果表明:算法HQ_DPSAP可有效支持任意区间计数查询,且具有较低的查询均方误差和较高的算法执行效率.
采用扩展公钥的云存储广播加密优化方法
李春花,王桦,张彦哲,周可
2017, 54(12):  2818-2824.  doi:10.7544/issn1000-1239.2017.20170902
摘要 ( 517 )   HTML ( 0)   PDF (1698KB) ( 292 )  
相关文章 | 计量指标
基于广播加密的云存储系统受到研究者的关注.然而,基本的广播加密方案不能适应云存储环境中用户和权限的动态变更情况.针对广播加密中密钥管理分发开销大的问题,提出一种扩展公钥的广播加密优化方法,通过保留初始产生公钥时使用的部分私有参数,当用户加入或撤离系统时,使用保留的私有参数产生新的公钥来加密数据.这样,合法用户仍可以使用之前已分发的私钥解密新公钥加密的数据,从而避免了用户动态变化时公钥的频繁变化和密钥的重复分发.通过引入懒惰回收机制,降低了权限变更和密钥定期更新带来的开销.测试结果表明:采用优化方案后,增加用户数量和权限撤销时,系统性能得到较大提高.
基于统计差分的轨迹隐私保护
朱维军,游庆光,杨卫东,周清雷
2017, 54(12):  2825-2832.  doi:10.7544/issn1000-1239.2017.20160647
摘要 ( 741 )   HTML ( 4)   PDF (1721KB) ( 481 )  
相关文章 | 计量指标
随着车联网不断地发展,车联网为驾乘者提供便捷服务的同时,也带来了相应的隐私保护问题.轨迹数据发布将可能泄露用户位置隐私,从而危害用户人身安全;为改变已有差分隐私保护方法中添加随机噪音的弊端,提出一种基于统计差分隐私的轨迹隐私保护方法.车辆行驶轨迹具有Markov过程的特点,根据车辆轨迹的特征计算轨迹中位置节点敏感度;并根据位置敏感度,统计阈值和敏感度阈值添加适量Laplace噪音;使用平均相对误差评价轨迹数据的可用性大小.实验证实了基于统计差分隐私的轨迹隐私保护方法的可用性和有效性.
基于流体系架构的分组密码处理器设计
李功丽,戴紫彬,徐进辉,王寿成,朱玉飞,冯晓
2017, 54(12):  2833-2842.  doi:10.7544/issn1000-1239.2017.20160670
摘要 ( 448 )   HTML ( 2)   PDF (2244KB) ( 237 )  
相关文章 | 计量指标
为提升密码处理器性能,构建了密码处理器性能模型.基于该模型,提出多级资源共享、绑定前/后异或操作、最大化算法并行度等处理器性能提升技术,并根据性能提升技术确定了功能单元的种类和数量.然而功能单元不仅数量较多,而且在操作位宽和操作延迟方面均有较大差异,如何有效组织这些功能单元成为了一个关键问题.利用流体系结构可以高效集成大量功能单元的特点,设计并实现了基于流体系结构的可重构分组密码处理器原型,并通过把功能单元划分为基本处理单元,bank间共享单元和簇间共享单元3个层次来解决功能单元处理位宽和操作延迟的差异.在65nm CMOS工艺下对处理器原型进行综合,并在该结构上映射了典型的分组密码算法.实验结果证明:该处理器以较小的面积获得了较高的性能,对典型分组密码算法的处理速度,不仅超越了国际上的密码专用指令处理器,而且高于国内可重构阵列结构密码处理器.
基础理论
随机图中k-独立集的相变性质
卢友军,许道云
2017, 54(12):  2843-2850.  doi:10.7544/issn1000-1239.2017.20160694
摘要 ( 553 )   HTML ( 0)   PDF (1700KB) ( 343 )  
相关文章 | 计量指标
相变性质是ER(Erds-Rényi)随机图理论具有的重要性质,一个简单无向图G=(V,E)中的k-独立集是一个具有k个顶点的独立集.为更好地理解ER随机图中k-独立集的结构特性,提出并利用一阶矩和二阶矩方法严格证明了当2≤k=ο(n)时随机图G(n,p)中k-独立集出现相变的临界概率p\-c=1-n\+-2/k-1.利用m≈pC\+2\-n时随机图G(n,p)和G(n,m)等价的性质给出了随机图G(n,m)中k-独立集出现相变的临界边数m\-c=[n(n-1)/2(1-n\+-2/k-1)].实验结果表明:当2≤k=ο(n)时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真得到的临界值一致且临界值与图节点总数n和独立集节点数k有关,而当k=ω(n)时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真临界值不一致.
基于启发策略的动态平衡图划分算法
李琪,钟将,李雪
2017, 54(12):  2851-2857.  doi:10.7544/issn1000-1239.2017.20160690
摘要 ( 703 )   HTML ( 5)   PDF (1511KB) ( 405 )  
相关文章 | 计量指标
随着计算技术的发展以及大数据时代的来临,分布式计算已成为研究的热点,其中大图迭代计算作为其研究的重点,降低划分后子图之间的通信边规模是改善计算性能的关键.传统算法很难在切割率最小化与负载均衡上同时满足.由于图划分属于NP组合优化问题,提出了一种动态平衡算法来解决图的平衡划分,确保在子图边界点划分最优的基础上引入扰动策略使其跳出局部最优扩大搜索空间,最后在真实世界图上验证算法的可行性,分别从平衡系数、切割边规模与传统算法进行了比较.在指定的扰动次数下,此算法比常见的算法hash,Chunk,Metis在割边率上分别降低了近40%,30%,5%.与Metis相比,平衡系数也更加地优化,实验结果证明了该算法的有效性.
软件技术
基于RDD关键度的Spark检查点管理策略
英昌甜,于炯,卞琛,王维庆,鲁亮,钱育蓉
2017, 54(12):  2858-2872.  doi:10.7544/issn1000-1239.2017.20160717
摘要 ( 688 )   HTML ( 1)   PDF (5567KB) ( 260 )  
相关文章 | 计量指标
Spark默认容错机制由程序员设置检查点,并利用弹性分布式数据集(resilient distributed dataset, RDD)的血统(lineage)进行计算.在应用程序复杂度高、迭代次数多以及数据量较大时,恢复过程需要耗费大量的计算开销.同时,在执行恢复任务时,仅考虑数据本地性选择节点,并未考虑节点的计算能力,这都会导致恢复时间增加,无法最大化发挥集群的性能.因此,在建立Spark执行模型、检查点模型和RDD关键度模型的基础上,提出一种基于关键度的检查点管理(criticality checkpoint management, CCM)策略,其中包括检查点设置算法、失效恢复算法和清理算法.其中检查点设置算法通过分析作业中RDD的属性以及对作业恢复时间的影响,选择关键度大的RDD作为检查点存储;恢复算法根据各节点的计算能力做出决策,选择合适的节点执行恢复任务;清理算法在磁盘空间不足时,清除关键度较低的检查点.实验结果表明:该策略在略增加执行时间的情况下,能够选择有备份价值的RDD作为检查点,在节点失效时能够有效地降低恢复开销,提高节点的磁盘有效利用率.