基于三维网格-R树的混合索引方法研究

针对三维场景下空间数据分布不均匀呈现区域密集的问题,本文提出并建立了三维网格-R树混合索引结构,在此基础上给出详细的维护与查询算法。该混合索引结构综合了网格快速划分三维空间以及R树高效查询的优点,较好地解决了海量非均匀分布的三维数据的快速管理、查询问题。最后针对上述混合索引结构模型构建了实验系统,对不同大小、不同分布下的数据集进行范围查询、k近邻查询对比测试,实验结果均表明了该混合索引结构在查询方面的良好性能。     

基于Internet的数字城市三维可视化研究

研究了基于Internet的数字城市三维可视化．使用分层组合模型建立了城市模型并使用GRID模型建立城市地形模型,该模型适合Internet环境下城市三维可视化．在服务器端设计一个中间件对城市空间数据进行预处理,提高了客户端三维城市模型显示的速度．在服务器端使用基于R树的索引,实现对建筑物空间数据的索引,提高了网络环境下查询分析的效率．     

基于元素区间编码的GML数据索引方法

根据GML数据查询的需要,在分析XML文档编码和空间索引技术的基础上,提出一种基于扩展的元素区间编码的GML索引方法.首先通过扩展的区间编码方法对GML文档中的元素、属性、文本、几何体等要素进行编码;其次依据元素编码算法并将非空间节点、空间节点、元素节点从GML文档树中分离,产生元素编码序列;在此基础上根据节点类型的不同对属性和文本节点建立B+树索引以实现值查询,对几何体节点建立R树索引以实现空间数据的分析操作,并在查询处理时通过查询优化算法避免不必要的节点的遍历,进一步提高查询效率.实验结果表明,基于元素区间编码的GML数据索引方法是可行的、高效的.     

基于改进R*树的移动GIS多尺度渐进传输与表示

针对传统单一尺度空间数据在低速无线网络环境中难以由移动GIS下载与表示的问题,在研究矢量数据多尺度表示与R*树空间索引的基础上,设计并实现了改进的多尺度R*树空间索引算法.该算法使得R*树中非叶子结点能够关联合适尺度的空间对象实体,保证海量的矢量数据在服务器端得到了有效的多尺度组织.在该算法的基础上,借助于移动GIS端所设计的缓冲式多尺度空间数据存储与管理,以及基于请求/应答模型的GML流式数据传输,设计并实现了面向移动GIS的矢量数据多尺度渐进传输模型,从而使得移动GIS能够以较高的效率下载和表示各种尺度的空间数据.通过真实的土地利用现状空间数据实验,验证了该方法在无线网络情况下能够有效地提高移动GIS的数据传输效率.     

空间数据查询优化研究

由于空间数据量的庞大以及空间对象、空间数据查询的高度复杂性,提高空间数据查询速度已成为空间数据库应用的难点和热点。通过阐述基于线性四叉树的快速邻域查询算法和建立CELL树索引两种算法为例,对提高空间数据库查询优化效率的研究进行一些讨论。     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

网格化MRRF距离矩阵并行生物进化树算法

针对传统生物进化树执行效率不高的问题,提出一种网格化MapReduce-Robinson-Foulds(MRRF)距离矩阵并行生物进化树算法.首先,基于HashRF算法基本思想,设计实现了生物进化树MapReduce模型的网格化构建,以及网格参数计算;其次,利用两阶段MapReduce过程分别获得Robinson-Foulds距离子矩阵和联合后的距离总矩阵,实现了进化树在MapReduce架构下的Robinson-Foulds矩阵表示.最后,通过与Hash和HashRF算法进行对比,显示MRRF算法在运行时间和算法加速比上均要优于对比算法,并通过仿真对网格计算节点在不同核心数情况下对算法的影响进行了实验研究.     

不同维数下空间对象的反最近邻查询

反最近邻查询是在最近邻查询基础上提出的一种新的查询类型,是空间数据库的应用拓展,在不同维数下,根据不同的索引结构,反映出空间对象的反最近邻查询差异性较大,从不同索引结构的特性出发,分析了低维环境下基于R*-树的反最近邻查询优势,提出高维环境下一种新的基于SRdnn-树索引结构的空间对象反最近查询方法,优化了不同维数下空间对象的反最近查询性能,提高了查询效率.     

基于聚类的逆向Skyline查询算法

逆向Skyline查询能够应用到诸如决策支持、用户偏好支持以及市场行为分析等方面。由于参考对象q的存在,在执行逆向Skyline查询的过程中数据空间被划分成许多分区。然而,存在的算法都没有考虑这个问题的影响,直接使用原始数据集建立索引结构。本文提出了一种新的逆向Skyline查询方法CRSQ,它考虑了这个问题。CRSQ首先根据查询对象q对数据进行聚类,然后建立R-tree索引,最后利用高效修剪策略修剪索引搜索空间。实验结果表明CRSQ算法是有效的,它相对于没有聚类技术的算法获得了50%以上的性能提高。     

一种高效的空间索引结构

为高效地处理空间数据，必须对数据库建立索引机制以快速存取数据。然而，由于空间数据的特殊性使得传统索引方法不能很好地适应空间数据的存取。介绍了一种目前较流行的索引结构－R树及其主要算法。在所研究的空间分析数据库系统SADBS中实现了R树索引。     

PSP：一种高效的偏序域上skyline查询处理方法

