Search for the Best but Expect the Worst - Distributed Top-k Queries over Decreasing Aggregated Scores

We consider distributed top-k queries in wide-area networks where the index lists for the attribute values (or text terms) of a query are distributed across a number of data peers. In contrast to existing work, we exclusively consider distributed top-k queries over decreasing aggregated values. State-of-the-art distributed top-k algorithms usually depend on threshold propagation to reduce expensive data access across the network, but fail to compute tight thresholds if the aggregation function is decreasing. Decreasing aggregation functions, however, occur naturally, for example when considering conjunctive queries. Our proposed algorithms allow for efficient execution of these kind of queries, using a combination of threshold propagation and semijoin techniques. We demonstrate these techniques for the problem of top-k peer selection in a Peer-To-Peer Web search engine. Our experimental results on real-world data shows the superiority of our approach over pure thresholding