[Colloq] PhD Thesis Defense Panfeng Zhou- Tuesday, Aug. 8, 10am

[Rachel Kalweit]

College of Computer and Information Science
presents
PhD Thesis Defense
Panfeng Zhou

will speak on
Querying Multi-dimensional Data and Spatio-temporal Data with 
Non-overlapping Access Methods

Tuesday, August 8, 2006
10:00am
366 West Village H
Abstract
Multi-dimensional indexing and spatio-temporal indexing are widely used 
in spatial databases (e.g., VLSI, GIS, image databases) and moving 
objects databases (e.g., GPS, cellular databases). The R-tree family is 
one of the most popular multi-dimensional and spatio-temporal access 
methods. However, overlaps among index entries are a major impediment of 
the R-tree which affects both query performance and concurrency performance.

The hB-pi tree is a multi-dimensional access method which does not have 
overlap, and its index page fanout is insensitive to the dimension 
increases. In addition, the hB-pi tree integrates the concurrency and 
recovery algorithms from the II-tree. But the hB-pi tree indexes the 
whole space no matter whether or not there is any data in some 
sub-spaces. Indexing empty space (i.e., space without data inside) leads 
to unnecessary data page accesses which increase with growing dimension. 
This dissertation addresses this problem by proposing the hB-pi* tree, 
which efficiently indicates empty spaces and improves query performances 
while preserving the hB-pi's high fan-out and good concurrency. Our 
methods can be applied to any kd-tree based access methods. The hB-pi* 
tree outperforms the hB-pi tree and the R*-tree in querying low to 
medium dimensional (i.e., 2D to 8D) point data sets. To the author's 
knowledge, the hB-pi* tree is the first access method that has good 
query performance as well as good concurrency performance in indexing 
low to medium point data sets. The hB-pi*
tree also shows a performance that is comparable to that of the R*-tree 
in querying spatial objects with extents. Our claims are supported by 
extensive experimental evaluation.

Furthermore, we introduce the (historical and spatial) range close-pair 
query for moving objects} as an important problem for spatio-temporal 
databases. The purpose of a range close-pair query for moving objects is 
to find pairs of objects that were closer than a threshold during time 
interval I and within spatial range R, where the threshold, I and R are 
user-specified parameters.  This dissertation solves the range 
close-pair query using two components: a retrieval component and a 
close-pair identification component.  The retrieval component breaks up 
long trajectories into trajectory segments, which are produced in 
increasing time order, without the need for sorting. The retrieval 
component takes advantage of a new index mechanism, the Multiple 
TSB-tree which divides the space into non-overlapping cells. The 
segments are then pipelined to the close-pair identification component. 
The identification component introduces a novel spatial sweep that 
sweeps by time and one spatial dimension in parallel. Extensive 
experimental results are provided, demonstrating the advantages of the 
new approach.

Committee:
    Professor Betty Salzberg, advisor
    Professor Gene Cooperman
    Assistant Professor Donghui Zhang
    Assistant Professor George Kollios, Boston