2层无线传感器网络由于具有寿命长和易扩展的特点，已经成为当前的研究热点.Top-k查询是一种重要的查询类型，但是大多数的Top-k查询不能执行精确查询任务.提出了一种精确的Top-k查询算法PI-TQ(privacy-preserving integrity-verification Top-k query)，同时提供了隐私保护和完整性验证功能.算法采用2次查询方法以减少数据通信量，利用基于干扰数的扰动算法实现隐私保护，并采用概率空间邻居验证模式实现完整性验证.仿真结果表明，PI-TQ算法与同类算法相比较，可以明显减少查询的通信量和计算代价，同时保证查询结果的正确性、隐私性和完整性.

随着互联网的发展，尤其是云计算概念的诞生，人们在加密数据搜索与处理等方面的需求日益增加，使得全同态加密变得愈加重要.全同态加密的思想是20世纪70年代Rivest等人首次提出的，如何构造满足全同态性质的体制一直是困扰密码学家的难题，直到2009年Gentry基于理想格提出了第1个全同态加密体制使得该方面的研究取得突破性进展.随后许多密码学家在全同态加密方案的研究上作出了有意义的工作，促进了全同态加密向实用化的发展.对全同态加密的研究动态进行了概要的介绍，包括Gentry提出的第1个全同态加密方案及其优化；基于整数的全同态加密方案；基于LWE问题的全同态加密方案等.随后探讨了全同态加密的一般性应用框架，并以云计算、电子投票、数字水印3个应用为例，介绍了全同态加密的重要应用价值.

为及时阻止网页中篡改信息的传播且使真实信息得到有效利用，提出一种在浏览器端标示篡改的分块网页脆弱水印算法.算法首先按浏览器显示字符所在标签将网页分块，然后将基于块内容生成的水印信息置乱加密后嵌入在网页的颜色属性中.认证时，通过比较网页块提取水印和重构水印的不同比特个数与阈值的关系判定网页块的有效性.对判定为篡改的网页块，通过修改其浏览器端显示字符和尾标签的属性使其在浏览器端屏蔽并标示篡改，阻止伪造信息传播的同时不影响其他信息的继续使用.实验结果表明，算法在水印嵌入方法上有较好的隐蔽性，文件增量较小.当阈值为2时，算法能够较准确地检测出篡改并在浏览器端合理准确地定位标示网页块，且有效提高了算法的时间效率.

随着云存储技术的迅猛发展，越来越多的用户利用云存储服务将本地文件存储转移到云端实现与多个用户的文件共享.针对云环境下多个用户共享同一文件时存在不同访问权限的问题，提出了一种高效的云环境下多用户文件共享方案.新方案基于Elgamal加密系统和代理重加密技术，实现了文件拥有者只需对共享文件加密一次就能够使共享用户访问不同内容的目标.和现有方案相比，新方案的优势体现在：在保证密文生成存储空间不变的同时，文件拥有者对共享文件加密的计算量只与文件块数的指数加密运算呈线性增长关系；共享用户解密文件时只需线性次数的指数解密运算就可以访问各自不同的文件内容.分析表明，新方案更加适合云计算环境的特点，即云服务提供商可以为瘦客户端用户提供无穷的计算和存储能力.

粒计算是知识表示和数据挖掘的一个重要方法.它模拟人类思考模式，以粒为基本计算单位，以处理大规模复杂数据和信息等建立有效的计算模型为目标.针对具有多粒度标记的序信息系统的知识获取问题，提出了基于序粒度标记结构的粗糙近似.首先，介绍了序标记结构的概念，并在序标记结构的对象集中定义了一个优势关系，同时给出了由优势关系导出的优势标记块，并进一步定义了基于优势关系的集合的序下近似与序上近似和序标记下近似与序标记上近似的概念，给出了近似算子的一些性质.证明了由序标记结构导出的集合的下近似质量与上近似质量是一对对偶的必然性测度与可能性测度.最后，定义了多粒度序标记结构的概念，并讨论了多粒度序标记结构中不同粒度下近似集之间的关系.

基于区间分析和免疫学原理，探讨非线性区间数规划问题解的概念和性质，以及求解的免疫优化方法和算法的理论基础.首先，基于该问题的最优值区间，给予最优解概念；研究区间值优化问题有效解的性质，探讨区间自然扩张规划与区间数规划的解之间联系，获得有效解是最优解的充分条件以及寻优的有效途径.其次，基于免疫应答的简化机制，设计具有群体规模小、可调参数少、结构简单等特点的非主从结构微免疫优化算法，并获证该算法具有收敛性和低计算复杂度.通过扩展标准测试函数和应用事例，比较性的数值实验结果显示，此算法执行效率高、搜索效果好，对低、偏高维非线性区间数规划具有较好应用潜力.

