Smallworld Technical Paper No. 1 - Ten Difficult Problems in Building a GIS

Richard G. Newell & David G. Theriault

Abstract

Building a GIS is a fruitful area if one likes the challenge of having difficult technical problems to solve. Some problems have been solved in other technologies such as CAD or database management. However, GIS throws up new demands, therefore requiring new solutions. This paper has chosen to examine ten difficult problems, why they need to be solved and gives some indication of the state of the art of current solutions.

Introduction

The subject of Geographical Information Systems has moved a long way from the time when it was thought to be concerned only with digital mapping. Whereas digital mapping is limited to solving problems in cartography, GIS is much more concerned with the modelling, analysis and management of geographically related resources. At a time when the planet is coming under increasing pressure from an ever more demanding, increasing population, the arrival of GIS technology has come none too soon.

However, there is a widespread lack of awareness as to the true potential of GIS systems in the future. When the necessary education has been completed, will the systems be there to handle the challenge? It has to be said that the perfect GIS system has not yet been developed.

Many of the fundamental problems have now been identified, and indeed attempts (sometimes good ones) to solve them have been embodied in today's commercially available systems. However, no system has an adequate solution to all of them and indeed, some are not addressed by any system (Rhind and Green, 1988).

In this paper we have chosen to examine ten important problems which we believe need to be solved. Ten is a somewhat arbitrary number since it would have been easy to find many more. However, one has to draw the line somewhere. Also we call the problems difficult, as opposed to unsolved, because for most of them, there is now some light at the end of the tunnel and, indeed, implemented solutions exist.

The fundamental causes of difficulty in GIS stem from the huge volumes of spatially related data, the nature of the data itself, and the wide spectrum of different organisations with diverse application requirements. Problems can be classified under the following four categories:

• Data capture - this will be the single biggest cost in implementing a new system.
• Performance - most systems strain under the volume of data and scale of the tasks invoked.
• Customisation - every organisation is different; no black box system is going to be adequate.
• Integration - today's systems are disjoint, in the future data and functions will need to be provided in one seamless environment.

Our ten problems are really different manifestations of these four and so the rest of this paper is devoted to a commentary on each of them in turn. As most organisations are at the data capture stage, it is not surprising that this is the area where most work has been done in trying to improve the process.

The Topology Capture Problem

The lack of a really good solution to this problem is probably going to contribute most to the slow speed of implementation of GIS systems in the future. Although much progress has been made using scanning and vectorisation technology to capture map geometry (Nimtz, 1988), the addition of feature information, the generation of meaningful topology and the association of user data involves a large human element. Some modern topological editors do help to ease the burden (Visvalingam et al, 1986), but essentially, the only solution is to throw man-hours at it (Chrisman, 1987). Thus for some time we will be seeing expedient solutions using raster backdrops without topology.

Large Data Volumes

The volume of data required to represent the resources and infrastructure of a municipality is of the order of 0.5 to 1 gigabyte per 100,000 of population, supporting examples can be found where an urban region would require 14 million points simply to represent the map planimetry (Bordeaux, 1988). Not only are the municipal records required to be handled in the database, but also large amounts of map data in the form of coordinates, lines, polygons and associations of these. Today's database technology is barely up to the task of allowing the handling of geographic data by large numbers of users with adequate performance. Serious questions have been raised as to whether the most popular form of database, the relational model, will be able to handle the geometric data with adequate response. Certainly, if this data is accessed via the approved route of SQL calls, the achievable speed is orders of magnitude less than that which can be achieved by a model structure built for the task (Frank, 1988).

A common approach to this problem is to partition the database into separate map sheets. Frequently this is achieved by interfacing a sheet based CAD drafting system to a database (but see continuous mapping below). Another approach for avoiding the shortcomings of commercially available database systems is to build a special purpose database system to handle the graphics, which lives alongside the commercially available database system. A third approach, based on checking-out subsets of the database, followed by checking-in the changes, can overcome the problem of reviewing and editing (but see continuous mapping and version management below).

The idealistic solution of implementing one database system to handle both kinds of data with optimum performance is a large undertaking, and even then does not satisfy the user who has already committed to an existing commercially available database.

