The Hong Kong University of Science and Technology
Department of Computer Science


PhD Thesis Defence


"Spatial and Continuous Spatial Queries on Smart Mobile Clients"

By

Mr. Haibo Hu


Abstract

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 computing, 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
explore 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 contribute 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 distinct
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 consider the issue of location sensing and propose a generic
framework for monitoring 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 corresponding 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 fuzziness 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
thesis contributes to both the theoretical and practical aspects of the
middleware infrastructure for the next generation of location-based
services.


Date:			Friday, 12 August 2005

Time:			1:00p.m.-3:00p.m.

Venue:			Room 2464
			Lifts 25-26

Chairman:		Prof. Reinhard Renneberg (CHEM)

Committee Members:	Prof. Dik-Lun Lee (Supervisor)
                     	Prof. Qiong Luo
                        Prof. Lionel Ni
                        Prof. Danny Tsang (ELEC)
                        Prof. Arkady Zaslavsky (Comp. Sci. & Software Engg.,
						Monash Univ.)


**** ALL are Welcome ****