R*-树空间索引的优化研究

针对大型空间数据库应用的需求及己有空间索引技术的不足,在论述R-树及R*-树索引技术的相关概念、数据结构、算法描述及性能分析的基础上,提出了一种改进的R*-树空间索引结构。研究结果表明：改进后的R*-树与原始的R*-树相比具有更高的性能。     

Using B<Superscript>+</Superscript>-trees for processing of line segments in large spatial databases

Points, lines, and regions are the three basic entities for constituting vector-based objects in spatial databases. Many indexing methods (G-tree, K-D-B tree, Quad-tree, PMR-tree, Grid-file, R-tree, and so on) have been widely discussed for handling point or region data. These traditional methods can efficiently organize point or region objects in a space into a hashing or hierarchical directory. They provide efficient access methods to meet the requirement of accurate retrievals. However, two problems are encountered when their techniques are applied to deal with line segments. The first is that representing line segments by means of point or region objects cannot exactly and properly preserve the spatial information about the proximities of line segments. The second problem is derived from the large dead space and overlapping areas in external and internal nodes of the hierarchical directory caused by the use of rectangles to enclose line objects. In this paper, we propose an indexing structure for line segments based on B ⁺ -tree to remedy these two problems. Through the experimental results, we demonstrate that our approach has significant improvement over the storage efficiency. In addition, the retrieval efficiency has also been significantly prompted as compared to the method using R-tree index scheme. These improvements derive mainly from the proposed data processing techniques and the new indexing method.     

R*-树空间索引的改进

R*-树基于局部调整的思想对节点进行管理,存在时间与效率上的不足。为克服R*-树的不足,给出了一种新型的存储结构,并给出新型存储结构的插入、溢出、分裂等空间索引常用操作的算法。分析新的存储结构的优点,并通过实验结果说明该方案比R*-树具有更高的效率。     

Authenticated indexing for outsourced spatial databases

In spatial database outsourcing, a data owner delegates its data management tasks to a location-based service (LBS), which indexes the data with an authenticated data structure (ADS). The LBS receives queries (ranges, nearest neighbors) originating from several clients/subscribers. Each query initiates the computation of a verification object (VO) based on the ADS. The VO is returned to the client that can verify the result correctness using the public key of the owner. Our first contribution is the MR-tree, a space-efficient ADS that supports fast query processing and verification. Our second contribution is the MR*-tree, a modified version of the MR-tree, which significantly reduces the VO size through a novel embedding technique. Finally, whereas most ADSs must be constructed and maintained by the owner, we outsource the MR- and MR*-tree construction and maintenance to the LBS, thus relieving the owner from this computationally intensive task.     

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.     

Indexing moving objects for directions and velocities queries

Moving object databases are required to support different types of queries with a large number of moving objects. New types of queries namely directions and velocity queries (DV queries), are to be supported and covered. The TPR-tree and its successors are efficient indexes that support spatio-temporal queries for moving objects. However, neither of them support the new DV queries. In this paper, we propose a new index for moving objects based on the TPR*-tree, named Direction and Velocity of TPR*-tree or DV-TPR*-tree, in order to build data a structure based on the spatial, direction and velocity domains. DV-TPR*-tree obtains an ideal distribution that supports and fulfils the new query types (DV queries). Extensive performance studies show that the query performance of DV-TPR*-tree outperforms the TPR-tree and its successors.     

基于R树的空间数据索引技术的探索

目前,基于空间数据库管理系统的空间数据索引技术的研究与应用正不断地兴起,且日趋成熟。分析经典的空间数据索引技术R-树和R^＊-树的优势与特点,在R^＊-树索引结构的基础上融合了传统的四叉树索引方法的精髓,提出了一种改进的R^＊-树索引技术一即R^＊Q-树索引方法。设计并实现了R^＊Q-树索引方法中索引构造算法的主要改进部分,并采用大量的随机实验数据验证了改进算法对提高空间数据索引效率的有效贡献。     

Spatial join processing using corner transformation

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the R*-tree based algorithm proposed by Brinkhoff et al. (1993. 1994). This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations     

The clustering property of corner transformation for spatial database applications

Spatial access methods (SAMs) are often used as clustering indexes in spatial database systems. Therefore, a SAM should have the clustering property both in the index and in the data file. In this paper, we argue that corner transformation preserves the clustering property such that objects having similar sizes and positions in the original space tend to be placed in the same region in the transform space. We then show that SAMs based on corner transformation are able to maintain clustering both in the index and in the data file for storage systems with fixed object positions and propose the MBR-MLGF as an example to implement such an index. In the storage systems with fixed object positions, the inserted objects never move during the operation of the system. Most storage systems currently available adopt this architecture. Extensive experiments comparing with the R¹-tree show that corner transformation indeed preserves the clustering property, and therefore, it can be used as a useful method for spatial query processing. This result reverses the common belief that transformation will adversely affect the clustering and shows that the transformation maintains as good clustering in the transform space as conventional techniques, such as the R¹-tree, do in the original space.     

