[Colloq] PhD Thesis Defense, Jing Shan, Tuesday, Aug. 15

[Rachel Kalweit]

College of Computer and Information Science
presents a PhD Thesis Defense by:
Jing Shan

Title:
The Spatial C-Tree: An Index Method with High Concurrency and Efficient 
Recovery


Tuesday, August 15, 2006
10:00am
366 West Village H

Abstract

Indexes are used in database management systems as a mechanism to speed 
up data retrieval. A good index structure should ensure that the data 
access through it is efficient and transactional. For one dimensional 
data, the B$^{+}$-tree and its variants, such as the B$^{link}$-Tree and 
the $\Pi$-tree, are used widely because of their good query performance 
and concurrency control and recovery. However, structures for 
multidimensional data, despite the intense research for more than two 
decades, have not been so successful. Very few of the many proposed 
structures are implemented in commercial databases. For those that have 
been used, users are confronted with either poor performance or low 
concurrency.

We proposed a new spatial access method called the Spatial C-Tree.  Our 
approach extends the C-Tree framework, which provides efficient 
concurrency control and robust recovery mechanism. We have implemented 
the Spatial C-Tree and compared it with several R-Tree variants. Our 
performance results show that the Spatial C-Tree performs very well in 
terms of insertion and exact match queries with various data sets. Our 
range query performance is also comparable to the R-Tree variants. The 
query performance and the high concurrency guarantee make the Spatial 
C-Tree a promising access method for spatial data.

Thesis Defense Committee:
   Professor Betty Salzberg (Advisor)
   Dr David Lomet (Microsoft Research)
   Professor Donghui Zhang
   Professor Rajmohan Rajaraman

-- 
Rachel Kalweit
College of Computer and Information Science
202 West Village H
Northeastern University
phone: 617-373-2462
fax: 617-373-5121
rachelb at ccs.neu.edu