基于语义的网络大数据组织与搜索
摘要：随着信息技术的飞速发展,网络空间中出现海量异构的数据资源,网络大数据逐渐引起了人们的关注.从网络大数据中发现并获取用户所需的数据资源,需要对网络大数据进行有效地组织管理并进行基于数据语义的相似搜索.为此,需要从网络数据资源中抽取其特征/属性构造高维语义空间,并将数据资源及用户查询信息抽象为语义空间中的特征向量或高维点,进而通过比较特征向量间夹角余弦值或高维点之间的距离来衡量语义相似性.高维索引技术可以对高维语义空间中的数据资源进行有效组织管理,实现基于数据语义的相似性搜索;而降维技术可以消除语义空间维数过高所引发的＂维灾＂影响.文中对现有的高维数据索引及降维技术进行了系统的综述,然后介绍了现有的基于分布式技术实现高维数据语义相似性搜索的研究工作,最后并展望了未来工作.数据管理系统评测基准：从传统数据库到新兴大数据
摘要：大数据时代的到来意味着新技术、新系统和新产品的出现.如何客观地比较和评价不同系统之间的优劣自然成为一个热门研究课题,这种情形与三十多年前数据库系统蓬勃发展时期甚为相似.众所周知,在数据库系统取得辉煌成就的发展道路上,基准评测研究一直扮演着重要角色,极大推进了数据库技术和系统的长足发展.数据管理系统评测基准是指一套可用于评测、比较不同数据库系统性能的规范,以客观、全面反映具有类似功能的数据库系统之间的性能差距,从而推动技术进步、引导行业健康发展.数据管理系统评测基准与应用息息相关：应用发展产生新的数据管理需求,继而引发数据管理技术革新,再催生多个数据管理系统/平台,进而产生新的数据管理系统评测基准.数据管理系统评测基准种类多样,不仅包括面向关系型数据的基准评测,还包括面向半结构化数据、对象数据、流数据、空间数据等非关系型数据的评测基准.在当今新的数据系统发展中,面向大数据管理系统的评测基准的研究热潮也如期而至.大数据评测基准研究与应用密切相关.总体而言,尽管已有的数据管理系统评测基准未能充分体现大数据的特征,但是从方法学层面而言,三十多年来数据管理系统评测基准的发展经验是开展大数据系统研发最值得借鉴和参考的,这也是该文的主要动机.该文系统地回顾了数据管理系统评测基准的发展历程,分析了取得的成就,并展望了未来的发展方向.H-Tree：一种面向大数据流在线监测的层次索引
摘要：随着计算机网络的迅猛发展和大数据时代的到来,数据越来越频繁地呈现出多属性异构的特点.这种包含多种不同类型属性的大数据流称为异构大数据流（Heterogeneous Big Data Streams）.在面向大规模数据在线监测分析的应用中,通常需要在异构大数据流上注册大规模监测规则.因此,对于每一个数据流元组,必须用最小的计算开销满足所有的规则.同时,由于大数据流上监测规则集异常庞大,提高规则监测的性能是大规模数据流在线监测的关键.基于此,该文提出一种层次化的索引结构H-Tree及其在线规则匹配算法.具体的,H-Tree将大数据流上的属性集划分为离散型属性和连续型属性.基于不同的属性集,构建两层索引结构：在第1层,通过改进的红黑树对离散型谓词构建触发索引;在第2层,通过量化连续型谓词构建多维索引结构.H-Tree的在线规则匹配算法利用关联关系表对两层索引的监测结果进行融合过滤.实验分析表明,与经典的R＋方法相比较,H-Tree通过层次化的索引结构,在不降低准确度的前提下,显著提升了大数据流的监测效率.面向大规模机群的可扩展OLAP查询技术
摘要：大数据时代,由中低端硬件组成的大规模机群逐渐成为海量数据处理的主流平台之一.然而传统基于高端硬件平台设计的并行OLAP查询算法并不适应这种由不可靠计算单元组成的大规模并行计算的环境.为改善其在新计算环境下的的扩展性和容错性,该文对传统数据仓库的数据组织模式及处理模式进行改造,提出了全新的无连接雪花模型和TRM执行模型.无连接雪花模型基于层次编码技术,将维表层次等关键信息压缩进事实表,使得事实表可以独立处理数据,从数据模型层保证了数据计算的独立性;TRM执行模型将OLAP查询的处理抽象为Transform、Reduce、Merge 3个操作,使得OLAP查询可被划分为众多可并行执行的独立子任务,从执行层保证了系统的高度可扩展特性.在性能优化方面,该文提出了Scan-index扫描和跳跃式扫描算法,以尽可能地减少I/O访问操作;设计了并行谓词判断、批量谓词判断等优化算法,以加速本地计算速度.实验表明：LaScOLAP原型可以获得较好的扩展性和容错性,其性能比HadoopDB高出一个数量级.一种能效优化的MapReduce资源比模型
摘要：随着云计算的快速发展,IT资源规模的不断扩大导致能耗问题日益凸显.为降低MapReduce编程模型带来的高能耗,文中研究Map/Reduce任务的资源消费特征及该特征与能效的关系,旨在寻找一种能够指导资源分配和任务调度的资源模型,进而实现能效优化.文中提出任务的能效与任务被分配的资源量无关,而与其被分配的各种资源的资源量比例相关,且存在一个＂最佳资源比＂使得能效达到最高.基于此,文中首先提出了普适的资源和能效模型,从模型层面证明最佳资源比和能效之间的关系,量化空闲资源量和空闲能耗;随后分析MapReduce编程模型,将普适资源比模型变换到MapReduce下.通过抽象的数据的＂生产者-消费者＂模式,求解Map/Reduce任务的最佳资源比;最后,通过实验从任务能效和空闲能耗两个角度证明了最佳资源比的存在,并根据实验结果,对MapReduce执行过程进行划分,给出了部分Map/Reduce任务的最佳资源比.最佳资源比的提出和求解将有利于基于该最佳资源比的任务调度和资源分配算法的研究,进而实现Map/Reduce任务能效的提高.YARM：基于MapReduce的高效可扩展的语义推理引擎
摘要：随着语义网的快速发展,RDF语义数据大量涌现.大规模RDF语义数据推理的一个主要问题是计算量大、完成计算需要消耗很长的时间.显然,传统的单机语义推理引擎难以处理大规模的语义数据.另一方面,现有的基于MapReduce的大规模语义推理引擎,缺乏对算法在分布和并行计算环境下执行效率的优化,使得推理时间仍然较长.此外,现有的推理引擎大多存在可扩展性方面的不足,难以适应大规模语义数据的增长需求.针对现有的语义推理系统在执行效率和可扩展性方面的不足,文中提出了一种基于MapReduce的并行化语义推理算法和引擎YARM.为了实现分布和并行计算环境下的高效推理,YARM做出了以下4点优化：（1）采用合理的数据划分模型和并行化算法,降低计算节点间的通信开销;（2）优化推理规则的执行次序,提升了推理计算速度;（3）设计了简洁的去重策略,避免新增作业处理重复数据;（4）设计实现了一种新的基于MapReduce的并行化推理算法.实验结果表明,在真实数据集和大规模合成数据集上,YARM的执行速度比当前最新的基于MapReduce的推理引擎快10倍左右,同时YARM还表现出更好的数据和系统可扩展性.海量高维向量的并行Top-k连接查询
摘要：在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.基于MapReduce快速kNN Join方法
摘要：kNN连接是空间数据库领域里一个基本而又重要的问题,被广泛地应用于多个其他领域.它对提高众多实际应用的性能有着重要意义.随着目前参加kNN连接的数据集的增大和要求的响应时间的缩短（尤其在一些应急环境中）,作者实际上对kNN连接的效率要求更高.然而,目前的方法大多基于单个进程或者单台机器,并不具有很好的伸缩性.为了解决这个问题,作者引入了map-reduce框架来运行kNN join并提出了两种新的方法：基于map-reduce的分布式网格概略化kNN join（DSGMP-J）和基于map-reduce的voronoi diagram下kNN join（VDMP-J）.并把它们和最新的方法 H-BNLJ进行了实验对比.实验结果证明了作者提出的DSGMP-J和VDMP-J方法具有较优的伸缩性.MapReduce集群中最大收益问题的研究
摘要：MapReduce是目前最为流行的用于大数据分析的并行系统之一.许多企业已经搭建了自己的MapReduce集群,为广大用户提供计算服务.用户可以向集群提交具有完成时限要求的MapReduce作业,若作业被按时完成,则企业可以获得一定的收益.针对这种应用场景,该文首次提出了MapReduce集群中的最大收益问题.为有效地解决该问题,首先提出了一种基于序列的任务调度策略（简称为SEQ策略）,并证明了在处理具有完成时限约束的作业时SEQ策略存在优势.基于SEQ策略,该文提出了最大收益的调度算法（Scheduling Algorithm for Maximum Benefit,简称AMB算法）,该算法可以快速地确定可接收作业,并给出有效的执行方案,以达到最大化收益的目的.另外,针对在实际应用中的某些异常情况（如节点宕机）,该文也设计了有效的超时处理策略,进一步增加了算法的实用性.最后,通过大量的实验验证了该文所提出算法的有效性.大规模图像特征检索中查询结果的自适应过滤
摘要：针对大规模图像的快速检索问题,提出了面向倒排索引结构的检索方法中查询结果的自适应过滤方法：全面过滤和不完全过滤.目的是在不影响查询精度的前提下,提高查询效率.根据查询特征所在的空间位置,全面过滤通过构造以查询特征点为球心的超球体并自适应地计算半径,只对位于超球体内部的查询结果进行排序,从而减少需要排序的查询结果数量,提高查询效率.在此基础上,为了降低过滤查询结果的时间开销,不完全过滤将倒排列表划分为若个子倒排列表并将对应的聚类中心用于过滤查询结果.为了验证所提出方法的有效性,以一种典型检索方法：基于残差量化的检索方法为应用实例,分别将全面过滤和不完全过滤与该检索方法相结合.此外,为了提高特征量化效率,将一种欧式距离下限定理与残差量化相结合并用于过滤特征量化过程中非近邻聚类中心.通过在公开数据集进行实验,实验结果表明在保证具有相同平均查全率的前提下,全面过滤和不完全过滤都能明显减少基于残差量化的检索方法的查询时间,不完全过滤比全面过滤具有更快的检索速度.此外,非近邻聚类中心过滤可以有效提高残差量化的特征量化效率.可信云服务
摘要：云服务是一类依托于云计算平台的新兴网络服务,其外包服务模式以及云平台自身的安全风险引起了用户的信任问题.云服务可信与否成为用户业务向云迁移的最大顾虑.如何构建安全可信的云服务,成为近年来研究领域的热点之一.该文在分析云计算安全威胁的基础上,提出了可信云服务的定义,并从用户信任预期、安全威胁来源和技术针对的安全目标等角度对可信云服务研究技术的类型进行了划分;然后,系统地梳理了数据存储外包、计算外包、虚拟机外包等典型云服务的安全可信研究工作;最后,探讨了可信云服务的未来研究趋势.云数据安全存储技术
摘要：云计算因具有资源利用率高、节约成本等诸多优点而将成为未来的主流计算模式.然而,包括隐私保护在内的数据安全存储问题却成为云计算推广的巨大障碍.该文首先列举了云计算在数据安全上面临的主要挑战,指出了云计算的租用商业模式和其采用的两种关键技术——虚拟化技术和多租户技术是云存储存在诸多安全问题甚至安全悖论的根本原因.从加密存储、安全审计和密文访问控制3个方面对云数据安全存储的最新研究进展分别进行了评述.在加密存储上,介绍了云数据安全存储框架和主要的安全存储技术;在安全审计上,分析了外包数据安全审计,特别是公开审计面临的主要难题,介绍了包括云数据在内的外包数据完整性公开证明的主要模型和方法,并指出了它们的优势和不足;在云密文的访问控制上,详述了基于属性的云密文访问控制方法,并指出了这些方法的优劣.最后指出了云数据安全存储研究面临的主要问题并预测了相关研究的未来发展趋势.云存储中的数据完整性证明研究及进展
摘要：随着云存储模式的出现,越来越多的用户选择将应用和数据移植到云中,但他们在本地可能并没有保存任何数据副本,无法确保存储在云中的数据是完整的.如何确保云存储环境下用户数据的完整性,成为近来学术界研究的一个热点.数据完整性证明（Provable Data Integrity,PDI）被认为是解决这一问题的重要手段,该文对此进行了综述.首先,给出了数据完整性证明机制的协议框架,分析了云存储环境下数据完整性证明所具备的特征;其次,对各种数据完整性证明机制加以分类,在此分类基础上,介绍了各种典型的数据完整性验证机制并进行了对比;最后,指出了云存储中数据完整性验证面临的挑战及发展趋势.Web服务流程的结构范式及其判定算法
摘要：服务组合是一种利用已有Web服务构建新的增值服务的有效方法,然而当前缺乏对组合产生的服务流程进行结构健壮性层次划分和判定的准则.针对上述问题,提出Web服务流程结构范式,从路径的可达性和结构冗余性两个角度将结构范式划分为四个层次.基于逻辑Petri网建模服务流程为服务网,将服务流程结构范式的判定转化为对服务网组成结构的分析.在服务网的基础上构建控制流网,从而将服务流程中的控制流和数据流进行分离.定义了控制流网语言,并提出一种通过约简求解控制流网语言的方法.通过对控制流网语言中字符序列组成结构特征的分析,获取服务网的结构性质,完成对服务流程结构范式层次的判定.给出了服务流程结构范式的定义、判定定理以及算法,并通过实例验证了文中方法对流程结构范式进行判定的可行性和有效性.IVirt：基于虚拟机自省的运行环境完整性度量机制
摘要：完整性度量是检测程序篡改的重要方法,但是在虚拟化环境下传统的检测方法已体现出不足.例如,度量软件与被度量对象处于相同操作系统中易受攻击.该文从安全性和性能两方面出发,提出了一种基于虚拟机自省的完整性度量机制IVirt（Integrity for Virtualization）.该机制从虚拟机外部通过地址转换和内容定位得到所需的虚拟机内存数据,从而对虚拟机内部的程序进行完整性度量,以检验程序是否遭到篡改.该文以典型的虚拟机监视器Xen为例实现了IVirt原型系统.相比于同类工作,IVirt一方面将度量软件与被度量对象分离,防止度量软件遭到攻击;另一方面采用地址转换来度量运行时状态,这区别于采用事件拦截机制的度量方法,以降低性能开销.实验结果表明,该方法能够检测出虚拟机运行时的软件篡改,而且在性能上不会引入过高的代价.一种基于逻辑Petri网的Web服务簇组合方法
摘要：Web服务组合是实现快速服务增值和软件重用的重要方式,但现有的静态服务组合和动态服务组合方式都有待于进一步完善.文中集成静态服务组合和动态服务组合的优点,提出了一种在虚拟层面上基于服务簇进行服务组合的思想;研究并提出了一种基于服务簇的服务组合方法,并应用逻辑Petri网对其进行形式化建模描述;给出了服务簇网的基本组合模型,并分别对其完备性继承作了分析;研究了服务簇网组合的代数运算性质.最后,通过实验证明了服务簇网组合运算的可行性和有效性.