Accessing Spatial Information in Resource-constrained and Resource-rich Environments

Open Access
An, Ning
Graduate Program:
Computer Science and Engineering
Doctor of Philosophy
Document Type:
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
  • Geo-spatially Crawling
  • Cluster Computing
  • Energy Profile
  • Selectivity Estimation
  • Spatial Information
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.