Authenticated Top-K Aggregation in Distributed and Outsourced Databases

Top-k queries have attracted interest in many different areas like network and system monitoring, information retrieval, sensor networks, and so on. Since today many applications issue top-k queries on distributed and outsourced databases, authentication of top-k query results becomes more important. This paper addresses the problem of authenticated top-k aggregation queries (e.g. “find the k objects with the highest aggregate values”) in a distributed system. We propose a new algorithm, called Authenticated Three Phase Uniform Threshold (A-TPUT), which provides not only efficient top-k aggregation over distributed databases but also authentication on the top-k results. We also introduce several enhancements for A-TPUT to reduce both the computation cost and the communication cost. Finally, we confirm the efficiency of our solutions through an extensive experimental evaluation.