三维GIS中混合树空间索引结构的研究

目的在空间数据库应用中，解决随着数据量的增加，单一的空间索引结构制约检索性能的问题．方法提出一种三维GIS中基于八叉树和R＊树的混合树空间索引结构OR＊树。该结构在对三维索引空间进行八叉划分的基础上应用R＊树索引技术，将操作空间限定在某一特定的区域．结果实现了R＊树以及OR＊树的试验程序，并通过均匀分布的随机数据测试了不同层数OR＊树的空间开销与插入、删除、查找所访问的磁盘页数．结论试验数据分析表明，该方法有效降低了R＊树的插入、删除与查询操作的开销。数据量越大OR＊树的效率越高．     

一种极小化交叠空间数据索引结构

针对现有的基于R-树和四叉树的空间索引结构中存在的问题,以减少兄弟节点间的交叠为目标,通过定义空间数据的排序方法对要索引的数据空间及其子空间按照数据的分布进行分割,使得索引树上每层节点间的交叠极小化,同时使树的高度尽可能低,建立了一种新的空间数据索引结构一QRMO树.给出了QRMO树的生成、节点插入和区域杳询算法及相应算法的町行性和正确性定理及时间复杂度分析.对新结构进行了中间节点交叠试验分析和对比,实验表明,新的索引结构上的同层节点问的交叠得到明显减少.     

R-树和四叉树的空间索引结构:RQOP_树

针对现有的基于R-树和四叉树的空间索引结构中存在的问题,通过建立数据矩形间的序关系对数据空间进行分割,提出了一种新的空间数据索引结构:RQOP树.在此结构中,节点的构造是按照空间数据的分布来进行的而不是像其它基于R-树和四叉树的空间索引结构只是对数据空间进行均匀划分而得到,使树的高度尽可能低,同时使兄弟节点间的交叠相对较小.在区域查询算法中引入了查询窗口包含节点MBR的判断加快了查询的速度.给出了RQOP树的生成、节点插入和区域查询算法,并给出了相应算法的可行性和正确性定理及时间复杂度分析.实验表明:新索引结构的查询速度明显加快.     

一种静态环境下的空间索引结构

R树作为目前最流行的动态空间数据索引结构,被广泛应用于原型研究和商用空间数据库系统中.R树的变体很多,但大多数应用于动态环境下,对于静态空间数据环境(指不更新或更新少的空间数据),R树及其变体虽然适用,但效率不高.本文在已有空间数据索引结构的基础上,根据静态空间数据的特点,提出一种新的适用于该环境的空间索引结构,该方法可减少I/O访问次数,提高空间查询效率.     

3DGIS中基于改进R树的空间索引技术研究

空间索引是GIS的重要技术之一。3DG1S作为新一代GIS技术的重要分支,其数据管理技术较二维地理信息系统复杂,迫切需要引入适应3DGIS环境的三维空间索引技术。作为一种高效的多维索引技术,R树及其变种已在二维地理信息系统中得到广泛应用。针对3DGIS的特点,通过改进R树的部分算法,和修改R树的数据结构,本文给出了一种适宜3DGIS数据管理的改进R树索引方法。基于三维地理信息系统平台GeoView3D开发的实例证明,改进R树索引较传统R树索引具有同层节点重叠率低,空间利用合理,空间操作快的优点,可以满足3DGIS中大场景数据的显示和查询等操作。     

嵌入式内存数据库查询算法改进

目前绝大多数嵌入式数据库系统中使用B树或B＋树索引机制,它的优点是效率高,能动态维持平衡。然而研究表明B树索引机制平均空间利用率仅达到50%左右。这对存储空间有限的嵌入式设备而言,存在浪费存储空间的问题。在比较和分析B树索引机制,AVL树索引机制,HASHAVL树索引机制的实现思想及其优缺点后,提出了基于B树的查询改进算法,该算法能够解决B树中存在的顺序查找效率低的问题,保留了随机查找空间利用率高的优点,为实时性要求不高和资源有限的嵌入式系统提供了更好的数据查找方法。     

受限空间连接查询及代价分析

针对已有的空间连接查询算法无法解决限定范围内的空间连接查询问题,提出了受限的空间连接查询,在给定查询范围内找到满足某种空间谓词的空间对象,给出直接解决方法和基于R-树的受限空间连接查询算法.基于QR树的优良特性,提出一种基于QR树的受限空间连接查询算法,该算法既避免了四叉树的较大存储代价,又克服了R树的节点重复的弊端,使得受限空间连接查询可以在多棵较小的R树上进行,较好地解决了空间连接查询开销较大的问题.对所提出的算法进行代价分析,实验证明算法具有较高效率.     

一种改进的桶载入PMR四叉树算法

PMR四又树是一种基于线性四又树的空间数据结构，能存储任意类型的空间对象，其算法是在刷新内存中的节点到磁盘之前，把尽可能多的四又树装入主存，关键思想是以某种方式排列输入数据使得磁盘上的部分不会被再次插入，对桶载人PMR四叉树的算法做了适当改进，使得四叉树的构造速度相对于原有的构造方法大大提高，桶载人PMR四叉树的性能有所改善，并可运用到许多基于规则划分的空间数据结构上。     

基于改进QR-树的空间数据索引的研究

分析了基于常规QR-树建立空间数据索引的数据结构,常规四叉树在数据量特别大时．导致其QR-树深度特别深,占用空间大,查询效率低,并且平面区域分割极限的确定很不灵活。提出了一种改进QR-的数据模型来建立高效的空间数据索引,通过检测水平和垂直相交区域以确定图元所属节点,从而实现海量数据的快速检索。     

一种基于空间划分树裁剪外包框的空间索引方法