为解决偏序域上的skyline查询问题,本文提出一种高效的偏序域上的skyline查询处理方法,来满足人们对查询效率日益增长的需求.首先,为提高偏序域上skyline的查询效率,将倒排索引引入skyline查询,提出一种基于倒排的索引结构.其次,提出基础算法(Basic Partially-ordered Skyline Processing based on inverted index,PSP_B),PSP_B包含两个阶段:第一阶段,能够通过映射将偏序域转化成全序域,并建立倒排索引;第二阶段,通过倒排索引提前找到扫描结束点,得到最终的skyline结果.再次,在PSP_B的基础上,进一步提出优化算法(Improved Partially-ordered Skyline Processing based on inverted index,PSP_I).PSP_I通过先分组再建索引的方法能够进一步提高计算效率.最后,用大量的实验证明本文所提算法的正确性和高效性.     

MapReduce框架下k-支配轮廓查询算法

随着维度和数据量的不断增长,已有的轮廓查询方法已无法为用户提供更好的查询支持.本文采用并行处理框架MapReduce 结合k-支配轮廓查询算法来解决此类查询问题.在对输入的数据集进行预排序的基础上,提出了基于MapReduce 的单轮扫描算法和双轮扫描算法,通过在不同维度、数据分布、节点个数等方面的实验测试及对比,验证了算法的有效性.     

MapReduce框架下基于抽样的分布式K-Means聚类算法

提出一种MapReduce框架下基于抽样的分布式K-Means聚类算法,解决海量数据环境下并行执行K-Means算法时,时间开销较大的问题.该算法使用抽样方法,在保证数据分布不变的前提下,对数据集的规模进行约减,并在MapReduce框架下对聚类算法进行优化.实验结果表明,该算法在保持良好聚类效果的同时,能有效缩短聚类时间,对大规模数据集具有较高的执行效率和较好的可扩展性.     

云环境下基于MapReduce的海量服务选择研究

当处理分布式、大规模的服务选择时,传统服务选择方法存在着效率不高和全局Qo S性能低下的问题。基于Map Reduce框架,设计了一种云环境下的海量服务选择方法以解决此问题。首先,基于Map Reduce框架,利用Skyline算法,筛选海量候选服务,生成Skyline服务库;其次,基于迭代式Map Reduce框架,运用多目标模拟退火算法,从所生成的Skyline服务库中优选Skyline服务,产生一组Pareto最优的组合服务;最后,依据用户的个性化和多样性需求,执行Top-k查询,优选出满足用户偏好的k个组合服务。该方法适应于具有分布式环境、高维Qo S的海量服务选择,能快速返回组合服务,且其全局Qo S较优。     

缓存模式下的轮廓查询优化方法

研究在缓存模式下,利用一组预存储的临时轮廓快照集来高效等价重构用户新提交的轮廓查询Q,并提出一种新颖的缓存模式下轮廓查询处理算法(APSQCM)来完成该任务.APSQCM算法由两阶段组成,第一阶段捕获Q与缓存中临时轮廓快照间的内在关联,进而获取能够用来等价重构Q的所有轮廓基;而在第二阶段中,APSQCM算法使用轮廓基来快速产生Q的正确结果集.实验结果表明,APSQCM算法具有有效性和实用性.     

MapReduce框架下的查询结果共享

当前的大规模数据分析通常在MapReduce框架下执行查询。由于MapReduce框架本身的冗余性以及查询之间的重叠性,复用已有查询的结果可以大幅提高查询的执行效率。复用查询的结果需要对其进行存储和匹配管理,产生高昂的系统开销,抵消复用的部分效果。本文针对目前先进的查询结果复用系统ReStore在管理查询结果和匹配中存在的效率低下的问题,提出森林结构的Job存储管理技术和与之相适应的匹配算法,提高查询的匹配效率,减少系统的开销。为了使系统能够充分复用已执行查询的结果,本文提出对多个查询进行预处理的方案,通过改变各查询进入Pig编译器进行编译的顺序,从而改变Job的执行顺序,使得加载相同数据集的Job同时执行,减少与存储库进行匹配的次数。实验表明：在构建存储结构与匹配已有结果过程中,本文提出的方法与ReStore相比,节约16.3%的时间开销,伸缩性也更好。     

Parallel bulk-loading of spatial data with MapReduce: An R-tree case

Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases.To solve this problem,a novel method of bulk-loading spatial data using the popular MapReduce framework is proposed.MapReduce combines Hilbert curve and random sampling method to parallel partition and sort spatial data,thus it balances the number of spatial data in each partition.Then the bottom-up method is introduced to simplify and accelerate the sub-index construction in each partition.Three area metrics are used to test the quality of generated index under different partitions.The extensive experiments show that the generated R-trees have the similar quality with the generated R-tree using sequential bulk-loading method,while the execution time is reduced considerably by exploiting parallelism.     

多核处理器下SKLOIS多级安全数据库查询方法研究

针对传统方法存在多核处理器下SKLOIS多级安全数据库查询不准确的问题,提出一种新的多核处理器下SKLOIS多级安全数据库查询方法。用一个加权有向图对多核处理器下SKLOIS多级安全数据流图进行描述。为数据流图中所有结点分配一个内核。依据数据流图中规定的执行顺序执行给定查询语句,完成查询语句的并行执行。查询语句通过LBT树模型获取,通过定义三种多核处理器下的SKLOIS多级安全数据库查询类型获取LBT搜索空间大小的上界和下界。搜索整个查询执行计划空间,获取一个具有最小开销的LBT查询树,给出LBT方法的查询代码。实验结果表明,所提方法具有很高的查询响应速度,且针对更新数据具有快速适应能力。     

基于窗口查询的轮廓查询算法

轮廓查询在涉及多标准决策的空间数据库应用中起着非常重要的作用,轮廓的计算在数据库通信方面受到很大关注,特别是无需访问所有的数据文件就能很快的返回轮廓中的点的算法.本文提出一种基于窗口查询的轮廓查询算法,通过不断变换查询窗口来缩减查询空间,所访问的空间数据点数目大大减少,查询结果有很好的健全性和完整性.