HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6512
Title: Authenticated query processing
Authors: Papadopoulos, Stavros
Issue Date: 2010
Abstract: An increasing number of enterprizes outsource database functionality to third-party service providers, which answer queries received from clients. These providers may be untrustworthy and possibly tamper with the results. Authenticated query processing enables the clients to verify that the results indeed originate from the data owner (authenticity), and include all data satisfying the query (completeness). The most popular database outsourcing model requires that the data owner and the service provider construct identical copies of an authenticated data structure (ADS) on the outsourced data. The ADS is cryptographically signed by the owner. The service provider uses the ADS to answer the queries and generate a verification object, which includes cryptographic information for establishing the authenticity and completeness of the results. In this thesis we present methods for authenticated query processing in several challenging scenarios. Initially, we devise efficient solutions for authentication on relational data streams, where the highly dynamic nature of the data motivates the need for efficient continuous query processing, fast ADS updating, and provision for temporal completeness that allows the clients to verify that there are no missing results in between updates. Subsequently, we propose sophisticated ADSs for authenticating spatial queries, such as ranges, nearest neighbor (NN) queries, etc. Finally, we design the authenticated multi-step NN framework, which enables efficient verification of NN query results, in settings where the distance function is expensive and/or the data dimensionality is high. We demonstrate the performance superiority of our solutions against our competitors through extensive analytical and experimental evaluations.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2010
xii, 138 p. : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2010 Papado
URI: http://hdl.handle.net/1783.1/6512
Appears in Collections:CSE Doctoral Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.