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

当期目录

2015年 第52卷 第9期    出版日期:2015-09-01
软件技术
基于数据源分类可信性的真值发现方法研究
马如霞, 孟小峰
2015, 52(9):  1931-1940.  doi:10.7544/issn1000-1239.2015.20140684
摘要 ( 1394 )   HTML ( 1)   PDF (2043KB) ( 1249 )  
相关文章 | 计量指标
网络的普及和电子商务的发展改变了人们信息获取以及消费的方式.Web已经成为大多数人获取信息的重要来源.与此同时,互联网信息质量问题也逐渐凸显.Web中存在大量过时、错误、虚假、片面的信息.其中,不同网站为相同对象提供冲突信息的问题尤为突出.如何从这些冲突信息中找到正确信息成为亟待解决的问题,这类问题又被称为真值发现问题.通过对现有真值发现问题解决方法的调研,发现现有方法均未考虑数据源分类可信性差异对真值发现的影响.因此,提出基于数据源分类可信性的真值发现问题.提出2种方法探测数据源分类可信性差异,并采用贝叶斯的方法迭代计算数据源分类可信性和属性值准确性.另外,通过考虑数据源覆盖率和对象难度对真值发现的影响,进一步提高真值发现算法的准确性.一个真实数据集的实验结果表明,所提方法可以显著提高真值发现的准确性.
基于频繁项集的海量短文本聚类与主题抽取
彭敏, 黄佳佳, 朱佳晖, 黄济民, 刘纪平
2015, 52(9):  1941-1953.  doi:10.7544/issn1000-1239.2015.20140533
摘要 ( 1695 )   HTML ( 7)   PDF (1801KB) ( 1883 )  
相关文章 | 计量指标
社交网络短文本规模大、传播快、质量低、模态多样等特性导致现有基于向量空间模型的文本聚类技术在对其进行聚类时面临维度高、特征稀疏和噪声干扰等挑战.对此,提出基于频繁项集的短文本聚类与主题抽取STC-TE(short text clustering & topic extraction)框架.首先研究短文本的多特征对文本质量的影响,在基于高质量短文本集挖掘出的大量频繁项集基础上,设计基于相似度的频繁项集过滤策略SIF(similarity-based itemset filtering),可过滤掉85%的非重要频繁项集;然后定义基于相关文本集的频繁项集相似度,并提出聚类个数自适应的频繁项集谱聚类算法CSA_SC(clusters self-adaptive spectral clustering),实现频繁项集聚类与主题抽取;最后基于主题词将大规模短文本划分到相应的主题簇中,从而实现短文本聚类.基于100万条新浪微博文本的实验结果表明,STC-TE框架能够全面准确地抽取主题信息,快速有效地实现海量短文本分类.
一种语义增强的空间关键词搜索方法
韩军,范举,周立柱
2015, 52(9):  1954-1964.  doi:10.7544/issn1000-1239.2015.20140686
摘要 ( 1037 )   HTML ( 2)   PDF (2421KB) ( 625 )  
相关文章 | 计量指标
空间关键词搜索立足于查找满足用户查询意图且空间距离相近的兴趣点(point of interest, POI),在地图搜索等领域有着广泛的应用.传统的空间关键词搜索方法仅考虑关键词与POI点在文本上的匹配程度,忽略了查询的语义信息,因而会导致相关结果丢失以及无关结果引入等问题.针对传统方法的局限,提出了语义增强的空间关键词搜索方法S3(semantic-enhanced spatial keyword search).该方法对查询关键词中包含的语义信息进行分析,并结合语义相关性和空间距离对POI点进行有效的排序.S3方法主要有以下2个技术挑战:1)如何对语义信息进行分析.为此,S3引入了知识库对POI数据进行语义扩充,并提出了一种基于图的语义距离度量方式.结合语义距离和空间距离,S3给出POI点的综合排序方案.2)如何在大规模数据上即时地返回top-k搜索结果.针对这一挑战,提出了一种新型的语义-空间混合索引结构GRTree(graph rectangle tree),并研究了有效的剪枝策略.在大规模真实数据集上的实验表明,S3不仅能够返回更为相关的结果,而且有着很好的效率和可扩展性.
基于Nash-Pareto策略的自动数据分布方法及支持工具
王晓燕, 陈晋川, 郭小燕, 杜小勇
2015, 52(9):  1965-1975.  doi:10.7544/issn1000-1239.2015.20140832
摘要 ( 765 )   HTML ( 0)   PDF (4497KB) ( 641 )  
相关文章 | 计量指标
大数据时代的来临为数据存储与管理提出了新的挑战.随着数据量的迅猛增加,自动数据分布逐渐成为分布式系统中的研究重点和难点.根据对数据分布问题中数据、负载和节点3个要素的研究和分析,将数据分布问题抽象为称为DaWN(data,workload,node)的三角模型,并将3要素之间的相互关联关系抽象为数据分片、数据分配和负载执行3条纽带;据此,提出了解决自动数据分布问题的基本架构,对各功能模块的协动关系进行探讨;同时,结合已有的研究工作,采用Nash-Pareto优化均衡策略使得前述各机制相得益彰,实验结果验证了其有效性.为使研究工作更多地应用于实践,设计并实现了自动数据分布辅助原型工具ADDvisor(automatic data distribution advisor),协同支持自动数据分布的执行,共同促进大规模分布式联机事务处理系统的并行性能和自动化管理技术的发展.
基于LCSS的数据流相似性查询处理算法研究
王少鹏, 闻英友, 赵宏
2015, 52(9):  1976-1991.  doi:10.7544/issn1000-1239.2015.20140479
摘要 ( 1057 )   HTML ( 0)   PDF (5482KB) ( 726 )  
相关文章 | 计量指标
数据流相似性查询广泛应用于智能家居、环境监测等领域.当前以LCSS(longest common subsequence)作为相似性测度函数的研究并不多.NAIVE算法使用基本动态规划方法计算测度函数值,通过该值与相似阈值的比较得到查询结果,对基于LCSS的数据流相似性查询问题进行研究.针对NAIVE算法必须在动态规划矩阵所有成员取值的计算完成后才能得到查询结果的缺点,提出了一种基于PS(possible solution)-CC(column critical)域优化策略的数据流相似性查询处理算法.该算法划定了每个窗口上动态规划矩阵的PS域和CC域,很好地利用了这2个域中成员所具有的性质和相似性查询的特点,无须获得测度函数的最终值便可得到查询结果,省略了很多矩阵成员的计算.实验部分证明了该算法的有效性,与同类算法相比,在处理具有更高精度结果要求的查询时效果更好.
数据时效性修复问题的求解算法
李默涵,李建中
2015, 52(9):  1992-2001.  doi:10.7544/issn1000-1239.2015.20140687
摘要 ( 951 )   HTML ( 0)   PDF (2027KB) ( 856 )  
相关文章 | 计量指标
数据过时问题普遍存在于实际应用中,因此将数据库中的过时数据修复为最新值是提高数据质量的关键步骤.当前主要有基于规则和基于统计2类数据修复方法.基于规则的修复方法能够将领域知识直观地表达为规则的形式,但是难以表达数据中某些复杂的关联关系;基于统计的方法能够表达数据中的复杂关联关系,并修复许多通过规则难以发现和修复的错误,但是该类方法均需要学习较复杂的条件概率分布,且难以直接应用数据语义相关的领域知识.研究数据时效性的修复问题,同时,为了克服当前2类数据修复方法的缺点,提出一类新的修复规则,将规则和统计的方法结合起来修复过时数据.该规则一方面能够以传统规则的方式表达领域知识,另一方面还能够使用其特有的分布表来描述数据随时间变化的统计信息.接着,还给出了修复规则学习算法和数据时效性修复算法.真实和虚拟数据上的实验均验证了算法的有效性.
支持多种查询的室内移动对象索引
贲婷婷,秦小麟,许建秋
2015, 52(9):  2002-2013.  doi:10.7544/issn1000-1239.2015.20131230
摘要 ( 840 )   HTML ( 1)   PDF (3322KB) ( 481 )  
相关文章 | 计量指标
随着室内定位技术的广泛应用,室内位置服务快速发展.移动对象索引技术作为支撑位置服务的核心技术,大多数都基于室外环境,难以直接应用于室内空间.现有的室内移动对象索引,仅关注对移动对象历史数据的查询,且支持的查询类型单一.为此,提出MQII(multiple queries indoor index)索引结构,对移动对象历史和当前位置信息进行索引,能够同时支持对象位置查询、轨迹查询以及时空范围查询.索引采用对象链表和桶链表结构,实现从对象和时空范围2个方面对移动对象数据的管理;提出针对该索引结构的有效更新、查询算法;实验结果表明,与现有室内移动对象索引相比,索引不仅能够支持历史查询和当前查询,还能够同时高效支持对象位置查询、轨迹查询和范围查询.该方法可应用于办公楼、医院等多种室内空间.
基于Hive的计算结果特征提取与重用策略
谢恒,王梅,乐嘉锦,孙莉
2015, 52(9):  2014-2024.  doi:10.7544/issn1000-1239.2015.20140548
摘要 ( 990 )   HTML ( 1)   PDF (2583KB) ( 648 )  
相关文章 | 计量指标
现有MapReduce工作流中作业之间需将计算结果物化到HDFS(Hadoop distributed file system),大量磁盘I/O导致其效率较低.基于现有代表性工作Hive,提取并保存MapReduce工作流产生计算结果的数据特征,提出一种计算结果匹配和重用策略.首先,根据查询条件定义连接图与连接体等结构,用于可复用计算结果的匹配.基于该结构,根据HiveQL(Hive query language)解析出的抽象语法树,提出生成查询语句连接体算法,并遍历候选连接体列表,给出最佳重用方案生成方法,包括单连接体重用和多连接体重用策略.进一步,为了增加计算结果的重用概率,提出多键选择、推迟算数运算和语义理解3种方法.最后,使用数据仓库基准测试数据集TPC-H和SSB进行实验,验证了所提出的重用计算结果以提高数据处理速度的有效性.
一种高效过滤-提纯音频大数据检索方法
张兴忠, 王运生, 曾智, 牛保宁
2015, 52(9):  2025-2032.  doi:10.7544/issn1000-1239.2015.20140694
摘要 ( 934 )   HTML ( 0)   PDF (2118KB) ( 484 )  
相关文章 | 计量指标
针对互联网音频大数据的高速检索问题,结合音频指纹技术与过滤-提纯思想,提出一种面向音频大数据的鲁棒高效检索方法.在经典的Philips音频指纹基础上,提出了一种基于bag-of-features(BoF)的音频中间过滤指纹用于快速缩小检索范围,与Fibonacci Hashing检索相比提高检索速度约130倍;并设计了一种基于阈值的固定间隔抽样匹配方法,大幅减少匹配计算量,进一步提高检索速度可达140倍.实验结果显示:使用该方法在约10万首音频中对不同时长的音频片段进行批量检索,平均检索时间均小于1s;对音频进行MP3转换、重采样、随机剪切后再检索,召回率均在99.47%以上,理论准确率接近100%.
基于关联图模型的医学图像Top-k查询方法
李鹏远, 潘海为, 李青, 韩启龙, 谢晓芹, 张志强
2015, 52(9):  2033-2045.  doi:10.7544/issn1000-1239.2015.20140692
摘要 ( 862 )   HTML ( 1)   PDF (3007KB) ( 661 )  
相关文章 | 计量指标
找到与病人具有相似纹理特征的医学图像,有助于医生结合历史病历信息对病人作出更为准确的诊断.基于此,大量的研究工作围绕如何提高基于内容的医学图像检索技术的准确性展开.然而,现有的基于内容的医学图像检索技术均是基于查询图像与数据库中图像的逐张匹配过程,面对迅速增长的医学图像数量,查询等待时间过长成为医学图像检索领域的另一主要问题.鉴于用户往往只对前k(Top-k)个检索结果感兴趣,提出了一种基于关联图模型的医学图像Top-k查询方法.首先,提出一种关联图模型,使用该模型可以有效地刻画医学图像之间关联关系的模糊性;继而利用关联图模型,提出一系列关联性度量计算方法,从而使得仅需对图像匹配一次即可更新所有图像与查询图像之间的相似度范围.由此,提出Top-k查询方法以及基于游走的查询优化策略.实验证明提出的方法可以有效地减少图像匹配次数,降低时间复杂度.
网络技术
信息中心网络内缓存替换算法性能分析与优化
王永功, 李振宇, 武庆华, 谢高岗,
2015, 52(9):  2046-2055.  doi:10.7544/issn1000-1239.2015.20140101
摘要 ( 931 )   HTML ( 3)   PDF (3260KB) ( 626 )  
相关文章 | 计量指标
信息中心网络(information centric networking, ICN)是一类受到广泛关注的新型互联网体系结构.通过对网络内(in-network)缓存的充分利用,信息中心网络可以极大地增强内容分发效率.网络内缓存的管理机制一直是信息中心网络研究中的热点问题.分析了网络内缓存的基准缓存替换最近最少使用(least recently used, LRU)算法的性能,指出多跳LRU缓存中广泛存在的“缓存退化”问题:在首个缓存节点发生缺失的内容请求也很难被下游的缓存命中.针对这一问题,提出一种基于预过滤的O(1)复杂度的改进算法.在原有缓存前放置一个仅记录内容标识的预过滤缓存,完成对原始内容请求的整形,使得预处理后的请求流量可以更容易被后面几跳缓存命中.基于真实互联网拓扑的实验表明,在信息中心网络典型应用场景下,预过滤LRU的缓存命中率可以达到LRU的2~3倍.
信息安全
一种基于攻击意愿分析的网络风险动态评估模型
马春光,汪诚弘,张东红,李迎涛
2015, 52(9):  2056-2068.  doi:10.7544/issn1000-1239.2015.20140177
摘要 ( 972 )   HTML ( 2)   PDF (3642KB) ( 827 )  
相关文章 | 计量指标
针对目前利用攻击图进行风险评估时,存在过于依赖已知漏洞知识库、仅仅利用原子攻击本质属性进行量化分析而没有很好地关联攻击者主观的攻击意愿等问题,提出了一种基于攻击者攻击意愿分析的动态风险评估模型.通过融合已知威胁和潜在威胁构建原子攻击库,分析在系统网络环境下不同时期攻击者所面临的攻击压力,量化攻击者决策时的攻击意愿,将攻击意愿和原子攻击本身的攻击性质加入到贝叶斯网络攻击图的动态推理模型中.实验证明了该模型的合理性,并且该系统更适合于实际网络环境下的实时风险评估.
网络技术
未来互联网虚拟化研究
余涛,毕军,吴建平
2015, 52(9):  2069-2082.  doi:10.7544/issn1000-1239.2015.20140207
摘要 ( 924 )   HTML ( 4)   PDF (3254KB) ( 670 )  
相关文章 | 计量指标
目前的互联网基于“端到端”原则设计,并且由许多目标与策略迥异的互联网服务提供商共同创建和维护.若想升级互联网体系结构,需要得到他们全体的一致同意,因此几乎不可能在互联网上部署全新的网络结构和协议.为了避免互联网结构出现僵化,人们提出可用网络虚拟化方法增加互联网范式的多样性.通过在一个公共的基底网络上引入多种不同的互联网结构,互联网虚拟化可以促进互联网创新并推动更多种类的新应用出现.分别从互联网体系结构和实验平台2个方面,对过去和当前正在进行的有关未来互联网的虚拟化研究进行分析、归类和概述,并总结未来互联网虚拟化研究的发展趋势.
系统结构
温度约束多核处理器最大稳态吞吐量分析
张必英, 陈红松, 崔刚, 傅忠传
2015, 52(9):  2083-2093.  doi:10.7544/issn1000-1239.2015.20140656
摘要 ( 776 )   HTML ( 0)   PDF (3480KB) ( 389 )  
相关文章 | 计量指标
随着多核处理器功耗密度的不断增大,温度约束条件下的性能分析已经成为多核处理器早期设计优化的重要组成部分.当处理器运行不同的任务时,处理器温度具有很大的差异性,但现有研究成果并没有考虑任务差异性对处理器性能的影响.针对采用动态频率电压调节作为温度管理技术的多核处理器,为了提高在温度约束条件下稳态吞吐量的分析准确性,考虑不同任务之间的差异性,提出一种新的最大吞吐量分析方法.将任务特征引入性能分析模型,论证了当多核处理器吞吐量达到最大值时各处理器核上任务特征之间的关系,将最大稳态吞吐量分析归结为线性规划问题.仿真实验结果表明,所提方法具有较好的分析准确性,任务特征对多核处理器最大吞吐量具有非常大的影响.
常带宽服务器混合任务低功耗调度算法
张忆文, 郭锐锋, 邓昌义
2015, 52(9):  2094-2104.  doi:10.7544/issn1000-1239.2015.20140611
摘要 ( 711 )   HTML ( 2)   PDF (2552KB) ( 405 )  
相关文章 | 计量指标
针对包含有截止期限限制的周期任务和有响应时间要求的非周期任务的实时系统混合任务集,提出常带宽服务器混合任务低功耗调度算法(constant bandwidth server mix task low power scheduling algorithm, CBSMTLPSA).该算法是2阶段调度算法,并且结合了动态电压调节(dynamic voltage scaling, DVS)技术和动态功耗管理(dynamic power management, DPM)技术.离线阶段确定任务的离线速度,充分利用处理器的资源;在线阶段通过回收周期任务提早完成的空闲时间以及服务器产生的空闲时间,利用DVS技术调节处理器的运行速度,并且当处理器处于空闲状态时,判断是否使用DPM技术以达到进一步降低能耗的目的.仿真实验表明所提出的CBSMTLPSA算法比CBS/DRA-W(constant bandwidth server for dynamic reclaim algorithm base workload)算法节约6.02%~34.14%的能耗;CBSMTLPSA算法的能耗与非周期任务的响应时间的乘积比CBS/DRA-W算法低5.86%~34.06%.
基于高速缓存负荷均衡的动态二进制翻译研究
李战辉, 刘畅, 孟建熠, 严晓浪
2015, 52(9):  2105-2113.  doi:10.7544/issn1000-1239.2015.20140220
摘要 ( 675 )   HTML ( 1)   PDF (3193KB) ( 612 )  
相关文章 | 计量指标
针对动态翻译时指令和数据高速缓存访问负荷大幅增加且增幅不均衡导致翻译器性能下降的问题,提出基于指令高速缓存与数据高速缓存访问负荷动态均衡的软硬件协同翻译方法.该方法为处理器设计高速缓存负荷平衡状态,该状态将数据高速缓存分为普通区和负荷平衡区(load balancing area, LBA),普通区缓存正常的程序数据,负荷平衡区通过负荷转化通道(load transforming channel, LTC)吸收动态翻译器调度器地址空间转换操作在指令高速缓存上产生的部分负荷,以提高数据高速缓存利用率.EEMBC(embedded microprocessor benchmark consortium)测试基准实验结果表明,在同等处理器资源的情况下,该方法将指令高速缓存访问次数平均减少35%,数据高速缓存访问次数平均减少58%,动态翻译器综合性能提高171%.
人工智能
基于马尔可夫逻辑的中文零指代消解
宋洋, 王厚峰
2015, 52(9):  2114-2122.  doi:10.7544/issn1000-1239.2015.20140620
摘要 ( 969 )   HTML ( 1)   PDF (1011KB) ( 653 )  
相关文章 | 计量指标
中文零指代消解问题包括零指代项的识别和零指代项的消解2个相互关联的子任务. 传统的方法在解决该问题时,往往不考虑2个子任务间的关联关系,比如识别出的零指代项必须被消解以及发生消解的必须是零指代项等约束. 基于马尔可夫逻辑网络模型可以将零指代项的识别和零指代项的消解2个子任务融合在统一的机器学习框架下进行联合推断与联合学习,采用局部规则分别针对零指代项的识别和消解进行预测,采用全局规则描述这2个子任务间的关联关系. 基于OntoNotes3.0的中文数据集上的实验结果显示,基于马尔可夫逻辑网络的联合学习模型相比于独立学习模型以及多个baseline方法能够获得更好的实验效果.
差分选择策略在复杂多目标优化问题中的研究
郑金华, 刘磊, 李密青, 尹呈, 王康
2015, 52(9):  2123-2134.  doi:10.7544/issn1000-1239.2015.20140472
摘要 ( 835 )   HTML ( 4)   PDF (4270KB) ( 686 )  
相关文章 | 计量指标
在多目标进化算法中,如何提高生成解的质量一直是研究的热点与难点.为解决以上问题,该算法从差分进化算法与计算资源分配策略2个方向进行了研究.根据多目标问题从决策空间到目标空间的映射关系以及差分进化算法基本原理,提出了一种基于双种群的多目标差分选择策略.它利用2个种群来区分个体间收敛性差别,在调整差分参数以适应多目标算法特性的基础上,以收敛性差别为依据选择参与差分运算的个体,从而提高差分算法性能,加快子代个体收敛.另外,根据子代个体收敛速率的不同,动态调整计算资源的分配,进一步提高算法收敛性.与ε-MOEA和MOEA/D-DRA在一系列复杂的多目标优化问题上进行了对比实验,结果表明了所提策略的有效性.
一种病理图像自动标注的机器学习方法
张钢,钟灵,黄永慧
2015, 52(9):  2135-2144.  doi:10.7544/issn1000-1239.2015.20140683
摘要 ( 1490 )   HTML ( 4)   PDF (2767KB) ( 978 )  
相关文章 | 计量指标
病理图像能够揭示疾病的原因及严重程度,在临床诊断中有重要应用.病理图像中局部区域与病理特性之间不明确的对应关系为建立计算机辅助诊断模型带来了困难.基于全局图像特征表达和等分小块等方法难以有效表达病理特性的局部性.提出一种基于多示例多标签学习的活检病理图像自动标注框架,对病理特性的局部性进行表达.通过带区域约束条件的分割算法把病理图像划分为若干视觉上不连续的区域,对区域进行基于纹理和内部结构的特征提取,把病理图像转化为多示例样本,在此基础上提出一种基于贝叶斯学习的多示例多标签稀疏集成算法.在本地大型三甲医院的皮肤科活检样本数据集上进行方法有效性评估,结果表明该方法能得到医学上可接受的标注准确率,从而说明其有效性.
软件技术
一种针对模型转换的图形化建模语言
何啸, 麻志毅, 邵维忠, 胡长军
2015, 52(9):  2145-2162.  doi:10.7544/issn1000-1239.2015.20148187
摘要 ( 796 )   HTML ( 0)   PDF (7262KB) ( 578 )  
相关文章 | 计量指标
模型转换是模型驱动开发的核心操作,它通常被实现成一种特殊的程序.模型转换可以实现不同模型、模型和代码,以及模型和各种结构化文档之间的转换.随着模型驱动方法的发展,模型转换正在被运用到越来越复杂的问题上,从而导致越来越庞大的规模和越来越复杂的程序结构.为了更好地控制转换开发过程中的复杂性,需要一种图形化的建模语言,支持对转换程序的分析和设计.提出一种针对模型转换程序的可视化建模语言VisTML(the visual transformation modeling language).它包含7种不同的视图,每个视图都包含一组建模概念.这些概念覆盖了整个转换程序开发过程中(从需求到部署运行)的所有主要阶段,支持开发人员在不同的抽象层次基于不同视角刻画模型转换.用VisTML对转换程序进行建模,有助于控制其复杂性,并促进开发人员的相互沟通与分工合作.最后介绍了VisTML的支持工具TModeler,并且通过3个案例论证VisTML的可行性与有效性.