水面无人艇(unmanned surface vehicle, USV)是一种重要的海洋自主机器人，当前正被广泛研究并逐渐应用于实际.然而USV的安全航行问题仍严重制约其自主性能的提高，尤其是在复杂海况下的危险规避问题亟待解决.以Sarsa在线策略强化学习算法为基础，提出了USV在复杂海况下的自适应危险规避决策模型，并以渐进贪心策略作为行为探索策略，证明了USV自适应危险规避决策过程能够以概率1收敛到最优行为策略.论证结果表明，采用在线策略强化学习算法提升USV在复杂海况下的危险规避性能是可行的.

区域功能发现对完善城市规划有着重要的指导意义.区域居民的出行特征提取与发掘可以作为建立模型分析区域功能的数据支撑.随着智能交通技术在轨道交通系统的应用，大量蕴含行人移动性和出行目的地信息的客流数据被采集得到，发现客流数据与地铁站相关区域功能有紧密联系.从地铁客流数据中提取出乘客出行模式和地铁站客流模式，并以此为基础建立概率图模型，实现了区域出行特征聚类.首先，以地铁客流数据为基础提取了乘客出行模式和地铁站客流模式，发现地铁站客流集中性和潮汐性的特性，能在一定程度上反映地铁的区域功能.然后，采用了文本分析领域经典的概率图模型，建立基于潜在狄利克雷分配(latent Dirichlet allocation, LDA)主题模型的地铁客流出行特征聚类模型，将具有出行规律相似性的地铁站聚类在一起.最后，通过分析聚类实验结果，发现在不同客流峰段内的区域功能和相互客流关系.

目前的人脸识别算法经常忽视训练过程中噪声的影响，训练数据受到污染时识别性能会明显下降.针对该问题，提出了融合整体与局部特征的低秩松弛协作表示的人脸识别算法.通过低秩分解抑制训练样本的稀疏噪声，得到更加有效的人脸信息.利用松弛协作表示得到判别性更强的编码系数，增强人脸识别系统的判别性.为进一步提高识别率，提取局部特征的同时引入整体特征，运用整体特征和局部特征共同表示人脸图像.实验结果表明，尽管训练过程、测试过程都受到噪声污染，提出的算法对有光照、遮挡及表情变化的正面人脸图像的识别具有很好的鲁棒性，比现有的识别算法拥有更高的识别率.

为了解决复杂函数优化问题，采用SEIRS传染病模型提出了SEIRS算法.在该算法中,假设某个生态系统由若干人类个体组成,每个个体均由若干个特征来表征.该生态系统存在一种传染病在个体之间传染，该传染病攻击的是个体的部分特征.每个染病个体均经历易感、潜伏、发病和治愈等阶段，这些阶段的综合作用决定了个体的体质强弱;利用SEIRS传染病模型所描述的疾病传播机理构造出了相关算子,使个体之间能充分交换信息.结果表明：E-E，I-I和R-R算子能使体质强壮的个体向体质弱的个体传递强壮特征信息，使得后者能向好的方向发展；S-E，S-R，E-I(ω)和R-S(ω)算子能使处于不同状态的个体获得其他个体的平均特征信息，从而降低了该个体陷入局部最优解的概率；S-S算子能使个体的活跃度提高，从而扩大其搜索范围；E-R和I-R算子既具有S-S算子的特征又具有S-E，S-R，E-I(ω)和R-S(ω)算子的特征.体质强壮的个体能继续生长，而体质虚弱的个体则停止生长,从而确保本算法具有全局收敛性.测试结果表明：本算法具有搜索能力强的特点，对求解复杂函数优化问题具有很高的收敛速度.

最小生成树(minimum spanning tree, MST)是图论中最为经典算法之一.基于MST结构的聚类、分类和最短路径查询等复杂图算法，在效率和结果质量方面均有显著提高.然而，随着互联网的迅猛发展，图数据规模也变得越来越大，包含千万甚至上亿个顶点的大图数据越发常见.因此，如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一.除此之外，由于大图数据的动态性特征，如何动态地维护算法结果也势必成为最受关注的问题之一.针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题，首先提出了分区Prim(partition Prim, PP)算法，基于此提出了顶点驱动的并行MST算法——PB(PP Boruvka)算法，并论证了PB算法的正确性.另外，基于MapReduce和BSP框架实现了PB算法.针对只删除动态图特征，提出了MST维护算法，以实现高效的增量计算.对提出的计算和维护算法进行了代价分析和比较.最后，使用真实和模拟数据集，验证了PB算法和维护算法的有效性、高效性和可扩展性.

