虚拟旅游中海量3D点云数据的细节层次索引技术研究

虚拟旅游中的3D点云数据特别庞大,批量索引成为了当今的研究热点。许多索引树存在兄弟结点空间区域重叠、不能实现细节层次索引、索引效率低等问题。为此,将点数据反射强度和细节层次技术引入R树,在改进R树的基础上提出LODR树。建树前,将点云数据进行排序、分组、去除空间重叠等预处理。树的每层设有不同反射强度阈值,把叶结点中满足阈值条件的索引记录沿父-祖父-曾祖父的家谱关系上移,并插入对应的非叶结点,利用该方法创建细节层次索引树。利用反射强度控制数据冗余,棱锥裁剪技术实现查询优化。实验结果表明,LODR树在细节层次索引、查询效率等方面具有明显优势。     

基于CURE聚类算法的静态R树构建方法

R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。     

基于KD树和R树的多维云数据索引

针对云存储系统大多基于键值对模型存储数据,多维查询需要对整个数据集进行完全扫描,查询效率较低的问题,提出了一种基于KD树和R树的多维索引结构(简称KD-R索引)。KD-R索引采用双层索引模式,在全局服务器建立基于KD树的多维全局索引,在局部数据节点构建R树多维本地索引。基于性能损耗模型,选取索引代价较小的R树节点发布到全局KD树,从而优化多维查询性能。实验结果表明：与全局分布式R树索引相比,KD-R索引能够有效提高多维范围查询性能,并且在出现服务器节点失效的情况下,KD-R索引同样具有高可用性。     

支持线段查询索引结构CB树

在空间数据库中点、线段和区域是构成向量对象的三种基本实体。现有的索引结构能够将点或区域对象有效地组织成散列或分层目录,并且提供精确的检索方法。然而,这些索引结构索引线段时会出现以下问题。索引结构不能准确地表示线段的空间信息,这将阻碍对线段空间数据的高质量存储。位于层次目录中节点之间将产生大量死空间和重叠区域,随着时间的推移这将降低系统性能。提出一种采用数据压缩的索引结构CB树。与R树索引结构相比,CB树具有较优查询效率,占用较少存储空间。     

基于聚类的Hilbert R-树空间索引算法

R-树适合于动态索引,但空间重叠大,而Hilbert R-树也不能有效降低节点覆盖和交叠,直接影响R-树的查询效率。为适应大量的GIS查询应用需要,提出对Hilbert R-树节点进行聚类的索引算法,较好地解决相邻数据的聚类存放,使叶节点MBR面积减小,内部节点交叠降低,并对该算法进行实验测试和性能分析,结果表明该算法具有较高的查询效率。     

一种改进的XML压缩树索引技术

压缩树索引技术是XML数据压缩的热点问题之一,本文提出一种压缩树索引改进方法.针对压缩树在查询过程中不能很好的解决向上匹配与向下匹配的问题,改进方法引入正排索引和倒排索引.当查询到组一级时,利用正排索引可以快速的查找出以该组为父节点的子组.而选出符合值谓词的元素后,在进行向上匹配时利用倒排索引可找出该元素的父节点.新的索引方法在保留原压缩树索引优点的基础上,解决了压缩树索引在查询过程中匹配问题.     

一种全新的 R树节点选择算法 *

在 R树插入算法中采用全新的节点选择算法 ,一改传统的从根节点开始自上而下的节点选择方案 ,而是从叶节点层开始 ,先自下而上再自上而下地选择叶节点 ,较好地解决了同层节点重叠所导致的查询效率低下的问题。实验证明 ,提出的 R树空间索引方法 ,不仅在查询效率上明显优于 R*树,而且 R树生成的时间开销也减少了 50%左右 ,综合性能超过了 R*树 ,便于扩展到三维甚至多维空间中 ,以实现对空间数据和时空数据的高效查询功能。     

三维激光点云数据的可视化研究

大量的点云数据是通过三维激光扫描得到的,而点云数据的显示快慢受到了数据索引的直接影响,这是一个基础性问题。经过研究,八叉树与叶节点KD树相结合的混合空间索引结构以及LOD构建的层次细节模型是用来解决点云数据管理与可视化效率不高的问题的有效方法。在局部,通过在叶子节点中构建的KD树实现高效的查询和显示;在全局,为了实现快速检索与调度使用了八叉树模型。采用这种混合数据模型进行点云组织,建立空间索引,并对点云数据进行LOD构建,实现了点云数据的高效检索以及可视化。     

基于Spark的3D点云数据空间索引技术

针对Spark引擎不支持多维空间查询的问题,提出基于R树的二级空间索引,即在每个Worker节点上创建R子树,并将这些子树作为孩子,在Master节点上创建R树。针对LRU算法内存替换粒度粗、结果不够精确的问题,提出基于数据使用权重的内存替换方法。该方法将每次实际使用数据量与其总量的比值作为替换权重,将热点场景数据以RDD形式持久化至内存中,提高了基于内存查询的效率。根据远粗近细的视觉原理提出细节层次查询,该方法 将最能代表物体特征的点云数据先传输给客户端,或者仅把简化模型点数据传给客户端,以解决网络带宽不足和数据加载延迟的问题。实验证明,文中方法能有效解决Spark多维空间的查询问题,查询效率得到了明显提高。     