Continuous Mapping - the seamless database

As one begins to build a GIS, the problem of large data volumes appears to be the most important one to solve. A solution in the form of the map sheet approach, chosen by most systems today, simply mirrors what happens with physical map sheets. This is then combined with map management techniques to try to hide the cracks. While this partitioning helps to solve the first problem, it destroys the end user's dream of a single, continuous, seamless landscape. At best this may be termed contiguous mapping, but in all cases, such schemes lead to difficulties when one is trying to deal with objects which span more than one map sheet. The problem of dealing with variable density data, for example between urban and rural areas, is tackled in an ad hoc manner as there is no single size of map sheet to yield optimal performance in all cases.

The reason that a map sheet approach is popular is that it can easily be implemented with a conventional filing system and it is straightforward to find which files should be searched for a given spatial query. However, the system can hardly be called integrated, since the geometry, topology and the relationship between graphic and application data are all handled in an ad hoc manner.

What is now demanded is that map data is handled just as it is in the real world truly continuously, with no cracks. But this must be done so that spatial queries of the form "inside an area" or "near to an object" can be handled efficiently. A common query is of the form "conforming to such-and-such and is on the screen" i.e. filtering out the rest of the world. Normal indexing methods provided with conventional database systems are inadequate to answer this type of query, and so a variety of spatial indexing methods have been invented to try to solve this problem.

The general idea is to construct a tree structured index (e.g. quad tree, range tree, field tree) the leaves of which are not disjoint they overlap in two dimensional space and this accommodates objects of different sizes at different levels. In this respect, the quad tree (Samet, 1984) is beautifully simple but has serious deficiencies for large data volumes. The range tree (Guttman, 1984) is rather more complicated but is more efficient. Systems which are optimal for retrievals are not necessarily optimal for updates and vice versa. As data is read far more often than it is written, the emphasis should be on providing maximum retrieval performance, while still maintaining an acceptable rate of interactive update.

However, given today's disk technology, it matters little how efficient the index is if the data is scattered on disk. Thus it is essential that data is clustered on disk so that spatially similar data have similar addresses (Bundock, 1987). This can be achieved in the relational and other tabular models provided that data is stored ordered by a properly generated spatial key. There are a lot of good ideas now in this area but it is yet to be seen which are the best.

Accommodating Existing Databases

There are a number of shortcomings in existing available database technology for the building of a GIS. Nevertheless, there are now many organisations which have committed in a big way to one of the emerging de-facto standard database systems. It is not acceptable for a GIS vendor to try to displace such a database with something else tuned for GIS applications. It is necessary to engineer a solution which preserves the users' investment while at the same time doing as good a job as possible in providing a GIS capability. As mentioned above, if one tries to handle all data in the commercial DBMS, then it is highly likely that a serious performance problem will result. If one runs a geometric DBMS alongside, then serious problems of backout, recovery and integrity may result. It would seem that what is needed is some "virtual DBMS" which can act as a front end to two or more physical DBMSs, and that this should have a knowledge of all aspects to do with data dictionary, integrity, and access to the various data.

Version Management - the problem of the long transaction

It is necessary that large databases can be accessed simultaneously by multiple users. The normal assumption in a commercial DBMS is that a transaction is a short term affair, and that a locking system can be used to keep users from unintentionally interfering with one another. Such methods are used to preserve the integrity of the database at all times. As far as any particular user is concerned, there are two versions of the database of which he is aware, the version when he started his transaction and the version he can see at the instant prior to committing it. The problem is, when a user is in mid transaction in such systems, then all other users are locked out of doing certain things particularly updating any records that have been locked. This is all fine, provided that the transactions are short.

However, in a GIS system, as in design database systems in general, a transaction can be very long indeed, possibly days or even weeks. A planner for example may take a considerable time to complete his work before he gets it approved and therefore available to the other users of the system. In these circumstances it is totally unreasonable to expect other users to avoid the area.

Copying the whole database is completely impractical in many cases. A system of check-out, check-in can be used, but this gives rise to the problem of achieving integrity through combining incompatible changes in different checked-in versions. It is quite possible for two separate sets of changes to have integrity, but for the combination to lack it.