近年来，Skyline计算在决策应用中起着越来越重要的作用.针对单机处理的研究已较为成熟.现今大数据爆炸，Skyline计算面临着大数据处理的问题.MapReduce是一个并行模型，广泛应用于数据密集型应用处理中.众所周知，MapReduce处理要求任务是可分解的.Skyline计算在MapReduce上执行时，分解任务的方法有网格划分、基于角度的划分等.网格划分仅在数据维度较低时表现良好；基于角度的划分适用于低维和高维数据，但在划分前需要一个复杂并且费时的坐标转换过程.现采用一种与基于角度的划分类似的基于超平面投影的划分来分解数据集，这种划分适用于低维和高维数据，而且其在划分前的坐标转换较为简单.根据超平面投影的划分提出了一种在MapReduce上处理Skyline计算的算法MR-HPP(MapReduce with hyperplane-projections-based partition)，并在该算法的过滤阶段提出了一种有效的过滤算法PSF(presorting filter).大量基于Hadoop平台的对比实验表明该算法的准确性、高效性和稳定性.

内存申请是引发共享存储系统上MapReduce性能下降的主要瓶颈之一，特别是对于需要处理大量键值的应用尤为严重.为了解决此问题，提出了一种内存开销低、能高效处理大规模键值的MapReduce并行计算框架——MALK(high-efficient MapReduce for applications having large amount of keys).MALK对于离散的大规模键值采用连续的存储管理方法，避免了大量小块内存的申请；通过更细粒度地处理Map阶段的任务和流水化Reduce阶段的任务，来减少系统运行过程中同时活跃的数据量，从而将应用程序对内存的需求控制在一个较小的范围内；并提出一种Hash表的复用机制，通过复用Hash表的存储空间来避免流水过程中Hash表内存的重复申请；MALK还综合考虑了任务的粒度和数量对任务管理开销和整体性能的影响，把Reduce阶段的任务数量设成对系统性能最优的值.实验结果表明：相对于Phoenix++，MALK的性能最高可提升3.8倍(平均2.8倍)；在Map和Reduce阶段，MALK最多可节省95.2%和87.8%的存储空间；MALK在Reduce阶段还取得了更好的负载均衡，降低了L2和LLC Cache的缺失率.

近年来，为了提高统计机器翻译系统的准确性，普遍应用海量语料训练出大规模语言模型和翻译模型.而模型规模的不断增大，给统计机器翻译带来了突出的计算性能问题，使得现有的单机串行化翻译处理难以在较快的时间内完成计算，该问题在处理联机翻译时更为突出.为了克服单机机器翻译算法在这方面的局限性，提高大规模统计机器翻译处理的计算性能，面向一个实际的联机翻译系统，提出了一个分布式和并行化翻译解码算法框架，对整个大规模语言模型和翻译模型同时采用分布式存储和并行化查询机制，在此基础上进一步研究实现完整的翻译解码并行化算法.研究实现了一个基于分布式内存数据库的层次短语并行化机器翻译解码器，该解码器使用分布式内存数据库存储和查询大数据量的翻译模型表和语言模型表，克服了传统的机器翻译系统所面临的内存容量和并发度方面的限制.为了进一步提高并行解码速度，还研究实现了另外3项优化技术：1)将翻译模型表的同步规则和Trie树结构的语言模型表转化为基于内存数据库的“键-值”结构的Hash索引表的方法；2)对Cube-Pruning算法进行了修改使其适用于批量查询；3)采用并优化了批量查询方式减少语言和翻译模型查询时的网络传输开销.所提出的解码算法实现了基于大规模语料统计机器翻译时的快速解码，并具备优异的系统可扩展性.实验结果表明：与单机解码器相比，单句翻译速度可提高2.7倍，批量翻译作业的总体解码性能可提高至少11.7倍，实现了显著的计算性能提升.

