基于P2P的空间矢量数据索引网络动态优化机制的研究
|
摘要
计算机技术的迅速发展给地理信息系统带来了巨大的变化,随着空间数据量和计算复杂性的增加,地理信息系统所采用的集中式模式面临着诸多挑战。P2P技术作为一种新的分布式计算模式,为分布式地理信息共享提供了新的技术手段。该技术能够有效利用网络中的边缘资源,把网络中参与者的网络资源整合起来,利用参与者的存储空间和计算能力来保存海量数据和处理各种请求,从而提高分布式矢量地理数据的组织效率与索引性能。
本文对已有的混合结构P2P空间索引网络进行分析总结,提出一种基于混合结构索引网络的优化机制。该优化机制是基于索引树结构的一种新的组策略思想,将具有相同空间数据语义的客户端加入到同一组中,由组中成员节点共同负担查询请求任务,并且由组中的当前索引节点负责本组成员节点的管理。本文提出的组策略主要包括节点加入机制、传输节点选取机制、当前索引节点替换与备份机制和组管理机制。组策略可以加强原索引网络的拓扑结构,提高整个网络的查询性能和稳定性。经PeerSim的仿真模拟,验证了该优化机制是可行的。最后,本文在JXTA平台上实现了基于P2P的空间矢量数据索引网络动态优化机制的原型系统。测试结果表明,有组策略的索引网络能够有效利用客户端的网络资源,提高查询性能。
The rapid development of computer technology has brought great changes in geographical information system. With the increasing of spatial data size and computational complexity, geographical information system which uses the centralized model is facing many challenges. P2P technology as a new distributed computing model provides a new way for geographical information sharing. The technology can effectively make use of the edge of network resources and can integrate the network resources of participants. It can improve the efficiency of distributed vector geographical data organization and the performance of spatial indexing by utilizing the storage space and computing capabilities of participants to save amounts of data and process kinds of requests.
In this thesis, an optimization mechanism is proposed based on analyzing and summarizing the existing hybrid P2P spatial indexing network. The optimization mechanism is a new idea of group strategy based on the structure of index tree. In this idea, peers with the same spatial data semantics are joined in the same group in which the burden of query is shared by group members together. The current index node in the group is responsible for the management of group members. The group strategy contains node join, the transmission node selection, the current index node replacement and backup and group management mechanism. It can enhance the topology of the original indexing network and improve the query performance and stability of the overall network by using group strategy. The simulation results used PeerSim verify the feasibility of the optimization mechanism. In addition, a P2P based prototype system of dynamic optimization mechanism for spatial vector data indexing network is implemented, which is based on JXTA platform. The experimental results indicate that the indexing network with group strategy can effectively make use of clients’network resources and improve the query performance.
本文对已有的混合结构P2P空间索引网络进行分析总结,提出一种基于混合结构索引网络的优化机制。该优化机制是基于索引树结构的一种新的组策略思想,将具有相同空间数据语义的客户端加入到同一组中,由组中成员节点共同负担查询请求任务,并且由组中的当前索引节点负责本组成员节点的管理。本文提出的组策略主要包括节点加入机制、传输节点选取机制、当前索引节点替换与备份机制和组管理机制。组策略可以加强原索引网络的拓扑结构,提高整个网络的查询性能和稳定性。经PeerSim的仿真模拟,验证了该优化机制是可行的。最后,本文在JXTA平台上实现了基于P2P的空间矢量数据索引网络动态优化机制的原型系统。测试结果表明,有组策略的索引网络能够有效利用客户端的网络资源,提高查询性能。
The rapid development of computer technology has brought great changes in geographical information system. With the increasing of spatial data size and computational complexity, geographical information system which uses the centralized model is facing many challenges. P2P technology as a new distributed computing model provides a new way for geographical information sharing. The technology can effectively make use of the edge of network resources and can integrate the network resources of participants. It can improve the efficiency of distributed vector geographical data organization and the performance of spatial indexing by utilizing the storage space and computing capabilities of participants to save amounts of data and process kinds of requests.
In this thesis, an optimization mechanism is proposed based on analyzing and summarizing the existing hybrid P2P spatial indexing network. The optimization mechanism is a new idea of group strategy based on the structure of index tree. In this idea, peers with the same spatial data semantics are joined in the same group in which the burden of query is shared by group members together. The current index node in the group is responsible for the management of group members. The group strategy contains node join, the transmission node selection, the current index node replacement and backup and group management mechanism. It can enhance the topology of the original indexing network and improve the query performance and stability of the overall network by using group strategy. The simulation results used PeerSim verify the feasibility of the optimization mechanism. In addition, a P2P based prototype system of dynamic optimization mechanism for spatial vector data indexing network is implemented, which is based on JXTA platform. The experimental results indicate that the indexing network with group strategy can effectively make use of clients’network resources and improve the query performance.
引文
[1]汤国安,赵牡丹,杨昕等.地理信息系统(第2版)[M].北京:科学出版社, 2010.
[2] Wang ZG, Xu JJ, Chen M, et al. An exploration of WebGIS based building information system[C]. In Proceedings of the 6th WSEAS International Conference on Software Engineering, Parallel and Distributed System, Corfu Island: WSEAS, 2007: 57-62.
[3] Dejan S. Milojicic, Vana Kalogeraki, et al. Peer-to-Peer Computing[R]. Technical Report HPL-2002-57RI. California: Hewlett-Packard ComPany, 2002.
[4] LIU CHEN, MA XIUJUN, CHEN GUANHUA, et al. A peer-to-peer architecture for dynamic executing GIS web service composition[C]// IGARSS 2005: Proceedings of IEEE International Geoscience and Remote Sensing Symposium. Seoul, South Korea: IEEE Press, 2005: 979-982.
[5] SUN YANFENG, MA XIUJUN, XIE KUNQING, et al. A compensation mechanism in GIS web service composition[C]// IGARSS 2005: Proceedings of IEEE International Geoscience and Remote Sensing Symposium. Seoul, South Korea: IEEE Press, 2005: 940-943.
[6] A V SKVORTSOV. Algorithms for improving the quality of R-trees[J]. Russian Physics Journal, 2004,6(44): 588-595.
[7] Raphael A. Finkel, Jon Louis Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys[J]. Acta Informatica - ACTA , 1974,1(4): 1-9.
[8] N. R. Timos Sellis and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects[C]. Proceedings of the 13th International Conference on Very Large Data Bases, 1987:507-518.
[9] Donghui Zhang, TianXia. A Novel Improvement to The R*-Tree Spatial Index using Gain/Loss Metrics[C]. Proceedings of the 12th annual ACM international workshop on Geographic information systems, 2004:204-213.
[10] Ravi Kanth V Kothuri, Siva Ravada, Daniel Abugov. QuadTree and R-Tree Indexes in Oracle Spatial: A Comparison using GIS Data[C]. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, 2002:546-557.
[11] S. S. Norio Katayama. The SR-Tree: An index structure for high-dimensional nearest neighbor queries[C]. Proceedings of the 1997 ACM SIGMOL international conference on Management of data, 1997:369-380.
[12] G. Proietti. An optimal algorithm for decomposing a window into maximal QuadTree blocks[J]. Acta Informatica 36, 1999, 257–266.
[13] H. S. Egemen Tanin, Aaron Harwood. A distributed QuadTree index for peer-to-peer settings[C]. Proceedings of the 21st International Conference on Data Engineering (ICDE 2005), 2005: 254-255.
[14] A.Touir, J.P. Cheiney. FI-QuadTree: A New Data Structure for Content-Oriented Retrieval and Fuzzy Search. Springer Berlin / Heidelberg[J]. Advances in Spatial Databases, 1991: 23-32.
[15] Gershon Kedem. The Ouad-ClF Tree: A Data Structure for Hierarchical On-Line Algorithms[C]. Proceedings of the 19th conference on Design automation, 1982:352-357.
[16] Hanan Samet, Gisli R.Hjaltason. Speeding up construction of pmr QuadTree-based spatial indexes[J]. TheVLDB Journal, 2002,2(11): 109-137.
[17] ShuiChao, LiHui, LiuFeng, JiaYan. Node clustering ion the P2P environment[C]. Proceedings of the International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies (ICNICONSMCL’06). Washington, DC: IEEE Computer Society, 2006: 61-66.
[18] Shihui Wang, Yan Zhang, Wei Wang. Reliable Self-Clustering P2P Overlay Networks[C]. Proceedings of the 31st Annual International Computer Software and Applications Conference. Washington, DC: IEEE Computer Society, 2007: 105-108.
[19] DaoChao Huang, Hengkui, et al. A novel superior peer selection algorithm in large-scale DHT system[C]. Proceedings of IC-NIDC2010, 2010: 804-808.
[20] Ahmed M. Mahdy, Jitender S. Deogun, Jun Wang. Mobile Ad Hoc Networks: A Hybrid Approach for the selection of super peers[C]. Proceedings of the Second IFIP International Conference on Wireless and Optical Communications Networks, 2005: 280-284.
[21] Lu Gao, Min Peng. Optimal superpeer selection based on load balance for P2P file-sharing system[C]. Proceedings of the 2009 International Joint Conference on Artificial Intelligence. Washington, DC: IEEE Computer Society, 2009: 92-95.
[22] Rdiger Schollmeier. A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications[C]. In Proceedings of the IEEE 2001 International Conference on Peer-to-Peer Computing (P2P’01), Linkping, Sweden, August 2002: 101-102.
[23]郑纬民等.对等计算研究概论[J].中国计算机学会通讯, 2005, 7(2): 38-51.
[24] K. Lua, J. Crowcroft, M. Pias, R. Sharma, S. Lim. A survey and comparison of peer-to-peer overlay network schemes[J]. Proceedings of the IEEE Communications Surveys and Tutorials, 2005, 7(2): 72-93.
[25] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrishnan. Chord: A scalable peer-to-peer lookup ervice for Internet applications[J]. Proceedings of the ACM SIGCOMM’01, 2001:149-160.
[26] BY Zhao, L. Huang, J. Stribling, SC Rhea, AD Joseph, JD Kubiatowicz. Tapestry: a resilient global-scale overlay for service deployment. Selected Areas in Communications, IEEE Journal on , 2004, 1(22):41-53.
[27] S. Voulgaris, M. van Steen. An epidemic protocol for managing routing tables in very large peer-to-peer networks[C]. Proceedings of the 14th IFIP/IEEE International Workshop on Distributed Systems: Operations and Management(DSOM 2003), 2003: 41-54.
[28] Clarke I, Sandberg O, Wiley B, et al. Freenet: a distributed anonymous information storage and retrieval system[C]. Designing Privacy Enhancing Technologies: Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability, Jul 25-26, 2000, Berkeley, CA, USA. LNCS 2009. Berlin, Germany: Springer-Verlag, 2000:44-66.
[29] Scott Oaks, Bernard Traversat, Li Gong. JXTA技术手册[M].技桥,译.北京:清华大学出版社, 2004.
[30] Project JXTA: An Open, Innovative Collaboration[M]. Sun Micro systems white paper, 2005.
[31]邬伦,刘瑜,张晶,马修军,韦中亚,田原.地理信息系统原理、方法和应用[M].北京:科学出版社, 2001.
[32]过志峰,王宇翔,杨崇峻.空间数据索引与查询技术研究及其应用.计算机工程与应用, 2002, 38(23):176-178.
[33] Tanin E, Harwood A, Samet H. Using a distributed QuadTree index in Peer-to-Peer networks[J]. VLDB Journal, 2007, 16(2):165-178.
[34] Adina Crainiceanu, Prakash Linga, et al. P-Tree: A P2P index for resource discovery applications[C]. Proceedings of the 13th Int. World Wide Web Conference on Alternate Track Papers and Posters, 2004: 390-391.
[35] C. A. Shaffer, H. Samet. Optimal quadtree construction algorithms[J]. Computer Vision, Graphics, and Image Processing, 1987, 37(3): 402-419.
[36] F. A. Schreiber, R. C. Wolfler. Use of neural networks to estimate the number of nodes of an edge quadtree[J]. Graphical Models and Image Processing. Academic Press, 1997, 59(2): 61-72.
[37] Hung-Yi Lin, Po-Whei Hung. Perfect KDB-tree: A compact KDB-tree structure for indexing multidimensional data[C]. Proceedings of the 3rd IEEE International Conference on Information Technology and Applications, 2005: 411-414.
[38] Ripeanu M. Peer-to-peer architecture case study: Gnutella network[C]. Technical report, TR-2001-26. Chicago, IL, USA: University of Chicago, 2001.
[39] WU JIAGAO, JIANG NAN, ZOU ZHIQIANG, et al. HPSIN: A new hybrid P2P spatial indexing network[J]. The Journal of China Universities of Posts and Telecommunications, 2010, 17(3): 66-72.
[40] Peersim simulator[EB/OL]. http://sourceforge.net/projects/Peerim. 2005.
[41] VIVID Solutions. JTS Topology Suite Technical Specifications v1.4 [EB/OL]. (2003-08-17)[2011-02-02]. http://www.vividsolutions.com/jts/jtshome.htm. 2009.
[42]黄琳.基于P2P网络的矢量地理数据组织与索引技术的研究[D].南京:南京邮电大学, 2011.
[2] Wang ZG, Xu JJ, Chen M, et al. An exploration of WebGIS based building information system[C]. In Proceedings of the 6th WSEAS International Conference on Software Engineering, Parallel and Distributed System, Corfu Island: WSEAS, 2007: 57-62.
[3] Dejan S. Milojicic, Vana Kalogeraki, et al. Peer-to-Peer Computing[R]. Technical Report HPL-2002-57RI. California: Hewlett-Packard ComPany, 2002.
[4] LIU CHEN, MA XIUJUN, CHEN GUANHUA, et al. A peer-to-peer architecture for dynamic executing GIS web service composition[C]// IGARSS 2005: Proceedings of IEEE International Geoscience and Remote Sensing Symposium. Seoul, South Korea: IEEE Press, 2005: 979-982.
[5] SUN YANFENG, MA XIUJUN, XIE KUNQING, et al. A compensation mechanism in GIS web service composition[C]// IGARSS 2005: Proceedings of IEEE International Geoscience and Remote Sensing Symposium. Seoul, South Korea: IEEE Press, 2005: 940-943.
[6] A V SKVORTSOV. Algorithms for improving the quality of R-trees[J]. Russian Physics Journal, 2004,6(44): 588-595.
[7] Raphael A. Finkel, Jon Louis Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys[J]. Acta Informatica - ACTA , 1974,1(4): 1-9.
[8] N. R. Timos Sellis and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects[C]. Proceedings of the 13th International Conference on Very Large Data Bases, 1987:507-518.
[9] Donghui Zhang, TianXia. A Novel Improvement to The R*-Tree Spatial Index using Gain/Loss Metrics[C]. Proceedings of the 12th annual ACM international workshop on Geographic information systems, 2004:204-213.
[10] Ravi Kanth V Kothuri, Siva Ravada, Daniel Abugov. QuadTree and R-Tree Indexes in Oracle Spatial: A Comparison using GIS Data[C]. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, 2002:546-557.
[11] S. S. Norio Katayama. The SR-Tree: An index structure for high-dimensional nearest neighbor queries[C]. Proceedings of the 1997 ACM SIGMOL international conference on Management of data, 1997:369-380.
[12] G. Proietti. An optimal algorithm for decomposing a window into maximal QuadTree blocks[J]. Acta Informatica 36, 1999, 257–266.
[13] H. S. Egemen Tanin, Aaron Harwood. A distributed QuadTree index for peer-to-peer settings[C]. Proceedings of the 21st International Conference on Data Engineering (ICDE 2005), 2005: 254-255.
[14] A.Touir, J.P. Cheiney. FI-QuadTree: A New Data Structure for Content-Oriented Retrieval and Fuzzy Search. Springer Berlin / Heidelberg[J]. Advances in Spatial Databases, 1991: 23-32.
[15] Gershon Kedem. The Ouad-ClF Tree: A Data Structure for Hierarchical On-Line Algorithms[C]. Proceedings of the 19th conference on Design automation, 1982:352-357.
[16] Hanan Samet, Gisli R.Hjaltason. Speeding up construction of pmr QuadTree-based spatial indexes[J]. TheVLDB Journal, 2002,2(11): 109-137.
[17] ShuiChao, LiHui, LiuFeng, JiaYan. Node clustering ion the P2P environment[C]. Proceedings of the International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies (ICNICONSMCL’06). Washington, DC: IEEE Computer Society, 2006: 61-66.
[18] Shihui Wang, Yan Zhang, Wei Wang. Reliable Self-Clustering P2P Overlay Networks[C]. Proceedings of the 31st Annual International Computer Software and Applications Conference. Washington, DC: IEEE Computer Society, 2007: 105-108.
[19] DaoChao Huang, Hengkui, et al. A novel superior peer selection algorithm in large-scale DHT system[C]. Proceedings of IC-NIDC2010, 2010: 804-808.
[20] Ahmed M. Mahdy, Jitender S. Deogun, Jun Wang. Mobile Ad Hoc Networks: A Hybrid Approach for the selection of super peers[C]. Proceedings of the Second IFIP International Conference on Wireless and Optical Communications Networks, 2005: 280-284.
[21] Lu Gao, Min Peng. Optimal superpeer selection based on load balance for P2P file-sharing system[C]. Proceedings of the 2009 International Joint Conference on Artificial Intelligence. Washington, DC: IEEE Computer Society, 2009: 92-95.
[22] Rdiger Schollmeier. A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications[C]. In Proceedings of the IEEE 2001 International Conference on Peer-to-Peer Computing (P2P’01), Linkping, Sweden, August 2002: 101-102.
[23]郑纬民等.对等计算研究概论[J].中国计算机学会通讯, 2005, 7(2): 38-51.
[24] K. Lua, J. Crowcroft, M. Pias, R. Sharma, S. Lim. A survey and comparison of peer-to-peer overlay network schemes[J]. Proceedings of the IEEE Communications Surveys and Tutorials, 2005, 7(2): 72-93.
[25] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrishnan. Chord: A scalable peer-to-peer lookup ervice for Internet applications[J]. Proceedings of the ACM SIGCOMM’01, 2001:149-160.
[26] BY Zhao, L. Huang, J. Stribling, SC Rhea, AD Joseph, JD Kubiatowicz. Tapestry: a resilient global-scale overlay for service deployment. Selected Areas in Communications, IEEE Journal on , 2004, 1(22):41-53.
[27] S. Voulgaris, M. van Steen. An epidemic protocol for managing routing tables in very large peer-to-peer networks[C]. Proceedings of the 14th IFIP/IEEE International Workshop on Distributed Systems: Operations and Management(DSOM 2003), 2003: 41-54.
[28] Clarke I, Sandberg O, Wiley B, et al. Freenet: a distributed anonymous information storage and retrieval system[C]. Designing Privacy Enhancing Technologies: Proceedings of the ICSI Workshop on Design Issues in Anonymity and Unobservability, Jul 25-26, 2000, Berkeley, CA, USA. LNCS 2009. Berlin, Germany: Springer-Verlag, 2000:44-66.
[29] Scott Oaks, Bernard Traversat, Li Gong. JXTA技术手册[M].技桥,译.北京:清华大学出版社, 2004.
[30] Project JXTA: An Open, Innovative Collaboration[M]. Sun Micro systems white paper, 2005.
[31]邬伦,刘瑜,张晶,马修军,韦中亚,田原.地理信息系统原理、方法和应用[M].北京:科学出版社, 2001.
[32]过志峰,王宇翔,杨崇峻.空间数据索引与查询技术研究及其应用.计算机工程与应用, 2002, 38(23):176-178.
[33] Tanin E, Harwood A, Samet H. Using a distributed QuadTree index in Peer-to-Peer networks[J]. VLDB Journal, 2007, 16(2):165-178.
[34] Adina Crainiceanu, Prakash Linga, et al. P-Tree: A P2P index for resource discovery applications[C]. Proceedings of the 13th Int. World Wide Web Conference on Alternate Track Papers and Posters, 2004: 390-391.
[35] C. A. Shaffer, H. Samet. Optimal quadtree construction algorithms[J]. Computer Vision, Graphics, and Image Processing, 1987, 37(3): 402-419.
[36] F. A. Schreiber, R. C. Wolfler. Use of neural networks to estimate the number of nodes of an edge quadtree[J]. Graphical Models and Image Processing. Academic Press, 1997, 59(2): 61-72.
[37] Hung-Yi Lin, Po-Whei Hung. Perfect KDB-tree: A compact KDB-tree structure for indexing multidimensional data[C]. Proceedings of the 3rd IEEE International Conference on Information Technology and Applications, 2005: 411-414.
[38] Ripeanu M. Peer-to-peer architecture case study: Gnutella network[C]. Technical report, TR-2001-26. Chicago, IL, USA: University of Chicago, 2001.
[39] WU JIAGAO, JIANG NAN, ZOU ZHIQIANG, et al. HPSIN: A new hybrid P2P spatial indexing network[J]. The Journal of China Universities of Posts and Telecommunications, 2010, 17(3): 66-72.
[40] Peersim simulator[EB/OL]. http://sourceforge.net/projects/Peerim. 2005.
[41] VIVID Solutions. JTS Topology Suite Technical Specifications v1.4 [EB/OL]. (2003-08-17)[2011-02-02]. http://www.vividsolutions.com/jts/jtshome.htm. 2009.
[42]黄琳.基于P2P网络的矢量地理数据组织与索引技术的研究[D].南京:南京邮电大学, 2011.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |