Research On Distributed Spatio-Temporal Indexing Methods Based On Peer-to-Peer Computing

Spatio-temporal data can help people learn about history, current and future, and it is a key factor to improve the ability of perception, insight and prophesy about various status evolutions. With the development of information detection and collection technology, spatio-temporal data is not little and partial any more, but huge and abroad. Considering this kind of situation and the trend of integration and ubiquity, the spatio-temporal under centralized mechanism can't satisfy users'need for query, and the shortages of low efficiency and single-point-failure lead to the development of distributed one. However, the distributed computing under master-slave and hierarchical styles can't satisfy the distributed object environment either, because this kind of distributed mechanism causes key nodes, which may become the bottle neck and weak point of the whole system, and is bad for system scalability and reconstruction.This paper suggested peer-to-peer computing mechanism to organize the construction of distributed spatio-temporal index, mainly from homogeneity and heterogeneity two sides. Combining with users'spatio-temporal query types, we try to design a distributed mechanism with good query performance, stable update capability, which can also support semi-structured described query. The main contributions of our work are:(1) This paper gave a deeply, generally and innovatively summarization about related work. So far, there are a limited number of works about distributed index. After summarizing several related works, this paper found some related theory, respectively from centralized spatio-temporal index and P2P based multidimensional index two aspects. The innovation of this paper is adopting a kind of visualization method to show the related work and the relationship among the authors, which can help to directly find the venation of various works, as well as the research method and style.(2) This paper described the P2P based distributed spatio-temporal index problem and proposed the framework of the whole index. Since the referenced work is limited, it needs to identify the problem radically. This paper gives a P2P based distributed spatio-temporal object model, build the model between the dispersive spatio-temporal objects and distributed servers using spatio-temporal division method, and combined the spatio-temporal data storage in history-oriented and future-oriented query. Besides, this paper proposed a double-level framework, which includes the local level and entire level. Each node firstly completes the local information organization and index construction, and then joins the entire spatio-temporal information organization and index construction. The framework depicted the basal protocols of index query, construction and maintenance, which is reasonable, integrated, and scalable, and lay foundation for the later research. (3) This paper proposed a double-ring structure index for history-oriented query in P2P spatio-temporal index. Aimed at dealing with the huge scale and complex query of historical spatio-temporal data, this paper proposed a double-ring structure index, which consists of a spatio ring and a temporal ring. This kind of index can independently support query from spatio and temporal dimensions, and make selectively estimation and query towards the double rings by building histogram. Based on this theory, the paper developed a histoy-oriented query P2P spatio-temporal index—DRHSTI, and designed the range query, KNN query and trajectory query. Since the double-ring query increased the index maintenance overhead, the paper adopted local spatio-temporal index node publish, dynamic slice index time-ring and cache technology to decrease the maintenance overhead of double-ring. Experiments showed that the double-ring based P2P distributed spatio-temporal index could not only keep low maintenance overhead, but also efficiently supported the history-oriented spatio-temporal query.(4) This paper putted forward an adjacent domain connection based future query oriented in P2P spatio-temporal index. The future-oriented predicted query is of huge dynamic updating and index query, so the efficiency of updating is one of the key problems. The method using physical special adjacent nodes to exchange the partial spatio-temporal states abstract, and then using the logical adjacent nodes further away to control the entire spatio-temporal states, could avoid the information lost caused by Hilbert curve dimensional degrade and increase the efficiency of query and update. Based on this principle, the paper proposed PeerFOX, which designed the routing table, point and region routing protocol using the concept of adjacent domain connection. Besides, the PeerFOX showed the algorithm of future-oriented range query, KNN query and continual query, and the index maintenance algorithm under dynamic environment. Experiments showed that PeerFOX could well deal with the update problem and have excellent query efficiency.(5) This paper developed an XML clustering based semi-structured query oriented descriptive spatio-temporal information organization method and index construction mechanism. Under heterogeneous environment, the format, criterion and measurement of the spatio-temporal data in each node are different, so the descriptive information is different when doing some query. Because of this query difficulty, this paper clustered the descriptive information XML, assembled the nodes with similar XML, and established the index based on domain. This kind of descriptive information was well organized in one domain, thus the semi-structural descriptive query could be in the domain and greatly decreased the forwarding cost. In designing the XML clustering, the paper developed an XML clustering method based on cluster-core, which could improve the clustering precision and speed, and also supported the incremental clustering. Experiments showed that the XML clustering based on cluster-core was of good quality and high efficiency. In addition, establishing index based on the XML clustering results could improve the efficiency of semi-structured spatio-temporal index query.(6) Application research. From homogeneity and heterogeneity aspects, this paper applied the research achievements to mobile objects on battlefield and spatio-temporal information resources in aerospace. The paper also designed and implemented two conceptual prototype systems to validate the validity and feasibility of its methods and technologies.