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
H
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
© 2008 SpringerScience+Buisiness Media, LLC.
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer
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 identified 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 definitive Encyclopedia of GIS that lays out many of the computer science/mathematics foundations
of the field 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 USs 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 first
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 field 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 field 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 first 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 field 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 fingertips 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 fire 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 significant 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 field, which are keyed to Driver’s Ed, the Encyclopedia also provides a handy sourcebook for the Mr.
Goodwrenches while defining 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 field. 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
field, 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 significant 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 benefits 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 finally 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 significant 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 significant application of computing. Sometime around 1995, the
earlier view of GIS as an assistant performing tasks that the user found too difficult, 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 fixed or mobile sensors providing flows 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 reflected 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, NASAs 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 flows of real-time data
from massive numbers of devices distributed over the Earth’s surface, in areas of scientific interest such as the sea floor,
in vehicles acquiring data on traffic movement, and in battlefields. 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 field, 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 field
X Foreword by Michael Goodchild
that has emerged between two existing and recognized fields, 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 field 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 define a focus, given the multi-disciplinary nature of the field. 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 field.
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 reflect 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 field 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 definition, scientific fundamentals, application domains, and future trends. Many include short
definitional entries cross-referenced to related regular entries in order to discuss specific 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 definitional 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 field
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 scientifically 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 fields, each one an important sub-area within GIS. These fields 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,
field 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