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

当期目录

2014年 第51卷 第1期    出版日期:2014-01-15
人工智能
玻尔兹曼机研究进展
刘建伟 刘 媛 罗雄麟
2014, 51(1):  1-16. 
摘要 ( 2107 )   HTML ( 5)   PDF (2999KB) ( 2140 )  
相关文章 | 计量指标
深度学习是机器学习中的新兴研究领域,能够很好地用于解决目标识别、语言理解等复杂问题.玻尔兹曼机作为深度学习的典型代表近年来受到了广泛研究.鉴于玻尔兹曼机的理论意义和实际应用价值,系统综述了玻尔兹曼机的研究进展,首先概述了玻尔兹曼机的相关概念,包括单层反馈网络的结构和拓扑结构分类,然后详细描述了玻尔兹曼机的学习过程和几种典型学习算法,接着对近几年玻尔兹曼机研究的新进展进行了阐述,最后提出了玻尔兹曼机中有待进一步研究解决的问题.
软件技术
面向并发性能下降的调度策略的综述
吕 方, 崔慧敏, 霍 玮, 冯晓兵,
2014, 51(1):  17-30. 
摘要 ( 554 )   HTML ( 2)   PDF (1913KB) ( 591 )  
相关文章 | 计量指标
随着行业应用的飞速扩张,数据中心以及云等日益成为主流服务平台.高性能的片上多核系统也随之成为重要的可分配资源之一.然而,在对多用户提供服务(并发执行、并置执行)时,其所固有的共享资源会引发严重的并发性能下降.在此背景下,多核系统的性能以及资源利用率问题成为研究热点.软件调度策略作为一种性价比较高的调节手段对于缓解资源冲突一直行之有效,然而,硬件技术的变迁对其调节的效力将产生一定影响.首先从片上多核结构关键技术入手,对共享资源的变化进行了详细阐述,在此基础上,对当前主流应用领域中两种不同类型的软件调度策略进行介绍和分析.在总结现有策略的局限性以及面临的新挑战的同时,对未来的研究趋势作了展望.
图形图像
基于物理仿真的布料动画研究综述
梁秀霞, 韩慧健, 张彩明,
2014, 51(1):  31-40. 
摘要 ( 619 )   HTML ( 3)   PDF (1390KB) ( 1135 )  
相关文章 | 计量指标
随着计算机图形技术的发展,布料动画成为3D游戏和动画电影相关领域研究者共同关心和研究的课题,并呈现蓬勃发展的趋势.布料动画的主要目标是表现布料丰富的运动细节,获得细腻、逼真的动画效果,可广泛应用于游戏、动画和虚拟现实等众多领域.论述了国内外基于物理仿真的布料动画建模的研究现状,总结了基于物理仿真的布料动画基本理论和方法.通过对近年来该领域相关文献的分析和归纳,发现其中存在的优缺点和相互间的联系,力图为3D游戏和动画中布料动画仿真技术的研究提供系统的思路.
软件技术
PAA:海量数据上一种有效的近似聚集查询算法
韩希先 李建中 高 宏
2014, 51(1):  41-53. 
摘要 ( 1025 )   HTML ( 1)   PDF (3632KB) ( 556 )  
相关文章 | 计量指标
聚集查询是一种常用但是耗时的数据库操作.相对于准确查询,以少得多的响应时间向用户返回满足置信区间的近似结果通常是一种更好的选择.现有的近似查询方法无法在海量数据上高效地处理满足任意精度的近似聚集查询.提出一种新的算法PAA(partition-based approximate aggregation)来有效处理满足任意置信区间的近似聚集.维属性的数据空间被划分为同样大小的空间区域,每个分片维护着维属性落入对应空间区域的元组.PAA算法维护表的随机样本RS,其执行包括两个阶段.在阶段1,如果利用预构建的随机样本RS不能返回满足用户要求的近似结果,那么在阶段2,PAA算法从与查询区域相交的空间区域对应的分片集合IPS中获得更多的随机元组.PAA算法的特色在于:1)如何在不知道IPS包含的每个分片满足谓词的元组数量情况下,从IPS中获得需要的随机元组;2)如何有效减少阶段2中的随机I/O费用.实验表明,相对于现有方法,PAA算法可以获得两个数量级的加速比.
一种大规模图数据上已知项搜索的优化方法
钟 鸣 王 盛 刘梦赤
2014, 51(1):  54-63. 
摘要 ( 452 )   HTML ( 0)   PDF (2795KB) ( 419 )  
相关文章 | 计量指标
近年来,在社交网络、生物信息、软件工程、知识工程等领域,以图为天然组织结构的数据开始大量涌现,从而使得图数据的查询、搜索、挖掘等问题迅速成为研究热点.然而,由于图的计算复杂度高,现有的图数据关键词搜索方法的可伸缩性差,难以应用于大规模图数据.创新性地从对用户搜索意图的探索出发,探讨了可能存在的不同类型的图搜索及其优化潜力,提出了根据不同类型搜索的特点采用专门的优化策略的思想;并针对其中非常重要和常见的“已知项搜索”提出了一种启发式优化方法,利用图中局部拓扑信息构建索引,并使用MapReduce技术处理大规模图数据,实现在搜索前裁剪匹配顶点,以少量可能存在的top-k答案丢失为代价来显著缩减搜索空间.实验证明该方法能够极大地减少已知项搜索的响应时间.
基于键规则的XML实体抽取方法
刘显敏 李建中
2014, 51(1):  64-75. 
摘要 ( 544 )   HTML ( 0)   PDF (5040KB) ( 453 )  
相关文章 | 计量指标
XML上实体抽取问题的任务是要从XML数据中抽取出描述现实世界某个物理实体的数据实体.利用XML查询提供实体的表示方法,基于键规则中有关实体的语义信息,给出了求解XML上实体抽取问题的基于键规则的实体抽取(key-based entity extraction, KEE)方法.KEE方法利用查询松弛技术,自动地生成抽取实体的候选查询集合,基于相似性测度,从候选查询中选取适用于抽取实体的查询集合.作为KEE方法的一个具体实现,SharingEE算法利用标准化的查询松弛技术,减少了候选查询中的冗余,利用基于自动机的查询处理技术,在多个候选查询之间共享中间结果,从而减少计算开销.在真实和模拟数据上运行的实验验证了算法的效率和有效性.实验结果表明,KEE方法可以很好地解决实体抽取问题,并可以扩展到大规模数据上.
一种基于区域划分的数据流子空间聚类方法
于 翔, 印桂生, 许宪东, 王建伟,
2014, 51(1):  88-95. 
摘要 ( 585 )   HTML ( 1)   PDF (2367KB) ( 519 )  
相关文章 | 计量指标
数据流子空间聚类的主要目的是在合理的时间段内准确找到数据流特征子空间中的聚类.现有的数据流子空间聚类算法受参数影响较大,通常要求预先给出聚类数目或特征子空间,且聚类结果不能及时反映数据流的变化情况.针对以上缺陷,提出一种新的数据流子空间聚类算法SC-RP,SC-RP无需预先给出聚类数目或特征子空间,对孤立点不敏感,可实现快速聚类,通过区域树结构记录数据流的变化并及时更新统计信息,进而根据数据流的变化调整聚类结果.通过在真实数据集与仿真数据集上的实验,证明了SC-RP在聚类精度和速度上优于现有的数据流子空间聚类算法,且对聚类数目及数据维度均具有良好的伸缩性.
概念格的内涵缩减与数据库推理依赖
薛金蓉, 安秋生, 郑 军,
2014, 51(1):  96-103. 
摘要 ( 449 )   HTML ( 0)   PDF (1127KB) ( 501 )  
相关文章 | 计量指标
值依赖是数据库推理问题研究的一个新课题.首先介绍了形式背景和概念格,提出了值依赖的形式概念模型.将数据属性的安全敏感级别引入到值依赖研究中,提出推理依赖及α极大推理依赖概念,并建立了形式概念格的内涵缩减与数据库推理依赖之间的关系.进一步证明了由概念格的内涵缩减推导出数据库中完备的、无冗余的α极大推理依赖集.最后提出并实例验证了发现数据库中全部推理依赖集的算法.推理依赖是关系数据库中最重要的属性依赖关系之一,其研究对检测和消除数据库推理通道具有十分重要的意义.
差分隐私保护下一种精确挖掘top-k频繁模式方法
张啸剑, 王 淼, 孟小峰,
2014, 51(1):  104-114. 
摘要 ( 1043 )   HTML ( 3)   PDF (2268KB) ( 958 )  
相关文章 | 计量指标
频繁模式挖掘是分析事务数据集常用技术.然而,当事务数据集含有敏感数据时(如用户行为记录、电子病例等),直接发布频繁模式及其支持度计数会给个人隐私带来相当大的风险.对此提出了一种满足ε-差分隐私的top-k频繁模式挖掘算法DP-topkP(differentially private top-k pattern mining).该算法利用指数机制从候选频繁模式集合中挑选出top-k个携带真实支持度计数的模式;采用拉普拉斯机制产生的噪音扰动所选模式的真实支持度计数;为了增强输出模式的可用性,采用后置处理技术对top-k个模式的噪音支持度计数进行求精处理.从理论角度证明了该算法满足ε-差分隐私,并符合(λ,δ)-useful要求.实验结果证明了DP-topkP算法具有较好的准确性、可用性和可扩展性.
障碍空间中保持位置隐私的最近邻查询方法
朱怀杰 王佳英 王 斌 杨晓春
2014, 51(1):  115-125. 
摘要 ( 433 )   HTML ( 0)   PDF (3051KB) ( 480 )  
相关文章 | 计量指标
基于位置服务的隐私保护是近年来空间数据库领域研究的热点.然而,现有的位置隐私保护方法只支持简单的最近邻查询,没有考虑障碍物的空间.但是障碍物的空间在实际中是普遍存在的,因此,研究障碍空间中保持位置隐私的最近邻查询问题是有意义的,也是一个难点.针对这个问题,提出了一种基于第三方可靠服务器的方法.该方法能够保证用户在享受基于位置服务所提供的实际准确答案的同时,其位置信息不被泄露.该方法首先针对用户查询的准确位置,利用第三方可靠服务器来构造一个匿名的区域并发送给位置服务器,进行匿名区域的查询处理.在查询处理过程中,提供了两种查询处理方法:1)基于线段的最大障碍距离的查询处理方法(基本方法),即利用线段的最大障碍距离来扩展匿名区域,返回扩展后的区域内的结果;2)优化查询处理方法,即在基本方法的基础上,进行迭代优化,进一步缩小扩展区域.然后把匿名区域的查询处理的结果返回给第三可信方.最后,第三方可靠服务器根据用户的准确位置,把实际准确结果返回给用户.实验结果和理论表明了这两种查询处理方法的有效性和正确性.
基于敏感属性值语义桶分组的t-closeness隐私模型
张健沛 谢 静 杨 静 张 冰
2014, 51(1):  126-137. 
摘要 ( 1163 )   HTML ( 1)   PDF (2740KB) ( 509 )  
相关文章 | 计量指标
t-closeness模型是数据发布领域中用于抵御相似性攻击和偏斜攻击的一种有效方法,但其采用的EMD(earth mover's distance)距离没有考虑等价类与数据表间敏感属性分布的稳定性,不能全面地衡量分布间距离,在分布间稳定差异过大时会大大提高隐私泄露的风险.针对这种局限,提出了一种SABuk t-closeness模型,它在传统t-closeness模型的基础上,为更加准确地度量分布间距离,以EMD距离与KL散度(kullback-leibler divergence)结合构建距离度量标准.同时,根据敏感属性的层次树结构,对数据表进行语义相似性桶分组划分,然后采用贪心思想生成满足要求的最小等价类,并且运用k-近邻的思想来选取QI(quasi-identifiers)值相似的元组生成等价类.实验结果表明,SABuk t-closeness模型在牺牲少量时间的前提下减少了信息损失,能在有效地保护敏感信息不泄露的同时保持较高的数据效用.
网络技术
无线网络的差异化比特错误率估计方法
张招亮, 陈海明, 黄庭培, 崔 莉,
2014, 51(1):  138-150. 
摘要 ( 614 )   HTML ( 0)   PDF (2947KB) ( 460 )  
相关文章 | 计量指标
在无线网络中,比特错误率(bit error rate, BER)的估计是许多上层协议的基础,对数据传输的性能具有重要的影响,目前已成为一个重要的研究课题.但是现有BER估计编码未考虑实际网络的BER分布特征,估计误差较大.在实测分析802.11无线网络的BER分布特征的基础上,提出了一种采用差异化思想来提高BER估计准确度的方法差异化估错码(differentiated error estimation, DEE),其主要思想是在数据包中插入具有不同估错能力的多级估错位,并随机均匀地分布各估错位.然后,借助BER与奇偶校验错误概率的理论关系来估计BER.此外,DEE利用BER非均匀分布特征来优化各级估错位的能力,提高出现概率较高的BER的估计准确度,以降低平均估计误差.在7个节点组成的测试床上评价了DEE的性能.实验结果表明,与最近的研究成果估错码(error estimation code, EEC)相比,DEE可将估计误差平均减少约44%.当估错冗余较低时DEE可将估计误差减少约68%.此外,DEE具有比EEC更小的估计偏差.
移动传感网中基于密度和距离的概率广播算法
沈 悦, 郭龙江, 李金宝,
2014, 51(1):  151-160. 
摘要 ( 491 )   HTML ( 1)   PDF (3026KB) ( 411 )  
相关文章 | 计量指标
广播是移动传感器网络(mobile wireless sensor networks)中最基本的信息传播方式,但现有的广播算法在广播时需要大量中间转发节点,造成大量消息冗余转发,从而导致能量浪费.因此提出一种基于节点密度和距离的概率(broadcasting algorithm named node density and distance-based probability, NDDP)广播算法.该算法平均转发率为5S/(Nπr2),这里S为网络区域面积,N为网络节点总数,r为通信半径.理论分析得出该算法的平均广播接收率超过95%.ns-2模拟结果表明平均广播接收率达到92%以上,并且网络节点密度越大算法的转发率越低,越节能.模拟实验结果表明NDDP算法无论在稳定性方面还是在节能性方面均优于Smite和Sidewinder中的广播算法.
基于Inter-Flow网络编码的多Sink无线传感器网络Anycast路由
仝 杰, 杜治高, 钱德沛,
2014, 51(1):  161-172. 
摘要 ( 676 )   HTML ( 0)   PDF (2360KB) ( 479 )  
相关文章 | 计量指标
以最大化时间驱动型传感器网络的生命周期为目标,基于Inter-Flow网络编码,提出了多Sink环境下编码感知的交叉路径任播路由协议——CodeMesh.首先分析多跳无线网络下单播流间编码条件,提出并证明了多Sink任播网络模型下的编码规则;进而提出多流编码簇的概念,以及确定编码簇个数和优化编码簇成员的方法;定义了统一量化编码和非编码路径代价,并综合链路质量、负载平衡和编码收益的路由度量;最后设计了兼具反应式源路由和主动式路由特点的任播编码路由协议.CodeMesh充分利用Sink节点丰富的计算和通信资源,将路由优化与重构、路由更新与维护与周期性数据收集过程相结合,大大降低了路由开销.部署于实验床平台的实验结果表明,CodeMesh能够有效寻找到具有最多编码机会的路径,从而减少数据传输次数,提高网络传输效率,同时平衡节点负载和能耗,延长整个网络的生存时间.
基于远程动态可重构的WSN节点研究与实现
李沂滨 贾智平 谢 帅 刘福财
2014, 51(1):  173-179. 
摘要 ( 683 )   HTML ( 2)   PDF (1315KB) ( 624 )  
相关文章 | 计量指标
作为近年来的一个研究热点,无线传感网 (wireless sensor network, WSN)是一项可能改变现有工作与生活方式的技术.一个无线传感网系统可能由几十个到上万个节点组成.每个节点在保证具有足够的信息处理和通信能力的前提下,还需要满足低功耗和低成本的要求.从高效能计算的角度看,以FPGA为代表的可重构硬件已经被证明是提高系统计算效能的重要方式.传统上,在嵌入式系统中,FPGA被认为并不适用于低功耗设计.然而,FPGA的可重构不仅包括静态可重构还包括远程的部分动态可重构(partial dynamic reconfiguration, PDR).通过对芯片的某一特定区域的时分复用,在所需芯片面积减小的情况下,芯片的功耗可以大大减少.除此之外,WSN部署后的维护和功能的更新也可以通过FPGA芯片的远程PDR来实现.描述了基于远程硬件PDR技术的WSN节点.通过对几个典型算法(IIR,GPSR,SHA-2,FFT)的PDR实现,得出节点的功耗、面积与存储消耗,并与软件实现方式进行了比较.实验结果表明,通过采用 PDR技术,在计算时间减少的情况下,所需的芯片面积减少27%,运行时功耗最多可减少60%(829mW).
基于压缩感知的无线阵列及协同信号处理
余 恺, 印 明, 宗晓杰, 王营冠, 王 智,
2014, 51(1):  180-188. 
摘要 ( 658 )   HTML ( 0)   PDF (3129KB) ( 810 )  
相关文章 | 计量指标
传感器阵列信号处理是目标监测重要手段之一,传感器节点向后端数据融合中心发送原始信号不可避免地导致传输延时大、能耗高等问题.为实现低功耗、高精度、灵活部署的目标监测,提出了基于压缩采样的无线阵列.借助新兴的压缩感知理论,解决低功耗低速率无线通信难以满足阵列原始信号的实时传输的问题,并保证阵列测向性能;同时根据相邻节点信号的相关性,设计了基于模型先验知识的信号协同重构算法,以较低的运算负荷完成信号的重构.仿真表明基于压缩感知的无线阵列能实现有效的目标测向,同时在数据量严重受限时性能明显优于传统方法.最后,通过简易实验验证了该方法在低成本平台上的可行性.
人工智能
基于浮动车数据的快速交通拥堵监控
吴佩莉, 刘奎恩, 郝身刚, 张全新, 谭毓安,
2014, 51(1):  189-198. 
摘要 ( 691 )   HTML ( 1)   PDF (2088KB) ( 507 )  
相关文章 | 计量指标
浮动车技术是近年来智能交通系统中所采用的、获取道路交通信息的先进技术手段之一,可作为大规模实时交通监控的数据源.由于浮动车数据规模庞大,从大量移动对象中有效处理流数据是其中一大难点.采用相似轨迹聚类的思想,结合与拥堵特征相关的交通参数,提出了拥堵同伴发现算法.该算法能从浮动车轨迹流数据中筛选出可能发生拥堵的浮动车数据,从而对拥堵区域变化趋势进行概化预测,由预测结果决定负载处理方式.此外,设计基于预测的多优先级调度算法用以实现整个监控流程.提出的方法可有效降低处理浮动车数据的代价,实现快速交通拥堵监控.通过在城市路网中大规模出租车轨迹数据上的实测,验证了这种算法的有效性和优势.
混合云存储中海洋大数据迁移算法的研究
黄冬梅 杜艳玲 贺 琪
2014, 51(1):  199-205. 
摘要 ( 672 )   HTML ( 2)   PDF (1656KB) ( 1699 )  
相关文章 | 计量指标
海洋数据是一种典型的大数据,如何利用混合云存储架构存储海洋大数据是海洋数据管理面临的一个挑战.针对混合云存储架构中的关键问题——数据迁移,提出了海洋大数据的生命周期,并且基于此给出混合云存储中海洋大数据的迁移算法.在迁移算法中,将海洋数据的敏感度、数据访问频率、数据大小、数据时间长度等因素作为迁移因子.迁移算法兼顾考虑了数据存储容量、海洋数据本身的属性特征和数据访问过程中的动态变化.实验验证混合云存储模式能大大降低数据管理成本,同时,通过提出的迁移算法保证了数据的访问速度.
企业搜索引擎个性化表示与结果排序算法研究
李贵林 杨禹琪 高 星 廖明宏
2014, 51(1):  206-214. 
摘要 ( 550 )   HTML ( 2)   PDF (2722KB) ( 451 )  
相关文章 | 计量指标
针对企业搜索引擎提出一种基于本地文档库的个性化表示与结果排序算法,以帮助用户找到真正感兴趣的结果.首先,采用聚类分析对用户浏览的历史文档聚类;其次,采用模糊推理技术对所形成的分类进行分析,发现用户对各分类的喜好程度;再次,按用户对各分类喜好程度的不同,为各分类分配抽样文档数;最后,采用多种抽样技术,从各分类中抽取典型文档.来自不同分类的典型文档构成了表示用户个性的本地文档库.结果排序算法通过计算通用企业搜索引擎的搜索结果与本地文档库中各文档的相似性,对结果集重新排序,从而体现出用户个性.实验结果表明,与传统的基于关键词的个性化表示与结果排序算法相比,基于本地文档集的个性化表示与结果排序算法可以给出更能反映用户个性的查询结果,且可以对用户偏好的变化作出更迅速的反映.
图形图像
一种尺度自适应的Mean Shift跟踪算法
张凤军, 赵 岭, 安国成, 王宏安, 戴国忠,
2014, 51(1):  215-224. 
摘要 ( 937 )   HTML ( 2)   PDF (4189KB) ( 518 )  
相关文章 | 计量指标
针对传统Mean Shift中跟踪窗口尺度不能实时适应跟踪目标变化这一问题,提出一种基于图割理论的Mean Shift尺度自适应算法.根据每一帧图像的Mean Shift迭代结果,在其周围的一个小区域内,利用先验的肤色混合高斯模型构造图并建立关于标号的能量模型,使用max flow/min cut算法计算出能量函数最小值实现图割,在图割后的肤色团块中寻找最大团判定为跟踪目标,并以该团的尺度来实时调整目标跟踪窗口.实验结果表明,该方法克服了缩放10%核带宽的经典尺度适应方法的带宽趋于缩小问题,实时地反映跟踪目标真实尺度变化,避免背景中其他目标的干扰,具有较好的实用性和鲁棒性,而且可以应用到娱乐游戏控制中,丰富人机交互操作方式.
融合HCRF和AAM的足球视频精彩事件检测
同 鸣 丁力伟 姬成龙
2014, 51(1):  225-236. 
摘要 ( 635 )   HTML ( 0)   PDF (3025KB) ( 501 )  
相关文章 | 计量指标
精彩事件检测在体育视频语义分析领域具有很高的学术研究价值和广泛的市场应用前景.利用隐条件随机场(hidden conditional random field, HCRF)模型在表达和识别语义事件方面的强大功能,创新性地提出了一种融合了HCRF和情感激励模型(affective arousal model, AAM)的精彩事件检测方法. 首先,通过精彩事件视频结构语义分析,定义了13种多模态语义线索,以准确描述精彩事件富含的语义信息;其次,在基于概念格的多模态语义线索聚类基础上,添加时域特征信息,以构建特征值加权的情感激励模型,得到了各类精彩事件的情感激励值;最后,在小规模训练样本情况下,有效建立了各类精彩事件检测的HCRF模型,基于视频语义镜头序列、情感激励值序列和精彩事件之间的映射关系,从多模态语义线索、视频结构语义、情感语义等多个维度挖掘了精彩事件的潜在规律,实现了同一HCRF模型下各类精彩事件的同时检测. 实验证明了该方法的有效性.