  Spurred by developments such as cloud computing, there are increasing efforts
for outsourcing of data management. A company (data owner) who lacks expertise
and comptational resources can outsource his data to a third-party service
provider (server), who provides storage and query evaluation on the outsourced
data as the services. One of the security concerns of the outsourcing paradigm
is the integrity of the returned query results on the outsourced data. In this
paper, we consider the outsourcing of probabilistic databases, on which query
evaluation is of high complexity. A dishonest server may return cheap (and
incorrect) query answers, hoping that the client who has weak computational
power cannot catch the incorrect results. To address this issue, we design
efficient integrity verification methods for both all-answer and top-k query
evaluation on outsourced probabilistic databases. Our empirical results
demonstrate the effectiveness and efficiency of our verification methods.
