Multi-level spatial index techniques are always used in large spatial databases. After a general survey of R-tree relevant techniques, this paper presents a novel 2-level index structure, which is based on the schemas...Multi-level spatial index techniques are always used in large spatial databases. After a general survey of R-tree relevant techniques, this paper presents a novel 2-level index structure, which is based on the schemas of spatial grids, Hilbert R-tree and common R-tree. This structure is named H2R-tree, and it is specifically suitable for the indexing highly skewed, distributed, and large spatial database. Algorithms and a sample are given subsequently.展开更多
对基于R-Tree的空间连接代价模型进行了探讨,主要研究了HUANG Y W提出的空间连接代价模型。利用最优/最差选择策略降低该算法的时间复杂度,对基于缓冲区的代价模型提出了改进后的评估公式,通过实验验证了改进后的模型比原模型提高了评...对基于R-Tree的空间连接代价模型进行了探讨,主要研究了HUANG Y W提出的空间连接代价模型。利用最优/最差选择策略降低该算法的时间复杂度,对基于缓冲区的代价模型提出了改进后的评估公式,通过实验验证了改进后的模型比原模型提高了评估的精确度。展开更多
In view of the shortage of the spatial skyline query methods(SSQ methods) in dealing with the problem of skyline query in multidimensional space, a spatial skyline query method based on Hilbert R-tree in multidimensio...In view of the shortage of the spatial skyline query methods(SSQ methods) in dealing with the problem of skyline query in multidimensional space, a spatial skyline query method based on Hilbert R-tree in multidimensional space is proposed. This method takes the advantages of Hilbert R-tree which combines R-tree and Hilbert curve with high efficiency and dimensionality reduction. According to the number of query points, the proposed method in static query point environment is divided into single query point of SSQ method(SQ-HSKY algorithm) and multi-query points of SSQ method(MQP-HSKY algorithm). The SQ-HSKY method uses the spatial relationship between objects to propose pruning strategy and the skyline set in the filtering and refining process are computed. The MQP-HSKY method uses the topological relationship between data points and query points to prune non skyline points and generate the dominant decision circle to obtain the global skyline set. Theoretical study and experiments confirm the effectiveness and superiority of these methods on the skyline query.展开更多
Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases. To solve this problem, a novel method of ...Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases. To solve this problem, a novel method of bulk-loading spatial data using the popular MapReduce framework is proposed. MapReduce combines Hilbert curve and random sampling method to parallel partition and sort spatial data, thus it balances the number of spatial data in each partition. Then the bottom-up method is introduced to simplify and accelerate the sub-index construction in each parti- tion. Three area metrics are used to test the quality of generated index under different partitions. The extensive experiments show that the generated R-trees have the similar quality with the gener- ated R-tree using sequential bulk-loading method, while the execution time is reduced considerably by exploiting parallelism.展开更多
为提高网格环境下海量空间数据管理与并行化处理效率,将网格环境下的分布并行处理技术与空间索引相融合,提出了一种空间索引框架(grid slot and hash Rtree,GSHR-Tree).该索引树结构基于散列hash表和动态空间槽,结合R树结构的范围查询...为提高网格环境下海量空间数据管理与并行化处理效率,将网格环境下的分布并行处理技术与空间索引相融合,提出了一种空间索引框架(grid slot and hash Rtree,GSHR-Tree).该索引树结构基于散列hash表和动态空间槽,结合R树结构的范围查询优势和哈希表结构的高效单key查询,分析改进了索引结构的组织和存储.构造了适合于大规模空间数据的网格并行空间计算的索引结构,该索引树算法根据空间数据划分策略,动态分割空间槽,并将它们映射到多个节点机上.每个节点机再将其对应空间槽中的空间对象组织成R树,以大节点R树方式在多个节点上分布索引数据.以空间范围查询并行处理的系统响应时间为性能评估指标,通过模拟实验证明,该GSHR-Tree索引满足了当前网格环境空间索引的需要,并具有设计合理、性能高效的特点.展开更多
The characteristic of geographic information system（GfS） spatial data operation is that query is much more frequent than insertion and deletion, and a new hybrid spatial clustering method used to build R-tree for GI...The characteristic of geographic information system（GfS） spatial data operation is that query is much more frequent than insertion and deletion, and a new hybrid spatial clustering method used to build R-tree for GIS spatial data was proposed in this paper. According to the aggregation of clustering method, R-tree was used to construct rules and specialty of spatial data. HCR-tree was the R-tree built with HCR algorithm. To test the efficiency of HCR algorithm, it was applied not only to the data organization of static R-tree but also to the nodes splitting of dynamic R-tree. The results show that R-tree with HCR has some advantages such as higher searching efficiency, less disk accesses and so on.展开更多
文摘Multi-level spatial index techniques are always used in large spatial databases. After a general survey of R-tree relevant techniques, this paper presents a novel 2-level index structure, which is based on the schemas of spatial grids, Hilbert R-tree and common R-tree. This structure is named H2R-tree, and it is specifically suitable for the indexing highly skewed, distributed, and large spatial database. Algorithms and a sample are given subsequently.
基金Supported by the National Natural Science Foundation of China(No.61872105)the Science and Technology Research Project of Heilongjiang Provincial Education Department(No.1253lz004)the Scientific Research Foundation for Returned Scholars Abroad of Heilongjiang Province of China(No.LC2018030)
文摘In view of the shortage of the spatial skyline query methods(SSQ methods) in dealing with the problem of skyline query in multidimensional space, a spatial skyline query method based on Hilbert R-tree in multidimensional space is proposed. This method takes the advantages of Hilbert R-tree which combines R-tree and Hilbert curve with high efficiency and dimensionality reduction. According to the number of query points, the proposed method in static query point environment is divided into single query point of SSQ method(SQ-HSKY algorithm) and multi-query points of SSQ method(MQP-HSKY algorithm). The SQ-HSKY method uses the spatial relationship between objects to propose pruning strategy and the skyline set in the filtering and refining process are computed. The MQP-HSKY method uses the topological relationship between data points and query points to prune non skyline points and generate the dominant decision circle to obtain the global skyline set. Theoretical study and experiments confirm the effectiveness and superiority of these methods on the skyline query.
基金Supported by the National High Technology Research and Development Program of China (863 Program) (2011AA12A306)the National Natural Science Foundation of China (40801160,60902036)
文摘Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases. To solve this problem, a novel method of bulk-loading spatial data using the popular MapReduce framework is proposed. MapReduce combines Hilbert curve and random sampling method to parallel partition and sort spatial data, thus it balances the number of spatial data in each partition. Then the bottom-up method is introduced to simplify and accelerate the sub-index construction in each parti- tion. Three area metrics are used to test the quality of generated index under different partitions. The extensive experiments show that the generated R-trees have the similar quality with the gener- ated R-tree using sequential bulk-loading method, while the execution time is reduced considerably by exploiting parallelism.
文摘为提高网格环境下海量空间数据管理与并行化处理效率,将网格环境下的分布并行处理技术与空间索引相融合,提出了一种空间索引框架(grid slot and hash Rtree,GSHR-Tree).该索引树结构基于散列hash表和动态空间槽,结合R树结构的范围查询优势和哈希表结构的高效单key查询,分析改进了索引结构的组织和存储.构造了适合于大规模空间数据的网格并行空间计算的索引结构,该索引树算法根据空间数据划分策略,动态分割空间槽,并将它们映射到多个节点机上.每个节点机再将其对应空间槽中的空间对象组织成R树,以大节点R树方式在多个节点上分布索引数据.以空间范围查询并行处理的系统响应时间为性能评估指标,通过模拟实验证明,该GSHR-Tree索引满足了当前网格环境空间索引的需要,并具有设计合理、性能高效的特点.
文摘The characteristic of geographic information system（GfS） spatial data operation is that query is much more frequent than insertion and deletion, and a new hybrid spatial clustering method used to build R-tree for GIS spatial data was proposed in this paper. According to the aggregation of clustering method, R-tree was used to construct rules and specialty of spatial data. HCR-tree was the R-tree built with HCR algorithm. To test the efficiency of HCR algorithm, it was applied not only to the data organization of static R-tree but also to the nodes splitting of dynamic R-tree. The results show that R-tree with HCR has some advantages such as higher searching efficiency, less disk accesses and so on.
