hide
Free keywords:
-
Abstract:
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.