空间查询处理技术综述

空中索引是依据空间对象的位置和形状或空间对象间的某种关系,按照一定顺序排列的一种数据结构。不同方式组织起来的索引结构需采用不同的检索方法,因此空中索引在一定程度上决定了空间查询处理的效率。回顾了常用的空间查询处理方法,并对现有的空中索引结构及空间查询处理技术进行了系统分类,分别对欧式空间、道路网络及无线广播环境下用于空间查询处理的空中索引及查询算法进行了详细描述。     

HBase中基于时空特征的监测视频大数据关联查询研究

针对传统的时空索引构建、维护困难且实时查询效率低等问题,首先提出基于HBase的时空索引构造方法。该方法采用HBase作为监测视频大数据时空特征索引结构,通过Z填充曲线对空间特征进行降维存储,并利用时间、空间和属性特征之间的关联及依赖规则来安排rowkey索引键,可有效解决传统的时空索引构建、维护困难的缺陷。此外,针对传统的时空索引实时查询效率低的问题,进一步提出了基于Z曲线的时空关联查询算法,该算法对查询空间计算Z值范围和建立空间划分子集,利用划分后的时空特征进行列索引查询得到候选数据集并反查HBase索引表完成关联查询。实验结果表明,与传统的R树索引算法相比,提出的基于HBase的时空索引构造方法索引插入效率更高,提出的基于Z曲线的时空关联查询算法能够快速高效地处理时空关联查询。     

道路网络环境下的近似反k最近邻查询算法

针对欧式空间中基于R树索引结构的反最近邻查询技术不适用于道路网环境,利用任意度量空间中的M树索引结构代替R树索引结构,进行道路网络中的反最近邻查询处理.然而,由于网络距离的计算代价高的问题,使得基于M树索引的反k最近邻查询效率很低.因此,采用道路网络嵌入技术,映射道路网络到高维向量空间,简单的L∞距离准确近似计算网络距离.在此基础上,提出道路网中近似反k最近邻查询的ARkNN算法,并对本文L∞距离近似网络距离的质量、k-中心聚类算法选取参考点的有效性和ARkNN算法的查询效率进行了实验验证.     

XML-enabled空间数据库的索引系统

基于可伸缩矢量图形空间信息表达模型和合理的数据库结构,提出空间索引算法优化选择策略。结合设计模式思想,设计高内聚、低耦合的空间数据索引系统。该系统具有并行建立空间索引的能力,能实现异构XML-enabled空间数据库并行查询。实验结果证明,其检索效率比普通SQL查询高约66%。     

MSCR树：一种移动终端电子地图索引结构

现有空间数据索引结构并未同时考虑移动终端电子地图的多比例尺特性及嵌入式设备性能的限制,造成对大区域进行空间查询操作时装载开销过大。深入分析了多种空间索引结构的特点,提出一种新的空间索引结构——MSCR树索引结构,该结构将多级地图中的空间元素线性化,同时以压缩的方式存储空间元素外包矩形数据以提高数据读写效率。实验表明,MSCR树算法有效地提高了查询性能与空间利用率。     

一种基于受限网络的移动对象索引结构

为了提高受限网络中移动对象索引效率和满足近邻查询需求,基于FNR-Tree索引结构和Geohash编码算法,提出一种能够满足近邻查询的移动对象索引结构RNR(restricted network R-Tree).通过添加哈希表、链表等辅助索引结构来提升索引结构操作效率,融合Geohash编码和相关算法来使得索引结构能高效满足近邻查询的需求.通过将指定区域按一定规则划分,可使得索引结构具备在不规则范围查询的能力.使用旧金山市地理数据和移动对象数据对索引结构性能进行了测试,结果表明RNR具有较高索引结构操作效率,并且能够高效地提供窗口查询和近邻查询的功能.     

基于Voronoi划分的位置数据KNN查询处理方法

K最近邻(KNN)查询是空间数据查询研究的重要内容。目前的KNN查询方法在处理大规模的位置数据时,存在着更新和查找失衡的问题,导致查询效率较低。因此,提出基于Voronoi划分的位置数据KNN查询处理方法。首先,创建了一个二级空间索引结构——VRI,包含VHash和VR树两部分。一级索引结构VHash表示Voronoi图的直邻;二级索引结构VR树,按照各Voronoi单元所在的最小矩形区域的重叠面积,自下而上地生成对应的R树。其次,基于VRI索引结构提出了位置数据的KNN查询算法及动态维护算法,在KNN查询方法中,采用VR树进行定位,VHash查找K近邻,能够有效地对查询点定位,查找速度快。再次,针对数据更新的情况,索引结构也能够及时更新,在更新的时间段内,对于位置数据随时间变化的KNN查询,提出了利用记录表进行有效查询的方法。最后,实验表明,提出的基于Voronoi划分的空间索引结构和其对应的KNN查询算法均具有较好的性能和适应性。     

一种有效的空间数据仓库区域聚集查询索引结构

空间数据仓库有效地支持对空间数据的管理和分析，提供更加全面的决策支持．讨论了一种有效的空间决策支持手段——空间区域聚集查询的实现．基于aggregate cubetree和aR—tree提出了一个可以有效地在空间维和非空间维上进行区域聚集查询的索引结构aCR-tree及其相关算法，并计算分析了查询算法的时间复杂度．与现有技术相比aCR-tree降低了存储代价和每次查询访问的节点数，通过实验证明，该索引结构可以提供较好的存储性能和查询性能．     

