Encyclopedia of GIS

Shashi Shekar • Hui Xiong (Eds.)

Encyclopedia of GIS

With 723 Figures and 90 Table s

123

SHASHI SHEKHAR

McKnight Distinguished University Professor

Faculty of Computer Science and Engineering

Univ ersity of Minnesota

Minneapolis, MN 55455

USA

UI XIONG

Assistant Professor

Management Science and Information Systems Department

Rutgers Business School

Newark and New Brunswick Rutgers, the State University of New Jersey

Newark, NJ 07102

USA

Library of Congress Control Number: 2007933825

ISBN: 978-0-387-35973-1

This publication is available also as:

Print publication under ISBN: 978-0-387-30858-6 and

Print and electronic bundle under ISBN: 978-0-387-35975-5

Science+Business Media, LLC., 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with revie ws or

scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by

similar or dissimilar methodology now kno wn or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identiﬁed as such, is not to be

taken as a n expression of opinion as to whether or not they are subject to proprietary rights.

springer.com

Printed on acid free paper SPIN: 11420118 2109letex – 5 4 3210

To our families . . .

Foreword by Brian Berry

The publication of a deﬁnitive Encyclopedia of GIS that lays out many of the computer science/mathematics foundations

of the ﬁeld is a major event, the culmination of a half century of development. I was part of the earliest stirrings in the

mid-1950s. A small group of geography graduate students at the Univ ersity of Washington, William Garrison’s “space

cadets,” began to assemble what became the foundations of contemporary spatial analysis and to refocus mathematical

cartography while working with civil engineer Edgar Horwood on his attempts to use the printers of the time to produce

grey-shaded maps. Our attention was captured by Sputnik, however, we didn’t anticipate that the US’s response, the rapid

development of NASA and satellite systems, would be the key to the equally rapid development of remote sensing, or

that global positioning would rewrite cartography. Among the innovations of the time were Torsten Hägerstrand’s ﬁrst

simulation models of space-time diffusion processes and early econometric interest in spatial autocorrelation. Both

themes are now central to spatial analysis.

The GIS focus s hifted when Garrison, Marble and I relocated to the Chicago region. Garrison and I helped fund civil

engineer Howard Fisher’s ﬁrst generation computer graphics software, SYMAP I, and Marble and I organized NSF

workshops to spread the word and drew together an initial overview of the ﬁeld in Spatial Analysis. Fisher took his

ideas to the Ford Foundation and a subsequent grant to Harvard University, where he established the Laboratory for

Computer Graphics. The Lab served as the focus for research in the ﬁeld well into the 1970s, providing the spark

to such innovators as Jack Dangermond, who subsequently established ESRI and created what became the world’s

most widely used computer graphics software. Meanwhile, hardware development proceeded apace, as did i maging and

positioning capabilities created by the Department of Defense and NASA, facilitating the resulting emergence of digital

cartography and the establishment of the ﬁrst large-scale Geographic Information Systems such as the Canada Land

Inventory. The rest, as they say, is history – albeit given a new dynamic by the Internet and the continued evolution of

computing capabilities both on the desktop and in the supercomputer.

Fifty years after these beginnings, the result is a large and complex ﬁeld spanning many disciplines, continuing to grow

and to expand into an expanding array of applications. Cartographers have eschewed their pen-and-ink, and rudimentary

mapmaking is at the ﬁngertips of everyone with Internet access. Road atlases are fast giving way to satellite navigation

systems. Congress continues to be concerned with the privacy issues raised by geographic information system capabil-

ities, yet police and ﬁre departments can no longer function eff ectively without GIS and Homeland Security without

modern database and data mining capabilities. From city planning to store location, property taxation to highway build-

ing, disaster response to environmental management, there are few arenas in which GIS is not playing a signiﬁcant role.

What is important is the cross-cutting capability that was recognized when the NSF funded the Center for Spatially-

Integrated Social Science (CSICC) at the University of California, Santa Barbara, or my own university’s Ph.D. program,

a joint venture of the School of Economic, Political and Policy Sciences, the School of Natural Sciences and Mathemat-

ics, and the School of Engineering and Computer Sciences.

I like to tell my colleagues that there are three levels of GIS education: “Driver’s Ed,” “Mr. Goodwrench,” and

“Design Team.” Driver’s Ed provides essential skills to the broad base of software users, the Mr. Goodwrenches of

