Location based spatial queries in mobile environments.

摘要

Location-dependent queries, such as determining the proximity of points of interest (e.g., hotels, gas stations) to a mobile host, are an important class of inquiries. I propose novel approaches to support spatial queries from mobile hosts with high scalability, short response time, and strong user privacy protection. There are four main sub-topics in this dissertation. The first topic is related with static point of interest (e.g., restaurants, gas stations) information retrieval. I illustrate how previous query results cached in the local storage of neighboring mobile peers can be leveraged to either compute spatial queries at a local host or improve the query result accuracy by leveraging the sharing capabilities of wireless ad-hoc networks (e.g., IEEE 802.11b/g). Since users have mobility, the second topic is about utilizing dynamic information (e.g., real-time traffic information) to improve query accuracy. Security and privacy are always important issues for all systems. I design solutions for spatial query privacy protection in mobile environments which is the third topic. The last topic concerns a distributed geotechnical information management architecture as an application of several proposed algorithms. Each topic is described in more detail as follows.; Static information. In order to improve query efficiency, each mobile host caches data packets downloaded from the data source (e.g., a data broadcast channel or a DB server) in its local memory. Since all the data objects located inside mobile host cache are all from database servers, I define the area which is covered by the cached data as a verified region. For any spatial query, a mobile host can execute both mechanisms---accessing the data source and requesting verified region information from peers. Afterward the mobile host reorganizes the cached data returned from peers and attempts to fulfill his/her spatial query. This process is termed the verification procedure. Because the access latency is relatively long in broadcast systems, the verification procedure can usually be accomplished before the required data packets arrive to improve query efficiency.; Dynamic information. Most nearest neighbor algorithms rely on static distance information to compute queries (e.g., Euclidean distance or spatial network distance). However, the final goal of a user when performing an NN search is often to travel to one of the points of the search result. In this case, finding the nearest neighbors in terms of travel time is more important than the actual distance. In the existing NN algorithms, dynamic real-time events (e.g., traffic congestions, detours, etc.) are usually not considered and hence the pre-computed nearest neighbor objects may not accurately reflect the shortest travel time. I propose a novel travel time network that integrates both spatial networks and real-time traffic event information. Based on this foundation of the travel time network, I develop a local based greedy nearest neighbor algorithm and a global-based adaptive nearest neighbor algorithm that both utilize P2P sharing of real-time information to provide adaptive query search results.; Privacy protection. With the proliferation of mobile devices, location-based services have become more and more popular in recent years. However, users have to reveal their location information to access location-based services with existing service infrastructures. It is possible that adversaries could collect the location information, which in turn invades users' privacy. There are existing solutions for query processing on spatial networks and mobile user privacy protection in Euclidean space. However there is no solution for solving queries on spatial networks with privacy protection. Therefore, I provide network distance spatial query solutions which can preserve user privacy by utilizing K-anonymity mechanisms.; Geotechnical information management architecture. Web services can help facilitate the exchange