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

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

PAA:海量数据上一种有效的近似聚集查询算法

聚集查询是一种常用但是耗时的数据库操作.相对于准确查询,以少得多的响应时间向用户返回满足置信区间的近似结果通常是一种更好的选择.现有的近似查询方法无法在海量数据上高效地处理满足任意精度的近似聚集查询.提出一种新的算法PAA(partition-based approximate aggregation)来有效处理满足任意置信区间的近似聚集.维属性的数据空间被划分为同样大小的空间区域,每个分片维护着维属性落入对应空间区域的元组.PAA算法维护表的随机样本RS,其执行包括两个阶段.在阶段1,如果利用预构建的随机样本RS不能返回满足用户要求的近似结果,那么在阶段2,PAA算法从与查询区域相交的空间区域对应的分片集合IPS中获得更多的随机元组.PAA算法的特色在于:1)如何在不知道IPS包含的每个分片满足谓词的元组数量情况下,从IPS中获得需要的随机元组;2)如何有效减少阶段2中的随机I/O费用.实验表明,相对于现有方法,PAA算法可以获得两个数量级的加速比.     

空间数据立方体的空间度量聚集*

叙述了空间数据立方体空间度量的基本定义;描述了空间度量的聚集概念,并结合具体图例讲述了点状、线状、面状空间度量的聚集过程;解释了空间数据立方体维上钻、维下翻、维层次上钻、维层次下翻的空间度量聚集操作基本原理。     

用于索引视域的凸多边形树

智能手机等设备在拍摄照片和录制视频时会将拍摄位置和光学参数记录到影像文件中,可以提取并利用这些信息,在二维平面空间中还原出图片所对应的扇形视域(field-of-view,FOV).将影像文件及其对应的FOV存储在计算机中,用来支持用户对影像文件的空间查询.一种典型的空间查询是用户在地图上指定查询区域,计算机找出拍摄到...     

基于位图连接索引的复杂多维层次的连接和聚集算法

在ROLAP中往往涉及到大量数据的复杂即席查询，从SQL角度看，这些查询通常都包含多表连接和分组聚集操作。本文提出了一种连接和聚集操作的新算法JAMDHBJI，该算法充分考虑了ROLAP中复杂多维层次的特点，同时考虑到并非全部维都具有维层次的语义特性，将维层次编码和位图连接索引有效结合，把复杂的连接和分组聚集操作转化为在事实表上的区域查询，从而大大提高了连接和分组聚集的效率。理论分析表明该算法是高效的。     

路网数据流的预测聚集查询新方法研究

时空数据流的聚集查询技术已经成为数据库领域的研究热点。到目前为止,还没有一种有效的全时态聚集索引适用于非欧氏空间的路网数据流聚集查询。实现路网数据流的全时态聚集查询,必须解决:(1)路网的非欧氏空间特性问题;(2)路网上移动对象的重复计数、非均匀分布以及预测聚集问题。Sketch RR-tree解决了非欧氏空间特性和重复计数问题;为解决非均匀分布问题,借鉴草图划分思想,提出动态草图索引结构DynSketch:采用AMH智能划分Sketch RR-tree,使每个划分区域内车辆均匀分布,以提高聚集查询质量;同时,基于DynSketch,结合ES预测模型,提出了路网数据流的预测聚集查询算法。     

集群上一种面向空间连接聚集的并行计算模型

单机运行环境难以满足海量空间数据的连接聚集操作对时空开销的需求,集群上的并行计算是高效处理海量空间数据的连接聚集操作的关键. Map-Reduce是云计算中一种应用于大规模集群进行大规模数据处理的分布式并行编程模型,分析发现,Map-Reduce并不直接支持以既高效又自然的方式来处理具有二次归约特征的并行空间连接聚集操作.因此,提出了一种并行计算模型——Map-Reduce-Combine（MRC）来有效地处理大规模空间数据的连接聚集操作.MRC在Map-Reduce 模型上增加一个Combine阶段,有效地合并分散在各个Reducer的部分聚集结果.针对并行任务划分中空间对象的单分配问题,提出了过滤优化算法,提高了MRC下处理空间连接聚集查询的效率.实验验证所提出的并行计算模型在处理空间连接聚集查询时具有良好的效率、有效性、可扩展性和简单性.     

加权路网空间中动态聚集最近邻居查询算法

聚集最近邻居（ANN）查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义,能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足：缺少针对大规模动态路网数据的高效索引结构,在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足,提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引,提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制（IER）算法结合起来的剪枝方法,以完成静态空间下的ANN查询;随后针对动态场景下数据点位置频繁更新的问题,加入时间窗口及安全区域更新策略,以减少算法的重复计算次数,实验结果表明效率能提高8%～85%;最后针对路网权重变化的ANN查询问题,提出两个基于校正的连续查询方法,在历史查询结果的基础上,根据权重变化的增量来得到当前的查询结果,在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明,所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。     

多维空间索引结构SHG-Tree(英文)

