扩展的锥形方向关系查询处理方法

通过加入距离约束,扩展锥形方向关系的描述方式,提出新的查询处理方法——扩展锥形方向二叉树,该方法能处理方向空间连接的查询过滤,通过组合方向和距离关系,提高定性推理的准确性。与传统基于索引的方法相比,该方法能够有效处理大数据集中任意对象间方向关系的查询和定性推理,实现简单、查询效率和推理准确性较高。     

多路R树连接的加权处理

空间连接运算是空间数据查询中最重要、最耗时的基本操作之一,其中基于R树的空间连接(RJ)被认为是一种高效的处理机制,但在空间连接的精化阶段处理复杂的空间数据时需要很大的系统开销。基于MBR及直接查询谓词,提出了一种加权处理方法,并扩展了R树结构及MRJ算法。从而优化了多路R树连接的筛选处理,能得到更加有效的候选集;同时,减少了磁盘访问次数,可节省CPU及I/O的时间开销。还通过应用实例验证了其在空间数据库查询优化方面的优势。     

RTC树的构建与不确定近邻关系查询方法

空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.     

一种面向大规模空间文本数据的空间结构匹配算法

为了支持各类基于位置的服务,人们提出了各种查询和搜索空间文本数据的方法和技术.传统的空间关键字查询和近期提出的空间模式匹配不支持用户定义查询关键字对象以及对象之间细致的空间结构关系,使得查询结果集庞大但无效结果偏多,不能满足用户高效且精确的查询需求.本文因此提出了一种新的查询模式——空间结构匹配查询(Spatial Structure Matching,SSM),允许用户定义一组查询关键字对象并指定任意两个对象之间的距离和方向约束.为了解决SSM查询问题,本文首先提出了一种基于多路连接的基准方法,将SSM查询问题分解为单个对象的关键字匹配,两个对象的边匹配和多个对象的聚合匹配.为了提高SSM查询效率,本文提出了基于扫描线算法的边匹配计算,利用对象的地理位置信息来降低边匹配计算开销.本文利用同时满足查询关键字,距离和方向约束的空间对象构造对象连接图,从而将SSM查询问题转换为在对象连接图上搜索与SSM查询结构同构的子图匹配问题,并且利用经典的子图同构匹配算法求解获得最终的查询结果.在四个大规模空间文本数据集上的实验结果表明,本文所提算法的查询效率远高于对比算法,返回的查询结果集精简有效且...     

基于MBR&IR的拓扑关系查询处理方法

为了提高空间数据库系统的查询效率,基于传统的拓扑关系查询方法,将内部最大矩形IR引入到R*树索引结构中,提出了基于MBR&IR的拓扑关系查询处理方法.该方法的基本思想是通过增加IR这一约束条件,在过滤步骤判断出满足查询条件的数据对象,排除不符合查询条件的数据对象,提高了过滤步骤的性能,减少了提纯步骤的系统消耗,从而提高了查询效率.实验结果表明,该方法在查询效率上优于传统的拓扑关系查询方法.     

基于观察者方位的方向关系及其查询处理

通过分析观察者本身及其方位特点,在基于投影的模型基础上,首先提出了一种新的基于观察者方位的方向关系模型.然后结合新模型的特点,对方向关系查询空间建立了R+-树索引,利用拓扑学和矩形代数理论,提出了三步过滤法用以减少索引空间,降低了R*-树中矩形的重叠区域,减少了查询路径.最后给出了方向关系查询算法.实验表明,与传统的基于投影模型的查询方法相比,新模型的基于观察者方位的查询方法节省了I/O时间,提高了查询效率.     

连续多方向区域查询的空间向量模型算法

针对判定空间对象间方向关系模型不能给出带有方向特征的定量分析,导致查询区域只是单方向开放区域的问题,结合向量运算和MB树,提出了一种能够解决连续开放区域的方向关系查询空间向量模型算法。该算法主要包括对查询目标进行过滤和提纯两个步骤。在过滤过程中,分析了查询区域与包含空间目标的最小边界矩形(MBR)顶点之间的位置关系,给出了相应的判断方法,利用MB树中MBR的有序性对被查询节点的MBR给出了有效的剪枝规则,从而使查询时能有效减少系统I/O;在提纯过程中,处理过滤步骤中筛选出来的与查询区域有交的MBR,从中找到位于查询区域中的目标点。实验结果表明,空间向量模型算法不仅可以解决单方向开放区域问题,而且能够有效地解决连续多方向区域查询问题,它在二维和三维空间都具有适用性。     

R树家族的演变和发展

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

一种空间数据挖掘查询索引的研究及应用

从数据库技术角度出发,对空间数据挖掘查询的数据库支持技术和空间数据挖掘系统与GIS数据库的集成技术进行了研究;首先介绍了空间数据挖掘与GIS的关系,及目前在该领域存在的一些问题和缺陷;然后提出了一种支持空间数据挖掘查询的索引和数据访问方法——距离方向连接索引(Distance-Direction associated Join Indices,DDJI),并给出了基于这种索引技术的空间数据挖掘算法及实现技术,研究了基于DDJI的各种空间数据挖掘算法的统一实现技术;实验研究证明,与传统方法相比,DDJI的实现方法在性能上具有较大优势。     