the world learn how to put together and maintain working software-hardware installations, while Design Teams create

new and improved GIS capabilities. Most of the new data handling capabilities reside in the arenas of computer sci-

ence/mathematics, while advances in inference are coming from innovations in the ability to handle space-time dynamics

while simultaneously accounting for serial and spatial dependence.

The Encyclopedia of GIS provides an essential reference work for all three categories of users. In contrast to the current

textbooks in the ﬁeld, which are keyed to Driver’s Ed, the Encyclopedia also provides a handy sourcebook for the Mr.

Goodwrenches while deﬁning the platform on wh ich future Design Teams will build by focusing – more than existing

VIII Foreword by Brian Berry

works – on the computer science/mathematical foundations of the ﬁeld. I know that the GIS community will value this

important reference and guide, and I will cherish it as a milestone. It marks how far we have come – far beyond what

our group of pioneers dreamed might be possible a half century ago. Professors Shekhar and Xiong and the considerable

community of contributors to the collection have provided us with a comprehensive and authoritative treatment of the

ﬁeld, extensively cross-referenced with key citations and further readings. Importantly, it is available in both printed and

XML online editions, the latter with hyperlink ed citations. The GIS world will be indebted to them. No GIS bookshelf

should, as they say, be without it.

McKinney, Texas

August, 2007

Brian J. L. Berry

School of Economic, Political and Policy Sciences

The University of Te xas, Dallas

Dallas, TX

USA

Foreword by Michael Goodchild

Geographic Information Systems date from the 1960s, when computers were mostly seen as de vices for massive com-

putation. Very signiﬁcant technical problems had to be solved in those early days: how did one convert the contents of

a paper map to digital form (by building an optical scanner from scratch); how did one store the result on magnetic tape

(in the form of a linear sequence of records representing the geometry of each boundary line as sequences of vertices);

and how did one compute the areas of patches (using an elegant algorithm inv olving trapezia). Most of the early research

was about algorithms, data structures, and indexing schemes, and, thus, had strong links to emer ging research agendas

in computer science.

Over the years, however, the research agenda of GIS expanded away from computer science. Many of the technical

problems of computation were solved, and attention shifted to issues of data quality and uncertainty; the cognitive

principles of user interface design; the costs and beneﬁts of GIS; and the social impacts of the technology. Academic

computer scientists interested in GIS wondered if their research would be regarded by their colleagues as peripheral –

a marginally interesting application – threatening their chances of getting tenure. Repeated efforts were made to have

GIS recognized as an ACM Special Interest Group, without success, though the ACM GIS conferences continue to

attract excellent research.

The entries in this encyclopedia should ﬁnally lay any lingering doubts to rest about the central role of computer science

in GIS. Some research areas, such as spatiotemporal databases, have continued to grow in importance because of the

fundamental problems of computer science that they address, and are the subject of several respected conference series.

Geospatial data mining has attracted signiﬁcant attention from computer scientists as well as spatial statisticians, and it is

clear that the acquisition, storage, manipulation, and visualization of geospatial data are special, requiring substantially

different approaches and assumptions from those in other domains.

At the same time, GIS has grown to become a very signiﬁcant application of computing. Sometime around 1995, the

earlier view of GIS as an assistant performing tasks that the user found too difﬁcult, complex, tedious, or expensive

to do by hand, was replaced by one in which GIS became the means by which humans communicate what they know

about the surf ace of Earth, with which they collectively make decisions about the management of land, and by which

they explore the effects of alternative plans. A host of new issues suddenly became important: how to support processes

of search, assessment, and retrieval of geospatial data; how to overcome lack of interoperability between systems; how

to manage large networks of ﬁxed or mobile sensors providing ﬂows of real-time geographic data; how to offer useful

services on the very limited platform of a cell phone; and how to adapt and evolve the technology in order to respond to

emergencies and to provide useful i ntelligence. A revitalized research agenda for computer science emerged that show s

no sign of diminishing, and is reﬂected in many of the topics addressed in this encyclopedia.

For example, computer scientists are engaged in the development of data structures, algorithms, and indexing schemes

to support the hugely popular virtual globes (Google Earth, Microsoft’s Virtual Earth, NASA’s World Winds) that have

emerged in the past few years and are stimulating a whole new generation of applications of geospatial technology.

Research is ongoing on sensor networks, and the complex protocols that are needed to handle ﬂows of real-time data