IRT树索引结构的研究

论文针对R树在处理一些特定空间数据对象集时的不足,研究了基于最小外接直角等腰三角形(MIRT)的新的索引结构—IRT树。探讨了IRT树的空间平面划分和空间数据结构特征,给出了IRT树的节点分裂算法和搜索算法。进一步对IRT树和R树进行了比较分析。由分析可知,对于一些特定数据集,IRT树在查询准确率、数据存储和空白空间冗余方面均有一定的优势。     

一种散乱分层点云的有序化精简方法

针对激光扫描仪所得点云散乱分层的特点,提出一种有序化的精简方法。首先基 于已知标记点建立三维R-tree 和八叉树集成的空间索引,快速准确地获取局部点云数据,保证 良好的数据检索效率。然后根据局部点云数据的参考平面法向量信息,选取工件坐标系中的一 个坐标轴作为参数化的方向,对局部点云数据进行参数化并拟合二次曲面。最后对R-tree 叶节 点内的二次曲面进行有序化采样,使散乱分层的点云变为单层,得到整个型面的有序参考点集。 应用实例表明,该方法适用于大规模的、具有复杂几何特征且存在一定程度散乱分层的点云, 可以有效地提高数据点的整体精确度,且不会丢失点云的细节特征,具有较强的实用性。     

基于结点分裂优化的R-树索引结构

针对R-树索引空间查询效率低下的问题,提出一种基于结点分裂优化的R-树索引结构：SR-树索引。SR-树索引在结点分裂过程中,通过增加叶子结点的空间数据聚集性来减少叶子结点最小外接矩形的覆盖面积。为了有效降低磁盘读写消耗,SR-树结点在写入索引时,首先将索引树在内存中建好,然后在文件中写入树信息,最后通过递归的方式写入结点。实验结果表明,与R-树索引相比,SR-树索引可以在减少最小外接矩形重叠面积的同时,有效降低查询响应时间,从而达到提高查询效率的目的。     

时空相点移动对象数据索引PM-Tree

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点是如何提高窗口查询的效率.这类索引通常以同一线路为单位来组织轨迹数据的存储.索引通常采用两层的R-tree索引结构,上层的2D R-tree用于索引在某个区域内的线路,下层的2D R-tree用于索引某个时间段内在这些区域的移动对象.这类索引在处理轨迹信息的时间维度的时候,仅仅是把时间维度等同于空间的维度来进行R树维度的扩展.由于R树算法不能有效地降低最小限定矩形的空间堆叠问题,尤其是在数据量较大、数据维数增加时表现得更为明显.所以,为了提高路网中移动对象时空信息的存储以及查询的效率,本文则将轨迹信息中的时间数据和空间数据整合起来,提出了一种移动对象数据索引PM-tree(Phase-point Moving Object Tree).首先运用映射函数把路网中移动对象运动轨迹的二维时空矩形投影成带参数的一维"时空相点",并讨论了时空相点之间的偏序关系,建立了基于相点偏序划分的相点序分枝结构,为索引的建立提供了理论支撑.接着论文以MON-tree索引为基础,以相点序分枝结构来改进其下层索引结构,提出了时空相点移动对象数据索引,该索引能完成运动轨迹时空的一体化查询,能避免类R-tree索引中最小限定矩形堆叠导致的效率低下的问题,有效地缩小搜索空间.最后论文实现了索引的增量式动态更新管理.通过实验的对比分析,表明PM-tree索引不但能有效提高储存空间的利用率,"一次一集合"的查询模式还提高了查询性能.     

一种基于R-树的空间索引结构

为了有效构建R-树,通过分析数据矩形的性质,结合改进的K-均值算法,提出一种用于构建R-树的数据矩形聚类新方法,给出基于R-树和四叉树的空间索引结构以及该空间索引结构的构造算法和节点插入算法。研究结果表明,该索引结构具有更紧凑的结构和更高的空间查询效率。     

A new double sorting-based node splitting algorithm for R-tree

A storing of spatial data and processing of spatial queries are important tasks for modern data-bases. The execution efficiency of spatial query depends on underlying index structure. R-tree is a well-known spatial index structure. Currently there exist various versions of R-tree, and one of the most common variations between them is node splitting algorithm. The problem of node splitting in one-dimensional R-tree may seem to be too trivial to be considered separately. One-dimensional intervals can be split on the base of their sorting. Some of the node splitting algorithms for R-tree with two or more dimensions comprise one-dimensional split as their part. However, under detailed consideration, existing algorithms for one-dimensional split do not perform ideally in some complicated cases. This paper introduces a novel one-dimensional node splitting algorithm based on two sortings that can handle such complicated cases better. Also this paper introduces node splitting algorithm for R-tree with two or more dimensions that is based on the one-dimensional algorithm mentioned above. The tests show significantly better behavior of the proposed algorithms in the case of highly overlapping data.     

空间区域聚集查询方法研究

为了提高空间数据仓库中区域聚集查询的响应性能,通过使用R_tree对空间维进行分层后,采用物化视图存储空间对象及R_tree中间结点的聚集信息,能够有效地支持空间维和非空间维上的区域聚集查询。