Query processing in multiresolution spatial databases

Prasher, Sham (2005). Query processing in multiresolution spatial databases PhD Thesis, School of Information Technol and Elec Engineering, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE20972.pdf Full text application/pdf 13.09MB 3
Author Prasher, Sham
Thesis Title Query processing in multiresolution spatial databases
School, Centre or Institute School of Information Technol and Elec Engineering
Institution The University of Queensland
Publication date 2005
Thesis type PhD Thesis
Supervisor Xiaofang Zhou
Total pages 245
Collection year 2005
Language eng
Subjects 08 Information and Computing Sciences
Formatted abstract

The advent of remote sensing, satellite, and information system technologies have seen a rapid increase in the amounts of geographic spatial data being generated and stored. In parallel there is an ever-growing commercial and private market for the use of such data. Several examples where spatial data can he used to improve business practice, or facilitate new applications include agriculture, navigation, traffic monitoring, weather monitoring, construction planning, and town planning. In addition, many applications may utilise the same spatial dataset for different purposes. Mobile users may wish to view a very large scale map when using a portable device with limited display real-estate. Conversely climatologists will need to view a large region in order to properly plot weather patterns. 

Multiresolution databases are suitable for the growing needs of spatial applications as they facilitate access to spatial data over different resolutions, while maintaining only a single stored instance at a fixed resolution. However, these systems have only been explored with respect to map visualisation where the number of supported resolutions is very small. Given the scope of applications, and varying capabilities of hardware display devices, it is desirable to support as many resolutions as possible. 

Another concern with multiresolution systems is that they have been designed only for map visualisation. Hence only issues regarding the spatial window query have been investigated. A spatial data repository could potentially be used for many other applications such as analytical data mining. Therefore the database should be able to support hath small-scale and large-scale processing simultaneously and efficiently. 

In this thesis a point-based multiresolution data structure is proposed to handle both small-scale and large-scale spatial operations. The structure is first applied to the cartographic processes simplification and tokenisation to evaluate efficiency when handling small data loads. Next it is applied to the amalgamation operation under high data loads to simulate use for data mining applications. 

The data structure uses z-values to encode spatial geometries. The advantage of this approach is twofold. First a large number of resolutions of data can be extracted from a single instance of the data stored at one resolution. Second, certain topological anomalies that commonly occur in cartographic processes, as well as other operations that manipulate spatial data, can be avoided. These advantages overcome two drawbacks of existing multiresolution systems. Moreover, the z-value coding scheme can be used to control the precision of query results, which is very useful considering that lowering the resolution of spatial data also compromises its accuracy. Providing a correlation between resolution and accuracy can make the expression of spatial queries more practical. Thus users may specify the maximum allowable error in results instead of specifying a map scale. 

Using z-values allows B-trees to be used instead of the default R-tree structure for multidimensional indexing. Reducing dimensionality in most cases facilitates speedier query processing. Spatial queries are developed for the tested operations under the proposed data structure. Experimental evaluations reveal that the data structure performs superiorly to current single-resolution spatial database schemes for all operations using real-world datasets. Under simplification and tokenisation the structure exhibits efficiency for data loads suitable for high resolution CRT displays. When used for amalgamation the structure performs efficiently for resolutions where results are produced to within a respectable 50-900 metres accuracy. Finally the structure is shown to also be more resilient to frequent data updates when compared with a single-resolution alternative. 

Keyword Database design
Database management
Geographic information systems

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
 
Citation counts: Google Scholar Search Google Scholar
Created: Tue, 14 May 2013, 09:00:45 EST by Mr Lachlan Wong on behalf of Scholarly Communication and Digitisation Service