from massive numbers of devices distributed over the Earth’s surface, in areas of scientiﬁc interest such as the sea ﬂoor,

in vehicles acquiring data on trafﬁc movement, and in battleﬁelds. Semantic interoperability, or the ability of systems to

share not only data but the meaning of data, remains a thorny problem that will challenge the research community for

many years to come.

As a collection of well-written articles on this expanding ﬁeld, this encyclopedia is a welcomed addition to the GIS

bookshelf. The fact that its compilers have chosen to emphasize the links between GIS and computer science is especially

welcome. GIS is in many ways a boundary object, to use a term common in the community of science historians: a ﬁeld

X Foreword by Michael Goodchild

that has emerged between two existing and recognized ﬁelds, in this case computer science and geography, and which

has slowly established its own identity. As it does so, contributions such as this will help to keep those links alive, and

to ensure that GIS continues to attract the interest of leading researchers in computer science.

Michael F. Goodchild

National Center for Geographic Information and Analysis

and Department of Geography

University of California

Santa Barbara, CA

USA

Preface

Interest in Geographic Information Systems, Science, and Services (GIS) has tremendously grown in recent years in

many different ways. Researchers from a variety of academic disciplines are using spatial thinking and GIS tools to

develop spatially-explicit models. Broad public interest in this subject is being fuelled by popular applications like

Google maps, personal navigation devices, MapQuest, etc. Web-based software developers are increasingly exploring

“mash-ups” integrating different information sources to web-based maps, such as Google Earth and MS Virtual Earth.

Therefore, there is a need to bring key GIS concepts and results to a diverse audience as current GIS literature (e. g.,

textbooks, journals, conference-proceedings, trade-books) largely caters to either GIS specialists or end-users of popular

GIS software.

The GIS research community is enthusiastically embracing encyclopedias, i. e., collections of articles on numerous top-

ics in a ﬁeld, as a tool to bring key ideas from a ﬁeld to a general audience. This is not only evident from the preparation

of multiple encyclopedias of GIS in the 2007–2008 time-frame, but also from the generous time commitments from

GIS researchers contributing to the encyclopedia projects as authors, ﬁeld editors and reviewers. The concurrent devel-

opment of multiple GIS encyclopedias helped us deﬁne a focus, given the multi-disciplinary nature of the ﬁeld. This

encyclopedia focuses on computational aspects of a variety of GIS concepts for a variety of reasons. First, computa-

tional advances are making GIS available to a wide variety of end-users, software developers and researchers. Second,

many geo-spatial datasets are large and gro wing rapidly due to advances in cyber -infrastructure, including sensor and

data management technologies. This will make computational issues even more critical in the coming years. Finally,

computational technologies are advancing at a rapid pace, making new capabilities possible every few years. While

the recent advances, e. g., Google Earth and Microsoft Virtual Earth, look impressive, we are likely to see even bigger

advances due to growing computing power in the years to come.

Despite the focus on computational aspects of GIS, it was still challenging to narrow down the list of possible articles

in order to explain the key software, datasets, and processes used by geographers and computational scientists. After

all, our goal was to provide a comprehensive and authoritative treatment of GIS, providing easy access to the ﬁeld.

We re viewed the topics in calls-for-papers for conferences and journals along with the keywords in relevant books and

model curricula. We also consulted various leaders in the GIS area. Additionally, we tried to balance the set of topics

to reﬂect the interests of industry, government and academia. For example, topics such as GIS standards as well as

examples of GIS software from industry and the public domain were included in the topic list. Similarly, we included

topics lik e crime mapping, evacuation planning and location-based services. Naturally, the list includes a variety of

academic topics ranging from “Spatial Cognition” to “Statistical Modeling.”

The next major challenge was to identify suitable ﬁeld editors and authors representing the world leaders in selected

topic areas. Many researchers usually focus on conference and journal papers. Yet, we were pleasantly surprised by the

generosity of time and expertise received from so many enthusiastic GIS colleagues for this encyclopedia project. Field

editors went beyond their call of duty to identify and invite potential authors, and review contributions in order to ensure

technical quality while working with Springer project managers to keep the project on schedule. This is a wonderful

sign of the energy and collegiality of the computational GIS research community.

Springer’s encyclopedia group provided thoughtful guidelines for the entries. Typical entries are 3000 words and pro-

vide balance among deﬁnition, scientiﬁc fundamentals, application domains, and future trends. Many include short

