Chris Jones: Multiscale Spatial Databases

Multiscale Spatial Databases

Summary of EPSRC-funded project "Multiscale Spatial Databases and Map Generalisation"

The research addresses the problem of providing efficient access to geographical map data at multiple levels of detail. Derivation of a map at a particular scale and with a particular thematic emphasis is referred to as map generalisation. It involves processes of selection, elimination, shape simplification, caricature, amalgamation and displacement of map features. The objective of the research is to build a multiscale spatial database that facilitates retrieval of selected types of map data at an appropriate level of detail and renders the data as a legible map. One of the major motivations for the research is mapping on the internet and hence speed of retrieval and map display are very important. The strategy is to store data that has been pre-processed by map generalisation procedures that enable component geometry to be labelled with scale-variable priorities. A variety of multiresolution map data storage schemes have been evaluated.

In order to provide for the display of combinations of map features at arbitrary scales, it is not practicable to pre-generalise the data entirely. Thus approximately generalised data can be retrieved before applying conflict resolution procedures to ensure that constraints affecting legibility are obeyed. These relate for example to minimum separation distances between displayed symbols. A major challenge in pre-generalising map data is that of ensuring topological integrity among multiple map features. Techniques for topological maintaining map generalisation with multiple features have been developed in a related project on map generalisation.

This project has made several significant contributions to the problem of multi-scale spatial data access, resulting in:

The strategy for maintaining multi-scale geographical information has addressed the specification of consistency in multi-scale data and the need for rendering the data in a way that ensures legibility [Jones et al 2000]. It provides a framework for the development and evaluation of methods for multiscale spatial database access and for graphical conflict resolution.

Work on multi-scale spatial database access methods resulted in the design of alternative schemes based on sequence numbers and on a multi-way tree respectively. Their merits in comparison with simple multiple representations have been clearly demonstrated. Both schemes were implemented in various ways with the Informix object-relational database. Large test datasets were used to demonstrate the overall superiority of sequence-number techniques. Experiments with indexing techniques demonstrated the benefits of a 3D R-tree integrating dimensions of space and resolution [Zhou and Jones 2001]. Subsequent research developed techniques for retrieving multiple representations of map features at individual scales as well as at multiple scales. This employed parameters to control the style of generalisation in addition to the scale [Zhou and Jones 2003].

Research on graphical conflict resolution of map data retrieved from a multi-scale database led to the design and implementation of novel iterative techniques for resolving proximity conflicts by local displacements of map features. The techniques were compared experimentally with an alternative approach based on simulated annealing [Lonergan and Jones 2001; van der Poorten, Zhou and Jones, 2002; Li, Zhou and Jones, 2002].

Publications on multiscale databases:

Zhou S and C.B. Jones (2003) "A multirepresentation spatial data model". In Hadzilacos et al (eds) Advances in Spatial and Temporal Databases, Proceedings of International Symposium on Spatial and Temporal Databases SSTD 2003 Lecture Notes in Computer Science, 2750, 394-411. [PDF]

Li M., S. Zhou, C.B. Jones (2002). "Multi-agent Systems for Web-Based Map Information Retrieval". GIScience 2002: Geographic Information Science, Second International Conference, Boulder, CO, USA, Lecture Notes in Computer Science 2478, Springer, 161-180. [PDF]

van der Poorten P.M., S. Zhou, C.B. Jones (2002). "Topologically-Consistent Map Generalisation Procedures and Multi-scale Spatial Databases". GIScience 2002: Geographic Information Science, Second International Conference, Boulder, CO, USA, Lecture Notes in Computer Science 2478, Springer, 209-227. [PDF]

Zhou S. and C.B. Jones (2001) "Design and implementation of multi-scale databases". C.S. Jensen, M.Schneider, B. Seeger and V. Tsotras (eds), Advances in Spatial and Temporal Databases, 7th International Symposium, SSTD 2001, Lecture Notes in Computer Science 2121, Springer, 365-384. [PDF]

Lonergan M.E. and C.B. Jones (2001) 'An iterative displacement method for conflict resolution in map generalisation', Algorithmica, 30, 287-301. [PDF]

Jones C.B, A.I. Abdelmoty, M.E. Lonergan, P. van der Poorten and S. Zhou (2000) "Multi-scale spatial database design for online generalisation". 9th International Symposium on Spatial Data Handling, Beijing, International Geographical Union, 7b.34-44. [PDF]

Jones C.B., J.M. Ware and C.D. Eynon (1999) 'Triangulated spatial models and neighbourhood search: an experimental comparison with quadtrees',The Visual Computer vol.15(5), pp235-248. [PDF]

Jones C.B. and J.M. Ware (1998) 'Nearest neighbour search for linear and polygonal objects with constrained triangulations'. Proceedings 8th International Symposium on Spatial data Handling, International Geographical Union, pp 13-21.

Jones C.B. and J.M. Ware (1998) 'Proximity search with a triangulated spatial model', The Computer Journal 41(2), pp 71-83. [PDF]

Ware, J.M. and Jones, C.B. (1998), "Matching and Aligning Features in Overlayed Coverages", Proc. of 6th International Symposium on Advances in Geographical Information Systems (ACM-GIS'98), pp 28-33. [PDF]

Abdelmoty A.I. and C.B. Jones (1997), "Towards Maintaining Consistency in SpatialDatabases", Proceedings of the Sixth International Conference on Information and Knowledge Management, CIKM'97, Las Vegas, USA, ACM Press, pp 293-300. [PDF]

Ware J.M. and C.B. Jones (1997) 'A multiscale data storage scheme for 3D GIS' in Z.Kemp (ed) Innovations in GIS 4, Taylor and Francis, pp 9-24.

Jones C.B, D.B. Kidner, L.Q. Luo, G.Ll. Bundy and J.M. Ware (1996) 'Database Design for a Multiscale Spatial Information System'. International Journal of Geographical Information Science, 10(8), pp 901-920.

Jones C. B. , D. B. Kidner and J. M. Ware (1995). 'Equivalence Tests for Integration of Multi-Source Spatial Data'. Proceedings EuroCarto, XIII, Joint Research Centre, European Commission, pp 13-22.

Kidner D.B. and C.B. Jones (1994) 'A deductive object-oriented GIS for handling multiple representations'. Advances in GIS Research I, Proceedings 6th International Symposium on Spatial Data Handling, Edinburgh,Taylor and Francis, pp 882-900.

Jones C.B., D.B. Kidner and J.M. Ware (1994) 'The Implicit TIN and multiscale spatial dabases', The Computer Journal 37(1), pp 43-57.

Ware J.M and C.B. Jones (1992), 'A multiresolution topographic surface database', International Journal of Geographical Information Science, 6(6), pp 479-496.

Jones, C.B., J.M. Ware, G.L. Bundy (1992), 'Multiscale spatial modelling with triangulated surfaces', Proceedings 5th International Symposium on Spatial Databases, Charleston, pp 612-621.

Jones, C.B. (1991),'Database architecture for multi-scale GIS', Proceedings Auto-Carto 10, Baltimore, ACSM/ASPRS, pp 1-14.

Jones, C.B. (1989), Data structures for three dimensional spatial information systems in geology', International Journal of Geographical Information Systems, 3(1), pp 15-31.

Jones, C.B. and I.M. Abraham (1987), 'Line generalisation in a cartographic database', Cartographica, 24(3), pp 32-45.

Jones, C.B. and I.M. Abraham (1986), 'Design considerations for a scale-independent cartographic database', Proceedings Second International Symposium on Spatial Data Handling, Seattle, 1986, pp 384-398.