Researches On The Top-k Query Processing Techniques Over Uncertain Data In P2P Networks

With the rapid development of information technology, P2P network received widely attention; it has become one of the most popular applications on network share. Because user does not always want to find out all the accurate results, all they need are those top k results in sequence of all the related results. In this case, as a basic aggregation query, Top-k plays an important role in many fields. In P2P networks, Top-k query processing also holds a fairly important position.In distributed environment including sensor network and P2P network, factors such as accuracy of measurement tools and testing environment and network postponing can lead to uncertain and obscure information; In recent years, although big progress has been made in Top-k query processing aimed at catch data in centralized database, in P2P distributed environment, how to get the uncertain data Top-k query efficiently in P2P remains difficult. So it is still a hot topic in this area.In this thesis we present a novel approach to process uncertain data Top-k query in large-scale P2P network, this approach is suitable for the super-peer P2P network structure, and it can make the full use of the super-peer’s capacity to complete the Top-k query processing over data. With this approach, firstly, we can build a peer constructs index for each local uncertain data using the improved quad-tree; And then establish the distributed ring index as the basis of quad indexing tree to make the uncertain data index distribute the different super-peer to realize the load balance in the network with the super-peer form gathering index and store summary information of all the uncertain data in the whole network. Based on the proposed index structure, this thesis puts forward an effective global number pruning strategy in super-peer to reduce the huge costs that spend on communication and computation firstly. Then we propose a local pruning approach in super-peer based on the relationship of upper and lower bounds to reduce the computation costs. After the merger effective candidate set, we can determine the final Top-k results through constant pruning. Extensive simulation experiments have been conducted to verify the correctness and the efficiency in this thesis, the experimental results show that this method has a good property in data transmission cost, the pruning ratio and the load balance.