ASPEN: an adaptive spatial peer-to-peer network

ABSTRACT

Geographic Information Systems (GIS) are increasingly managing very large sets of data and hence a centralized data repository may not always provide the most scalable solution. Here we introduce a novel approach to manage spatial data by leveraging structured Peer-to-Peer (P2P) systems based on Distributed Hash Tables (DHTs). DHT algorithms provide efficient exact-match object search capabilities without requiring global indexing and as a result they are extremely scalable. Furthermore, the adoption of uniform hash functions ensures excellent load balancing. However, range queries -- which are very common with spatial data -- cannot be executed efficiently because the hash functions unfortunately destroy any existing data locality. Here we report on the design of an Adaptive Spatial Peer-to-pEer Network (ASPEN) that extends Content Addressable Networks (CAN) to preserve spatial locality information while also retaining many of the load balancing properties of DHT systems. We introduce the concept of scatter regions, which are spatial data distribution units that optimize both load balancing and spatial range query processing at the same time. We present a data object key generation function and algorithms for spatial range queries. We rigorously evaluate our technique with both synthetic and real world data sets and the results demonstrate the efficient execution of spatial range queries in the ASPEN system.

REFERENCES

• 1: FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA, April 1995.
• 2: James Aspnes , Jonathan Kirsch , Arvind Krishnamurthy, Load balancing and locality in range-queriable data structures, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011785]
• 3: T. Bially. A Class of Dimension Changing Mapping and Its Application to Bandwidth Compression. In Ph.D. Dissertation Polytechnic Inst. of Brooklyn, June 1967.
• 4: R. Finkel and J. Bentley. Quadtree: A data structure for retrieval on composite keys. ACTA Informatica, 1974.
• 5: Jun Gao , Peter Steenkiste, An Adaptive Protocol for Efficient Support of Range Queries in DHT-Based Systems, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.239-250, October 05-08, 2004
• 6: B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica. Load Balancing in Dynamic Structured P2P Systems. In Proceedings of the 23rd Conference of the IEEE Communications Society, 2004.
• 7: J. Hellerstein, S. Ratnasamy, and S. Shenker. Range Query over DHTs. Technical Report IRB-TR-03-009, Intel Research, Berkeley, June 2003.
• 8: Dmitri V. Kalashnikov , Sunil Prabhakar , Susanne E. Hambrusch , Walid G. Aref, Efficient Evaluation of Continuous Range Queries on Moving Objects, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.731-740, September 02-06, 2002
• 9: A. Mondal, Y. Lifu, and M. Kitsuregawa. P2PR-Tree: An R-Tree-Based Spatial Index for Peer-to-Peer Environments. In EDBT Workshops, pages 516--525, 2004.
• 10: Sylvia Paul Ratnasamy , Scott Shenker , Ion Stoica, A scalable content-addressable network, 2002
• 11: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 12: Cristina Schmidt , Manish Parashar, Flexible Information Discovery in Decentralized Distributed Systems, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC'03), p.226, June 22-24, 2003
• 13: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 14: Egemen Tanin , Aaron Harwood , Hanan Samet , Sarana Nutanong , Minh Tri Truong, A serverless 3D world, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032246]
• 15: S. Zhou, G. R. Ganger, and P. Steenkiste. Location-based Node IDs: Enabling Explicit Locality in DHTs. Technical Report CMU-CS-03-171, Carnegie Mellon University, 2003.
• 16: Roger Zimmermann , Wei-Shinn Ku , Haojun Wang, Spatial Data Query Support in Peer-to-Peer Systems, Proceedings of the 28th Annual International Computer Software and Applications Conference - Workshops and Fast Abstracts - (COMPSAC'04), p.82-85, September 28-30, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design, Performance

Keywords:
distributed spatial databases, peer-to-peer systems