Research On Location And Textual Based Queries And Authentication Strategies

With the development of wireless communication technology and the growing popu-larity of smart terminals, as one of the key techniques supporting location-based services (LBSs), location-Dependent queries (LDQs) attract more and more attentions in both a-cademia and industry. Considering a significant number of uncertain data are accumulated in LBSs, and Top-k Dominating queries are widely utilized LDQ, researchers start to study how to process Top-k dominating queries on uncertain data, and many studies have been proposed, which only focus on static probabilistic database. However,these studies could not be employed to process uncertain data stream. There is no work investigating Top-k dominating queries over uncertain data stream. To scale up LBSs along with their ever-growing popularity, the database outsourcing paradigm is becoming increasingly popular. In this paradigm, there exist two major concerns in the outsourced spatial database model. First, since the service provider (SP) is not the real data owner (DO), it is not always trust-worthy and may send inaccurate or incorrect results to the client. Second, query results may be tampered with malicious attackers. Therefore, it has certain value of research to study how to provide efficient authentication strategies for LDQs. Driven by the advance in loca-tion positioning techniques and popularity of location sharing services, there are a rapidly growing amount of spatial-textual objects collected in the application of LBSs. The tech-nologies for spatial-textual objects are developing, and some research results have appeared in the literature. To our knowledge, most of the existing processing approaches are limited to Euclidean space, and none of them could be used in road network space. Hence, it is valuable to study processing techniques for spatial-textual objects in road network space.This paper firstly discusses the issue of Top-k Dominating queries over uncertain data streams. It first describes how to compute the dominating ability (score) for an uncertain data. Considering the computation score for each uncertain data is expensive, we compute score interval instead of computing score directly, and design techniques to compact the score interval. The technique of the sliding window (W) is employed in proposed SWPTD algorithm to retrieve the probabilistic Top-k Dominating query results (PTOPK) over uncer-tain data streams. We find when W is moving a step, SWPTD has to compute PTOPK from scratch, which indicates the information of the result obtained in the last step are not full taken advantage by SWPTD. When the size of W grows larger, the efficiency of SWPTD deteriorates sharply. Considering most of uncertain data not in PTOPK cannot be become a member of PTOPK in the next step. For each object oi?PTOPK, in its minimum time interval (MTI), it cannot be become a member of PTOPK. Therefore, it does not need to check each oi?PTOPK among the period of MTI, PEA algorithm is proposed based on this idea. Finally, simulation experiments demonstrate PEA is more efficient and has certain value of practical application.Among the many types of location-based queries, one important class is reverse k near-est neighbor (RkNN) query, which has various applications in LBS, marketing and decision support systems. This thesis takes a first step to address the RkNN query authentication problem. The method designed for the SP aims to retrieve RkNN query result and con-struct the compact VO based on influence zone. Furthermore, two approaches (IZ-Auth, AIZ-Auth) are proposed for the client to verify the query result. Particularly, IZ-Auth re-computes RkNN based on information extracted from VO. As each object in the influence zone Zk is a member of RkNN result, therefore, AIZ-Auth verify RkNN result based on the authentication of influence zone. And the complex of algorithms are analyzed. The exper-imental results show that both monochromatic and bichromatic RkNN query result can be authenticated by our approaches, and AIZ-Auth has better performance than that of existing solutions.This thesis takes the first step to investigate a novel problem, namely, reverse spatial and textual k nearest neighbor (RSTkNN) queries on road networks. We first formalize the RSTkNN queries and present several spatial keyword pruning methods to accelerate the query processing. Then, the framework of RSTkNN queries is proposed. In order to check each candidate spatial-textual objects, the first verifying algorithm (i.e., NE-RSTkNN) in our solutions is based on the network-expansion. In order to avoid expanding road networks multiple times as the first method does, we take advantage of Network Voronoi Diagram (NVD) to develop the second algorithm (i.e., VD-RSTkNN) to obtain RSTkNN results. The experimental results demonstrate the efficiency of our approaches, and VD-RSTkNN gains better performance.