中央研究院 資訊科學研究所

With the popularity of location-based services and the abundant usage of smart phones and GPS-enabled devices, the necessity of outsourcing spatial data has grown rapidly over the past few years. Meanwhile, the fast arising trend of Cloud storage and Cloud computing services has provided a flexible and cost-effective platform for hosting data from businesses and individuals, further enabling many location-based applications. Nevertheless, in this database outsourcing paradigm, the authentication of the query results at the client remains a challenging problem. In this talk, I will focus on the Outsourced Spatial Database (OSDB) model and introduce an efficient scheme, called VN-Auth, which allows a client to verify the correctness and completeness of the result set. The approach is based on neighborhood information derived from the Voronoi diagram of the underlying spatial dataset and can handle fundamental spatial query types, such as k nearest neighbor and range queries, as well as more advanced query types like reverse k nearest neighbor, aggregate nearest neighbor, and spatial skyline. We evaluated VN-Auth based on real-world datasets using mobile devices (Google Droid smart phones with Android OS) as query clients. Compared to the current state-of-the-art approaches (i.e., methods based on Merkle hash trees), our experiments show that VN-Auth produces significantly smaller verification objects and is more computationally efficient, especially for queries with low selectivity.

Wei-Shinn Ku received his Ph.D. degree in computer science from the University of Southern California (USC) in 2007. He also obtained both the M.S. degree in computer science and the M.S. degree in Electrical Engineering from USC in 2003 and 2006 respectively. He is an Associate Professor with the Department of Computer Science and Software Engineering at Auburn University, USA. His research interests include databases, mobile computing, geographic information systems, and location-based services. He has published more than 60 research papers in refereed international journals and conference proceedings. He is a member of the ACM and the IEEE.