Accessing Spatial Information in Resource-constrained and Resource-rich Environments
Open Access
- Author:
- An, Ning
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- October 12, 2001
- Committee Members:
- Vijaykrishnan Narayanan, Committee Member
C Lee Giles, Committee Member
Donna Jean Peuquet, Committee Member
Anand Sivasubramaniam, Committee Chair/Co-Chair - Keywords:
- Geo-spatially Crawling
Cluster Computing
Energy Profile
Selectivity Estimation
Spatial Information - Abstract:
- Spatial information has always been a need of the human society. Over the past two decades or so, Spatial Database Management Systems (SDBMS) have achieved a great deal in storing, processing and retrieving spatial information. The continuing advancement of technologies, however, persistently raises the bar for SDBMS to meet demands in various environments, particularly in emerging resource-constrained and evolving resource-rich environments. To investigate various issues in accessing spatial information in these two environments, this thesis conducts the following five studies. Our first two studies present histogram-based selectivity estimation techniques for spatial selections and spatial joins respectively. In our first study, Cumulative Density scheme gives very accurate results for spatial selections (usually less than 5\% error) with negligible and constant estimation time cost, regardless of dataset or query window parameters. Similarly, Geometric Histogram scheme proposed in our second study can accurately quantify the selectivity of spatial joins. Using a detailed cycle-accurate energy estimation framework and four different memory resident datasets, our third study examines the pros and cons of three previously proposed spatial indexing alternatives on a mobile device. This study is the first one to analyze spatial index structures from both the energy and performance angles, and its key contribution is in pointing out that performance and energy do not always go hand in hand. It also shows that the nature of the query also plays an important role in determining the energy-performance trade-offs. Further, technological trends and architectural enhancements are influencing factors on the relative behavior of the index structures. Our fourth study indicates that a distributed index structure spanning the disks of the workstations in a cluster can provide an efficient shared storage structure to access spatial data in high performance environments. This goal can be attained without significantly compromising the index creation time. Finally, in our ongoing study of the spatial (location-related) information on the World Wide Web, we offer four hypotheses about this kind of information that can be used to build a geo-spatial crawler to effectively retrieve spatial (location-related) information from the World Wide Web.