An efficient P2P range query processing approach for multi-dimensional uncertain data

In recent years, the management of uncertain data has received much attention in a centralized database. However, to our knowledge, no work has been done on this topic in the context of Peer-to-Peer (P2P) systems, and the existing techniques of P2P range queries cannot be suitable for uncertain data. In this paper, we study the problem of answering probabilistic threshold range queries on multi-dimensional uncertain data for P2P systems. Our novel solution of the problem, PeerUN, is based on a tree structure overlay which has the optimal diameter and can support efficient routing in highly dynamic scenarios. The issues (also faced with multi-dimensional uncertain data) of existing techniques for multi-dimensional indexing over a structure P2P network are (1) they process queries efficiently at the cost of huge maintenance overhead; (2) they have low maintenance costs, but they suffer poor routing efficiency or introduce huge network overhead. PeerUN can process range queries on multi-dimensional uncertain data efficiently with low maintenance costs. PeerUN achieves this by introducing a series of novel queries processing algorithms and a cost-based optimal data replication strategy. Experimental results validate the effectiveness of the proposed approach. © 2009 Springer Berlin Heidelberg.