障碍空间中基于R+树的空间Skyline查询方法

为了解决已有研究成果无法有效解决障碍空间中的空间Skyline查询问题,提出了障碍物环境下基于R+树的空间Skyline查询方法——SOS算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用R+树的快速定位特性有效地剪枝掉大量被支配的数据点,缩小查询范围,提高算法效率。精炼过程主要根据障碍距离以及数据点与查询点间的拓扑关系对候选集中数据点进行二次筛选,最终得到Skyline集合。进一步给出新增点的ADD_SOS算法和删除点的DEN_SOS算法。理论研究和实验结果表明,该算法在处理障碍空间中的空间Skyline查询问题时具有优势。     

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.     

An Object Model of Direction and Its Implications

Direction is an important spatial concept that is used in many fields such as geographic information systems(GIS) and image interpretation. It is also frequently used as a selection condition in spatial queries. Previous work has modeled direction as a relational predicate between spatial objects. Conversely, in this paper, we model direction as a new kind of spatial object using the concepts of vectors, points and angles. The basic approach is to model direction as a unit vector. This novel view of direction has several obvious advantages: Being modeled as a spatial object, a direction object can have its own attributes and operation set. Secondly, new spatial data types such as oriented spatial objects and open spatial objects can be defined at the abstract object level. Finally, the object view of direction makes direction reasoning easy and also reduces the need for a large number of inference rules. These features are important in spatial query processing and optimization. The applicability of the direction model is demonstrated by geographic query examples.     

Adaptive and incremental processing for distance join queries

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in online query processing or Internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bidirectional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multistage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multistage algorithms outperform previous work by up to an order of magnitude for both k-distance, join and incremental distance join queries, under various operational conditions.     

Efficient processing of spatial joins with DOT-based indexing

A spatial join is a query that searches for a set of object pairs satisfying a given spatial relationship from a database. It is one of the most costly queries, and thus requires an efficient processing algorithm that fully exploits the features of the underlying spatial indexes. In our earlier work, we devised a fairly effective algorithm for processing spatial joins with double transformation (DOT) indexing, which is one of several spatial indexing schemes. However, the algorithm is restricted to only the one-dimensional cases. In this paper, we extend the algorithm for the two-dimensional cases, which are general in Geographic Information Systems (GIS) applications. We first extend DOT to two-dimensional original space. Next, we propose an efficient algorithm for processing range queries using extended DOT. This algorithm employs the quarter division technique and the tri-quarter division technique devised by analyzing the regularity of the space-filling curve used in DOT. This greatly reduces the number of space transformation operations. We then propose a novel spatial join algorithm based on this range query processing algorithm. In processing a spatial join, we determine the access order of disk pages so that we can minimize the number of disk accesses. We show the superiority of the proposed method by extensive experiments using data sets of various distributions and sizes. The experimental results reveal that the proposed method improves the performance of spatial join processing up to three times in comparison with the widely-used R-tree-based spatial join method.     

A Filter Flow Visual Querying Language and Interface for Spatial Databases

In this paper a visual approach to querying in spatial databases is presented. A filter flow methodology is used to consistently express different types of queries in these systems. Filters are used to represent operations on the database and pictorial icons are used throughout the language for filters, operators and spatial relations. Different granularities of the relations are presented in a hierarchical fashion for spatial constraints. The language framework and functions are described and examples are used to demonstrate its capabilities in representing different levels of queries, including spatial joins and composite spatial joins. Here, the primary focus is on the query language itself but an overview of the implemented interface of the language is also provided.     

DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B⁺-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART.     

空间聚类与方向关系的融合技术研究

在大数据量的环境下,传统空间数据的空间关系仅描述两个空间物体,从而出现数据存储冗余,检索速度慢等问题。提出改进的聚类算法对空间物体聚类,再在聚类结果的基础上表示空间物体的方向关系。提出了基于密度的K-均值算法和空间聚类与方向关系融合的新方法。所提方法增强了空间数据库对空间数据对象的空间方向关系的智能处理能力,节省了存储空间,提高了数据的查询速度。     

基于MapX的空间查询应用

空间查询是GIS应用系统的基本功能之一，空间查询的功能和效率是GIS应用系统的重要指标。本文讨论了利用MapX实现空间查询的方法，包括基本的图形与属性数据互查和基于空间关系的复杂查询，并给出了详细的实现方法和流程。     

Nearest Neighbor Queries in Shared-Nothing Environments

In this paper, we propose an efficient solution to the problem of nearest neighbor query processing in declustered spatial databases. Recently a branch-and-bound nearest neighbor finding (BB-NNF) algorithm has been designed to process nearest neighbor queries in R-trees. However, this algorithm is strictly serial (branch-and-bound oriented) and its performance degrades, during processing of a nearest neighbor query, if applied to a parallel environment, since it does not exploit any kind of parallelization. We develop an efficient query processing strategy for parallel nearest neighbor finding (P-NNF), assuming a shared nothing multi-processor architecture, where the processors communicate via a network. In our method, the relevant sites are activated simultaneously. In order to achieve this goal, statistical information is used. The efficiency measure is the response time of a given query. Experimental results, based on real-life and synthetic datasets, show that the proposed method outperforms the branch-and-bound method by factors.