Information retrieval system have to deal with imprecise information routinely, for example due to uncertainty in data extraction processes or due to probabilistic relevance models. Queries are usually performed in a top-k style manner where the the k most 'relevant' results for a query are computed.
Unfortunately the standard techniques for top-k queries fail in a distributed or peer-to-peer setting, as network transfer is very costly and requires specialized algorithm.
In fact it seems to be infeasible to compute the exact answer in large networks: We could demonstrate that the uncertainty during query processing forces existing algorithms to send a very substantial fraction of the data over the network, which is prohibitive expensive.
We therefore propose two approaches: First, to use query optimization techniques to improve network traffic in general, and second, to use data-adaptive sampling to reduce the relevant part of the data. In our experiments this greatly reduced the query execution time while still offering high recall.