Research On Authenticated Location-based Query Serivces In Cloud Environments

Continued advances in wireless communication technologies and the wide availability of positioning-enabled devices have led to a rapid market expansion in location-based services.With the explosive growth of the data scale,the cost of managing data and provisioning efficient location-based services locally becomes higher and might be unaffordable for small-to-medium location-based service providers.Cloud computing gives them a new option.Utilizing the advantages of cloud computing,such as rich computing resources,high reliability and relatively low price,more and more location-based service providers outsource their large-scale data and services to the third-party cloud service provider,which provides query services to clients on behalf of the location-based service providers.However,this outsourcing model brings a great challenge that the query results returned by the cloud service provider might be tampered due to a variety of reasons.Firstly,the cloud service provider might return tailored results for his/her own profits.Secondly,the cloud service provider might adopt some inferior algorithms that save computing resources but return suboptimal query results to the clients.Thirdly,growing security breaches and attacks on Clouds have been reported.In case that a cloud service provider is compromised,the query results could be forged.This problem draws more and more attention from both academic and industrial communities.How to provide authenticated location-based query services in cloud environments has become a hot research topic in cloud computing field.In this problem,we should make sure that the query results returned by the cloud service provider can be authenticated by the clients.How to provide efficient location-based query services and reduce the extra communication cost between the cloud service provider and clients and the computing cost at the clients side brought by the authentication function is the main challenge of this problem.In this paper,we focus on the most important data type in location-based services,spatial textual data,and study three authenticated location-based query services.The first is authenticated top-k spatial keyword queries.The second is authenticated spatio-textual similarity joins,and the third is authenticated location-aware publish/subscribe services.Through in-depth study,we make the following major contributions.(1)For the problem of authenticated top-k spatial keyword queries,we propose three schemes.The first is the basic approach,in which we propose an authenticated data structure for spatial textual data,named MIR-tree.However,the verification object constructed based on the MIR-tree(for clients' authentication)include much redundant textual information,which incurs high communication cost between the cloud service provider and clients and the computing cost at the clients side.Therefore,we propose an optimized scheme,named tree-forest indexes based scheme.In this scheme,we decouple the spatial and textual information in MIR-tree by splitting MIR-tree into tree-forest indexes.The verification object constructed based on the tree-forest indexes no longer includes redundant textual information.Therefore,the communication and computing cost can be both dramatically reduced.Moreover,we propose an entry pruning based scheme.By considering the constraints of both spatial proximity and textual similarity,we prune the entries in the verification object which are irrelevant to the authentication of query results.Thus,the verification object is further optimized.Extensive experimental studies on real large-scale datasets illustrate our proposed schemes can achieve good efficiency and scalability.(2)For the problem of authenticated spatio-textual similarity joins,we propose three schemes.The first is the pairwise authentication scheme.In this scheme,we propose an authenticated data structure named object hash tree.Based on the object hash tree,during join processing,a pair table that consists of the key information of each object pair is introduced for the cloud service provider to construct the verification object.The proposed second scheme is the cluster based scheme.In this scheme,we first propose a prefix inverted index.By using this index,during data preprocessing,the location-based service provider can filter the objects which must not be the join results and cluster the remaining objects in the data collection according to their spatial proximity and textual similarity.Compared with the pairwise authentication scheme,the filtered objects need not be included in the verification object,and thus the communication cost between the cloud service provider and location-based service provider is reduced.Moreover,when the location-based service provider authenticates join results,he/she only needs to examine the pairs constructed by the objects in each cluster,rather than all the object pairs in the data collection.Consequently,the computing cost at the location-based service provider side is also reduced.We also propose an order and bound based scheme to further optimize the cluster based scheme.Extensive experiments on a real-world dataset show the effectiveness and efficiency of our proposed schemes.(3)For the problem of authenticated location-aware publish/subscribe services,we propose an authenticated location-aware publish/subscribe framework under the assumption that messages are allowed a maximum delay ?t to be delivered to their corresponding subscribers.The location-based service provider organizes the messages within ?t in an authenticated data structure named TMR-tree.Based on the TMR-tree,the cloud service provider first computes the relevant messages for each subscription.During this process,we propose an inverted index pruning technique to reduce the times of inverted index(used to index the subscriptions)traversal,thus improving the efficiency of computing the relevant messages for each subscription.Then,the cloud service provider constructs a verification object for each subscription and the corresponding subscriber can authenticate the messages delivered to him/her.A thorough experimental study on a real-world dataset illustrates the effectiveness and efficiency of our proposed framework.