空间数据库中的一种混合索引结构的研究

空间索引是实现空间查询的关键技术,其性能的好坏直接决定着空间数据的存储效率及空间查询的性能。为了提高空间查询效率,提出一种混合空间索引结构松散QR-树：LQR-tree。针对已有的QR-树索引结构在节点分配中,可能存在较小的对象落入较大的节点中的问题,将松散四叉树和R-树相结合,能够实现节点下移,优化处理移动空间对象的查询,给出LQR-tree的结构和插入删除算法,并提出对应算法的相关定理和证明。     

一种基于二层网格的移动对象B+树索引

在已有的基于空间分割的移动对象B+树索引基础上,提出一种分割空间的新方法,对空间进行二层网格分割,使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明, 该索引结构的性能基本不受移动对象分布的影响。     

一种GIS自适应层次网格空间索引算法

分析了目前常用的空间索引算法的缺点,对应用最为广泛的网格空间索引数据结构进行了剖析;在描述了网格空间索引算法的同时,依据空间实体外接矩形的几何特性,给出了具有自适应能力的改进型网格空间索引算法———自适应层次网格空间索引算法;最后分析了此算法的自适应性和索引效率。     

A general method for maximizing the error-detecting ability ofdistributed algorithms

The bound on component failures and their spatial distribution govern the fault tolerance of any candidate error-detecting algorithm. For distributed memory multiprocessors, the specific algorithm and the topology of the processor interconnection network define these bounds. This paper introduces the maximal fault index, derived from the system topology and local communication patterns, to demonstrate how a maximal number of simultaneous component failures can be tolerated for a particular interconnection network and error-detecting algorithm. The index is used to design a mapping of processes to processor groups such that the error-detecting ability of the algorithm is preserved for certain multiple simultaneous processor failures     

基于柯西分布和父种轮换机制的种子优化算法

针对目前种子优化算法存在的空间探索能力不足、后代个体分布多样性较弱的问题,文中提出基于柯西分布和父种轮换机制的种子优化算法.首先,构建基于柯西分布的种群分布模型,用于前期探索阶段,提升算法的全局搜索能力.然后,建立基于赌轮法的父种轮换机制,提高后代种群的多样性.最后,构建个体距离阈值、分布方差和后代比例的自适应调整机制,提高算法对复杂优化问题的动态寻优能力.实验表明,文中算法的平均适应度值和弗里德曼检测指标排名均较优.     

面向移动GIS的动态四叉树空间索引算法

介绍了常用的空间索引算法，对其性能进行了比较，认为这些算法用于需要动态更新空间索引结构的移动GIS系统中时具有较大的局限性。针对移动GIS系统中对空间索引的特殊要求，提出了动态四叉树空间索引算法，对算法的计算效率进行了分析，实验表明该算法用于移动GIS系统时效果良好。     

基于序号索引的空间关联规则挖掘算法

针对空间关联规则挖掘算法的冗余计算问题,提出一种基于序号索引的空间关联规则挖掘算法。该算法适用于挖掘单层横向空间的关联规则,在自底向上和自顶向下的搜索过程中,用定序操作产生序号索引,通过序号索引在双向挖掘过程中修剪重复候选项和删除冗余计算,以提高算法效率。实验结果证明该算法比现有的算法更快速有效。     

云计算环境下资源调度系统设计与实现

在云计算环境下,对开放的网络大数据库信息系统中的数据进行优化调度,提高数据资源的利用效率和配置优化能力;传统的资源调度算法采用资源信息的自相关匹配方法进行资源调度,当数据传输信道中的干扰较大及资源信息流的先验数据缺乏时,资源调度的均衡性不好,准确配准度不高;提出一种基于云计算资源负载均衡控制和信道自适应均衡的资源调度算法,并进行调度系统的软件开发和设计;首先构建了云计算环境下开放网络大数据库信息资源流的时间序列分析模型,采用自适应级联滤波算法对拟合的资源信息流进行滤波降噪预处理,提取滤波输出的资源信息流的关联维特征,通过资源负载均衡控制和信道自适应均衡算法实现资源调度改进;仿真结果表明,采用资源调度算法进行资源调度系统的软件设计,提高了资源调度的信息配准能力和抗干扰能力,计算开销较小,技术指标具有优越性。     

基于QR树索引的面包含关系求解算法

为提高空间拓扑计算中求解面包含关系的效率,提出一种基于QR树索引的面包含关系求解算法。根据空间对象的几何信息建立QR树索引,利用QR树查找面包含的空间对象,并将该算法应用于基于线面包含关系的GML空间聚类。实验结果表明该算法能有效提高计算面包含关系的时间效率。     

一种基于HBase的空间关键字查询算法

针对传统关系数据库处理海量空间文本数据的不足,基于HBase数据库提出了一种结合Geohash编码与分词技术的空间文本索引方案,并基于该空间文本索引提出了一种多边形区域内的空间关键字查询算法。通过与传统经纬度索引方案的实验比较,验证了算法的高效性和可扩展性。     

一种基于混合聚类的空间索引算法

R-Tree允许兄弟节点之间的相互重叠,具有多路查找的特点,而Hilbert R-Tree也不能有效降低子空间的相互重叠,直接影响查询效率。提出了一种基于混合聚类的空间索引算法,将K-means和K中心点引入索引结构,改变了经典K-means算法对初始聚类中心的随机选取,减少了叶节点的MBR面积和各个子空间的重叠。通过实验表明,该算法具有更快的响应速度和查询效率。