中国邮电高校学报(英文) ›› 2010, Vol. 17 ›› Issue (3): 66-72.doi: 10.1016/S1005-8885(09)60468-4

• Network • 上一篇    下一篇

HPSIN: a new hybrid P2P spatial indexing network

吴家皋1,冯佳丽2,胡斌2,黄琳1,江南2,邹志强1   

  1. 1. 南京邮电大学
    2. 南京师范大学
  • 收稿日期:2009-10-10 修回日期:2010-01-21 出版日期:2010-06-30 发布日期:2010-06-29
  • 通讯作者: 吴家皋 E-mail:jgwu@njupt.edu.cn
  • 基金资助:

    国家级.国家自然科学基金;国家级.国家“863计划”项目

HPSIN: a new hybrid P2P spatial indexing network

  • Received:2009-10-10 Revised:2010-01-21 Online:2010-06-30 Published:2010-06-29

摘要:

Geographic information system (GIS) is increasingly managing very large sets of data, hence a centralized data index may not always provide the most scalable solution. Recently, the peer to peer (P2P) networks have become very popular for sharing information in a totally decentralized manner. In this paper, a new hybrid P2P spatial indexing network (HPSIN) is proposed, which combines distributed quad-tree with distributed Hash table (DHT) based Chord network to maintain both query efficiency and system load balance. In addition, a simple theoretical model based on opened queueing network for HPSIN is established. Assuming each peer as M/M/1 queueing processor in the model, fundamental characteristics of the system is captured, and expression of average query delay is obtained in close form. The theoretical analysis and numerical computing results show that there exists an optimum point of tradeoff between efficiency and load balance. By setting a proper value of start index level ls for different network scale and query rate, HPSIN will achieve the minimum overall query delay, therefore, can adapt to different P2P application environments.

关键词:

GIS, P2P networks, spatial indexing, queueing network, theory

Abstract:

Geographic Information System (GIS) is increasingly managing very large sets of data, hence a centralized data index may not always provide the most scalable solution. Recently, the P2P networks have become very popular for sharing information in a totally decentralized manner. In this paper, a new Hybrid P2P Spatial Indexing Network (HPSIN) is proposed, which combines distributed Quad-Tree with DHT-based Chord network to maintain both query efficiency and system load balance. In addition, a simple theoretical model based on opened queueing network for HPSIN is established, which captures the fundamental characteristics of the system. The theoretical analysis and numerical computing results show that there exists an optimum point of tradeoff between efficiency and load balance, which can achieve the minimum overall query delay.

Key words:

GIS, P2P networks, spatial indexing, queueing network, theory