deﬁnitional entries cross-referenced to related regular entries in order to discuss speciﬁc terms and concepts such as the

Global Positioning System, Digital Elev ation/Terrain Model, and Remote Sensing. Regular entries include key citations

and a list of recommended reading regarding the literature, and (online) internal hyperlinks to deﬁnitional entries and

XII Preface

current standards. This Encyclopedia is also simultaneously available as an XML online reference with hyperlinked

citations, cross-references, four-color art, links to Web-based maps, and other interactive features.

Key Features at a Glance

• Immediate point of entry into the ﬁeld for researchers

• A–Z format allows easy, intuitive access for newcomers to the ﬁeld

• Many headers for easy skimming and navigation of topics

• Includes coverage of GIS standards in dev elopment by ISO

• Cross-referenced entries

• Internationally renowned editorial board, both scientiﬁcally and geographically diverse

• Hundreds of contributors ensure balanced coverage

• Interactive features add to convenience, ease of use and understanding

• Peer-reviewed entries assure researchers that information is vetted

• eReference is available at springerlink.com

Content Organization

The encyclopedia is divided into 41 ﬁelds, each one an important sub-area within GIS. These ﬁelds include: Basic

Concepts; Basic Storage and Retrieval Structure; Cartography and Visualization; Commercial GIS; Commercial Spatial

Databases; Critical Evaluation of Standard Proposals; Data Exchange and Interoperability; Digital Road Map; Emergen-

cy Evacuations; Evacuation Planning and Operations; Geosensor Networks; GeoSpatial Semantic Web; GIS in Business

Intelligence, Routing; GIS Issues and Applications; Indoor Positioning; Information Collection Using Sensor Network;

Open Source GIS Software; Photogrammetry; Representation of Inexact Spatial Information; Road Network Databases;

Security and Privacy in Geospatial Information Systems; Spatial Analysis; Spatial Aspects of Bioinformatics; Spatial

Aspects of Distributed Computing; Spatial Aspects of Mobile Computing; Spatial Association Discovery; Spatial Co-

location Rule Mining; Spatial Constraint Databases; Spatial Data Warehousing and Decision Support; Spatial Database

Modeling for Applications; Spatial Indexing; Spatial Outlier Detection; Spatial Prediction; Spatial Thinking; Spatial

Time Series; Spatial Uncertainty and Imprecision; Spatio-Temporal Data Modeling; Spatio-Temporal Databases; Sta-

tistical Modeling for Spatial Data; Tesselation Data Models; and Use of Spatial Data for Simulation.

Acknowledgements

Many people hav e played a part in the production of this book and we are extremely grateful to them. In particular,

ﬁeld editors who have made excellent efforts include Vijay Atluri, Sudipto Banerjee, Yvan Bedard, Sanjay Chawla,

Robert Denaro, Liping Di, Frederico Fonseca, Andrew Frank, Oscar Franzese, Dimitrios Gunopulos, Erik Hoel, Kath-

leen Hornsby, Yan Huang, Robert Kauffman, Baris Kazar, Sangho Kim, Ravi Kothuri, Phaedon Kyriakidis, Xinrong

Li, Henry Liu, Chang-Tien Lu, Nikos Mamoulis, Helmut Mayer, Liqiu Meng, Mohamed Mokbel, Andreas Neumann,

Silvia Nittel, Leon Osborne, Sudhanshu Sekhar Panda, Srinivasan Parthasarathy, Peter Revesz, Ashok Samal, Markus

Schneider, Cyrus Shahabi, Jayant Sharma, Yufei Tao, Vassilis Tsotras, Ouri Wolfson, Chaowei Yang, Pusheng Zhang,

and Naijun Zhou.

We would like to thank the members of the spatial database research group in the Computer Science Department at the

University of Minnesota. They contributed in many different ways including providing literature surveys, organizing

topics, and reviewing articles. We would also like to thank some of the students enrolled in Csci 8701 and Csci 8715 for

contributing articles.

Finally, special thanks are due to many people at Springer for their enthusiasm, advice, and support. In particular , we

would like to thank Susan Lagerstrom-Fife, Oona Schmid, Jennifer Carlson, Andrea Schmidt, Simone Tavenrath, Sharon

Palleschi, and Yana Lambert, who at different times hav e played key roles in the dev elopment of this book.

August, 2007 Shashi Shekhar and Hui Xiong