摘要:网络边布局技术是网络可视化研究的重要内容,良好的边布局能够有效地展示网络的整体结构并从中揭示出某些隐含的信息模式.为了全面地总结和分析现有网络边布局技术,首先归纳了网络边布局的主要任务,回顾了指导网络边布局的美学标准.然后将网络边布局技术归纳为3类:边路由技术、边融合技术和边集束技术,分别阐述了各类技术中典型布局方法的主要原理和特征,并重点对边集束技术进行了分类分析.最后总结了目前研究中还存在的一些问题,展望了网络边布局技术的发展前景和面临的挑战,以期为相关领域的研究者提供有益参考.

摘要:近年来,基于Wi-Fi的无线定位研究日益受到关注.然而,在实际应用中,由不同终端设备的差异引起的定位偏差是一个重要问题.针对此问题提出了一种免标定、无监督的SSDR(signal strength difference ratio)解决方法.考虑采集训练数据的设备和测试数据的设备之间信号存在差异,首先将信号指纹特征进行去线性处理以获取新的特征;然后结合AP(access point)对定位结果的影响,提出了基于AP影响因子计算距离的标准;最后根据新的特征和距离计算准则消除不同设备之间的差异以实现定位.在真实的室内无线环境下的实验结果表明,所提出的SSDR方法相比于传统的直接基于信号强度和欧式距离计算准则的定位方法而言,可以提高10%~20%的定位精度,增强了无线定位系统的实际可用性.

摘要:视频烟雾检测具有响应速度快、非接触等优点,但由于烟雾形状、色彩、纹理千差万别,目前的算法很难取得令人满意的检测效果.为此,提出了一种鲁棒的特征提取方法,采用支持向量机(support vector machine,简称SVM)进行检测.首先,提取边缘方向直方图(edge orientation histogram,简称EOH).然后,采用圆周平移方式将EOH的最高柱变换到EOH的固定位置,消除了旋转变换的影响.为了进一步增强特征的鲁棒性,提取图像亮度和饱和度分量的Hu不变矩、均值、偏差、偏度和峰度特征.最后,将这些特征组成一个38维的特征矢量,采用SVM训练和识别烟雾.实验结果表明,这些特征具有很好的分类性能,能够在较大的训练库和测试库上达到98%和85%以上的检 测率.

摘要:在触控交互中,缺少触觉反馈会造成用户操作水平的降低和用户体验的下降.前人研究对在触控交互中增加触觉反馈这一方法进行了探索.然而,由于现有触摸屏技术仅能在用户点击屏幕后检测用户手指的位置,触觉反馈也只能在用户点击屏幕之后发挥作用.新的传感技术可以在触摸屏上方的悬浮空间(hover space)内提前检测到手指的位置.利用多对象选择任务(multi-target pointing task)比较了在悬浮空间中增加4种反馈方式对用户操作水平和用户体验的影响.实验结果显示,增加的点击振动反馈受到了用户的普遍青睐.然而,增加的触觉反馈对于用户的操作效率和正确率却没有影响.根据这些结果和前人的研究,提出了在悬浮空间中增加触觉反馈的设计建议.

摘要:手语是聋哑人互相之间常用的交流手段.但由于大部分口语使用者不懂手语, 因此影响了聋哑人参加正常的社交活动.因此,提出了一种利用简单的三维轨迹信息进行小规模手语词汇识别的方法,试图帮助聋哑人克服部分交流障碍.首先,对Kinect获取的三维轨迹进行预处理——对获得的三维轨迹根据打手语人的身高进行归一化,然后使用插值算法对轨迹进行均匀的指定点数的重采样.在进行匹配之前,测试集和原型图像集中的轨迹将会对齐,并使用DFT变换到频域空间,得到由实部、虚部、幅值串接而成的新的特征向量.最后,在频域中计算两条轨迹之间的欧氏距离以评估两条三维轨迹的相似度.对239个手语词汇集合的实验结果表明,该方法对于中国手语的孤立词识别是有效的.

摘要:社交网络中用户关系强度计算对于个性化社交服务呈现具有重要意义.同时,心理学研究表明人格特征是影响用户关系强度的关键因素之一.基于社会心理学中人与人之间的关系产生原理,提出一种内嵌人格分析的社交关系强度层次模型及计算方法.通过社交网络行为建模,建立用户大五人格特征预测模型,实现用户人格倾向性演算.同时结合偏好相似性和交互熟悉性计算,实现嵌入人格特征的用户关系强度的求解算法.最后,本文通过构建人人网社交关系仿真实验平台,验证了该方法的合理性和有效性.

