Algorithms and Data Structures for Large Scale Geographic Information Systems

Abstract

With the increasing availability of geographically referenced data, the e ciency of Geographic Information Systems (GIS) is becoming increasingly relevant. In this project, we address the problem of e ciently retrieving geographic data based on spatial relationships. We describe an implementation of a GIS solution based on Polygonal Map Quadtrees. This data structure is kept in memory while persistent storage is handled by an underlying database management system. To validate the implementation, we describe an experimental analysis in a wide range of scenarios. The experimental results suggest that this approach can have better performance than a state-of-the-art GIS framework in terms of running time.