空间数据库中,基于R树的时空索引使用最小外包框对时空数据进行近似以提高查询效率,通过裁剪外包框的冗余空间可以进一步提高索引的效率.针对这一问题,提出了一种基于CBB的改进的时空索引方法.首先,将优化方法从平面二维拓展到了时空维度中,计算可能的裁剪点,在空间索引中记录外包框中的冗余空间范围,对索引节点外包框的裁剪空间进行...     

DPHI-Tree:一种新型的并行高维主存索引树

随着主存技术的发展,系统级分布式主存多媒体数据库存储规模不断扩大,查询越来越复杂,分布式并行索引以其高性能而逐渐成为解决此类复杂查询问题的有效手段.文章提出一种新的适合于分布式并行索引的树结构--DPHI-Tree.该索引树以B树为基础,利用PCA降维技术,将树的各层节点采用不同的维度表示,提高了缓存空间的利用率,降低了CPU负载.另外,采用标识根到节点路径的二进制编码来对节点索引,在查询数据量急剧增加时,PHI-Tree对基于树的数据随机访问具有良好性能.     

面向动态环境的移动对象自适应索引方法

为适应动态变化的应用环境,提高索引的综合性能,提出一种自适应的移动对象索引--STBx树.给出了STBx树的索引结构、更新算法和查询算法,并且在性能分析的基础上给出了STBx树进行自适应调节的方法.STBx树以自学习和自适应的运行,在不打断服务的情况下对自身的更新性能和查询性能进行调节,从而达到最佳的平稳的综合性能,以适应更新操作和查询操作的比例以及性能需求动态变化的环境.实验表明：STBx树在动态应用环境下能够实现自适应的调节,并提供优秀的综合性能,优于传统的TPR*树和Bx树.     

基于四叉树的凸多边形查询算法

针对四叉树索引的开窗查询算法的局限性,本文改进了现有的四叉树索引结构,并在此结构上提出了基于四叉树的凸多边形查询算法,此算法特别适合于航空GIS当中的“飞机不动地图动”的显示模式,能大幅度提高显示效率.     

基于XML的数字地下空间索引QR树研究

为了提高数字地下空间数据库的存储效率与检索性能,设计基于可扩展标记语言(XML)的数字地下空间索引四叉矩形(QR) 树.该索引将检索过程涉及到的空间限制在整个索引空间的某一部分,XML利用其结构化的特点,改进了传统QR树索引文档与数据结构之间需要序列化的缺点,改善了因数据激增而下降的查找性能;同时利用XML的可扩展性,实现对索引信息规范化、结构化的描述,实现索引文档存储和数据结构组织的显式描述,解决了QR树存储开销较高、结点上溢和下溢问题,实现QR树动态维护,提高索引的稳定性.     

四叉树期权定价的一个反例

期权定价的方法有许多种,其中以二叉树图法最为直观与简单,它是标的资产价格连续时间模型的一种离散形式.从Kamiad B.开始又出现了许多对三叉树定价的研究,基于标的资产价格出现的不同可能性,本文对四叉树图进行了简单分析,并以一种特殊情况的四叉树为例证明了四叉树的期权定价并不是对所有的情况都成立.     

基于网格索引的Top-k偏好查询算法

目的设计基于网格索引的Top-k偏好查询算法,提高Top-k偏好查询问题的解决效率.方法利用网格索引,采用概念划分的方法,实现基于范围查询和NN查询两种方式的Top-k偏好查询算法.结果通过真实数据集测试结果表明算法能够结合网格索引的优点,与基于R树索引的传统算法相比,在k值不断增加的情况下,查询效率提高了50%,能适应多种空间特征数据对象集合.结论网格索引可以有效处理Top-k偏好查询.     

基于道路网络的移动对象全时态索引与查询

基于固定网络的移动对象索引MON树采用两层R树和一个散列表结构,该索引能有效地实现了对网络环境下的移动对象过去信息的索引与查询,但却不能实现对当前和将来信息的索引,针对这一问题,本文对MON树进行了扩展,使其能实现对移动对象过去、当前和将来信息的全时态索引,并在此基础上实施了范围查询。     

交通网络中移动对象定点CRNN查询算法

目的在交通网络中实现移动对象的定点CRNN查询监控,确定受到定点影响的移动对象集合.方法根据交通网络的特征,定义网络中RNN的概念,采用PMR四叉树来索引交通网络结构,利用监控树来简化对网络上移动对象的计算判断和监控.结果测试显示该算法能够针对现实交通网络,实现定点CRNN的查询监控.结论实验表明,在移动对象和查询数量增大时,该算法显示出较好的伸缩性.     

海量空间矢量数据综合研究

为支持不同分辨率、不同比例尺对地图的新要求,研究了海量空间矢量数据的组织方式,提出了基于全球四叉树的空间矢量数据的综合方法和准则,这些方法和准则可实现对海量空间数据中的点、线、面分别处理,合理分配它们在全球四叉树中的存储空间,研究成果很好地解决了海量空间数据的高效存取问题。     

反向最远设施查询及其代价模型的研究

针对现有反向最近邻查询不能有效支持满足弱影响集的设施查询这一类问题,利用离散边界点及邻域区等概念和相关定理实现对反向最远邻的判定.在此基础上提出反向最远设施查询,并给出其选择查询算法及索引结构.该算法可以准确地得到反向最远设施查询的结果,其动态更新算法可实现对查询点的反向最远设施查询结果的更新.在R~*-树的基础上构建RFF-树,并给出其选择查询算法的代价模型.实验结果表明,在3种不同数据分布空间中,采用基于RFF-树的反向最远设施选择查询的实际页面访问次数与代价分析预测的结果相近,代价模型的平均误差率约为12%.