摘要:智能手机和其他具备短距离无线通信能力设备的普及,使利用机会社交网络进行社会性活动的组织成为了可能.然而,机会网络中的消息传递需要代理节点的支持,代理节点的不协作,会大大降低消息传递的效率.为了解决消息传递过程中的"丢包"问题,引入了具有中介的市场模型作为活动组织激励机制.系统将消息发起者、代理节点和消息接收者分别与市场交易中的卖家、中间商和买家进行类比,分析在不同社会关系与社会属性下的社会福利和收益情况.同时,提出了代理选择的"流浪者算法",选择与多个社区相遇次数较多且与各社区相遇概率较大的用户(流浪者)作为代理,并基于MIT Reality Mining数据集进行实验.以具有中介的市场模型作为激励机制,比较了该数据集下使用不同代理选择算法时形成的收益与社会福利情况.在上述算法的基础上,基于Android平台初步实现了社会性活动组织的原型系统,为活动的组织提供服务.

摘要:语音合成技术是人机言语交互中重要的媒介方式,基元选取算法一直是拼接式语音合成中的研究重点.在传统的语音合成中基于代价函数的拼接合成基元选取算法的基础上,将双音子(diphone)的稳定段边界模型应用到单词和音节中,最后使用3种基元模型的分层不定长选音算法,从语料库中优选出最佳合成基元序列拼接合成最终语音.该算法一方面利用分层统一的不定长选音策略,尽可能地选取具有更好韵律特性和声学连续性的较大基元,从而显著减少拼接点,将有可能发生协同发音或者切分错误的拼接点包含到更大的基元内部;另一方面通过稳定段切分修改传统拼接基元边界类型,充分利用了diphone的稳定段边界良好的拼接特性,从而提高了合成语音的连续性和自然度.评测结果显示,这种方法与传统diphone拼接合成方法相比,其合成效果有显著的提升.

摘要:首先介绍了SIMD扩展技术,并分析了使用SIMD扩展的3种方式,认为通过调用特定目标平台优化的第三方库是应用领域软件开发者快速开发高效并行程序的较好的方式;其次,介绍了国产神威处理器SW-1600平台,并利用SIMD扩展和循环展开等技术开发了SW-VML(SW Vector Math Library),开发过程中提出了访存对界、简化向量条件分支的优化方法,解决了非对界访存、向量与标量数组转换影响性能的问题,并根据SW编译器对OpenMP的支持,开发了多线程OpenMp版;最后,在SW-1600平台上采用不同向量规模对SW-VML进行了测试,测试结果显示,SIMD向量化相对于串行程序加速比为2.08,4线程相对单线程平均加速比为2.26.SW-VML是在国产神威系列处理器上开发高效程序的向量函数软件包,也是在神威蓝光高性能计算平台单计算节点开发高性能程序的基础软件工具包.

摘要:动态异构多核处理器的处理器核可动态调整的特征给操作系统调度算法带来了新的机遇和挑战.利用处理器核动态可调整的特征能更好地适应不同任务的运行需求,带来巨大的性能优化空间.然而也带来新的代价和更复杂的公平性的计算.为了解决面向动态异构多核处理器结构上的公平性调度问题,提出了一个基于集中式运行队列的调度模型,以降低调度算法在动态处理器核变化所带来的维护开销.并重新思考在动态异构处理器结构下公平性的定义,基于原有CFS调度算法提出新的HFS调度算法.HFS调度算法不仅能简单而有效地利用动态异构多核处理器的性能优势,而且能提供在动态异构多核处理器上的公平性调度.通过模拟SCMP,ACMP,DHCMP平台,证明了提出的HFS调度算法能够很好地发挥DHCMP结构的性能特征,比运行目前主流调度算法的SCMP和ACMP结构提升10.55%的用户级性能(ANTT),14.24%的系统吞吐率(WSU).

摘要:生物基因测序是生物信息学分析中最常用的高性能计算任务.旨在通过分析生物基因测序日志找出生物基因测序日志中的任务特性,构建一种通用的适合分析生物基因测序的任务模型,并应用于面向基因测序的高性能计算系统的任务调度及性能优化.基于任务日志,主要分析了生物基因测序日志中任务到达时间的规律特性、任务运行时间和任务的并行尺寸等特性,通过这些任务特性利用指数分布、伽马分布、正态分布以及线性拟合构建了相应的局部任务模型,然后提出一种局部模型融合的方法,将各个局部模型合并为统一的任务模型.通过两种通用的模型评测方法对任务模型进行的评测结果显示,最终的任务模型与原有任务日志的4种任务属性趋于相同的分布,验证了所构建的任务模型具有很好的通用性.

