Continuous Spatial Authentication

Continuous Spatial Authentication,10.1007/978-3-642-02982-0_7,Stavros Papadopoulos,Yin Yang,Spiridon Bakiras,Dimitris Papadias

Continuous Spatial Authentication   (Citations: 2)
BibTex | RIS | RefWorks Download
Recent advances in wireless communications and positioning devices have generated a tremendous amount of interest in the continuous monitoring of spatial queries. However, such applications can incur a heavy burden on the data owner (DO), due to very frequent location updates. Database outsourcing is a viable solution, whereby the DO delegates its database functionality to a service provider (SP) that has the infrastructure and resources to handle the high workload. In this framework, authenticated query processing enables the clients to verify the correctness of the query results that are returned by the SP. In addition to correctness, the dynamic nature of the monitored data requires the provision for temporal completeness, i.e., the clients must be able to verify that there are no missing results in between data updates. This paper constitutes the first work that deals with the authentication of continuous spatial queries, focusing on ranges. We first introduce a baseline solution (BSL) that achieves correctness and temporal completeness, but incurs false transmissions; that is, the SP has to notify clients whenever there is a data update, even if it does not affect their results. Then, we propose CSA, a mechanism that minimizes the processing and transmission overhead through an elaborate indexing scheme and a virtual caching mechanism. Finally, we derive analytical models to optimize the performance of our methods, and evaluate their effectiveness through extensive experiments.
Conference: Symposium on Large Spatial Databases - SSD , pp. 62-79, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...For example, [6, 11, 21] study the authentication of relational queries; [7, 15] study the authentication of sliding window (data stream) queries; [12] addresses this issue on text similarity queries; [14, 22] study the authentication of static spatial queries; and [24] addresses the authentication of shortest path queries...
    • ...Existing techniques for authenticating static spatial queries such as [14, 22] cannot help in authenticating moving queries because their authentication target is the query result, which is a subset of the dataset, whereas the authentication targets of moving queries include both the query result and the safe region—the latter is not a subset of the dataset but dynamically computed by the LBS at run-time...
    • ...Query authentication In the literature, most authentication techniques [6, 7, 12, 14, 15, 21, 22, 24] are based on Merkle tree [8], which is an authenticated data structure (ADS) that is built on the dataset...
    • ...Existing spatial authentication techniques [14, 22] cannot help in authenticating moving queries because they focus on static queries, so that the authentication targets (i.e., the query results) are part of the dataset...

    Man Lung Yiuet al. Authentication of moving kNN queries

    • ...Papadopoulos et al. [22] designed a solution for the authentication of continuous spatial queries, i.e., queries that are constantly evaluated on a highly dynamic database (consisting of moving objects)...

    Ling Huet al. Verifying spatial queries using Voronoi neighbors

Sort by: