With the number of global mobile subscribers now exceeding 1.5 billion and with various mobile gadgets built on cutting-edge technologies gaining worldwide popularity, location-based services (LBSs), the killer applications in mobile com-puting, show compelling promise in the telecommunication market. However, although these mobile devices are equipped with CPUs, considerable amount of memory, wireless connections, batteries, and even positioning apparatus, these resources are still limited compared to their desktop/laptop counterparts. As such, research is necessary regarding the efficient management of these resources, especially the data....[ Read more ]

With the number of global mobile subscribers now exceeding 1.5 billion and with various mobile gadgets built on cutting-edge technologies gaining worldwide popularity, location-based services (LBSs), the killer applications in mobile com-puting, show compelling promise in the telecommunication market. However, although these mobile devices are equipped with CPUs, considerable amount of memory, wireless connections, batteries, and even positioning apparatus, these resources are still limited compared to their desktop/laptop counterparts. As such, research is necessary regarding the efficient management of these resources, especially the data.

In this thesis, we generally call these devices "smart mobile clients" and ex-plore their data-management issues in the context of location-based services. More specifically, we investigate how spatial and continuous spatial queries can be efficiently processed on these smart mobile clients, by letting the clients con-tribute their resources to the processing of these queries. What distinguishes this thesis from existing spatio-temporal database literature is that it proposes both comprehensive frameworks and detailed techniques to exploit the three most dis-tinct features of smart mobile clients, namely, the caching, location sensing, and the inaccuracy of the location-sensing technology.

The main body of the thesis addresses the three features and proposes our comprehensive solutions respectively.

We first devise a new caching model called "proactive caching", which serves as the caching framework to process all types of spatial queries on smart mobile clients. The new caching model reuses the cached data at the object level, and thus achieves outstanding performance compared with traditional page caching or semantic caching methods with respect to cache hit rate and bandwidth saving.

We then study location sensing and propose a generic framework for mon-itoring continuous spatial queries, where the clients detect their own locations and decide if they need to perform location updates. Since clients are aware of the queries being monitored through the notion of safe region, the framework guarantees 100% monitoring accuracy and significant savings in monitoring cost, that is, the wireless bandwidth and the server CPU overhead.

To address the inaccuracy issue of the location sensors, we introduce a new type of query that allows the users to specify their locations fuzzily by ranges rather than exact points. We apply this idea of fuzziness to the nearest neighbor (NN) query and propose the range nearest neighbor (RNN) query and the corre-sponding query processing techniques. In addition, we devise an auxiliary index called EXO-tree to speed up any type of NN queries. We show that the fuzzi-ness and user privacy can be preserved at the cost of just a small computational overhead.

Because spatial queries are fundamental to location-based services, this the-sis contributes to both the theoretical and practical aspects of the middleware infrastructure for the next generation of location-based services.