University of Illinois Urbana-Champaign

Efficient indexing of spatial objects in object-oriented databases

Lee, Jui-Tine

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/21955

Description

Title
Efficient indexing of spatial objects in object-oriented databases
Author(s)
Lee, Jui-Tine
Issue Date
1993
Doctoral Committee Chair(s)
Belford, Geneva G.
Department of Study
  • Geotechnology
  • Computer Science
Discipline
  • Geotechnology
  • Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Geotechnology
  • Computer Science
Language
eng
Abstract
  • The use of index structures can increase the performance of query processing. However, the index structures for standard databases are not suitable for the non-standard database applications such as geographical applications, CAD applications, VLSI designs and image processing. For non-standard databases, we need an index structure which preserves spatial neighborhood. In this thesis, we proposed two new access methods with improved performance: a projection method and a partition method.
  • In the projection method, we project a spatial data object onto each axis. The projection of an object forms an interval in each dimension. Then, we organize the projection intervals in each dimension as a B-tree. To perform a query, we need to search each of the B-trees and find the set of possible candidates for the given query in each dimension. Then we compute the intersections of those possible candidate sets, which is the final result.
  • In the partition method, if an object is not a point, the object is approximated by a bounding rectangle and then the bounding rectangle is transformed into a point in higher dimensions. The transformed points are organized as a directory tree. Instead of using one tree for each dimension like the projection method, the partition method builds up only one directory tree. All queries are performed against this directory tree.
  • After introducing our two methods, we perform several experiments to compare our methods with other methods for spatial databases under arbitrary data distributions and various types of queries.
Type of Resource
text
Permalink
http://hdl.handle.net/2142/21955
Copyright and License Information
Copyright 1993 Lee, Jui-Tine

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois