Spatial Data Query Support in Peer-to-Peer Systems


  Spatial Data Query Support in Peer-to-Peer Systems.ppt (Size: 224 KB / Downloads: 1)

Motivation


Spatial data sets are used for many applications, e.g., GIS, CAD, …
P2P systems provide a distributed platform that is very scalable.
Pros:
Scalability, no central point of failure
Cons:
Very dynamic (unreliable), topology maintenance required


Distributed Hash Tables (DHT)


DHT systems: Content Addressable Network (CAN), Chord, Pastry, etc.
Using DHT to allocate large data sets to many nodes with no central control
Data objects are near uniformly distributed through a hash function, resulting in superb scalability and load balance
Each node only maintains a small routing table to know its neighbors
Locating a particular data object requires O(logN) search steps on average


Content Addressable Network (CAN)


A scalable indexing mechanism in a P2P network
Creates a logical d-dimensional Cartesian coordinate space
Divides the space into zones, where each zone is controlled by a node in the system
Zones are dynamically partitioned or merged as nodes join and leave
Each Zone is addressed with a Virtual Identifier (VID), which is deterministically calculated from the location of the zone


Content Addressable Network (cont)


The new node arrives at the destination zone covering that point. The destination zone is split into two zones, each controlled by one node (old and new)


Content Addressable Network (CAN)


Data Object Operation (e.g. Insertion)
Generate a key based on the object identification and insert data object as a <key, value> pair
Map the key into a point P in the CAN plane by using a uniform hash function
Store the <key, value> pair at the node which owns the zone within which the point P is located
To retrieve the value, the same hash function is applied to the key in order to regenerate the point P and find the zone owns that point, the zone will return the value to the client