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


PhD Thesis Defence


"Indexing of Location-Dependent Data in Mobile Computing Environments"

By

Miss Baihua Zheng


Abstract

In the approaching era of pervasive computing, we can expect to see a huge
population of mobile clients, including people and devices, which require
access to information at any place. Hence, the locations of clients and
data objects have become important parameters for many information
services -- what we call location-dependent information services (LDISs).
This thesis focuses on the provision of LDISs via wireless broadcasting.
Compared to point-to-point connection, wireless broadcast systems provide
a more efficient data delivery method that allows simultaneous retrieval
of information by numerous clients. However, they introduce many
limitations that have not been considered in traditional computing
environments. This thesis conducts research on advanced indexing
techniques to improve the performance of LDISs.

For location-dependent data (LDD), the validity of a data value is
dependent on the location of the client retrieving the data value. The
retrieval of LDD requires the identification of the region that the client
is residing in, given a partition of the geographical space. For example,
finding the name of the city that the client is visiting requires
identifying which city the client is located in given the city boundaries
of a country. D-tree is proposed to efficiently determine the target
region by indexing the division of adjacent regions. Compared to the
existing approximation methods, such as Minimal Bounding Rectangles (MBRs)
in R-tree, D-tree does not index any overlapping region and therefore
avoids back-tracking. Compared to decomposition schemes, such as the
trapezoidal map, D-tree represents the divisions in the search space and
does not introduce any auxiliary line segments to the space. Therefore,
the storage cost of D-tree is very low. Simulation results of both
synthetical and real datasets show that D-tree outperforms existing
indexes significantly in terms of search time.

Next, we focus on nearest-neighbor search, which can be answered based on
the locations of the data objects in the search space. We propose the
grid-partition index which first partitions the whole search space into
disjoint sub-spaces, called grid cells, to efficiently narrow down the
required search space for a given query point and then for each grid cell
index only those objects that are possibly the nearest neighbors to some
query point within that grid cell. Since the indexing of objects is more
efficient than that of regions and the number of objects indexed by each
grid cell is much smaller than the whole population, the search
performance is improved. Three partition algorithms have been proposed to
partition the original space into disjoint grid cells with the help of a
newly defined performance metric, index efficiency.

Based on the proposed D-tree and grid-partition index, different kinds of
location-dependent queries (LDQs) can be efficiently answered. However, a
specific D-tree only serves one kind of LDQ and a grid-partition index is
only workable for a nearest-neighbor search. Therefore, a universal index
structure is still desirable to answer different LDQs. Motivated by this,
a Hilbert-curve index is proposed. To cater for the linear browsing
limitation of wireless broadcast systems, the objects are mapped onto a
linear space using a space-filling curve, namely the Hilbert curve.
Different search algorithms are devised to answer window queries,
k-nearest-neighbor queries, and continuous-nearest-neighbor queries. A
series of simulation experiments are conducted to evaluate the proposed
search algorithms.


Date:			Friday, 27 June 2003

Time:			2:00p.m.-4:00p.m.

Venue:			Room 2302
			Lifts 17-18

Chairman:		Dr. Yue-Kuen Kwok (MATH)

Committee Members:		Prof. Dik-Lun Lee (Supervisor)
			Prof. Frederick Lochovsky
			Dr. Dimitris Papadias
			Dr. David Bodoff (ISMT)
			Prof. Arbee L.P. Chen (Comp. Sci.,
					       National Tsing Hua Univ.)


**** ALL are Welcome ****