Over the last fifteen years GIS has become a fully-fledged technology, deployed across a range of application areas. However, although computer advances in performance appear to continue unhindered, data volumes and the growing sophistication of analysis procedures mean that performance will increasingly become a serious concern in GIS. Parallel computing offers a potential solution. However, traditional algorithms may not run effectively in a parallel environment, so utilization of parallel technology is not entirely straightforward. This groundbreaking book examines some of the current strategies facing scientists and engineers at this crucial interface of parallel computing and GIS.; The book begins with an introduction to the concepts, terminology and techniques of parallel processing, with particular reference to GIS. High level programming paradigms and software engineering issues underlying parallel software developments are considered and emphasis is given to designing modular reusable software libraries. The book continues with problems in designing parallel software for GIS applications, potential vector and raster data structures and details the algorithmic design for some major GIS operations. An implementation case study is included, based around a raster generalization problem, which illustrates some of the principles involved. Subsequent chapters review progress in parallel database technology in a GIS environment and the use of parallel techniques in various application areas, dealing with both algorithmic and implementation issues.; "Parallel Processing Algorithms for GIS" should be a useful text for a new generation of GIS professionals whose principal concern is the challenge of embracing major computer performance enhancements via parallel computing. Similarly, it should be an important volume for parallel computing professionals who are increasingly aware that GIS offers a major application domain for their technology.
Editors Biographical Details xiii(2) Acknowledgements xv(2) Contributors xvii 1 INTRODUCTION 1(12) R. G. HEALEY B. M. GITTINGS S. DOWERS M. J. MINETER 1.1 GIS Challenges 1(1) 1.2 Parallel Opportunities and Problems 2(1) 1.3 GIS and Parallel Processing 3(1) 1.4 The Context of this Book 4(2) 1.5 Intended Audience 6(1) 1.6 Outline Structure 7(1) 1.7 References 8(5) PART ONE: PARALLEL PROCESSING TECHNOLOGY IN CONTEXT 13(76) 2 THE DEVELOPMENT OF HARDWARE FOR PARALLEL PROCESSING 13(20) M. SAWYER 2.1 The Evolution of Parallel Processing 13(2) 2.2 A Classification of Parallel Architectures 15(3) 2.3 Interconnection Topologies 18(4) 2.4 Balancing Computation and I/O in the Parallel Environment 22(2) 2.5 Examples of Parallel Computers 24(4) 2.6 Industry Trends in Parallel Processing 28(2) 2.7 Conclusions 30(1) 2.8 References 31(2) 3 THE SOFTWARE ENVIRONMENT AND STANDARDISATION INITIATIVES 33(26) M. SAWYER 3.1 Basic Concepts in Parallel Programming 33(3) 3.2 Programming Paradigms 36(1) 3.3 The Data-Parallel Paradigm 36(2) 3.4 The Message Passing Paradigm 38(3) 3.5 Shared Memory Programming 41(3) 3.6 Object-Oriented Languages 44(1) 3.7 Linda 45(1) 3.8 The Parallel Random Access Machine (PRAM) 46(2) 3.9 New Developments in Standards for Parallel Processing 48(8) 3.10 Conclusion 56(1) 3.11 References 56(3) 4 HIGH-LEVEL SUPPORT FOR PARALLEL PROGRAMMING 59(30) S. M. TREWIN 4.1 Parallel Program Decomposition 60(1) 4.2 Functional Decomposition Techniques 61(2) 4.3 Data Decomposition Techniques 63(4) 4.4 Parallel I/O 67(2) 4.5 Portable, Reusable Parallel Utilities 69(1) 4.6 Existing Utility Libraries 70(8) 4.7 Developing and Using Libraries to Support GIS 78(4) 4.8 Conclusions 82(1) 4.9 References 83(6) PART TWO: DESIGN ISSUES 89(144) 5 ISSUES IN THE DESIGN OF PARALLEL ALGORITHMS 89(14) S. DOWERS M. J. MINETER R. G. HEALEY 5.1 General Context 89(4) 5.2 Generic versus Architecture-Specific Design 93(5) 5.3 Implications of Geographic Data for Parallel Processing 98(2) 5.4 Summary of Design Aims 100(1) 5.5 References 100(3) 6 DATA MODELS, REPRESENTATIONS AND INTERCHANGE STANDARDS 103(36) S. DOWERS 6.1 Role of Data Models 103(2) 6.2 Conceptual Framework 105(1) 6.3 Vector Models 106(7) 6.4 NTF Level 4 113(3) 6.5 NTF Level 4 -- Record Types and ASCII Representation 116(14) 6.6 Raster Data Models 130(1) 6.7 Raster Interchange Formats 131(1) 6.8 Raster Format for the Parallel Algorithm Designs 132(4) 6.9 Conclusions 136(1) 6.10 References 137(2) 7 A MODULAR APPROACH TO PARALLEL GIS ALGORITHM DESIGN 139(12) S. DOWERS M. J. MINETER R. G. HEALEY 7.1 Introduction 139(1) 7.2 Benefits of Modularity 139(2) 7.3 Design Approach 141(5) 7.4 Vector Input Module 146(2) 7.5 Vector Output Module 148(1) 7.6 Raster Input Module 149(1) 7.7 Raster Output Module 149(1) 7.8 Conclusions 150(1) 7.9 References 150(1) 8 PARALLEL VECTOR DATA INPUT 151(28) T. M. SLOAN S. DOWERS 8.1 Introduction 151(2) 8.2 Input Data 153(4) 8.3 Data Sorting and Merging 157(3) 8.4 Design Overview 160(5) 8.5 Processes 165(5) 8.6 Phases 170(6) 8.7 Design Notes and Limitations 176(1) 8.8 References 177(2) 9 CREATION OF VECTOR-TOPOLOGICAL DATA STRUCTURES 179(36) M. J. MINETER 9.1 Introduction 179(2) 9.2 Overview of Topology Building, Stitching and Output (TSO) 181(9) 9.3 Topology Building 190(7) 9.4 Stitching 197(11) 9.5 Object Collation and Output 208(2) 9.6 Structure of the TSO Framework 210(2) 9.7 Conclusions 212(1) 9.8 References 213(2) 10 PARTITIONING RASTER DATA 215(18) M. J. MINETER 10.1 Introduction 215(1) 10.2 Implications of the Characteristics of Algorithms 215(8) 10.3 Methods of Decomposition into SRBs 223(3) 10.4 SRB Distribution for Raster-to-vector Conversion 226(4) 10.5 Summary 230(1) 10.6 References 230(3) PART THREE: PARALLELISING FUNDAMENTAL GIS OPERATIONS 233(100) 11 VECTOR-TO-RASTER CONVERSION 233(20) T. M. SLOAN 11.1 Introduction 233(1) 11.2 Vector-to-Raster Conversion 233(4) 11.3 Parallelisation Strategies 237(5) 11.4 Parallel Algorithm Selection Criteria 242(3) 11.5 Design Overview 245(1) 11.6 External Interfaces 246(1) 11.7 Process Structure 247(3) 11.8 Modules 250(2) 11.9 Conclusions 252(1) 11.10 References 252(1) 12 RASTER-TO-VECTOR CONVERSION 253(12) M. J. MINETER 12.1 Introduction 253(2) 12.2 Methods of Raster-to-Vector Conversion 255(2) 12.3 Parallel Boundary Linking 257(4) 12.4 Boundary Smoothing 261(2) 12.5 Summary 263(1) 12.6 References 263(2) 13 VECTOR POLYGON OVERLAY 265(46) T. J. HARDING R. G. HEALEY S. HOPKINS S. DOWERS 13.1 Introduction 265(1) 13.2 Polygon Overlay Background 265(2) 13.3 Stages in Polygon Overlay 267(4) 13.4 Non-intersecting Polygons 271(1) 13.5 Techniques for Efficient Geom Intersection 271(5) 13.6 Previous Work Related to Parallel Polygon Overlay 276(1) 13.7 Design for Parallel Polygon Overlay 277(9) 13.8 Conclusions 286(1) 13.9 References 286(3) Appendix: Example Plane Sweep Overlay 289(22) 14 IMPLEMENTATION CASE STUDY: GENERALISATION OF RASTER DATA 311(22) M. J. MINETER G. G. WILKINSON S. DOWERS R. G. HEALEY 14.1 Introduction 311(1) 14.2 Image Generalisation 311(2) 14.3 Parallelisation Issues 313(3) 14.4 Implementation 316(11) 14.5 Performance 327(2) 14.6 Summary 329(1) 14.7 Acknowledgements 329(1) 14.8 References 329(4) PART FOUR: APPLICATION OF PARALLEL PROCESSING 333(108) 15 PARALLEL DATABASE MANAGEMENT SYSTEMS FOR GIS 333(18) R. G. HEALEY S. DOWERS B. M. GITTINGS M. J. TRANTER 15.1 Introduction 333(3) 15.2 Hardware 336(1) 15.3 Software 337(6) 15.4 Implications for GIS 343(3) 15.5 Conclusions 346(1) 15.6 References 346(5) 16 ALGORITHMS FOR PARALLEL TERRAIN MODELLING AND VISUALISATION 351(36) P. MAGILLO E. PUPPO 16.1 Introduction 351(2) 16.2 Terrain Models 353(1) 16.3 Problems Relevant to Terrain Modelling 354(7) 16.4 Parallel Algorithms for Delaunay Triangulation and the Voronoi Diagram 361(6) 16.5 Parallel conversion from RSG to TIN 367(3) 16.6 Parallel Algorithms for Topographic Characterisation 370(3) 16.7 Parallel Visibility Computation on Terrains 373(9) 16.8 Concluding Remarks 382(1) 16.9 References 382(5) 17 SPATIAL ANALYSIS 387(28) P. J. DENSHAM M. P. ARMSTRONG 17.1 Introduction 387(1) 17.2 Spatial Statistics 388(5) 17.3 Building Shortest Paths in Parallel 393(5) 17.4 Terrain Analysis 398(9) 17.5 Conclusions 407(2) 17.6 References 409(6) 18 PARALLEL PROCESSING APPROACHES IN REMOTELY SENSED IMAGE ANALYSIS 415(26) G. G. WILKINSON 18.1 GIS and Remote Sensing 415(1) 18.2 Parallel Processing in Remote Sensing -- General Issues 415(1) 18.3 Architecture and Data Mapping Issues 416(8) 18.4 Parallelising Algorithms for Remote Sensing: Experience and Possibilities 424(8) 18.5 Related Topics in Parallel Image Processing 432(1) 18.6 Conclusions 433(1) 18.7 References 433(8) PART FIVE: CONCLUSIONS 441(6) 19 TOWARDS PARALLEL LIBRARIES FOR GEOGRAPHICAL ALGORITHMS 441(6) M. J. MINETER R. G. HEALEY B. M. GITTINGS S. DOWERS 19.1 Summary of Findings 441(2) 19.2 The Need for Portable, Reusable Parallel Libraries 443(2) 19.3 References 445(2) GLOSSARY 447(6) INDEX 453
Richard Healey (University of Portsmouth, Portsmouth, UK) (Edited by) , Steve Dowers (University of Edinburgh, Edinburgh, Scotland) (Edited by) , Bruce Gittings (University of Edinburgh, Scotland) (Edited by) , Mike J Mineter (Univeristy of Edinburgh, Edinburgh, UK) (Edited by)
