An important requirement in Geographic Information Systems (GISs) is the ability to display numerous geometric objects swiftly onto the display window. As the screen size is fixed, the scale of a map displayed changes as the user zooms in and out of the map. Spatial indexes like R-tree variants that are particularly efficient for range queries are not adequate to generate large maps that may be displayed at different scales. We propose a generalization for the family of R-trees, called the Multi-scale R-tree, that allows efficient retrieval of geometric objects at different levels of detail. The remedy offered here consists of two generalization techniques is cartography: selection and simplification. Selection means some objects that are relatively unimportant to the user at the current scale will not be retrieved. Simplification means that, given a scale, the display of objects is shown with sufficient but not with unnecessary detail. These two together reduce the time required to generate a map on a screen. A major obstacle to the effectiveness of a Multi-scale R-tree is the proper decomposition of geometric objects required by the simplification technique. To investigate the problem, a Multi-scale Hilbert R-tree is designed and implemented. Extensive experiments are then performed on real-life data and a general and simple design heuristic is found to solve the decomposition problem. We show that, with the proposed design heuristic, the Multi-scale R-tree is a desirable spatial index for both querying and display purposes. (C) 2002 Elsevier Science B.V. All rights reserved.