GLIP: A Concurrency Control Protocol for Clipping Indexing

Multidimensional databases are now beginning to be used in a wide range of applications. To meet this fast-growing demand, the R-tree family is being applied to support fast access to multidimensional data, for which the R+-tree exhibits outstanding search performance. In order to support efficient concurrent access in multi-user environments, concurrency control mechanisms for multidimensional indexing have been proposed. However, these mechanisms cannot be directly applied to the R+-tree because an object in the R+-tree may be indexed in multiple leaves. This paper proposes a concurrency control protocol for R-tree variants with object clipping, namely, Granular Locking for clIPping indexing (GLIP), dubbed an R+-tree variant, the Zero-overlap R+-tree (ZR+-tree). To the best of our knowledge, GLIP is the first concurrency control approach designed specifically for the R+-tree and its variants. The proposed GLIP supports efficient concurrent operations on R+-trees with serializable isolation, consistency, and deadlock-free. Experiment results on both real and synthetic data sets validated the effectiveness and efficiency of the proposed concurrent access framework.     

FIRST: Fractal Indexing and Retrieval SysTem for Image Databases

We present an image indexing method and a system to perform content-based retrieval in heterogeneous image databases (IDB). The method is based upon the fractal framework of the iterated function systems (IFS) widely used for image compression. The image index is represented through a vector of numeric features, corresponding to contractive functions (CF) of the IFS framework. The construction of the index vector requires a preliminary processing of the images to select an appropriate set of indexing features (i.e. contractive functions). The latter will be successively used to fill in the vector components, computed as frequencies by which the selected contractive functions appear inside the images. In order to manipulate the index vectors efficiently we use discrete Fourier transform (DFT) to reduce their cardinalities and use a spatial access method (SAM), like R*-tree, to improve search performances. The sound theoretical framework underlying the method enabled us to formally prove some properties of the index. However, for a complete validation of the indexing method, also in terms of effectiveness and efficacy, we performed several experiments on a large collection of images from different domains, which revealed good system performances with a low percentage of false alarms and false dismissals.     

多维索引hB树的改进方法——hB*树

本文在hB树基础上提出多属性索引方法——hB^*树.hB*树索引结点溢出时先寻求避免分裂,以期得到较好的空间利用率;通过避免和消除多父结点,使hB^*树成为严格的树形结构.本文表明hB^*树提高了空间利用率,树形化的代价也不高.     

Approximate retrieval of high-dimensional data withL 1 metric by spatial indexing

High-dimensional data, such as documents, digital images, and audio clips, can be considered as spatial objects, which induce a metric space where the metric can be used to measure dissimilarities between objects. We investigate a method for retrieving objects within some distance from a given object by utilizing a spatial indexing/access method R-tree, which usually assumes Euclidean metric. First, we prove that objects in discreteL ₁ (or Manhattan distance) metric space can be embedded into vertices of a unit hyper-cube in Euclidean space when the square root ofL ₁ distance is used as the distance. To take fully advantage of R-tree spatial indexing, we have to project objects into space of relatively lower dimension. We adopt FastMap by Faloutsos and Lin to reduce the dimension of object space. The range corresponding to a query (Q, h) for retrieving objects within distanceh from a objectQ is naturally considered as a hyper-sphere even after FastMap projection, which is an orthogonal projection in Euclidean space. However, it is turned out that the query range is contracted into a smaller hyper-box than the hyper-sphere by applying FastMap to objects embedded in the above mentioned way. Finally, we give a brief summary of experiments in applying our method to Japanese chess boards. Takeshi Shinohara, Dr.Sci.: He is a Professor in the Department of Artificial Intelligence at Kyushu Institute of Technology. He obtained his bachelors degree in Mathematics from Kyoto University in 1980, and his Dr. Sci. from Kyushu University in 1986. His research interests are in Computational/Algorithmic Learning Theory, Information Retrieval, and Approximate Retrieval of Multimedia Data. Hiroki Ishizaka, Dr.Sci.: He is an Associate Professor in the Department of Artificial Intelligence at Kyushu Institute of Technology. He obtained his bachelors degree in Mathematics from Kyushu University in 1984, and his Dr.Sci. from Kyushu University in 1993. His research interests are in Computational/Algorithmic Learning Theory.     

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

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

Iconic pictorial retrieval using multiple attributes and spatial relationships

This work is on the use of multiple attributes or features and spatial relationships, with the help of a user interface based on an iconic paradigm, to retrieve images represented by iconic pictures. An icon has texture, color, and text attributes. Texture is represented by three statistical textural properties, namely, coarseness, contrast, and directionality. For text, the vector space model is used. For color, a representation based on a modified color histogram method which is less storage-intensive is proposed. The final icon similarity is the combination of the attribute similarity values using a proven adaptive algorithm. 2-D strings and its variants are commonly used to represent spatial relationships and perform spatial reasoning. We extended the method to include similarity ranking by using different similarity functions for different spatial relationships and an efficient embedding algorithm. Furthermore, our method solves the problem of query expressiveness which all methods based on 2-D string representations suffer from.     

