Data outsourcing is a cost-effective solution for data owners to tackle issues such as large volumes of data, huge number of users, and intensive computation needed for data analysis. They can simply upload their databases to a cloud and let it perform all management works, including query processing. One problem with this service model is how query issuers can verify the query results they receive are indeed correct. This concern is legitimate because, as a third party, clouds may not be fully trustworthy, and as a large data center, clouds are ideal targets for hackers. There has been significant work on query result verification, but most consider only simple queries where query results can be attained by checking the raw data against the query conditions directly. In this paper, we consider the problem of enabling users to verify the correctness of the results of analytic queries. Unlike simple queries, analytic queries involve ranking functions to score a database, which makes it difficult to build data structures for verification purposes. We propose two approaches, namely one-signature and multi-signature, and show that they work well on three representative types of analytic queries, including top-k, range, and KNN queries, through both analysis and experiments.
翻译:数据外包是数据所有者处理大量数据、大量用户和数据分析所需大量计算等问题的具有成本效益的解决办法。他们可以简单地将数据库上传到云层,让其执行所有管理工作,包括查询处理。这种服务模式的一个问题在于查询者如何核查他们收到的查询结果,这是正确的。这种关注是合理的,因为作为第三方,云可能不完全可靠,而作为一个大型数据中心,云云是黑客的理想目标。在查询结果核查方面已经做了大量工作,但多数人只考虑通过直接根据查询条件检查原始数据来取得查询结果的简单查询。在本文件中,我们考虑了使用户能够核查分析查询结果的正确性的问题。与简单的查询不同,分析性查询涉及对数据库进行评分的分级功能,这使得很难为核查目的建立数据结构。我们提出了两种方法,即一式签名和多式签名,并表明它们通过分析和实验在三种具有代表性的查询类型上很好的工作,包括顶部、射程和 KNNT查询。