Research On Spatial Data Index For Peer-to-Peer Environments

The application of spatial data has broken the limitation of traditional areas, and its scope, storage capacity and user formation have been experiencing the great development. In recent years the large scale and wide area spatial data application has become an important direction, which puts forward higher requirements for the access efficiency and application depth of spatial data in wide area environment. The deployment of most traditional distributed spatial data systems depends on the closely collaboration of heavyweight servers and lightweight clients, and the spatial data operations are compute-intensive and data-intensive, which may result in a single point of failure and the servers may become the bottleneck of the systems. These have become a limitation on computing capability, storage capacity and transmission efficiency, which prevent the utilization efficiency of spatial data in wide area environment.The peer-to-peer (abbreviated to "P2P") technology has recently already shown great success in file sharing, data storage, instant messaging, video streaming, and distributed computing. Currently, it has become the one of important technologies for construct large-scale distributed systems. The technology can fully harness various resources (including computing, storage and bandwidth) at the edge of the Internet. Theoretically, by employing the technology, the computing and storage resources could be sufficient to enable any applications that need these resources and the transmission speed could be also improved greatly. Therefore P2P is very suitable for spatial data systems that are compute-intensive and data-intensive.The spatial data index provides powerful support for efficient spatial data accessing in spatial data systems, and it is an important method that guarantee efficient applications for spatial data. As P2P distinguishes itself from traditional distributed networks in the following aspects such as scalability, decentralization and dynamism, the traditional distributed spatial data indexing methods can’t be used directly for P2P environments. Therefore, the paper researches on the key technologies of spatial data indexing for P2P environments, and the work has theoretical and practical value.The dissertation takes the wide-area distributed spatial data indexing method as the research framework, combined with the recent development of P2P technologies, and studies on many related problems, at last some efficient solutions are given. Main contribution of this dissertation is as follows.1) An overlay network architecture based on quasi-balanced multi-way tree is proposed. It can support efficient spatial data queries in structured P2P networks. The efficiency of the queries could be improved by increasing the fanout, and the architecture fully exploits the characteristics of non-uniform temporal distribution of the queries.2) Concerning the fact that the structure distinction between application layer and physical layer, an adaptive distributed aggregation algorithm based on peer latency is introduced, which aims at dynamically optimizing the applications of overlay. It not only saves the cost, but also makes the realization of load balancing easier. Therefore, the efficiency of the overlay could be improved substantially.3) A wide-area distributed spatial data indexing method based on super-tree structure is proposed, which is a combination of a linear structure and a hierarchical structure for organizing indexing information, and the size of the linear structure is determined by the capacity of the responsible peer. On the basis, an overlap minimization algorithm is introduced, which takes the query rate into account to reasonably improve the efficiency of the above method.4) On the basis of comparing and analyzing some current experiment methods, and combines with the main content and the key problems in this paper, a simulation platform for verifying the above proposed methods is designed and implemented, which is layered/modularized into several layers. The functional definition of each layer and the APIs between them are explained, and their detailed description is given later.The research is carried out from two aspects, the design and implementation of overlay network architecture and the distribution and organization of distributed spatial index information. Some methods are proposed to solve some key problems. The research results have positive implications for the development of spatial data indexing in wide-area distributed environment, and lay a foundation for the studies on distributed spatial data system architecture, so as to strongly promote the application of spatial data more deeply and more widely.