Users who are starting the implementation of a GIS system may be blissfully unaware of this problem. To start a project, most organisations will initiate a pilot study: a simplified data-model, only one or two users of the system and test data that can be thrown away if the pilot database becomes corrupted.

The situation in a production environment is the opposite of the above: a complex data-model, a large number of users and concurrent activities, and a large investment in the creation of the database. The problem of version management could dominate all database activities in a production system and yet does not manifest itself in a pilot project.

Versioning is not addressed by today's round of DBMSs. The complete problem covers the management of alternatives, the management of chronology (what did my database look like three months ago), the management and policing of change, and various forms of semantic versioning such as time series, variant designs and "as built" records.

Hybrid Vector Raster Database

It is an amusing paradox that whereas the bottle-neck with vector based GIS is in capturing the map base, the problem with remotely sensed data is the sheer volume of it that pours down upon us from the heavens, a veritable fire-hose of data. For example SPOT1, at 50Mbits/second, captures an area 60km x 60km in 9 seconds. Increasing resolution to 5 metres would mean boosting transmission to 200Mbits per second for every hour of daylight.

Whereas the value of an attribute-less map base is limited, the value of satellite data is potentially immense, for here surely we can observe and monitor the catastrophic way in which we humans are changing and damaging this paradise in which we live. Green issues aside, the vector people are still struggling with data capture while the image processing people have a major computational problem with the sheer bulk of data.

These two forms must come together in one system since the combination will yield far more than the parts. Currently vector based GIS systems tend to be separate from raster based image processing systems. Raster data is derived from a variety of sources e.g. rasterized paper maps (from scanners), grid data derived from digital terrain models and remotely sensed data (from satellites).

Many applications such as overlay analysis (described below), recording changes in land use and changes in the environment can be tackled much more effectively when the two forms of data can be manipulated, viewed and analysed in one integrated, seamless environment.

Overlay Analysis - a problem of robustness

Given a multi-thematic map base, overlay analysis is used to answer questions of the type: "show me all areas with sandy soil and agricultural land use, where the ground slope is less than 5 degrees because I want to grow potatoes".

The idea behind overlay analysis is very neat: one starts by producing a single combined topological model of all the themes which are to contribute to the analysis. Producing the combined topology is both a geometric as well as a topological problem. Once it has been produced, all queries and analyses can be carried out wholly in the topological domain without any further reference to the geometry and are therefore amenable to be tackled via conventional query languages such as SQL (Frank 1987).

The problem is that producing the combined topology robustly is far less trivial than it seems at first sight. Anyone who has wrapped their brain around the problem of producing a robust solid modeller will know the kind of pathological cases that can arise. Fortunately, the problem is not quite as bad as producing a robust solid modeller; however, any system implementor who underestimates the difficulty of this problem had better beware - schoolboy geometry just isn't good enough.

But robustness is not the only problem. It turns out that not infrequently two or more themes may share the same boundary curve. Typically these will have been digitized separately and with different accuracies, therefore their representations will be different in detail. If two such themes are now combined, then many superfluous small polygons (called slivers) will be produced. Slivers can easily outnumber the real polygons leading to an explosion in data volumes, messy graphics, a collapse in efficiency and questionable analysis. Sliver removal is just another of those irritating issues which must be addressed if a practical system is to result.

In any analysis, it is important to try to make some assessment of the accuracy of the results. In practice, each theme of data will contain inaccuracies and errors, the bounds of which may be known. The consequent effects of these individual errors on the results from many combined themes may be impossible to gauge (Walsh et al, 1987), overlay analysis systems available today should carry the caveat: "let the user beware". (As an aside here, the whole subject of quality meta data, including such aspects as source, accuracy and coverage would be a good candidate for the eleventh problem.)

Overlay analysis is one of those techniques which is mind-blowingly tedious to do without a GIS. However, without robust clean algorithms there is a grave risk that the results produced will be meaningless.

Very Large Polygons

