Research On Cost Model For P2P-based Distributed Spatio-Temporal Indexing Range Query

With the development of information collection technology, spatio-temporal data is increasing fast, not only from the aspect of amount, but also the extent of distribution. This, however, has directly driven the development of spatio-temporal query technology from centralized style to distributed one. As the technology of improving the spatio-temporal query efficiency, spatio-temporal index is developing towards distributed style as well. The cost model of index has been a very important research topic in database research field, and it plays an important role in judgment of index designing and optimization of data querying. Thus, the cost model has got much attention around the world.So far, the research of cost model based on centralized index has earned some achievements. However, the research of cost model based on distributed index, especially the condition under the P2P environment, need to be perfected. This paper proposed histogram-based cost model on P2P-based spatio-temporal index range query, which can build cost models for different P2P-based spatio-temporal index. In P2P mode, the spatio-temporal data is stored dispersedly, and each node lacks the entire knowledge of data distribution, which will cause the query messages delivered to each other repeatedly. Through the factor analysis towards the current P2P spatio-temporal index query cost, this paper has found the main factors which affect the query cost. This paper has got the following achievements:(1) Proposed the histogram construction and maintenance methods under P2P condition. Histogram technique occupies less storage space and needs lower maintenance overhead, so it is widely used in centralized spatial-time index cost models. However, in P2P spatio-temporal index, because the nodes are free to join and exit, each node can't learn the entire knowledge of all nodes, and the traditional histogram construction method loses effect. Through deep study of histogram and P2P technique, this paper developed a P2P-MinSkew algorithm to construct and maintain histogram under P2P environment, which used piggyback strategy and cost less.(2) Developed histogram-based cost constructing method in P2P spatio-temporal index range query. Because of the different facts of spatial-time index query cost between the P2P system and centralized one, the traditional cost model constructing methods in spatial-time index can't be used to the cost model construction in P2P spatial-time index. Through deep study of the mechanism of P2P spatial-time index and query methods, the paper adopted histogram technology and selective estimate to build the models, respectively to deal with the history oriented and future oriented range queries.(3) Building the cost models and simulating aimed at the current P2P spatio-temporal space. This paper built the cost models based on the current P2P spatio-temporal space, and simulated on the PeerSim simulator. According to the large amount of simulation results, the cost model was proved to be right and effective. The cost model technique is important to the optimization of P2P spatio-temporal index query. This paper designed the prototype conceptual system, which oriented the spatio-temporal queries of mobile targets on digitized battlefield. The experiments validated the optimization role of the cost model towards data queries.