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

当期目录

2013年 第50卷 第11期    出版日期:2013-11-15
综述
正定矩阵支持向量机正则化路径算法
廖士中1 王 梅1,2 赵志辉1,3
2013, 50(11):  2253-2261. 
摘要 ( 777 )   HTML ( 2)   PDF (1518KB) ( 763 )  
相关文章 | 计量指标
正则化路径算法是数值求解支持向量机 (support vector machine, SVM)分类问题的有效方法,它可在相当于一次SVM求解的时间复杂度内得到所有的正则化参数及对应SVM的解.现有的SVM正则化路径算法或者不能处理具有重复数据、近似数据或线性相关数据,或者计算开销较大.针对这些问题,应用正定矩阵方程组求解方法来求解SVM正则化路径,提出正定矩阵SVM正则化路径算法(positive definite SVM path, PDSVMP).PDSVMP算法将迭代方程组的系数矩阵转换为正定矩阵,并采用Cholesky分解方法求解路径上各拐点处Lagrange乘子增量向量;与已有算法中直接求解正则化参数不同,该算法根据活动集变化情况确定参数增量,并在此基础上计算正则化参数,这样保证了理论正确性和数值稳定性,并可降低计算复杂性.实例数据集及标准数据集上的实验表明,PDSVMP算法可正确处理包含重复数据、近似数据或线性相关数据的数据集,并具有较高的计算效率.
论文
一种基于教学模型的协同训练方法
胡菊花 姜 远 周志华
2013, 50(11):  2262-2268. 
摘要 ( 688 )   HTML ( 0)   PDF (2620KB) ( 632 )  
相关文章 | 计量指标
在很多实际问题中,很容易得到大量未标记数据而较难获取数据的标记;所以半监督学习在过去的10多年中得到了很大的关注.基于不一致性的半监督学习是其中一种十分重要的风范,协同训练是其代表方法.至今为止,大部分协同训练方法在选择未标记示例进行标记时只考虑预测学习器的置信度,而忽视了学习器的需求.受到真实教学系统的启发,提出了一种针对协同训练的教学模型TaLe,其中预测学习器是“教”者,而另一方则为“学”者.进而基于该模型给出了一种新的协同训练方法CoSnT,同时考虑了“教”的置信度和“学”的需求度.实验结果表明CoSnT在收敛效率和泛化性能上都优于标准的协同训练算法.
一种自适应的大间隔近邻分类算法
杨 柳, 于 剑, 景丽萍,
2013, 50(11):  2269-2277. 
摘要 ( 642 )   HTML ( 1)   PDF (1447KB) ( 641 )  
相关文章 | 计量指标
kNN分类算法虽然已经广泛地应用于模式识别的各个领域,但是如何对kNN进行改进仍然是一个研究热点.在各种改进方法中,大间隔近邻分类方法取得了较好的改进效果,但是该算法仍然有一些缺点,例如算法对所有测试样本选择的邻域大小(即k值)都是一样的.针对这一缺点,提出了将自适应选择k值引入到目标函数设定中的自适应大间隔近邻分类算法(ALMNN).该算法的主要步骤是:首先为每个测试样本计算一个k值,然后在每一类选取k个目标近邻,计算属于每一类的损失函数值,选择拥有最小函数值的类作为测试样本的类别.给出了ALMNN方法的算法描述,并且通过多个数据集的实验表明,提出的算法与传统的kNN,LMNN比较,可以在一定程度上提高分类的性能,减少了k值的选择对分类性能的影响,训练集的随机抽取对算法的分类性能影响较小.
一种基于混合遗传和粒子群的智能优化算法
马 超 邓 超 熊 尧 吴 军
2013, 50(11):  2278-2286. 
摘要 ( 704 )   HTML ( 3)   PDF (2058KB) ( 937 )  
相关文章 | 计量指标
粒子群算法(particle swarm optimization, PSO)原理简单、搜索速度快,但前期容易“早熟”.遗传算法(genetic algorithm, GA)具有很强的全局搜索能力,但收敛精度不高.综合考虑二者优缺点,把遗传算子引入PSO算法中,并采用交叉搜索的方法,调整惯性权重以及变异方式使粒子得到进化,当粒子种群进化到一定层度后,对部分粒子进行变异处理,这样不仅避免算法陷入局部最优解,而且获得较高收敛精度和执行能力,可解决工程中非线性、多极值的问题.据测试函数以及与其他寻优算法的对比分析表明,此混合策略在求解精度、搜索效率和处理不同复杂度问题等方面都有很好的优越性,具有满足工程需要的能力.
独立子空间中的场景特征增量学习方法
谢 昭 凌 然 吴克伟
2013, 50(11):  2287-2294. 
摘要 ( 742 )   HTML ( 0)   PDF (3021KB) ( 617 )  
相关文章 | 计量指标
针对特征提取与场景描述在场景分类任务中的重要性,提出了一种独立子空间内的场景特征增量学习方法,采用基于独立子空间分析的无监督学习方法获取结构化的特征基元,基元的优化过程融入增量学习的思想框架中,以解决大样本以及动态样本下的学习难题.通过特征基元的非线性映射获取一种规则网格划分下的图像块状描述子,最后结合空间金字塔匹配模型构建层次化的场景描述,有效提高了场景图像分类的精确度.在OT场景图像集上的实验结果表明,所得特征基元能够用于构建低维高效的场景描述,通过详细讨论相关参数对优化过程以及分类性能的影响,并与多种典型模型下的实验结果进行对比,充分验证了该方法在场景分类任务中的有效性.
一种求解截断Hinge损失的软阈值坐标下降算法
朱烨雷 王玉军 罗 强 陶 卿
2013, 50(11):  2295-2303. 
摘要 ( 1180 )   HTML ( 3)  
相关文章 | 计量指标
有效地减少支持向量数目能够提高分类器的鲁棒性和精确性,缩短支持向量机(support vector machine, SVM)的训练和测试时间.在众多稀疏算法中,截断Hinge损失方法可以显著降低支持向量的数目,但却导致了非凸优化问题.一些研究者使用CCCP(concave-convex procedure)方法将非凸问题转化为多阶段凸问题求解,不仅增加了额外计算量,而且只能得到局部最优解.为了弥补上述不足,提出了一种基于CCCP的软阈值坐标下降算法.用坐标下降方法求解CCCP子阶段凸问题,提高计算效率;对偶SVM中引入软阈值投影技巧,能够减少更多的支持向量数目,同时选择合适的正则化参数可消除局部最优解的不良影响,提高分类器的分类精度.仿真数据库、UCI数据库和大规模真实数据库的实验证实了所提算法正确性和有效性.
一种阴影区域的可通行性检测方法
高 华 赵春霞 张浩峰
2013, 50(11):  2304-2314. 
摘要 ( 714 )   HTML ( 1)   PDF (4246KB) ( 578 )  
相关文章 | 计量指标
可通行性检测是自主机器人视觉导航的基本方法之一.在乡村道路和城市环境中经常存在阴影,对基于可视化特征分类的可通行性检测影响很大,目前很少有针对阴影区域的可通行性检测的研究.提出一种阴影区域的可通行性检测方法,利用超像素技术把场景图像分割成同质、同光照条件的超像素,提出一种特征窗口定位方法寻找尽量包含同光照条件的特征提取窗口,运用局部二值模式(local binary pattern, LBP)提取方法对特征窗口内的像素进行描述,使用单类支持向量机(One-Class SVM)进行训练和分类,实现可通行性检测.实验表明,新方法不仅能够准确地对阴影区域内部的地形进行可通行性检测,而且可以实现对阴影区域和无阴影区域交汇部分的准确检测,在小面积阴影区域与小面积无阴影区域相互交错、交替出现的恶劣条件下仍能准确检测地形的可通行性,降低了可通行性检测在阴影边界的不连通性.
基于粒度偏移因子的支持向量机学习方法
郭虎升, 王文剑,
2013, 50(11):  2315-2324. 
摘要 ( 615 )   HTML ( 3)   PDF (2910KB) ( 501 )  
相关文章 | 计量指标
在实际应用中,数据集样本规模、分布密度的不平衡性可能会使传统支持向量机(support vector machine, SVM)得到的分类超平面不是最优.在对传统支持向量机最优分类面分析的基础上,结合粒度计算(granular computing, GrC)理论,针对数据规模和分布密度不平衡的数据集,提出一种基于粒度偏移因子的粒度支持向量机(granular SVM, GSVM)学习方法,称为S_GSVM方法.该方法将原始样本用Mercer核映射到高维空间,然后在高维空间中对数据进行有效的粒划分,通过对不同的粒计算不同的超平面偏移因子,重新构造支持向量机的凸二次优化问题,以得到一个泛化能力更好的分类超平面.S_GSVM方法充分考虑了数据复杂分布对于泛化能力的影响,对基于最大间隔的分类面进行改进.实验结果表明,S_GSVM方法在非平衡数据集上能得到较好的泛化性能.
多车辆合乘问题的两阶段聚类启发式优化算法
邵增珍, 王洪国, 刘 弘, 宋超超, 孟春华, 于洪玲,
2013, 50(11):  2325-2335. 
摘要 ( 611 )   HTML ( 0)   PDF (1563KB) ( 636 )  
相关文章 | 计量指标
车辆合乘问题研究在物流领域和交通领域意义重大.良好的合成策略不仅可以节省物流成本,降低交通拥塞,在减少噪声及提高环境等方面也是很有利的.针对确定性多车辆合乘匹配问题,提出了两阶段聚类的启发式匹配策略:第1阶段聚类过程提出匹配度的概念,用于指导将服务需求分配到某一具体车辆,从而将多车辆问题转化为单车辆问题;第2阶段聚类过程基于“先验聚类”插入思想,可降低单车辆匹配过程的插入试探次数,从而提高算法效率.为提高搭乘成功率并降低运营总成本,通过迁移对第1阶段聚类过程进行调整.实际算例结果表明,算法在可接受时间范围内不仅可提高搭乘成功率,还明显降低车辆的运行成本,表现出较强的实用性.
微博中基于统计特征与双向投票的垃圾用户发现
丁兆云, 周 斌, 贾 焰, 汪 祥,
2013, 50(11):  2336-2348. 
摘要 ( 660 )   HTML ( 3)   PDF (2362KB) ( 607 )  
相关文章 | 计量指标
传统微博中垃圾用户发现主要依靠用户的显示统计特征.针对微博中关注网络的有向特性,给出了有向网络中局部三角形数量统计算法DirTriangleC,结合用户博文数量和局部三角形比例发现隐式垃圾用户;针对统计特征方法对垃圾用户误报和漏报的缺点,提出了基于统计特征与双向投票算法AttriBiVote,利用用户信任的双向传播与其邻居节点的统计特征共同决定用户类别.真实的Twitter数据集上验证了DirTriangleC和AttriBiVote算法的有效性,结果表明DirTriangleC算法能够发现约837%的“完全非活跃”状态的隐式垃圾用户,相对依靠显示统计特征方法增加了约2倍数量的疑似垃圾用户;同时AttriBiVote算法发现垃圾用户的数量和准确性均高于依靠统计特征的垃圾用户发现方法;最后实验分析了AttriBiVote算法的时间开销.
一种结合特征选择和链接过滤的主动协作分类方法
李丽娜, 欧阳继红, 刘大有, 高文杰,
2013, 50(11):  2349-2357. 
摘要 ( 664 )   HTML ( 6)   PDF (1526KB) ( 619 )  
相关文章 | 计量指标
分类是网络数据挖掘中的重要研究课题之一.协作分类利用网络节点之间的依赖关系对相互链接的节点集合进行组合分类,其精度高于传统的分类方法,受到广泛关注,并被应用于文档分类、蛋白质结构预测、图像处理和社会网络分析等众多领域.提出一种结合特征选择和链接过滤的主动协作分类方法,算法首先基于最小冗余-最大相关方法选择重要的属性,并建立隐式链接;之后过滤初始链接得到显式链接,最后集成隐式和显式链接形成新的网络结构,再应用协作分类方法实现分类.在3个公共数据集上将该方法分别与典型的传统分类方法、协作分类方法进行对比,结果表明该方法能获得较高的分类精度,对稀疏标记的网络其优势更加明显.
RFID距离约束协议的分析与设计
辛 伟, 孙惠平, 陈 钟,
2013, 50(11):  2358-2366. 
摘要 ( 647 )   HTML ( 0)   PDF (1252KB) ( 523 )  
相关文章 | 计量指标
中继攻击给无线射频识别(RFID)安全带来了巨大威胁,攻击者通过原封不动地转发RFID读写器和标签的通信消息的方式,增加了读写器和标签通信的距离,破坏了RFID默认为短距离通信的隐含假设.而抵御中继攻击的主要方法是采用基于测量读写器与标签之间通信时间的距离约束协议,Hancke和Kuhn在2005年提出了第1个RFID距离约束协议HK,自此以后,陆续有新的距离约束协议问世.目的就是设计一个距离约束协议来抵御中继攻击,同时该协议适合于RFID标签计算资源有限的特点.首先回顾了已有的各种距离约束协议,分析了这些协议的优点和缺陷,并提出了针对距离约束协议的攻击模型,最后,基于HK协议,提出了一个新的距离约束协议HKM,该协议采用预定义质询和随机质询相结合的方式,并充分利用了HK协议浪费的内存,通过与现有的几个典型的距离约束协议进行对比,该协议在内存消耗和抵御中继攻击两个方面有较好的表现.
Flume系统的隐蔽信道搜索问题研究
曹 珲, 熊胜超, 张焕国, 严 飞,
2013, 50(11):  2367-2374. 
摘要 ( 451 )   HTML ( 0)   PDF (1108KB) ( 457 )  
相关文章 | 计量指标
Flume系统不仅可以为处于不同安全级别的进程传输信息提供安全保障,还可以通过显式标签机制解决在隐式标签系统中进程间通信连接超时导致的隐蔽信道问题.但是其系统中的部分不合理标签分配机制可能会导致信息在传递过程中同样存在泄露问题.针对这个问题提出一种隐蔽信道搜索模型(covert channel detection model, CCDM),将隐蔽信道的搜索问题抽象为有向图联通问题.最后结合回溯算法的思想提出IniaPathSearch算法和QuickPathSearch算法来对隐蔽信道进行自动搜索.实验结果表明,IniaPathSearch算法和QuickPathSearch算法可以正确有效地对Flume系统中隐蔽信道进行检测,并能为信息传递提供合法最短路径,其结果可以用于指导提高系统的安全性.
一种基于半监督GHSOM的入侵检测方法
阳时来 杨雅辉 沈晴霓 黄海珍
2013, 50(11):  2375-2382. 
摘要 ( 953 )   HTML ( 0)   PDF (867KB) ( 679 )  
相关文章 | 计量指标
基于神经网络的入侵检测方法是入侵检测技术的一个重要发展方向.在已有无监督生长型分层自组织映射(growing hierarchical self-organizing maps, GHSOM)神经网络算法的基础上,提出了一种半监督GHSOM算法.该算法利用少量有标签的数据指导大规模无标签数据的聚类过程.一方面借鉴cop-kmeans半监督机制,解决了原始算法中返回空划分的问题,并将其应用到GHSOM算法中.另一方面提出了神经元信息熵的概念作为子网生长的判断条件,提高了GHSOM网络子网划分的精度.此外还利用有标签的数据自动确定聚类结果的入侵类型.对KDD Cup 1999数据集和LAN环境下模拟产生的数据集进行的入侵检测实验表明:相比于无监督的GHSOM算法,半监督的GHSOM算法对各种类型的攻击具有较高的检测率.
一种超椭圆曲线密码处理器并行结构设计
方跃坚, 沈晴霓, 吴中海,
2013, 50(11):  2383-2388. 
摘要 ( 563 )   HTML ( 2)   PDF (1283KB) ( 601 )  
相关文章 | 计量指标
提出了一种超椭圆曲线密码处理器并行结构设计.处理器由多个具有相同结构的核组成,每个核由一个控制器、一个寄存器文件、一个运算单元组成.多个独立的核之间通过寄存器共享进行通信来协作完成复杂运算.每个运算单元执行自定义多操作数指令A(B+C)+D,并在指令产生过程和执行时对指令进行灵活配置.该设计可以实现核之间的指令级并行处理和不同指令执行阶段的流水线处理.在FPGA上的实验结果表明,与以往研究相比,该设计可以实现对超椭圆曲线密码点乘运算更高的加速.
一种高容量的分散式FPGA芯核水印算法
徐建波 龙 静 彭 理
2013, 50(11):  2389-2396. 
摘要 ( 447 )   HTML ( 2)   PDF (2150KB) ( 502 )  
相关文章 | 计量指标
为了提高芯核水印的嵌入容量和水印的安全性能,通过分析现有的基于FPGA的芯核水印技术,提出一种高容量的分散式FPGA芯核水印算法.算法设计首先采用一种水印预处理压缩机制,该机制主要是将加密后的版权信息构造成特定的线性组合表达式加以实现;其次,生成的线性组合表达式转换成水印嵌入时的位置信息和待嵌入的位信息,然后通过附加约束的方法将分散隐藏的位信息嵌入到FPGA的电路设计结构当中;最后,通过实验测试和性能分析,该算法不仅能以较少的实际嵌入量来标识更多的水印版权信息,而且大大降低了水印嵌入所带来的性能影响.此外,通过与现有的FPGA水印算法的实验比较,结果表明,提出的算法相对于其他的方法而言,具有水印容量大、资源开销小以及安全性能较高等优点.
基于检查点分级属性的软件动态可信评测模型
李 珍 田俊峰 杨晓晖
2013, 50(11):  2397-2405. 
摘要 ( 541 )   HTML ( 0)   PDF (1524KB) ( 465 )  
相关文章 | 计量指标
目前的可信计算机只能保证系统资源的静态安全,而系统开始运行后,终端计算机的可信性主要取决于在其上运行的软件行为的可信性.针对软件运行过程中的动态可信性,在传统软件行为模型的基础上引入了基于区间数据的检查点场景级属性,提出了基于检查点分级属性的软件动态可信评测模型.该模型基于预期行为轨迹进行软件行为的可信评测;采用检查点属性分级策略,对基于阈值的检查点可信评价进行简化,并将检查点属性主观分级赋权与场景级客观赋权相结合;通过建立场景级属性可信模型进行基于区间数据的场景级属性可信评测.理论分析表明基于分级属性的决策方法减少了与阈值的比较次数,实验结果验证了基于区间数据的场景级属性可信评测的有效性以及较高的攻击检测能力.
一种面向Xen虚拟计算环境的运行时内存泄漏检测方法
肖如良 姜 军 胡 耀 韩 佳 倪友聪 杜 欣 蔡声镇
2013, 50(11):  2406-2417. 
摘要 ( 526 )   HTML ( 0)   PDF (3108KB) ( 556 )  
相关文章 | 计量指标
虚拟计算环境中系统性能的稳定性问题研究对于云计算相关技术的研究和应用具有重要的理论和实际意义.长时间不停机系统的内存泄漏可能给实际应用带来严重后果,在虚拟计算环境中检测运行时内存泄漏是一个极具挑战性的问题.针对该问题,对内存泄漏的现象进行了分类.基于Xen虚拟机构建并实现了一种面向Xen虚拟计算环境的虚拟化内存泄漏检测(virtualization memory leak detection, VMLD)的方法,提出了相应的检测规则.通过修改虚拟机管理器,设计超级调用,实现了内部缓冲区维护、控制、拦截、监视等模块.实验结果表明,VMLD方法能有效地检测出运行时内存泄漏,并且具有较好的性能.
一种重构二进制代码中类型抽象的方法
马金鑫, 李舟军, 忽朝俭, 张俊贤, 郭 涛,
2013, 50(11):  2418-2428. 
摘要 ( 645 )   HTML ( 3)   PDF (1604KB) ( 638 )  
相关文章 | 计量指标
重构二进制代码中的类型信息对逆向工程、漏洞分析及恶意代码检测等方面具有重大的意义,由于类型信息在编译过程中被移除,且二进制代码中的低级抽象难以理解,因此类型重构一直被认为是恢复高级抽象遇到的困难问题之一,现有的大多工具对类型重构的准确度不够高.提出一种保守的类型重构方法,针对类型重构引入一种简单的中间语言,基于这种中间语言构造寄存器抽象语法树,并使用寄存器抽象语法树部分解决了基址指针别名问题,可有效收集基本类型和结构体类型的类型约束信息.提出一种判断二进制代码中的循环结构及识别循环变量的方法,可有效收集数组类型的约束信息,并据此生成类型约束,然后通过处理类型约束来重构最终的类型.使用CoreUtils中的15个程序作为测试用例,将该方法与IDA Pro进行对比实验.实验结果表明提出的方法不仅可以高效地重构数据类型,而且在结构体类型重构方面可恢复比IDA Pro多达5倍的数据.对这些数据的人工验证与分析表明,使用该方法重构的类型准确率高.
Xen虚拟CPU空闲调度算法
王 凯, 侯紫峰,
2013, 50(11):  2429-2435. 
摘要 ( 874 )   HTML ( 1)   PDF (1532KB) ( 511 )  
相关文章 | 计量指标
在Xen虚拟化环境下,Credit调度算法是非抢占式调度算法,当虚拟CPU空时它不会将空闲状态信息通知给Xen,因此不会放弃物理CPU的使用权.虽然已有文献提出在虚拟CPU空闲时的处理方法,但它依然存在很多问题,例如空闲虚拟CPU的空闲时间还存在浪费的现象、没有考虑特权Service OS的空闲状态和虚拟机空闲状态判断不准确等,这造成很多不必要的性能损失.针对这样的问题,在Credit算法的基础上提出了虚拟CPU空闲调度算法,虚拟CPU空闲状态接收模块接收到的虚拟CPU空闲通知,动态调整该虚拟机的虚拟CPU的credit值,并将空闲的CPU时间分配给调度队列中其他的虚拟CPU使用.同时,根据该虚拟机的虚拟CPU的平均空闲率,重新调整该虚拟机的权重,从而实现了反馈控制与虚拟机调度的动态集成,实验结果证明该调度方法使系统的整体性能得到大大提高.
小计算量下非规则数据密集型热函数的性能优化
郑宁汉, 古志民, 孙贤和,
2013, 50(11):  2436-2443. 
摘要 ( 566 )   HTML ( 0)   PDF (1334KB) ( 499 )  
相关文章 | 计量指标
随着云计算的兴起和发展,基于多核的非规则数据密集型应用越来越多,而大量的数据缺失问题导致这类应用的性能严重下降.利用空闲核资源的传统帮助线程方法试图提前将主线程所需要的非规则数据放入共享的最后一级缓存(last layer cache,LLC),如果帮助线程相对于主线程具有恰当的运算速度,能在主线程访问之前将有关缺失数据放入LLC中,则热函数的性能可被改进.然而,如果热函数缺乏计算任务(称之为小计算量热函数),使用这样的传统方法就无法构建一个相对于主线程有效预取的帮助线程,其热函数性能的改善将会大大降低.针对源代码级小计算量下非规则数据密集型热函数的性能优化问题,先对帮助线程预取QoS进行了形式化描述.在此基础上,通过引入提前量等参数模型,提出了一种小计算量下热函数的性能优化方法.在Intel Core 2 Duo Processor 6550处理器上,通过对科学计算测试程序em3d,mst和SPEC CPU benchmark 2006中的mcf的进行实验,相对于传统方法分别获得了1.97%,31.63%和1.10%的性能提升.
两种基于双向比较的最长公共子串算法
王开云, 孔思淇, 付云生, 潘泽友, 马卫东, 赵 强,
2013, 50(11):  2444-2454. 
摘要 ( 550 )   HTML ( 0)   PDF (2483KB) ( 468 )  
相关文章 | 计量指标
查找两个给定字符串的最长公共子串(LCSstr)是一类重要字符串分析问题,在字符串近似匹配、计算机病毒特征码对比等方面有着广泛的用途.最长公共子串算法目前主要包括动态规划算法(LCSstrDP)和后缀数组算法(LCSstrSA),分别用于短串和长串的最长公共子串计算.前者代码简洁,但计算速度较慢,后者速度很快但算法非常复杂.提出两种基于双向比较的最长公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最长公共子串长度,与LCSstrDP相比,代码同样简洁,平均计算效率提高近一个数量级,并且不需要额外的存储空间.LCSstrSCeL是在LCSstrSeL的基础上,增加字符跨越、连续同值区间跨越等机制,平均效率较LCSstrSeL亦有一定程度的提高,内存开销与LCSstrDP相近,在中小长度的字符串LCSstr计算中,平均计算效率高于LCSstrSA,某些情况下的计算效率可达到亚线性的速度.
空间数据库中的组障碍最近邻查询研究
杨泽雪, 郝忠孝,
2013, 50(11):  2455-2462. 
摘要 ( 647 )   HTML ( 0)   PDF (1691KB) ( 502 )  
相关文章 | 计量指标
已有的关于组最近邻查询的研究都是基于欧氏距离的,无法解决存在障碍情况下基于障碍距离的组最近邻查询问题.为此,提出障碍物环境中组最近邻查询的一种新的变体,即组障碍最近邻(group obstacle nearest neighbor, GONN)查询.GONN返回数据集中与查询点集中所有点的障碍距离之和最小的点.根据数据集中的点与查询点集的最小外包距离(minimum bounding rectangle, MBR)之间的不同位置关系,构造各种情况下查询点集的MBR相对于数据集中点的剪枝区域.利用剪枝区域剪去障碍集中对障碍距离计算无影响的障碍,给出数据集中点与查询点集之间障碍距离的计算算法.定义组障碍最近邻查询的剪枝规则,根据障碍距离计算给出组障碍最近邻查询的算法.并给出相关定理和证明.实验结果证明算法具有较高效率.
基于Hash索引的高通量基因序列比对并行加速技术研究
王文迪, 汤 文, 段 勃, 张春明, 张佩珩, 孙凝晖,
2013, 50(11):  2463-2471. 
摘要 ( 833 )   HTML ( 2)   PDF (2661KB) ( 777 )  
相关文章 | 计量指标
近年来随着高通量基因测序技术的迅速发展,测序成本和周期都得到了大幅降低.然而,新一代测序技术海量数据生成能力以及各类测序算法蕴含的高并发性却对现有计算机的运算能力提出了新挑战.以一个基于Hash索引算法实现的开源重测序程序(PerM)为例,研究了在商用多核CPU上加速该应用程序的关键技术.在一个64核SMP系统上的实验结果证明,提出的优化技术可以使Cache缺失率降低90%,性能提升4~11倍.接下来探讨了在一个包含Xilinx LX330 FPGA的加速卡上设计实现专用并行加速系统的相关问题.作为原型验证系统,在基于FPGA的PCIe加速卡上设计并实现了包含11个处理单元的脉动陈列并行计算系统.和Intel Xeon X7550 8核CPU相比,提出的并行加速器有30~65倍性能功耗比优势.
液体采集与建模技术综述
邹 玲 齐 越 赵沁平
2013, 50(11):  2472-2480. 
摘要 ( 555 )   HTML ( 1)   PDF (2846KB) ( 492 )  
相关文章 | 计量指标
在计算机图形学与虚拟现实技术领域中,自然现象的模拟作为一个难点得到了广泛的关注和研究.液体是一种最为常见的自然现象,对此类现象的建模具有极大的应用价值.传统的液体建模方法是基于物理的建模方法,但计算量较大.随着相机等采集设备的发展,出现了基于采集数据的液体建模方法.回顾了近年来国内外在液体采集和建模仿真方面的发展情况和研究进展;分析并总结了针对不同研究对象所采用的建模方法;最后提出液体采集与建模技术研究中存在的挑战及未来发展趋势.