GSHR-Tree: A Spatial Index Tree Based on Dynamic Spatial Slot and Hash Table in Grid Environments
-
摘要: 为提高网格环境下海量空间数据管理与并行化处理效率，将网格环境下的分布并行处理技术与空间索引相融合，提出了一种空间索引框架(grid slot and hash R tree，GSHR-Tree).该索引树结构基于散列hash表和动态空间槽，结合R树结构的范围查询优势和哈希表结构的高效单key查询，分析改进了索引结构的组织和存储.构造了适合于大规模空间数据的网格并行空间计算的索引结构，该索引树算法根据空间数据划分策略，动态分割空间槽，并将它们映射到多个节点机上.每个节点机再将其对应空间槽中的空间对象组织成R树，以大节点R树方式在多个节点上分布索引数据.以空间范围查询并行处理的系统响应时间为性能评估指标，通过模拟实验证明，该GSHR-Tree索引满足了当前网格环境空间索引的需要，并具有设计合理、性能高效的特点.Abstract: In order to improve the efficiency of parallel processing of a spatial mass data under the distributed parallel computing grid environment, this paper presents a new grid slot hash parallel spatial index GSHR-Tree structure established with the parallel spatial indexing mechanism. Based on the hash table and dynamic spatial slot, we have improved the structure of the classical parallel R-tree index. The GSHR-Tree index makes full use of the good qualities of R-Tree and hash data structure. A new parallel spatial index is constructed to meet the needs of parallel grid computing about the magnanimous spatial data in the distributed network. This arithmetic splits space into multi-slots by multiplying and reverting and maps these slots to sites in distributed and parallel system. Each site constructs the spatial objects in its spatial slot into an R-tree. On the basis of this tree structure, the index data is distributed among multiple nodes in the grid networks by using large node R-tree method. Instead of spatial object's recursive comparison where original R-tree has been used, the algorithm builds the spatial index by applying binary code operation in which computer runs more efficiently, and extends dynamic hash code for bit comparison, using the system response time of the parallel processing of spatial scope query algorithm as the performance evaluation factor. The result of the simulated the experiments shows GSHR-Tree is performed to prove the reasonable design and the high performance of the indexing structure presented in the paper.
-
图 1 网格环境下的动态空间数据索引框架
Fig. 1. The dynamic geospatial data index framework in grid environment
表 1 GSHR-Tree节点定义
Table 1. The definition of DR-H index node
GSHR-Tree Hash表节点的结构定义 GSHR-Tree叶节点的定义 GSHR-Tree路由节点的定义 struct R-Entry{
int m_ i0id；//对象ID
Rect m_rect；；//外包矩形
R-Entry* link；}；
Typedef R-Entry* R-EntryPtr；
struct Menties{int m_ iOid；//对象ID
Rect m_rect；}struct LefNode{
int PagNo；//本节点页号
int ParPNo；//父节点页号
short nIndex；//父节点下标
int count；//指针个数
int sytle；//数据库类型
R-EntryPtr[MAXLN]}；struct MidNode{
int PagNo；//本节点页号
int ParPNo；//父节点页号
short nIndex；//父节点下标
int count；//索引项数
int Menties[MAXMN]；//索引项数组}注：MAXLN定义为：#define MAXLN(int)((PGSIZE-(6*sizeof(int)))/sizeof(struct LefNode))；MAXMN定义为：#define MAXCARD(int)((PGSIZE-(6*sizeof(int)))/sizeof(struct MidNode)). 
下载: 导出CSV
-
[1] du Mouza, C., Litwin, W., Rigaux, P., 2007. SD-Tree: a scalable distributed Rtree. In: ICDE, Paris, France, 296-305. [2] Fornari, R.M., Iochpe, C., 2004. A spatial hash join algorithm suited for small buffer size. Proceedings of the 12th annual ACM International workshop on geographic information systems. Washington, D.C., U.S.A. . 118-126. [3] Guo, P., Wang, B., Wang, G.R., et al., 2005. PR-Tree: a multidimensional distributed index for peer-to-peer systems. Journal of Huazhong University of Science and Technology (Nature Science Edition), 33(Suppl. ): 221-225 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/ http://search.cnki.net/down/default.aspx?filename=HZLG2005S1061&dbcode=CJFD&year=2005&dflag=pdfdown [4] Hu, H.B., Li, J., Chen, Y.H., 2005. The supplementary R-Tree (SRT) algorithm used for GIS resources allocation in model base system under grid environment. 2005 IEEE International Geoscience and Remote Sensing Symposium, 2: 4. Seoul Korea. [5] Jiang, X.J., Wu, H.Z., Li, W.Q., 2006. R-tree method of matching algorithm for data distribution management. Journal of Computer Research and Development, 43(2): 362-367 (in Chinese with English abstract). doi: 10.1360/crad20060226 [6] Luo, Z.W., 2002. Using ORDBMS to store GIS data. Earth Science—Journal of China University of Geosciences, 27(3): 267-270 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-DQKX200203007.htm [7] Miyazaki, J., Abe, Y., Yokota, H., 2004. Availabilities and costs of reliable Fat-Btrees. Proceedings of the 10th IEEE Pacific Rim International symposium on dependable computing (PRDC'04). Washington, D.C., U.S.A. . [8] Tang, J.Y., Bai, X.Y., Yang, F., et al., 2005. Index replication strategy study based on DPB+Tree. Computer Science, 32(11): 112-114 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTotal-JSJA200511028.htm [9] Wu, X.C., Wu, L., 2006. Service-oriented distributed spatial information supporting system. Earth Science—Journal of China University of Geosciences, 31(5): 585-589 (in Chinese with English abstract). [10] Xie, Z., Feng, M., Ma, C.J., 2006. Index strategies for embedded-GIS spatial data management. Earth Science—Journal of China University of Geosciences, 31(5): 653-658 (in Chinese with English abstract). http://gateway.proquest.com/openurl?res_dat=xri:pqm&ctx_ver=Z39.88-2004&rfr_id=info:xri/sid:baidu&rft_val_fmt=info:ofi/fmt:kev:mtx:article&genre=article&jtitle=Earth%20Science&atitle=Index%20strategies%20for%20embedded-GIS%20spatial%20data%20management [11] Zhao, C.Y., Meng, L.K., Lin, Z.Y., 2006. Spatial data partitioning towards parallel spatial database system. Geomatics and Information Science of Wuhan University, 31(11): 962-965 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-WHCH200611005.htm [12] Zuo, C.S., Liu, X.S., Chen, X.H., et al., 2006. DPSlR+: a distributed and parallel spatial index tree based ondynamic spatial slot. Computer Science, 33(2): 121-125 (in Chinese with English abstract). http://www.oalib.com/paper/1650959 [13] 郭鹏, 王斌, 王国仁, 等, 2005. PR-tree: P2P环境下一种多维数据的分布式索引结构. 华中科技大学学报(自然科学版), 33(增刊): 221-225. https://www.cnki.com.cn/Article/CJFDTOTAL-HZLG2005S1061.htm [14] 蒋夏军, 吴慧中, 李蔚清, 2006. 数据分发管理匹配算法的R-树实现. 计算机研究与发展, 43(2): 362-367. https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200602030.htm [15] 罗忠文, 2002. 应用对象关系型数据库存储GIS数据. 地球科学——中国地质大学学报, 27(3): 267-270. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200203007.htm [16] 唐继勇, 白新跃, 杨峰, 等, 2005. 基于DPB+Tree的索引复制策略研究. 计算机科学, 32(11): 112-114. doi: 10.3969/j.issn.1002-137X.2005.11.029 [17] 吴信才, 吴亮, 2006. 面向服务的分布式空间信息支撑平台. 地球科学——中国地质大学学报, 31(5): 585-589. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200605001.htm [18] 谢忠, 凤鸣, 马常杰, 2006. 嵌入式空间索引策略. 地球科学——中国地质大学学报, 31(5): 653-658. https://www.cnki.com.cn/Article/CJFDTOTAL-DQKX200605015.htm [19] 赵春宇, 孟令奎, 林志勇, 2006. 一种面向并行空问数据库的数据划分算法研究. 武汉大学学报(信息科学版), 31(11): 962-965. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200611005.htm [20] 左朝树, 刘心松, 陈小辉, 等, 2006. DPSlR+: 一种基于动态空间槽的分布式并行空间索引树. 计算机科学, 33(2): 121-125. doi: 10.3969/j.issn.1002-137X.2006.02.034 -
点击查看大图
图(5) / 表(1)
计量
- 文章访问数: 3378
- HTML全文浏览量: 158
- PDF下载量: 65
- 被引次数: 0