摘要:现有的OpenMP代价模型较为简单,既没有充分考虑OpenMP程序的执行细节,也无法适应不同的循环并行执行方式.针对上述问题,对最先进的产品级优化编译器Open64中已有的代价模型进行扩展,以单个并行候选循环为对象,建立一种用于OpenMP自动并行收益分析的代价模型.该模型在改进了Open64原有DOALL并行代价模型的基础上,又增加了DOACROSS流水并行代价模型和DSWP并行代价模型.实验结果表明,建立的代价模型能够较好地评估循环并行执行开销的趋势,为OpenMP自动并行化中的收益分析提供了有效的支持.

摘要:聚类是研究空间多变量数据的重要工具之一.但是自动聚类算法通常需要用户预设参数然后生成结果,缺乏一种有效的交互机制将用户介入到聚类的过程,使之动态改变参数并对结果进行调整和评估.为此提出一种面向空间多变量数据聚类的可视分析流程,首先运用自动聚类算法对原始三维空间进行聚类,针对三维空间不易交互的缺陷将数据点投影到二维平面进行交互选择和可视编码,设置多种视图使用户实时而全面地理解数据分布和模式,交互地修正聚类结果,并根据一些编码的统计信息来判断结果的合理性和正确性.整个流程是渐进式的,即用户通过迭代逐步细化结果,最终抽取兴趣域.案例分析表明,新的可视分析流程能够有效地提高空间自动聚类算法的精度,也极大地缩短了用户交互的时间.

摘要:基于String Graph理论的序列拼接工具SGA是当前国际上的一种新型序列拼接工具.首先,形式化证明了SGA的序列拼接问题是一个NP完全问题,然后对SGA的拼接效率进行了分析,发现与业界同类拼接软件相比,SGA在内存开销方面具有优势,但却有更大的时间开销,其中构建索引占了60%~70%的比例.基于此,设计了一种并行优化策略,并实现了面向天河二号体系结构的并行策略来解决这一问题.分别在普通机群和天河二号上进行性能测试,针对小规模数据,优化后的索引构建时间比之前的最佳性能提高了3.06倍,中等规模数据提高了1.60倍,实验结果表明,其优化效果明显,且并行构建局部索引过程具有良好的线性扩展性.其中用到的优化方法和策略对相关问题的研究有一定的借鉴意义.这也表明,天河二号的超级计算能力能够很好地助力生命科学领域的相关研究.

摘要:网上购物已被越来越多的消费者接受,C2C网站作为主流购物平台提供数以万计的商品条目供消费者选择,其中有一定数量商品条目的商品描述具有误导性.误导性是指条目的商品描述与其实际价格不符合,通常的表现是描述商品的价格低于其应有的价格,以此吸引消费者,误导消费者到其购物页面.这既影响消费者的判断,又损坏购物网站的信誉度.为了找出这部分具有误导性的商品描述,提出了一种结合概率模型HMM和基于统计的异常值识别方法,能够有效地识别出误导性商品描述.HMM模型从概率的角度有效地确定商品描述所指代的商品,为C2C网站上商品描述的不规范导致的商品指代信息模糊提供了一种行之有效的解决方法.基于统计的异常值识别方法在处理C2C网站上商品信息比较单一时较为有效.用该方法在实际的电商网站数据集上进行了实验.实验结果证明了该方法的有效性.

摘要:查询结果重复率高是top-k查询处理过程中亟待解决的问题,已有的解决方法需要遍历初始结果集中所有的对象,因此,查询处理的效率较低.为了提高查询处理的效率,把初始结果集映射到欧氏空间中,根据拉式策略,可选用基于得分或基于距离两种方法之一从该空间选出差异最优子空间,在基于距离的方法中,对欧氏子空间进行分割并且利用探测位置和Voronoi图的几何特性减少二次查询对象的数目.在此基础上,提出了top-k查询结果有界多样化算法,并证明了算法的正确性.实验结果表明,所提出的算法提高了top-k查询处理效率.

