Spatial data occurs in several important and diverse applications in P2P systems, for example, P2P virtual cities, GIS, development planning, etc. For the problem of answering exact queries for spatial region data in the P2P environment, an R¡Vtree based structure probably is a good choice. However, since a peer system is dynamic, the global update characteristics of data insertion/deletion in an R¡Vtree can not work well in a P2P system. Moreover, the problem of overlaps in an R¡Vtree results in large number of the disk accesses (which will be considered as large number of messages in P2P systems). Therefore, a P2PR¡Vtree based indexing method for P2P systems has been proposed which has only local update to the proposed index structure when data insertion/deletion occurs. Although the P2PR¡Vtree can achieve the goal of the local update for data insertion/deletion, the overlapping phenomenon is still hard to solve. Recently, for region data access, an NA¡Vtree has been proposed which outperforms R¡Vtree¡Vlike data structures. Moreover, it does not have the problem of overlaps which may occur in an R¡Vtree. Basically, an NA¡Vtree does not split the spatial space, but it just classifies the spatial data objects by some rules. On the other hand, the Chord system is a well¡Vknown structured P2P system in which the data search is performed by a hash function, instead of flooding used in most of the unstructured P2P system. Since the Chord system is a hash approach, it is easy to deal with data insertion/deletion with only local update. However, the current Chord system can not work well with the region data, since it only works well with a single key value. Therefore, in this thesis, we propose to apply an NA-tree in the Chord system to encode spatial region data in the data key part used in the hash function to data search. That is, we still use one hash function of Chord to assign nodes to peers, and use another hash function to do data assignment by applying an NA¡Vtree to encode the spatial region data to data keys. First, we use three bits to present the first eight children in the NA¡Vtree. Next, we propose two methods to generate the key value of the remaining bits. For our first proposed method, it generates the remaining bits by adding 0¡¦s. This method is simple and applicable to the case that there are few objects in P2P systems. To avoid the case that a peer may own too many objects, the second method takes the central points of regions into consideration. This method is applicable to the case that there are too many objects in the P2P system. Finally, we concatenate the first three and the remaining bits to get the key values of objects. Thus, we combine the NA¡Vtree with the Chord system to solve the overlapping problem which the P2PR¡Vtree can not deal with. In our simulation study, we use six different data distributions to compare our method with the P2PR¡Vtree. From our simulation results, we show that the number of visited peers in our approach is less than that in the P2PR¡Vtree.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0717106-154503 |
| Date | 17 July 2006 |
| Creators | Wang, Ching-i |
| Contributors | San-Yih Hwang, Ye-In Chang, Chien-I Lee, Gen-huey Chen |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0717106-154503 |
| Rights | not_available, Copyright information available at source archive |
Page generated in 0.002 seconds