R-Tree及其变种的多维索引结构在数据的操作过程中通过对空间的分隔和不断调整将整个空间划分为大小不等的子空间以容纳足够的空间对象,这种方法能有效地实现多维空间对象的索引,但不能避免频繁的节点分裂与重组操作所造成的计算开销,也不能避免对叶子节点中的候选对象进行空间匹配所带来的计算开销。提出了一种能有效解决上述问题的索引结构:SHG-Tree。基于SHG-Tree的索引方法将多维空间划分为不同粒度的格子单元并将这些格子单元通过SHG-Tree按空间包含关系组织为层次树结构,同一层的格子互不相交且空间范围固定。空间对象通过文中提出的线性化方法转换为一系列不同粒度的互不相交的空间格子,进而将对象在其覆盖的格子中注册以实现空间对象至SHG-Tree的映射。查询操作只需将查询条件映射为相应的格子并取出这些格子中的对象作为查询结果。这种索引结构能有效减少节点的分裂和组合带来的计算开销,也解决了传统R-Tree索引中对于叶子节点中的候选对象进行区域匹配的计算开销。基于SHG-Tree的索引结构支持包括相交查询、区域查询、包含查询、top-N查询、k-NN查询等常用的多维查询,实验表明SHG-Tree能在毫秒级实现各种空间查询。     

基于聚集区域的强关联OLAP查询解决方案设计

聚集区域的OLAP查询解决方案是基于对数据仓库中数据立方体聚集区域认识的基础上提出的。它结合MO-LAP和ROLAP的特点,能够有效地识别出数据立方体中的聚集区域和稀疏点,通过不同的存储方式提高查询效率。基于上述思想,该文还提出了聚集区域查询(DSR)算法和严格约束的聚集区域查询(SDSR)算法,并对两种算法进行了仿真比较。     

一种加快WebGIS服务器响应速度的空间索引

WebGIS服务器向用户提供电子地图浏览服务.每一个请求/响应回合,服务器端都进行着具有多尺度特性的成批式数据访问.多尺度特性是指地图比例尺决定着地图显示内容的详略.基于R-tree的数据访问方法与多尺度性和成批性不相适应,存在"同级要素弱簇聚"和"I/O粒度偏小"两大问题,绘图数据访问效率不高.提出的多级R-tree能够解决上述两个问题.来自实验的统计数据表明,对于区域查询,基于多级R-tree的访问方法的效率明显高于基于R-tree索引的访问方法.使用多级R-tree能够有效地提高WebGIS服务器的响应速度.     

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树索引结构

针对现有R树无法支持空间数据多尺度表达的问题,提出了一种用于空间数据多尺度表达的R树变形索引结构:(1)允许空间对象出现在非叶结点上;(2)利用树的深度反映空间分辨率的变化,提供分辨率维的支持;(3)树的分支结构考虑对自动制图综合算法的支持.分析了该变形R树索引结构的空间数据多尺度查询过程,并着重对该索引结构生成算法中的约束条件、插入算法和分裂算法进行了讨论.针对相同数据源,使用该方法与基于四叉树的空间数据多尺度索引方法进行了对比实验,结果表明,该索引方法能有效检索多分辨率形式组织的空间数据,具有综合结果记忆功能,效率明显.     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

R树家族的演变和发展

近年来,针对空间数据库索引的研究引起了人们越来越多的兴趣和关注．为了快速、有效地处理存储于空间数据库中的海量空间数据,专家学者提出了大量的基于磁盘的空间索引方法．其中,1984年由Guttman提出的R树是目前最流行的动态空间索引结构,广泛应用于原型研究和商业应用中．其后,人们在此基础上针对不同空间运算提出了不同改进,经过20年的发展,不断产生的R树变体逐渐形成了一个枝繁叶茂的空间索引R树家族．该文回顾了R树及其各种主要变体;描述了基于R树的各种批量操作、空间查询处理算法、查询代价模型及查询优化过程;介绍了基于R树的并行处理、并发控制与锁定策略等方面的进展;并且分析了R树的未来研究方向．     

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

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

R-树结点分配的新算法

近年来,针对空间数据库索引的研究引起了人们越来越多的兴趣和关注。为了快速、有效地处理存储于空间数据库中的海量空间数据,专家学者提出了大量的基于磁盘的空间索引方法。其中,1984年Guttman提出的R-树是目前非常有效的空间索引结构。针对R-树的结点分配算法存在的不足,提出了一种新的结点分配算法。研究结果表明： 新的分配算法比原始的算法产生的交叠会更小,从而有效地控制了多路查询的几率,较明显地提高了空间查询的效率。     

面向多核处理器的空间数据库索引性能分析

空间数据库索引是提高空间查询性能的重要方法,片上多核处理器的出现,在提高数据库性能的同时,也给空间索引结构提出了新的挑战.面向多核处理器,还缺乏对各种主要空间数据库索引结构和性能的综合实验比较,从而无法定量分析影响索引性能的重要因素.针对目前主流的共享cache多核处理器,对R树,Hilbert R树、四又树及CR树在...