摘要:数据过时是影响数据质量的重要因素,因此判定数据时效性对于提高数据质量至关重要.当前判定数据时效性的方法可分为两类:基于时间戳的方法和基于规则的方法.基于时间戳的方法要求精确完整的时间戳,但这样的时间戳在很多应用中不存在.基于规则的方法不要求时间戳,但现有方法均依赖于冗余元组,且不能对数据时效性做出定量判定.同时,这些方法均基于确定规则,无法表达不确定的领域知识.针对上述问题,提出不确定时效规则及相应的数据时效性模型.基于该模型,进一步给出了两个可定量地判定数据时效性的算法.同时,还给出了时效规则的学习算法.真实数据上的实验结果验证了算法的有效性.

摘要:基于位置的服务可以指引用户找到在特定位置或区域内能够提供所需要服务的对象(比如找某个高校附近(经纬度标识)的咖啡店).向这类服务提交一个查询位置和多个关键词,该类服务返回k个最相关的对象,对象和查询的相关性同时考虑空间相近性和文本相似性.为了支持高效的top-k空间关键词查询,出现了多种混合索引,然而现有的这些索引为了提供实时响应均耗费大量存储空间.提出一种基于压缩技术的索引CSTI,该索引显著减少了存储开销(至少减少80%甚至到两个数据量级),同时保持高效的查询性能.大量基于真实和仿真数据集的实验结果表明,CSTI在空间开销和响应时间上均优于已有方法.

摘要:属性约简是粗糙集理论重要应用之一.考虑到决策信息系统中的噪声,针对一般二元关系,从知识分类能力角度给出了一种新的属性重要性度量方法,在此基础上提出了一种能够抑制噪声的近似属性约简算法,该算法适用于多种粗糙集扩展模型,摆脱了现有约简算法对特定二元关系的依赖.实验结果表明,近似约简算法通过调节近似参数,可有效增强抗噪性,在有效降低约简属性集规模的同时,提高了约简结果的分类性能.

摘要:割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.

摘要:空间co-location模式挖掘是空间数据挖掘的一个重要研究方向.空间co-location模式是空间对象的一个子集,它们的实例在空间中频繁关联.到目前为止,空间co-location模式挖掘都只关注某一个时刻的空间co-location模式.然而,在实际应用中,数据库中的数据是随着时间改变的,所以高效地增量挖掘空间co-location模式是非常必要的;空间co-location模式演化分析可以发现空间co-location模式的变化规律,预测特定事件的发生,但是对这些问题的研究并未见诸报道.研究了高效的空间co-location模式增量挖掘及空间co-location模式的演化分析,首先,提出了高效的空间co-location模式增量挖掘基本算法及剪枝算法.其次,在多个随时间变化的真实数据集上挖掘co-location演化模式.再次,证明了空间co-location模式增量挖掘基本算法及剪枝算法是正确的和完备的.最后,在"模拟+真实"的数据集上用充分的实验验证了增量挖掘基本算法的性能以及剪枝算法的剪枝效果.此外,把空间co-location增量挖掘基本算法、剪枝算法及演化模式挖掘算法应用到三江并流区域珍稀植物数据集上,增量挖掘出空间co-location模式及演化模式,预测了co-location模式的演化规律,更好地实现了对珍稀植物的动态跟踪和保护.

摘要:针对Xen虚拟化平台中虚拟机资源分配不合理的问题,提出了两种资源调度优化算法,即细粒度优化算法和粗粒度优化算法.细粒度优化算法主要解决单个物理节点上虚拟机资源分配不合理问题,能够根据物理节点上运行的各虚拟机的资源利用情况来调整资源分配量,适当增加利用率较高的虚拟机的资源,减少资源利用率低的虚拟机的资源,从而优化资源分配,提高资源利用效率,避免不必要的虚拟机迁移.粗粒度优化算法是针对集群中多个物理节点之间虚拟机负载不均衡问题而提出的.该算法结合粒子群优化技术,选择将集群系统中热点物理机上的部分虚拟机迁移到最适合的冷点物理机上,从而避免高载物理机宕机.实验结果表明,这两种资源调度优化算法能够有效解决虚拟机资源分配不合理的问题,具有较好的适用性和应用前景.

摘要:图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.

摘要:在时空数据中有一类表示用户在某一时间到达某一地点的数据——到达数据,到达数据可以是社交网站的签到数据、轨迹数据中的停留点及公共交通中乘客抵达的位置数据,这些数据的聚簇可以反映用户的聚集行为.基于到达数据,提出一类新的时空数据查询——时空异常聚簇发现.将到达数据进行周期性划分,通过时空聚类算法对一个时间段的数据进行聚类,比较不同时间段内聚簇的差异度,发现具有最大簇异常度的前k个簇.通过该查询发现的时空异常聚簇可以应用于城市安全管理、基于位置的服务和交通调度等方面.定义了异常簇查询模型,提出了针对任意形状聚簇的簇差异度度量,将异常簇查询转化为二分图最大匹配问题,对二分图构建与匹配进行了优化并提出了高效的查询算法.利用真实数据集进行了充分实验,验证了查询结果的实际意义,评估了所提出的各查询算法在不同参数设置下的查询效率.

