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.


op-k, Authentication, Distributed Databases, Outsourced Databases

Date of this Version



2012 ASE/IEEE International Conference on Social Computing and 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.