Abstract
A high performance geographic information system (GIS) is a central component of many real-time applications of spatial decision making. The GIS may contain gigabytes of geometric and feature data (e.g. location, elevation, soil type etc.) stored on a hierarchy of memory devices and represented as grids and large sets of polygons. The data is often accessed via range queries (like polygon clipping) and map-overlay queries. For example, a real-time visualization program retrieves the visible subset of GIS data around the current location of simulator via range queries fetching a million points/second. Such performance can be obtained only with major advances in exploiting parallelism and spatial database techniques within the computational geometry algorithms for range and map-overlay queries. In this paper, we develop and experimentally evaluate data partitioning and load-balancing techniques for range queries in High Performance GIS. We implement static and dynamic load-balancing methods on a distributed memory parallel machine (Cray T3D) for polygon data, and we experimentally evaluate their performance. Preliminary results show that both the static and dynamic load-balancing methods axe necessary for improved performance but are not sufficient by themselves. We propose a new quasi-dynamic load-balancing (QDLB) technique which achieves better load-balance and speedups than traditional methods. On 16 processors, we are able to process range queries in under 0.12 seconds for a map with 329,296 edges, where the range query size is 20-25% of the total area of the map. We are also able to achieve average speedups of 14 on 16 processors.
Original language | English (US) |
---|---|
Title of host publication | Advances in Spatial Databases - 4th International Symposium, SSD 1995, Proceedings |
Editors | John R. Herring, Max J. Egenhofer |
Publisher | Springer Verlag |
Pages | 196-215 |
Number of pages | 20 |
ISBN (Print) | 3540601597, 9783540601593 |
DOIs | |
State | Published - 1995 |
Event | 4th International Symposium on Large Spatial Databases, SSD 1995 - Portland, United States Duration: Aug 6 1995 → Aug 9 1995 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 951 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Other
Other | 4th International Symposium on Large Spatial Databases, SSD 1995 |
---|---|
Country/Territory | United States |
City | Portland |
Period | 8/6/95 → 8/9/95 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1995.
Keywords
- Declustering methods
- Geographic information systems
- High performance
- Load-balancing
- Polygon clipping
- Range query