MOF-tree: A spatial access method to manipulate multiple overlapping features

In this paper we investigate the manipulation of large sets of 2-dimensional data representing multiple overlapping features (e.g. semantically distinct overlays of a given region), and we present a new access method, the MOF-tree. We perform an analysis with respect to the storage requirements and a time analysis with respect to window query operations involving multiple features (e.g. to verify if a constraint defined on multiple overlays holds or not inside a certain region). We examine both the pointer-based as well as the pointerless MOF-tree representations, using as space complexity measure the number of bits used in main memory and the number of disk pages in secondary storage respectively. In particular, we show that the new structure is space competitive in the average case, both in the pointer version and in the linear version, with respect to multiple instances of a region quadtree and a linear quadtree respectively, where each instance represents a single feature. Concerning the time performance of the new structure, we analyze the class of window (range) queries, posed on the secondary memory implementation. We show that the I/O worst-case time complexity for processing a number of window queries in the given image space, is competitive with respect to multiple instances of a linear quadtree, as confirmed by experimental results. Finally, we show that the MOF-tree can efficiently support spatial join processing in a spatial DBMS.     

A fusion spatial attention approach for few-shot learning

Few-shot learning is a challenging problem in computer vision that aims to learn a new visual concept from very limited data. A core issue is that there is a large amount of uncertainty introduced by the small training set. For example, the few images may include cluttered backgrounds or different scales of objects. Existing approaches mostly address this problem from either the original image space or the embedding space by using meta-learning. To the best of our knowledge, none of them tackle this problem from both spaces jointly. To this end, we propose a fusion spatial attention approach that performs spatial attention in both image and embedding spaces. In the image space, we employ a Saliency Object Detection (SOD) module to extract the saliency map of an image and provide it to the network as an additional channel. In the embedding space, we propose an Adaptive Pooling (Ada-P) module tailored to few-shot learning that introduces a meta-learner to adaptively fuse local features of the feature maps for each individual embedding. The fusion process assigns different pooling weights to the features at different spatial locations. Then, weighted pooling can be conducted over an embedding to fuse local information, which can avoid losing useful information by considering the spatial importance of the features. The SOD and Ada-P modules can be used within a plug-and-play module and incorporated into various existing few-shot learning approaches. We empirically demonstrate that designing spatial attention methods for few-shot learning is a nontrivial task and our method has proven effective for it. We evaluate our method using both shallow and deeper networks on three widely used few-shot learning benchmarks, miniImageNet, tieredImageNet and CUB, and demonstrate very competitive performance.     

Design of an efficient VLSI architecture for non-linear spatial warping of wide-angle camera images

Endoscopic images are subjected to spatial distortion due to the wide-angle configuration of the camera lenses. This barrel type of non-linear distortion should be corrected before these images are subjected to further analysis for diagnostic purposes. An efficient digital architecture suitable for an embedded system which can correct the barrel distortion in real-time is presented in this paper. The theoretical approach of this spatial warping technique is based on least-squares estimation. The images in the distorted image space are mapped onto the corrected image space by using a polynomial mapping model. The polynomial parameters include the expansion coefficients, back-mapping coefficients, distortion centre and corrected centre. Several experiments were conducted by applying the spatial warping algorithm on many endoscopic images. A digital architecture suitable for hardware implementation of the distortion correction technique is developed by mapping the algorithmic steps onto a linear array of processing modules. Each module of a particular unit communicates with its nearest neighbours. The spatial warping architecture implemented and simulated with Altera’s Quartus II software shows an overall computation time of 1.8 ms with 50 MHz clock for an image of size 256 × 192 pixels, which confirms that the spatial warping module could be mounted as a dedicated unit in an endoscopy system for real-time applications.     

The DR-tree: A Main Memory Data Structure for Complex Multi-dimensional Objects

An efficient index structure for complex multi-dimensional objects is one of the most challenging requirements in non-traditional applications such as geographic information systems, computer-aided design, and multimedia databases. In this paper we first propose a main memory data structure for complex multi-dimensional objects. Then, we present an extension of the existing multi-dimensional index structure. Among existing multi-dimensional index structures, the popular R*-tree is selected. The R*-tree is coupled with the main memory data structure to improve the performance of spatial query processing. An analytical model is developed for our index structure. Experimental results show that the analytical model is accurate, the relative error being below 15%. The performance of our index structure is compared with that of a state-of-the-art index structure by experimental measurements. Our index structure outperforms the state-of-the-art index structure due to its ability to reduce a large amount of storage.     

织女星地理信息系统VegaGIS中的空间数据引擎CoSDE

介绍了VegaGIS中的空间数据引擎CoSDE的体系结构、设计和实现,通过空间数据引擎CoSDE提供的服务实现对多种空间数据库的直接访问。CoSDE采取了真正的三层C/S体系,屏蔽了客户端对数据库的直接访问,它与具体的数据库实现了物理上的分离,同时实现了真正的跨平台。