Load-balancing in high performance GIS: Declustering polygonal maps

Shashi Shekhar, Sivakumar Ravada, Vipin Kumar, Douglas Chubb, Greg Turner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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 languageEnglish (US)
Title of host publicationAdvances in Spatial Databases - 4th International Symposium, SSD 1995, Proceedings
EditorsJohn R. Herring, Max J. Egenhofer
PublisherSpringer- Verlag
Pages196-215
Number of pages20
ISBN (Print)3540601597, 9783540601593
DOIs
StatePublished - Jan 1 1995
Event4th International Symposium on Large Spatial Databases, SSD 1995 - Portland, United States
Duration: Aug 6 1995Aug 9 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume951
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Symposium on Large Spatial Databases, SSD 1995
CountryUnited States
CityPortland
Period8/6/958/9/95

Keywords

  • Declustering methods
  • Geographic information systems
  • High performance
  • Load-balancing
  • Polygon clipping
  • Range query

Fingerprint Dive into the research topics of 'Load-balancing in high performance GIS: Declustering polygonal maps'. Together they form a unique fingerprint.

  • Cite this

    Shekhar, S., Ravada, S., Kumar, V., Chubb, D., & Turner, G. (1995). Load-balancing in high performance GIS: Declustering polygonal maps. In J. R. Herring, & M. J. Egenhofer (Eds.), Advances in Spatial Databases - 4th International Symposium, SSD 1995, Proceedings (pp. 196-215). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 951). Springer- Verlag. https://doi.org/10.1007/3-540-60159-7_13