Towards Efficient Ranked Query Processing in Peer-to-Peer Networks

P2P computing is gaining more and more attention from both academia and industrial communities for its potential to reconstruct current distributed applications on the Internet. However, the basic DHT-based P2P systems support only

exact-match

queries. Ranked queries produce results that are ordered by certain computed scores, which have become widely used in many applications relying on relational databases, where users do not expect exact answers to their queries, but instead a ranked set of the objects that best match their preferences. By combing P2P computing and ranked query processing, this paper addresses the problem of providing ranked queries support in Peer-to-Peer (P2P) networks, and introduces efficient algorithms to solve this problem. Considering that the existing algorithms for ranked queries consume an excessive amount of bandwidth when they are applied directly into the scenario of P2P networks, we propose two new algorithms:

PSel

for ranked selection queries and

PJoin

for ranked join queries.

PSel

and

PJoin

reduce bandwidth cost by pruning irrelevant tuples before query processing. Performance of the proposed algorithms are validated by extensive experiments.