The Gridfit Algorithm : An Efficient and Effective Approach to Visualizing Large Amounts of Spatial Data

Abstract

In a large number of applications, data is collected and referenced by their spatial location. Visualizing large amounts of spatially referenced data on a limited-size display often results in poor visualizations due to the high degree of overplotting of neighboring data points. In this paper, we introduce a new approach to visualizing large amounts of spatially referenced data. The basic idea is to intelligently use the unoccupied pixels of the display instead of overplotting data points. After formally describing the problem, we present two solutions which are based on (1) placing overlapping data points on the nearest unoccupied pixel and (2) shifting data points along a screen-filling curve (e.g., Hilbert-curve). We then develop a more sophisticated approach called Gridfit, which is based on a hierarchical partitioning of the data space. We evaluate all three approaches with respect to their efficiency and effectiveness, and show the superiority of the Gridfit approach. For measuring the effectiveness, in addition to comparing the resulting visualizations we introduce mathematical effectiveness criteria measuring properties of the generated visualizations such as distance- and positionpreservation.