摘要:提出了一种基于本征图像分解的人脸光照迁移算法.首先,针对本征图像分解效果不彻底的情况,提出了一种改进的本征图像分解方法.在此基础上,为了保持人脸细节特征,提出了一种基于边缘保留的光照滤波算法,对参照人脸进行光照迁移至目标人脸,最后融合目标材质图像与滤波后光照图像进行人脸重光照.实验结果表明,与已有算法相比,该算法能够很好地保留迁移后的人脸肤色,并且所生成的重光照效果更准确、自然.

摘要:针对目前大规模复杂水面模拟中存在的效率不高、碰撞检测较为复杂等问题,提出了一种海洋尺度复杂水面模拟解决方案.首先,提出了一种球面投影网格方法实现大规模动态水面波动效果的模拟.与传统的投影网格方法相比,该方法不需要重新构造与球面直接相交的投影体,具有更高的绘制效率并且适合图形硬件加速.其次,设计了高效的交互式复杂水面的模拟方法,包括水面和刚体交互作用的模拟及刚体与地形的快速碰撞模拟.此外,给出了通用的泡沫绘制和海岸线绘制方法.实验结果表明,该方法的模拟结果较为逼真,能达到较高的绘制速度(FPS>60),适用于计算机游戏、虚拟现实等实时环境.

摘要:利用摄像头实现行人计数在智能视频监控领域有着重要的价值,但是行人互相遮挡、噪声、摄像机透视效果和图像背景等问题影响了人群计数的准确性.针对高密度人群场景的行人计数准确率的问题,提出了基于截面流量统计的行人计数方法,该方法基于梯度运动历史图像检测前景,并用有效运动图像改进了基于特征提取的行人计数方法,结合运动速度提取方法实现了行人计数.实验结果表明,提出的计数方法在高密度人群场景中具有较高的准确率和实时性,是一种针对高密度人群有效的行人计数方法.

摘要:在雾天情况下,雾对光线的散射使得室外场景的光照发生很大变化,太阳光和天空光的参数估计变得更为复杂.结合雾天情况下的大气散射模型,提出了室外场景的雾天基图像模型,并基于该模型提出了雾天室外场景图像光照参数估计算法.在已知场景基图像的条件下,利用迭代散射系数方法,优化求解雾浓度与场景深度图像,然后通过对去雾图像进行分解,获得最佳的去雾图像以及正确的光照分解系数.算法能够得到较为精确的雾浓度与场景深度图像.实验结果表明了算法的有效性.

摘要:局部二值模式(local binary patterns,简称LBP)是一种有效的纹理描述算子,具有算法复杂度低、消耗内存、原理清晰的优点.Damper-Shafter的证据理论满足比贝叶斯概率论更弱的条件,具有直接表达"不确定"和"不知道"的能力.提出了一种结合二者优势的纹理识别方法.该方法首先计算图像金字塔,并利用多尺度LBP去测量两个纹理图像之间的相似度;然后,通过融合每个测试样本的信息来组合测试纹理与每个训练样本相似性度量;最后,识别结果由不同纹理之间的最大证据类决定.实验结果表明,该方法对给定的图像数据集1和数据集2分别取得了96.43%和91.67%的正确率,优于最初基于LBP的纹理识别方法.

摘要:针对图像尺寸调整的缝切割方法中存在的结构断裂和变形扭曲等问题,提出了一种基于切缝对齐和变形校正的切缝优化算法以获得更好的图像尺寸缩放效果.算法首先利用基于图割的切缝优化方法获得当前需要移除的一条切缝,然后采取动态规划算法,由粗到细地优化得到切缝上下像素之间的高精度匹配对应关系,最后通过逆向映射来对图像进行变形以校正发生扭曲甚至断裂的结构信息.实验结果表明,该方法能够很好地弥补缝切割所产生的扭曲变形,达到结构连续的视觉效果.基于切缝对齐和变形校正的切缝优化算法可用于调整图像尺寸使之与相应的显示设备相符,具有巨大的应用潜力.