Caching and query processing of spatial data in mobile networks

The emergence of powerful portable devices, along with advances in wireless communication technologies, has made mobile computing a reality. Data management in mobile computing is a key research issue and has aroused much attention in the research community. Since users in mobile computing environments enjoy unrestricted mobility and ubiquitous information access, location information, both about the users and the data, is an important factor to consider in data management. In this thesis, we develop several caching and query processing techniques for spatial queries in mobile networks. To enhance spatial query processing in mobile peer-to-peer networks (MP2PNs), we propose a novel collaborative caching framework, namely, structure-embedded collaborative caching (SECC), which allows a peer to query its neighboring peers progressively to build up the query result. By designing a novel index structure called Signature Augment Tree (SAT), we address two crucial issues in SECC. First, we propose a cost-efficient collaborative query processing method in MP2PNs, including peer selection and result merge from multiple peers. Second, we develop a novel collaborative cache replacement policy which maximizes cache effectiveness by taking into consideration not only the peer performing cache replacement but also its neighbors. We implement two SECC schemes, namely, the periodical and adaptive SAT-based schemes, with different SAT maintenance policies. We further investigate a new type of spatial data, called bounded spatial datasets (BSDs), in which a spatial item is either an object with known exact location or a rectangular region confining a collection of unknown objects. BSDs collectively impose a set of constraints on the locations of the objects, which are used to derive the answer sets of spatial queries. We analyze the constraints in BSDs and derive the properties of the answer sets for two important types of spatial queries, namely, range and k-nearest-neighbor (kNN) queries. We investigate different strategies for determining the answer sets and propose two distributed query processing approaches, namely, the site-based approach and the area-based approach. Particularly, we prove an optimal division in the area-based approach. Moreover, we develop heuristics based methods to address key issues in query processing, including site selection and data collection. Finally, to reduce the computing cost for obtaining the optimal area division, we develop an alternative division scheme which can achieve similar performance as the optimal division method while incurring negligible computing cost during query processing. We provide extensive experimental results to support the superiority of the proposed methods