随着互联网的发展，对精彩视频点进行标注、评论和分享成为趋势.这类群体智慧信息的有效利用将有助于提升视频广告的投放效果.首先将用户提供的细粒度视频标签收集起来，通过视频时间轴加权计算生成视频热点，进而利用视频热点描述信息基于分类匹配的思想来选取广告，最后找出视频热点内用户对视频关注度下降幅度最大的时间点投放广告.实验证明，在数量为百万级的视频集合中，该方法选取的广告与视频的相关性达到85%左右.用户在广告播放过程中关闭广告的概率小于10%.与目前广泛应用的广告投放方式相比，广告的平均播放时间能提升21.5%，广告点击率能从0.65%提高至0.73%.

智慧矿山服务系统能够根据矿工的真实情境，实时提供最合适的信息服务，从而充分利用现有的各种信息系统资源，帮助矿工有效预防各类安全隐患.目前，该领域对于服务系统的实现仍然缺乏深入研究.为了弥补这个缺陷，结合煤矿的领域特征和实际需求，重点研究了服务系统实施过程中的3个关键问题：1)如何实现矿工的情境信息建模；2)如何为客户提供定制化的服务；3)如何验证服务调用的有效性.首先构建了煤矿传感器网络本体，建立了矿工的完整情境模型；然后定义情境信息与业务服务之间的配置模型，实现了业务服务的定制化调用；接着通过采用计算实验模拟各种事故场景来验证现有服务系统的有效性；最后对系统实现可能存在的问题以及未来的研究重点进行了讨论.

随着多核体系结构的出现和普及，片上总线逐渐成为影响片上系统功能和性能的关键部件.因此，片上总线的验证成为片上系统设计中一个重要组成部分.模型检测作为一种主流的形式化验证方法，可以自动化穷举搜索系统行为以决定片上系统的设计是否满足设计规范.然而，模型检测受制于状态空间爆炸问题，且现有规范语言如计算树逻辑和线性时序逻辑等的描述能力有限.提出了一种基于命题投影时序逻辑的WISHBONE片上总线符号模型检测方法.该方法将以Verilog硬件描述语言实现的WISHBONE总线转化为以NuSMV模型检测工具的建模语言SMV描述的系统模型，使用命题投影时序逻辑描述WISHBONE总线期望的性质，通过PLSMC工具验证系统模型是否满足期望的性质.实验结果表明该方法能够有效验证WISHBONE片上总线的定性性质，以及时间敏感和迭代性等定量性质.

错误定位是软件调试的重要环节，基于切片谱的统计错误定位技术，借助程序切片可以提高错误定位效率.而这类技术执行效果取决于构建切片谱的切片选择策略和怀疑度计算公式的选择.为评估不同的切片选择策略及怀疑度计算公式对错误定位效率的影响，提出一种基于切片谱的错误定位框架.该框架首先计算程序执行失败时的全切片和成功时的执行切片，随后提出一组基于相似度的切片挑选策略以构建切片谱，最后按照选定的公式计算怀疑度并生成定位报告.应用提出的错误定位框架，针对一组典型的Java基准程序开展错误定位实证研究.结果表明：最优怀疑度计算公式Wong，Russel&Rao和Binary的错误定位效率与切片选择策略无关，而提出的怀疑度计算公式HSS，Tarantula，DStar，Naish1和Naish2在低相似度切片谱上定位效果较好.

人们的行为受其他个体和连接彼此的社会网络的影响.研究基于影响网络的重要模型(DeGroot模型)，在此模型中，社会网络可用一个加权的有向图表示，网络中的每个个体对某个共同的兴趣问题具有一个初始态度，由于网络中节点的相互影响而会逐步发生改变.提出一种框架用于分析复杂社会网络的影响可控性.结果表明，如果网络中存在持相反观点且对影响免疫的个体，群体对于命题的观点或态度可被固执的个体集合控制.通过分析网络完全影响可控或部分影响可控的条件，得到相应的可控准则.此外，提出控制影响网络的具体方法.由于网络的结构可控性已被广泛用于分析各种复杂网络，分析了网络的影响可控性与结构可控性的关系.

作为一种新兴的社交媒体，微博由于其信息的简短性、实时性和公开性，在短短4年内已积累数以亿计的用户并且数量还在迅速增长，由此带来的社会影响日益广泛.对微博用户关系网络进行社区发现具有重要的理论和实际意义.根据微博网络的有向性及建立关注关系的随意性等特点，提出一种基于共同关注和共同粉丝的微博用户相似度，定义此相似度的模块化函数，依据贪心算法思想设计出基于此模块化函数最大化的社区发现方法，并在此基础上将该方法推广到具有标签信息的微博网络中.应用该方法处理了3个真实的微博用户关系网络数据，结果表明该方法可以有效地发掘微博用户关系网络中的社区结构.