|
1Dept. of Computer Science & Engineering, INHA University, INCHON 402-751, KOREA
2Department of Computer Science, YOUNGDONG University, YOUNGDONG, KOREA
E-mail: anlexwee@yahoo.com
Maps are the primary media of geographical information and the elementary objects manipulated in GIS. They are graphic representations of geographic surfaces on plane, generalized by mathematical rules and represented by visual symbols for different purpose. Maps imply the distributions, states and association of diverse natural or social phenomena. In the existent GIS, almost all of them adopt the layer-based approach to represent geographic information in map. In the layer-based approach, the spatial data are represented in a set of thematic maps, named layer, which denote some given themes such as road, building, subway, contour, border, and so on.
The layer-based approach has an advantage that is easy to process the spatial query and spatial analysis. As we know, the superposition (overlap) of spatial objects is a problem to process in spatial database. The management such as point query processing, region query processing and spatial information analysis processing of overlapped data in spatial objects is difficult to handle because of the too many candidates of spatial object. This problem can be avoid effectively by using the layer-based approach because in general, there is no superposition (overlap) of spatial object in a thematic map of real world.
However, the layer-based approach has the drawback as following:
1). It is difficult to extend the map. After the map has been made, if we need to extend the map, well, it is often occurred, such as, for an existent map, when we apply it for a new, special application, we need add corresponding geographic information in the existent map; On the other hand, it is often occurred that when the map is made completely, the new, more detailed geographical information are got, and need to add in the existent map. In these times, it is complex and difficult to add new spatial data in existent map.
2). When we display the spatial data in the user screen, there are many spatial objects invisibly because the scale ratio between map and view windows (it seems that we cannot see any building when we look earth in the moon!). But for the spatial objects organized in layer must be transferred and displayed. Here the huge size of spatial data transmission affects rapidly the system performance, especially in the Web-Based GIS that processes spatial data in slow Internet environment. We can control it among layers of a map though "controlling display scale mechanism" but cannot prevent it inside one layer.
In this paper, for solving the questions above, we have proposed a new method for representing the spatial data. That is scale-based approach. As in the layer-based approach, the maps are organized in a set of thematic maps that denote some given themes; in the scale-based approach we organized the maps in a set of maps, named Scale-View, which associates some given scales.
The remaining of this paper is organized as follows: Section 2 surveys on the existent layer-based approach and related concept, and section 3 proposes the scale-based approach. In Section 4, the organization of map in scale-based approach and the indexing structure are described, while a prototyped GIS using the proposed data representing method is described briefly. Lastly, Section 5 states the conclusion.
Figure 1. A Sample of Map Composed of Several Thematic Layers
Generally, the map in layer-based approach is organized as following step:
1). Analyzing the special property of target map, determining the theme of layers which will be divided;
2). Creating the layers depending on the themes, respectively.
3). Creating the indexing data for every layer.
Usually, the organization of map represented in layer-based approach likes as the Figure 2.
Figure 2. The Organization of Map in Layer-Based Approach
The layer-based approach has the following advantages:
1) Easy query processing and spatial analysis
The superposition (overlap) of spatial objects is a problem to process in spatial database. The management such as point query processing, region query processing and spatial information analysis processing of overlapped data in spatial objects is difficult to handle because of the too many candidates of spatial object. This problem can be avoid effectively by using the layer-based approach because in general, there is no superposition (overlap) of spatial object in a thematic map of real world.
2) Efficient management of data divided-transmission
When a map is represented in computer devices such as screen, considering display effect in user point of view, it is unnecessary to display all of the details of map. Here the display-scale control is used in the layers of map, and just the necessary layers are displayed. Actually, many traditional desktop GIS and existent Internet GIS hold out the concept of layer in representation of map.
However, as described in the section 1, the layer-based approach has the drawback as following:
1). It is difficult to extend the map.
2). It cannot availably save the question of displaying efficiency about huge size of spatial data in GIS.
In the representation of spatial data in GIS, we can make use of the principle of vision in people's eyes above. When we browse the Asia map in GIS, we can imagine that we do it in the spacecraft; and when we browse the panorama of Seoul, the capital of Korea, we can imagine that we do it in the plane. In more, when we browse small house in the Seoul, we can imagine that we do it in rooftop of the building that just is in side of it!
In the other hand, the view of map will change belong with the distance of map and our eyes. That is, if we observe a map in a far distance of view, many tiny spatial objects in the map will be invisible whereas the huge size of spatial objects will be invisible when we observe a map in a near distance of view. In this time, it is not necessary for the concerned spatial objects to display. So, for the map in which spatial objects are out of order, we can layer it in several scale-view using the size of spatial objects. That is, we can separate the map the several scale-view depending on the resolutions (scales) of map.
Firstly, "Spatial Object' is a basic element about the graphic representation of geographic phenomena in GISs. Here every geographic object is represented in a geometric object, which possesses location, shape, topologic relations and geometric sizing information as Figure 3:
Figure 3. Data Structure of Spatial Object
"Block" is abstract representation of a set of spatial objects. It can be look as an abstract spatial object (polygon). Inside it, it includes a set of spatial objects named child object, or a set of blocks named child block. So it is also an entity of these spatial objects. The "Block" can be separated into 3 kinds: Pure Block, Mixed Block and End Block. The elements of "Pure Block" are all blocks. The "Mixed Block" not only includes blocks but spatial objects while the "End Block" just includes spatial objects. The type of "Block" is illustrated in Figure 4, and the data structure of Block is illustrated in Figure 5.
Figure 4. The Type of Block
Figure 5. The Data Structure of Block
At finally, "Scale-View" is a set of block and a set of spatial objects that associate with a certain given scale. Liking layer concept in layer-based approach, here a complete map is represented in a set of "scale-view", which denote a view of this map in certain resolution (scale).
In order to locate the spatial object in given OID (spatial Object ID) or BID (Block ID), it is necessary to add the "spatial object allocation table" to record the relation of ID and storage position of spatial object. In addition, for save information about child object or child block relation of block, the "block link table" is also necessary.
Well, the details of implementation on map structure is not limit to one form. There are many methods to implement the map structure depending on concrete storage strategy and environment. Here one implementation on map structure is given in our prototyped GIS that are built to evaluate the scale-based approach. The structure of map in scale-based approach is illustrated in Figure 6 as following:
Figure 6. The File Structure of Map in Scale-Based Approach
Actually, for extending the map up, we do not create the "root block". Instead of it, we represent the highest scale-view in a set of blocks and a set of spatial object (if there need do it so).
The organization of map in scale-based approach is illustrated in Figure 7:
Figure 7. The Organization of Map in Scale-Based Approach
In the organization above, we can find that it is easy to extend map that is represented in scale-based approach. We can extend map in extending the corresponding object in a block and add the new spatial objects in the new created block and link it to the existent map.
Firstly, for a detail of block, liking as a general map, we index it in R*-Tree structure in where the child blocks are treated as general spatial objects. In addition we organize the map indexing structure as a "block link tree" that includes all R*-Tree indexing structure of blocks depending on the relation among blocks (child or parent) and the affiliation of block and scale-view. The indexing structure of block and map are illustrated in Figure 8 and Figure 9, respectively.
Figure 8. The Indexing Structure of Block
Figure 9. The Indexing Structure of Map
About the extension of map, there is no problem to join the new spatial objects or blocks to the target map in file storage structure, just only tiny modify on creation of indexing structure.
There are two cases for extension of an existent map, one is extending map more commodiously in order to enlarge scope of map, and another is extending map in more detail in order to increase precision of map.
In first case, for example, there are a map A, has 4 scale-views, A1, A2, A3, A4, and another map B, has 4 coordinate scale-views, B1, B2, B3, B4, if we want join the two map in one map C, the next steps need to be executed:
1). Creating index data of map C's root block depending on A's indexing data (A's R*-Tree) and B's indexing structure (B's R*-Tree) (the BMBR of C is new MBR that contains A's MBR and B's MBR);
2). Creating Map C's map indexing structure, link the blocks that locate in A1, A2, A3, A4 and B1, B2, B3, B4 (modify the BID of blocks), building coordinate scale-views C1, C2, C3, C4;
3). Creating New Map File C, insert map A's map data and B's map data orderly, and modify BID of blocks and OID of spatial objects;
4). For every block indexing data (R*-Tree) that are in C1, C2, C3, C4, modifying the related OID to new value that defined in step 3.
In second case, the new extended map can be created just through doing the step 2~4 above because that the scope of extended map (MBR of map) is not changed.
Figure 10. The Sample Map Created in Scale-Based Approach
In prototype Web-Based GIS, when the user request the all of Korea map, the server just transfers and displays the scale-view of "scale 1", and when the user browses the Seoul map, the server just transmits and displays the scale-view of "scale 2" (or scale-view of "scale 2" and "scale 3" in detail request). Furthermore, when user request street scene of certain district, the server just transmits and displays the corresponding region of scale-view of "scale 4" and so on. Usually, when user request a certain region, the server just transmits and displays the related region of scale-view in "scale 1", "scale 2", "scale 3" or "scale 4" (depending on the size of region) using the map indexing structure.
Digital representation of spatial object is not limit to one approach or one structure. Geographic information is always so complex that a higher-order abstraction is required for modeling the reality. The scale-based approach just provides a means for representing the products of geographic abstraction. Henceforth he congregation of layer-based approach and scale-based approach may be a direction of research about the representation of geographic information.
S. Aronoff 1991, "Geographic Information Systems", WDL Publications, 1991.
T. Brinkhoff 1993, H. Horn, H.P. Kriegel, R. Schneider, "A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems", Proc. 3rd Symp. on Large Spatial Databases, Singapore, 1993.
N.R. Chrisman 1987, "Fundamental Principles of Geographic Information Systems", Proceedings of 8th Int. Symp. On Computer Assisted Cartography, Auto-Cart 8, pp.32-41, Baltimore, Maryland, USA, Mar. 29-April 3, 1987.
M.F. Goodchild 1987, "A Spatial Analytical Perspective on Geographical Information Systems", IJGIS, Vol.1, No.4, pp.327-334, 1987.
M.F. Goodchild 1992, "Geographic Information Science", IJGIS, Vol.6, No.1, 1992.
Volker Grede 1998, "Multidimensional Access Methods", ACM Computing Surveys, Vol.30, No.2, June 1998.
R.H.Guting 1994, "An Introduction to Spatial Database Systems", VLDB Journal, Vol.3, No.4, 1994, pp357-399
D.J. Peuquet 1984, "A Conceptual Framework and Comparison of Spatial Data Models", Cartographica, 21:66-113, 1984.
J.M. Piwowar 1990, E.F. LeDrew, D.J. Dudycha, "Integration of Spatial Data in Vector and Raster Formats in a Geographic Information System Enviroment", IJGIS, Vol.4, No.4, 1990, pp.429-444.
H. Samet 1990, "The Design and Analysis of Spatial Data Structures", Addison Wesley, 1990.
A.Y. Tang 1996, T.M. Adams, and E.L. Usery, "A Spatial Data Model Design for Feature-Based Geographical Information Systems". IJGIS, Vol.10 No.5, pp.643-659, 1996.
E.L. Usery 1996, "A Feature Based Geographic Information System Model", Photogrammetric Engineering & Remoting Sensing, Vol.62, No.7, pp.833-838, 1996.
USGS 1990, "Spatial Data Transfer Standard", Version 12/90, Dept. of the Interior, U.S. Geographical Survey, National Mapping Division, December, 1990.
Z.K. Wei 1999, Y.H. Oh, J.G. Lee, J.H. Kim, D.S. Park, Y.G. Lee, H.Y. Bae, "Efficient Spatial Data Transmission in Web-Based GIS", ACM WIDM'99, pp38-42, Kansas City Mo USA, 1999.