When Slartibartfast designed the coast of Norway (The Hitch Hiker's Guide to the Galaxy, Adams, 1979), he was really setting a major challenge for the designers of Scandinavian GIS systems. He probably also designed the Stockholm Archipelago with its 23000 islands as a challenge to those trying to do spatial analysis in the Baltic. Whereas very large linear features can be straightforwardly subdivided into manageable pieces, very large polygonal areas, including those with many embedded islands are not amenable to the same techniques.

However, one doesn't need to travel to scenic northern regions to encounter this problem, since very large polygons can occur in everyday applications. The GIS designer is confronted with the problem of doing spatial analysis on small parts of such polygons, as well as answering questions to do with inside and outside, without processing the millions of points which there may be in such polygons.

As with very large databases, the goal is to produce systems whose performance is dependent only on the data of interest and not to be burdened with the irrelevant.

The Front End Language - the seamless programming environment

A problem with GIS customers, seen from the system vendor's viewpoint, is that they are all different. Each customer will have a different data-model and will want substantial enhancements to his user interface and functionality. Whereas there are good facilities for data-modelling, the tools for developing and customising today's systems leave a lot to be desired. Much effort has gone into toolkits for developing and customising systems including standard graphics libraries, user interface managers, data managers, windowing systems etc. However, if one wishes to get in and program any of the systems, one is confronted with operating system commands, Fortran, C, SQL, embedded SQL, some online command language, domain specific 4GLs or a combination of these; not to mention auxiliary "languages" to define user syntax, menus, data definitions, data dictionaries etc. With these kinds of programming tools it can take many man-months of skilled programmer effort to achieve even modest system customisation.

It is a common problem with systems that contain parts that are front ended by different languages that it is not possible to integrate them properly. For example, a graphics system for mapping, which is "hooked into" a database, typically does not allow the full power of the database to be accessed from within the graphics command language, nor can the power of the graphics system be invoked from within the database query language. What is really needed is a system such that all data and functions can be accessed and manipulated in one seamless programming environment (Butler, 1988).

What has been shown by a number of organisations is that the same development carried out with an on-line object orientated programming language can cut such development times by a very large factor (e.g. 20). Object orientation does not just mean that there is a database with objects in it, but that the system is organised around the concept of objects which have behaviour (methods). Objects belong to classes which are arranged in a hierarchy. Subclasses inherit behaviour and communication between objects is via a system of message passing thereby providing very robust interfaces.

Firstly, such a language should be able to provide facilities covering the normal requirements of an operating system, customisation, applications programming and most systems programming. Secondly, the language should have a friendly syntax that allows casual users to write simple programs for quick online customisation. Larger programs should be in a form that is easily readable and debuggable. Thirdly, the language must be usable in an interactive mode as well as being able to be "supercharged" by means of full compilation.

There are several languages around which satisfy some of these requirements: Basic is all right for simple programs (but look at what some people now achieve in the micro world with some of the more advanced modern Basics); Lisp has much of the power and speed, but is hardly readable (but just see what Autocad has achieved with Autolisp). Smalltalk has both speed and object orientation, but with the total exclusion of any other programming construct. Postscript is very widely used and has a number of the desired features, but is another write-only language (i.e. "unreadable" by anyone, including the original programmer). Hypertalk is wonderful, but you would not write a large system in it. C++ has much of the required syntax and semantics, but it is not available as a front end language and can therefore only be accessed by a select few system builders, normally employed by the system vendor.

Having dismissed most of the well known languages developed during the last 30 years, then what is required? It is an on line programming language, with a friendly Algol-like control structure and the powerful object oriented semantics of languages like Smalltalk.

The Query Language

Modern query languages such as SQL are not sufficient in either performance or sophistication for much of the major development required in a GIS system - but then one would argue that they were not intended for this. One can see why people like SQL; it can give immense power in return for some fairly simple "select" constructs. A problem which has to be addressed is spatial queries within the language, since trying to achieve this with the standard set of predicates provided is extremely difficult and clumsy. (An example of a spatial query is to select objects "inside" a given polygon.)

If the route adopted is to provide two databases in parallel, a commercial one driven by SQL and a geometry database to hold the graphics, then there is a problem constructing queries that address both databases. Ideally, the query language should be a natural subset of the front end language allowing access to the same seamless environment that the front end language provides. Much work needs to be done in the area of query languages for GIS.

Conclusion

Ten years ago the evolution of CAD systems was at about the same stage that the evolution of GIS systems is now. One can recall the arguments over whether mechanical design systems should be 2D or 3D; what was it that allowed a 3D system to claim to be a solid modeller? The purists endlessly discussed CSG versus BReps; Euler's rules had to be obeyed at all costs - while in the mean time the faceted modeller brigade stole the show. The surface designers insisted that C2 was a minimum and some pronounced that C7 was essential! Your surface system was definitely not macho unless it was founded on NURBS - even though the humble conic can handle adequately 95% of practical problems. Today, most of the world seems to be happy hacking away on a fairly modest little drafting system called Autocad.

So it is now with GIS: What is a GIS and what isn't a GIS? Do the ever longer synonyms for GIS say anything new? Should the system be based on raster or vector? One of us recently asked a vector bigot what percentage of spatial analysis problems can be tackled in the raster domain - back came his answer: "None!". Arguments about topological models are rife while protagonists argue about what are the acceptable ways to break the strict rules laid down for data-modelling, in order to achieve a working system.

Let us beware in GIS, too much concentration on how things are done as opposed to what we are trying to do will lead to much wastage of time and wrong decisions being made. It is all very well for the salesman to try to identify unique selling features in his product in order to exclude another vendor from the sale, but let us learn from the experience of CAD when this is happening. It is important to identify the real application requirements of a system, this can be crucially dependent on that system having strong fundamentals. These can be exposed by careful benchmarking (McLaren, 1988).

In this paper we have attempted to lay bare ten difficult problems in GIS. In fact they are not wholly in dependent problems indeed some are a consequence of trying to solve another. The encouraging thing is that most of them have now been identified, and indeed for many there are some promising solutions.

Acknowledgements

The authors gratefully acknowledge Robin McLaren for reading the draft of this paper and thank him for his thoughtful comments.

References

Adams, Douglas (1979). The Hitch Hiker's Guide to the Galaxy, Pan Books.

Bordeaux, La Communaut Urbaine de (1988). Programme du Concours pour un systSme interactif graphique de gestion de donnes urbaines localises.

Bundock, Michael (1987). Integrated DBMS Approach to Geographical Information Systems, Auto Carto 8.

Butler, R. (1988). The Use of Artificial Intelligence in GIS, Mapping Awareness and Integrated Spatial Information Systems, Vol. 2, No. 3.

Chrisman, N. R. (1987). Efficient digitizing for error detection and editing, International Journal of Geographical Information Systems, Vol. 1, No. 3.

Frank, Andrew U. (1987). Overlay Processing in Spatial Information Systems, Auto Carto 8.

Frank, Andrew U. (1988). Requirements for a Database Management System for a GIS, Photogrammetric Engineering and Remote Sensing, Vol. 54, No. 11.

Guttman, Antonin (1984). R-Trees: A Dynamic Index Structure for Spatial Searching, ACM

McLaren, Robin A. (1988) Benchmarking within the GIS Procurement Process, Mapping Awareness and Integrated Spatial Information Systems, Vol. 2, No. 4.

Nimtz, H. (1988). Scanning und Vektorisierungs Software zur Erfassung von Katasterplanwerken, Proceedings Automated Mapping/Facilities Management European Conference IV.

Rhind, D. W., Green, N. P. A. (1988). Design of a Geographical Information System for a Heterogeneous Scientific Community, International Journal of Geographical Information Systems, Vol. 2, No. 2.

Samet, H., (1984). The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys, Vol. 16, No. 2.

Visvalingam, M., Wade, P., Kirby, G. H. (1986). Extraction of area topology from line geometry, Proceedings Auto Carto London.

Walsh, Stephen J., Lightfoot, Dale R., Butler, David R. (1987). Assessment of Inherent and Operational Errors in Geographic Information Systems, Technical Papers, 1987 ASPRS-ACSM Annual Convention, Vol. 5.