Spatial DataBases with Application to GIS
Philippe Rigaux
Michel Scholl
Agnes Voisard
Morgan Kaufmann Publishers
Contents
FOREWORD ix
by Victor Vianu, University of California, San Diego
LIST OF FIGURES xvii
PREFACE xxiii
1 AN INTRODUCTION TO
SPATIAL DATABASES 1
1.1 Database Management Systems (DBMSs) 3
1.1.1 Basic Description and Main Features 3
1.1.2 Modeling Applications 6
1.1.3 Physical Data Management 8
1.2 Vocabulary in Geospatial Database Applications 9
1.2.1 Theme 9
1.2.2 Geographic Objects 9
1.3 Geospatial Data Manipulation 11
1.3.1 Simple Operations on Themes 12
1.3.2 Further Theme Operations 18
1.3.3 Other Typical GIS Operations 20
1.4 DBMS Support for Geospatial Data 21
1.4.1 Use of a Relational DBMS 22
1.4.2 Loosely Coupled Approach 24
1.4.3 Integrated Approach Based on DBMS Extensibility 25
1.5 Requirements for a Spatial DBMS 25
1.6 Bibliographic Notes 26
2 REPRESENTATION OF SPATIAL OBJECTS 29
2.1 Geographic Space Modeling 31
2.1.1 Entity-Based Models 31
2.1.2 Field-Based Models 34
2.2 Representation Modes 35
2.2.1 Tessellation 35
2.2.2 Vector Mode 38
2.2.3 Half-Plane Representation 42
2.3 Representing the Geometry of a Collection of Objects 46
2.3.1 Spaghetti Model 47
2.3.2 Network Model 47
2.3.3 Topological Model 49
2.4 Spatial Data Formats and Exchange Standards 51
2.4.1 Overview of Current Spatial Data Formats 52
2.4.2 The TIGER/Line Data Format 54
2.4.3 Recent Standardization Initiatives 61
2.5 Bibliographic Notes 64
3 LOGICAL MODELS AND
QUERY LANGUAGES 69
3.1 Reference Schemas 71
3.1.1 Administrative Units (Schema 1) 71
3.1.2 Highway Network Among Cities (Schema 2) 72
3.1.3 Land Use (Schema 3) 72
3.2 Reference Queries 73
3.3 Spatial Abstract Data Types 75
3.3.1 Extending Data Models with Spatial ADTs 75
3.3.2 Designing Spatial ADTs 80
3.3.3 Exploring Relationships Between Spatial Objects:
Topological Predicates 85
3.4 Relational Models Extended with ADT 88
3.4.1 Representation of the Reference Schemas 89
3.4.2 Reference Queries 92
3.5 Object-Oriented Models 100
3.5.1 A Brief Overview of Object-Oriented DBMS 100
3.5.2 Representation of Reference Schemas 101
3.5.3 Spatial Classes 104
3.5.4 Reference Queries 106
3.6 Bibliographic Notes 108
4 THE CONSTRAINT DATA MODEL 113
4.1 Spatial Data Modeling with Constraints 114
4.1.1 Point Sets as Infinite Relations 115
4.1.2 Finitely Representing Infinite Relations 117
4.1.3 Evaluating Queries on Infinite Instances 120
4.1.4 Summary of the Constraint Data Model 122
4.2 The Linear Constraint Data Model 123
4.2.1 Data Representation 124
4.2.2 Query Languages: First-Order Queries 125
4.2.3 Query Languages: Algebraic Queries 128
4.3 Modeling Entity-Based Data 134
4.3.1 Nested Relations 134
4.3.2 Queries 136
4.4 Modeling Field-Based Data and Moving Objects 139
4.4.1 Elevation Data 140
4.4.2 Moving Objects 141
4.4.3 Queries on Field-Based Data and Moving Points 143
4.5 Bibliographic Notes 145
5 COMPUTATIONAL GEOMETRY 149
5.1 An Introduction to Computational Geometry 150
5.2 Background 150
5.2.1 Basic Concepts of Algorithms 151
5.2.2 Algorithm Analysis 152
5.2.3 Optimality 153
5.2.4 Data Structures 155
5.3 Useful Algorithmic Strategies 157
5.3.1 Incremental Algorithms: The Convex-Hull Example 157
5.3.2 Divide-and-Conquer Strategy: The Half-Plane Intersection
Example 161
5.3.3 Sweep-Line Method: The Rectangle Intersection
Example 164
5.4 Polygon Partitioning 167
5.4.1 Trapezoidalization of a Simple Polygon 168
5.4.2 Triangulation of Simple Polygons 170
5.4.3 Convex Partitioning 173
5.5 Algorithms for Spatial Databases 175
5.5.1 Area Size of a Polygon and Related Operations 176
5.5.2 Point in Polygon 177
5.5.3 Polyline Intersections 179
5.5.4 Polygon Intersections 186
5.5.5 Windowing and Clipping 192
5.6 Bibliographic Notes 197
5.6.1 General Sources 197
5.6.2 Sources on Algorithms 198
6 SPATIAL ACCESS METHODS 201
6.1 Issues in SAM Design 204
6.1.1 What Is Expected of a SAM? 205
6.1.2 Illustration with a B+Tree 206
6.1.3 Space-Driven Versus Data-Driven SAMs 207
6.2 Space-Driven Structures 208
6.2.1 The Grid File 209
6.2.2 The Linear Quadtree 219
6.2.3 The z-Ordering Tree 227
6.2.4 Remarks on Linear SAM 237
6.3 Data-Driven Structures: The R-Tree 237
6.3.1 The Original R-Tree 238
6.3.2 The R∗Tree 252
6.3.3 R-Tree Packing 255
6.3.4 The R+Tree 257
6.3.5 Cost Models 259
6.4 Bibliographic Notes 261
7 QUERY PROCESSING 267
7.1 An Introduction to Query Processing 269
7.2 Two Optimal I/O Algorithms 271
7.2.1 External Sort/Merge 271
7.2.2 Distribution Sweeping (Rectangle Intersection) 274
7.3 Spatial Join 279
7.3.1 z-Ordering Spatial Join 280
7.3.2 Joining Two R-Trees 284
7.3.3 Spatial Hash Join 288
7.4 Complex Queries 292
7.4.1 Query Execution Plans 292
7.4.2 Spatial Joins with Refinement Step 296
7.4.3 Multiway Joins 300
7.5 Bibliographic Notes 303
8 COMMERCIAL SYSTEMS 311
8.1 An Introduction to Commercial Systems 312
8.1.1 How to Read This Chapter 312
8.1.2 Interacting with a GIS or with a Spatial DBMS 315
8.2 ArcInfo 317
8.2.1 Functionalities of ArcInfo 317
8.2.2 Spatial and Topological Information in ArcInfo 319
8.2.3 Representation of Sample Schemas 328
8.2.4 Querying with ArcInfo 332
8.3 ArcView GIS 341
8.3.1 ArcView Spatial Model 342
8.3.2 Querying with ArcView 343
8.4 Smallworld 347
8.4.1 Smallworld Spatial Data Model 347
8.4.2 Querying with Smallworld Object Browser 348
8.4.3 Discussion 351
8.5 Oracle Extension for Handling Spatial Data 352
8.5.1 Introduction to Oracle Spatial 352
8.5.2 Spatial Data Model 353
8.5.3 Spatial Operations 355
8.5.4 Spatial Indexing and Query Processing 357
8.6 PostgreSQL 360
8.6.1 Geometric Types and Operators 361
8.6.2 Creating the Database 363
8.6.3 Expressing Queries 364
8.7 Bibliographic Notes 368
BIBLIOGRAPHY 373
INDEX 395
ABOUT THE AUTHORS 409
Preface
“In that Empire, the Art of Cartography achieved such Perfection that the Map of one single Province occupied the whole of a City, and the Map of the Empire, the whole of a Province. In time, those Disproportionate maps failed to satisfy and the Schools of Cartography sketched a Map of the Empire which was of the size of the Empire and coincided at every point with it. Less addicted to the study of Cartography, the Following Generations comprehended that this dilated Map was Useless and, not without Impiety, delivered it to the Inclemencies of the Sun and of the Winters. In the Western Deserts there remain piecemeal Ruins of the Map, inhabited by Animals and Beggars. In the entire rest of the Country there is no vestige left of the Geographical Disciplines.”
JORGE LUIS BORGES
Suarez Miranda, Viajes de
Varones Prudentes, IV
Afew decades ago, paper maps were the principal means to synthetize and represent geographic information. Manipulating this information was limited to a manual, noninteractive process. Since then, the rapid development of new technologies to collect and digitize geographic data, together with an increasing demand for both interactive manipulation and analysis of this data, has generated a need for dedicated softwares, namely geographic information systems (GISs).
A GIS is more than a cartographic tool to produce maps. It stores geographic data, retrieves and combines this data to create new representations of geographic space, provides tools for spatial analysis, and performs simulations to help expert users organize their work in many areas, including public administration, transportation networks, military applications, and environmental information systems.
Due to the ever-increasing volume of geographic data, one of the major tasks of GIS is to efficiently manage huge databases of complex information. In a classical software architecture, this task is usually devoted to a database management system (DBMS). Most DBMSs in practical use are relational DBMSs. However, relational DBMSs are strongly geared toward business applications, which manipulate large but simple data sets. It turns out that these systems are unable to manage geographic data, in particular because of its inherent spatial component. There have been considerable efforts to extend and adapt DBMS technology to spatial information. This book aims at reporting on the major achievements in this field. Although there are increasing interdependencies between GIS and DBMS technologies, two different viewpoints can be taken. On the one hand, GISs see database systems as one tool among many that provide facilities for the storage and retrieval of data. In turn, this data is processed by other tools, such as spatial analysis or graphical user interfaces. DBMS designers, on the other hand, see GIS as one important, but not unique, application of their novel ability to handle spatial data. From a database point of view, the emphasis is less on the application itself than on the functionality; namely, the storage of large volumes of spatial information, the application of computational techniques on this information, and the development of efficient access methods to retrieve relevant data from voluminous data sets stored on disk.
This book is mainly influenced by the second perspective. It explores the various techniques (and thus the required extensions of classical DBMSs) necessary to meet the requirements of spatial data management, both at the user level and at the system level.
In many respects, these requirements go beyond the management of geographic data. Indeed, the ability to manipulate spatial information—which is at the core of the novel features of spatial DBMS—is useful for any application based on large spatial data sets, including computer-aided design (CAD), very large scale integration (VLSI), robotics, and image processing. We chose, however, to take our examples and illustrations from the field of geographic applications, both because this is still the primary target of spatial DBMS and because geographic applications served as the first motivation to develop spatial DBMS and thus strongly influenced its design.
Geospatial information concerns phenomena occurring above, on, and below Earth’s surface. Geospatial information is represented in maps. A map contains geographic objects such as land parcels, rivers, and roads that are related to the same geographic area. Any geographic object has the following components:
◆ The component referred to as spatial or geometric attribute, or spatial extent. This component describes the location, shape, orientation, and size of the object (for instance, a land parcel) in 2D or 3D space.
◆ The component that describes the object by means of nonspatial attributes. These attributes are also referred to as thematic or descriptive attributes (for instance, the name of a land parcel).
The foregoing characteristics are not exclusive to geographic information. For example, VLSI layout description also deals with objects having an extent in multidimensional space. This is why spatial databases should be preferred as a more generic term for information systems dealing with objects having a spatial component. Spatial databases should be distinguished from image information systems or image databases, which manage collections of 2D or 3D scenes. Medical databases, electronic documents, and cultural heritage collections are examples of potential image sources. Image databases support the search for scenes that contain certain objects or patterns. Location, direction, and size of the object are usually of little importance—a major difference from spatial databases, where these search criteria play an important role. Image databases will not be discussed further here.
Some of the tasks currently handled by GIS existed before GIS technology. These include systematic collection of data about land for census activities, atlases, public administration mapping efforts, public utilities management, new construction planning and engineering, urban and rural planning, and cartography, as well as tasks required by the military and various sciences, such as geography, geology, and geodesy. In addition, many regional and national agencies, as well as other organizations, use geographic data for less traditional tasks that have been influenced by the development of GIS technology, such as forest management, postal services, space applications, socioeconomic studies, and market analysis.
Organization of This Book
This book seeks to explain the major features of a spatial database. It deals with the concepts, techniques, and algorithms that have been developed around the core issues in database management, such as how to represent data, which operations should be supplied by the system to manipulate and retrieve this data, and how to access and retrieve data from secondary storage. The main objective is to identify the challenges raised by the peculiar nature of spatial information, and to describe the specific techniques recently developed to meet these novel requirements.
The book covers basic material and some advanced topics. As far as basic material is concerned, we provide a sound and detailed coverage of several well-established topics—for example, structures for spatial data representation or spatial access methods—that can serve as a reference for practitioners, scientists, and graduate students. Advanced topics and more specialized aspects are also introduced, either because we believe they will soon be adopted in commercial systems (this is the case for query processing techniques, for instance), or because they represent a new and exciting way of thinking about spatial data and its representation in database systems (for example, constraint databases). The presentation style of advanced material is based on intuition and examples, rather than on a meticulous and exhaustive treatment. The interested reader will find, at the end of each chapter, a section devoted to bibliographic notes. The book is organized in eight chapters, whose content is as follows:
◆ Chapter 1 provides introductory material toward understanding subsequent chapters. We present the main features of database management systems and GIS, and we introduce the vocabulary used throughout the book.
◆ Chapter 2 concerns spatial data representation. It studies the internal or physical representation of spatial objects.
◆ Chapter 3 presents logical models and query languages for representing and manipulating geographic information. Our discourse relies on common database technology; namely, extended relational and object-oriented database management systems.
◆ Chapter 4 deals with a recent alternative way of modeling and querying geographic information through constraint databases.
◆ Chapter 5 introduces algorithmic techniques for implementing the spatial operations presented in Chapter 3. These techniques belong to the field of computational geometry.
◆ Chapter 6 is devoted to the study of spatial access methods (SAMs), or spatial indices, necessary for accelerating the access to a large number of spatial objects stored on disk.
◆ Chapter 7 is an introduction to query processing techniques for evaluating end-user queries on spatial databases. It includes in particular some algorithms for spatial joins.
◆ Chapter 8 presents five products on the market. The first three are GIS platforms; namely, ArcInfo, ArcView, and Smallworld. The fourth is the Oracle relational DBMS spatial extension SDO, and the fifth is an open source DBMS, PostgreSQL.
The book has two potential audiences. The primary audience includes people from the database research community and database people developing tools for spatial applications. A second audience consists of geographers and GIS users interested in understanding the challenges in current and future GIS technology. We tried as much as possible to introduce the technical background necessary for readers with no expertise in databases. It can be anticipated, however, that readers with solid database background (the primary audience previously discussed) will be more interested in Chapters 1, 2, 4, 5, 6, and 7, whereas geographers and GIS users will find information that meets their needs in Chapters 1, 3, 6, and 8.
Acknowledgments
Writing this book would not have been possible without the contribution of many people, whom we wish to thank here. We are indebted to Jean-Paul Peloux and Laurent Raynal, with whom we published a preliminary version of this book in French. Jean-Paul focused on spatial indexing, whereas Laurent was particularly concerned with ArcInfo. Some of our colleagues provided us with many useful comments on many parts of the manuscript, among them Oliver Gunther (Chap- ¨ ter 2), Luc Segoufin (Chapters 4 and 5), Anne Verroust (Chapter 5), and Jean-Marc Saglio (Chapter 6). We are grateful to them.
We wish to thank Dave Abel, Martin Breunig, and Rolf de By, who as formal reviewers of parts of this book made many detailed and constructive remarks. In particular, Dave gave us extremely valuable feedback regarding the organization of the book and pointed to interesting issues, whereas Rolf did a tremendous job getting into the details of three chapters.
It would not have been possible to develop many of the aspects presented here without common reflection with colleagues, some of them being coauthors of publications. We wish to thank Benoˆıt David, Kenn Gardels, Gilles Grangeret, Stephane Grumbach, Oliver G ´ unther, Gaby ¨ Kuper, Yannis Manolopoulos, Apostolos Papadopoulos, Xavier Rhes´ e,´ Hans-Jorg Schek, Luc S ¨ egoufin, and Pierangelo Veltri.
Many people indirectly contributed to this book through their technical abilities, among them Gunter Feuer, Thomas Klinkski, and ¨ Vilim Vesligaj, who provided technical support at the Freie Universitat, Berlin; Catherine Breton and Daniel Marcel, who shared their ¨ knowledge of ArcView; Steffi Fritz and Cornelia Pester of Smallworld, Germany, who helped us set our Smallworld environment at the Freie Universitat, Berlin; Laurent Breton from IGN, who shared his exper- ¨ tise with ArcInfo; and Jose Moreira and Jean-Marc Saglio, with whom ´ we had many technical discussions about Oracle. We wish to thank them.
We also wish to acknowledge the programs and host institutions who helped us travel and meet each other, despite the distance, during this long process. Michel Scholl visited the Freie Universitat many ¨ times, thanks in particular to the Berlin-Brandenburg graduate school on distributed information systems (DFG grant no. GRK 316) and the Procope Franco-German exchange program (DAAD grant no. 312). Agnes Voisard visited CNAM and INRIA for extended periods through ` the Procope cooperation. We would also like to acknowledge the partial support of the European Network TMR Chorochronos. We are grateful to its members for the stimulating discussions of the past two years. We are indebted to our home institutions for their continuing support: the Vertigo database group in the Cedric lab of CNAM, the Verso database project at INRIA, and the database group at Freie Universitat Berlin. We are grateful to our colleagues in these institutions ¨ for the warm atmosphere in which this work was carried out, including notably Serge Abiteboul, Helmut Alt, Bernd Amann, Alain Cazes, Vassilis Christophides, Sophie Cluet, Claude Delobel, Daniel Faensen, Lukas Faulstich, Annika Hinze, Marcus Jurgens, Leonid Libkin, Alain ¨ Michard, Stephane Natkin, Andreas Sabisch, Heinz Schweppe, Anne- ´ Marie Vercoustre, Victor Vianu, Franc¸ois-Yves Villemin, Dan Vodislav, Franz Wagner, Gerald Wagner, and Gerald Weber. We owe a great deal to our secretaries Heike Eckart, Danny Moreau, and Virginie Moreau for their constant support in everyday life. We also thank our students Irini Fundulaki, Christophe Gurret, Laurent Mignet, and Cedric Du Mouza.
Finally, we are grateful for the assistance we received from the editorial staff at Morgan Kaufmann. We are especially thankful to Marnie Boyd, Belinda Breyer, and Diane Cerra for their patience during the entire process.
About the Authors
Philippe Rigaux holds a Master’s in mathematics and a Master’s in computer science from the University of Paris VII. From 1986 to 1992, he was a software engineer in private industry. From 1992 to 1995, he was a research assistant in the database group of the Conservatoire National des Arts et M´etiers (CNAM) in Paris, where he obtained his Ph.D. in 1995. He is currently an assistant professor in the CNAM database group. He has conducted research in the area of database management, strongly oriented toward spatial applications. His research interests include the design of query languages and query evaluation techniques. He has been involved in the program committee of various conferences in the field, such as SSD, ACM-GIS, and SSDBM.
Michel Scholl received his Ph.D. in computer science from the University of California at Los Angeles in 1977, and his French Th´ese d’´etat from the University of Grenoble in 1985. He was with INRIA (French Institut National de Recherche en Informatique et en Automatique) for twelve years, where he headed the Verso database group, prior to joining the faculty of the Conservatoire National des Arts et M´etiers (CNAM). Since 1989, he has been a full professor of computer science at CNAM. He manages the database group in the research laboratory CEDRIC of CNAM and has a joint position at INRIA in the Verso database group. His background includes computer-assisted instruction, packetswitched radio networks, data structures, and databases. His current research interests include spatial databases and digital libraries. He has served as program chair for the 5th International Symposium on Spatial Databases (SSD’97) and as program committee member of many conferences, including ACM SIGMOD, VLDB, and EDBT
Agnes Voisard ` received her Master’s and Ph.D. degrees in computer science from the University of Paris at Orsay (Paris XI) and INRIA (French Institut National de Recherche en Informatique et en Automatique) in 1989 and 1992, respectively. During the academic year 1991–92 she was a research assistant in the database group of the Conservatoire National des Arts et M´etiers (CNAM) in Paris. In 1992–93 she was an INRIA postdoctoral fellow at Ludwig Maximilian University in Munich. In 1993, she was appointed assistant professor of computer science at the Free University of Berlin, where she obtained her Habilitation in 1999. In January 2001, she joined Kivera, Inc. (Oakland, California) as a system architect. Her areas of expertise include geographic information systems, object-oriented databases, data modeling, graphical user interfaces, navigation systems, and interoperability in information systems. She has participated in several program committees, and was general chair of the 5th International Symposium on Spatial Databases (SSD’97).
Bibliography
[ABCK91] J. C. Antenucci, K. Brown, P. L. Croswell, and M. J. Kevany. Geographic Information Systems: A Guide to the Technology. Van Nostrand Reinhold (International Thomson Publishing), New York, 1991.
[Abe89] D. Abel. “SIRO-DBMS: A Database Toolkit for Geographical Information Systems.” Intl. Journal of Geographical Information Systems (IJGIS), 3(2):103–116, 1989.
[AG97] N. R. Adam and A. Gangopadhyay. Database Issues in Geographic Information Systems. Vol. 6 of Advances in Database Systems. Kluwer Academic Publishers, New York, 1997.
[Aga97] P. K. Agarwal. “Geometric Range Searching.” In CRC Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton, 1997.
[Ahr85] J. H. Ahrens. “Sequential Random Sampling.” ACM Trans. on Mathematical Software, 11(2), 1985.
[AHU74] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
[AHV95] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. AddisonWesley, Reading, MA, 1995.
[AO93] D. Abel and B. C. Ooi, editors. Proc. Intl. Symposium on Large Spatial Databases (SSD). Vol. 692 of Lecture Notes in Computer Science, Singapore. Springer-Verlag, Berlin/Heidelberg/New York, 1993.
[APR+98] L. Arge, O. Procopiuc, S. Ramaswami, T. Suel, and J. Vitter. “Scalable Sweeping Based Spatial Join.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1998.
[Arg97] L. Arge. “External Memory Algorithms with Applications in GIS.” In [vKNRW97], pages 213–249, 1997.
[Arm90] M. A. Armstrong. Basic Topology. Springer-Verlag, Berlin/Heidelberg/New York, 1990.
[AS83] D. Abel and J. L. Smith. “A Data Structure and Algorithm Based on a Linear Key for a Rectangle Retrieval Problem.” Computer Vision, Graphics and Image Processing, 24:1–13, 1983.
[AS93] W. G. Aref and H. Samet. “Decomposing a Window into Maximal Quadtree Blocks.” Acta Informatica, 30:425–439, 1993.
[AS95] W. G. Aref and H. Samet. “A Window Retrieval Algorithm for Spatial Databases Using Quadtrees.” In Proc. ACM Intl. Symp. on Geographic Information Systems (ACM-GIS), 1995.
[Ash99] M. Ashworth. Information Technology, Database Languages, SQL Multimedia, and Application Packages, Part 3: Spatial, ISO/IEC 13249-3, 1999.
[AV88] A. Aggarwal and J. S. Vitter. “The Input/Output Complexity of Sorting and Related Problems.” Communications of the ACM, 31(9):1116–1127, 1988.
[AV96] L. Arge and J. S. Vitter. Optimal Interval Management in External Memory. In IEEE Conf. on Foundations of Computer Science, pages 560–569, 1996.
[AVV95] L. Arge, D. E. Vengroff, and J. S. Vittter. “External-Memory Algorithms for Processing Line Segments in Geographic Information Systems.” In European Symposium on Algorithms (ESA), 1995.
[Bau72] B. G. Baumgart. “Winged Edge Polyhedron Representation.” Technical Report CS-TR-72-320, Stanford University, Department of Computer Science,1972.
[BBC98] A. Belussi, E. Bertino, and B. Catania. “An Extended Algebra for Constraint Databases.” IEEE Transactions on Knowledge and Data Engineering (TKDE), 10(5):686–705, 1998. A shorter version appeared in SSD’97.
[BD98] P. A. Burrough and R. A. McDonnell. Principles of Geographical Information Systems. Oxford University Press, Oxford/New York, 1998.
[BDK92] F. Bancilhon, C. Delobel, and P. C. Kanellakis, editors. Building an ObjectOriented Database System: The Story of O2. Morgan Kaufmann, San Francisco, 1992.
[BDQV90] K. Bennis, B. David, I. Quilio, and Y. Viemont. “G ´ EOTROPICS: Database ´ Support Alternatives for Geographic Applications.” In Proc. Intl. Symp. on Spatial Data Handling (SDH), 1990.
[Ben75] J. L. Bentley. “Multidimensional Binary Search Trees Used for Associative Searching.” Communications of the ACM, 18(9):509–517, 1975.
[Ben77] J. L. Bentley. “Algorithms for Klee’s Rectangle Problems.” Technical Report, Carnegie Mellon University, Department of Computer Science, 1977.
[Ben80] J. L. Bentley. “Multidimensional Divide and Conquer.” Communications of the ACM, 23:214–229, 1980.
[Ber97] P. Bergougnoux. “Bridging the Gap Between Computer Science and Geography.” GeoInformatica, 1(1): 1997.
[BF79] J. L. Bentley and J. H. Friedman. “Data Structures for Range Searching.”ACM Computing Surveys, 11(4), 1979.
[BG92] L. Becker and R. H. Guting. “Rule-Based Optimization and Query Processing ¨ in an Extensible Geometric Database System.” ACM Transactions on Database Systems, 17(2):247–303, 1992.
[BG94] G. Blankenagel and R. H. Guting. “External Segment Trees.” ¨ Algorithmica, 12:498–532, 1994.
[BGSW89] A. Buchmann, O. Gunther, T. R. Smith, and Y.-F. Wang, editors. ¨ Proc. Intl. Symposium on Design and Implementation af Large Spatial Databases (SSD). Vol. 409 of Lecture Notes in Computer Science, Santa Barbara. Springer-Verlag, Berlin/Heidelberg/New York, 1989.
[BHF93] L. Becker, K. Hinrichs, and U. Finke. “A New Algorithm for Computing Joins with Grid Files.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), 1993.
[BHG87] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, MA, 1987.
[BKK99] C. Boehm, G. Klump, and H. P. Kriegel. “XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension.” In [GPL99], pages 75–90, 1999.
[BKS93] T. Brinkhoff, H. P. Kriegel, and B. Seeger. “Efficient Processing of Spatial Joins Using R-Trees.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1993.
[BKSS90] N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger. “The R*Tree: An Efficient and Robust Access Method for Points and Rectangles.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 322–331, 1990.
[BKSS94] T. Brinkhoff, H. P. Kriegel, R. Schneider, and B. Seeger. “Multi-Step Processing of Spatial Joins.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 197–208, 1994.
[BM72] R. Bayer and C. McCreight. “Organization and Maintenance of Large Ordered Indexes.” Acta Informatica, 1(3):173–189, 1972.
[BM91] B. P. Buttenfield and R. B. MacMaster, editors. Map Generalization: Making Rules for Knowledge Representation. Longman Scientific and Technical, London,1991.
[BO79] J. L. Bentley and T. A. Ottmann. “Algorithms for Reporting and Counting Geometric Intersections.” IEEE Trans. on Comp., C(28), 1979.
[BS97] A. Brodsky and V. E. Segal. “The C3 Constraint Object-Oriented Database
System: An Overview.” In Proc. Intl. Workshop on Constraint Database Systems, LNCS 1191, pages 134–159, 1997.
[BTAPL99] C. Bonhomme, C. Trepied, M.-A. Aufaure-Portier, and R. Laurini. A Visual ´ Language for Querying Spatio-temporal Databases. In Proc. ACM Intl. Symp. on Geographic Information Systems (ACM-GIS), pages 34–39, 1999.
[Buc94] H. Buchanan. “Geographic Information: The Source Book for GIS.” In D. R. Green, D. Rix, and J. Cadoux-Hudson, editors, Standards for Spatial Data Transfer, pages 254–261. Taylor and Francis, London, in cooperation with the Association for Geographic Information, 1994.
[Bur94] P. A. Burrough. “Accuracy and Error in GIS.” In D. R. Geen and D. Rix, editors, The AGI Source Book for Geographic Information Systems, pages 87– 91. Association for Geographic Information, London, 1994.
[BW80] J. L. Bentley and D. Wood. “An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles.” IEEE Transactions on Computers, 29, 1980.
[BW88] K. E. Brassel and R. Weibel. “A Review and Conceptual Framework of Automated Map Generalization.” Intl. Journal on Geographical Information Systems, 2(3):229–244, 1988.
[BY98] J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, New York, 1998.
[Cat95] R.G.G. Cattell. “Object Databases and Standards.” In Proc. British National Conference on Databases, pages 1–11, 1995.
[CD85] B. Chazelle and D. P. Dobkin. “Optimal Convex Decomposition.” In G. T. Toussaint, editor, Computational Geometry, pages 63–133. North Holland, Amsterdam, 1985.
[CE92] B. Chazelle and E. Edelsbrunner. “An Optimal Algorithm for Intersecting Line Segments in the Plane.” Journal of the ACM, 39, 1992.
[Cha91] B. Chazelle. “Triangulating a Simple Polygon in Linear Time.” Discrete and Computational Geometry, 6:485–524, 1991.
[Cha94] T. M. Chan. “A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections.” In Proc. Canadian Conf. on Computational Geometry, 1994.
[CL93] J.-P. Cheylan and S. Lardon. “Towards a Conceptual Data Model for the Analysis of Spatio Temporal Processes: The Example of the Search for Optimal Grazing Strategies.” In Proc. Intl. Conf. on Spatial Information Theory (COSIT), LNCS 716, pages 158–176. Springer-Verlag, Berlin/Heidelberg/ New York, 1993.
[Clu98] S. Cluet. “Designing OQL: Allowing Objects to Be Queried.” Information Systems, 23(5):279–305, 1998.
[CMTV00] A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos. “Closest Pair Queries in Spatial Databases.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 2000.
[Com82] D. Comer. “The Ubiquitous B-Tree.” ACM Computing Surveys, 11(2):121–137, 1982.
[CR91] J. T. Coppock and D. W. Rhind. Geographical Information Systems: Principles and Applications. Vol. 1: Principles (chapter: “The History of GIS”). Longman Scientific and Technical, London, 1991.
[CR99] J. Chomicki and P. Revesz. “A Geometric Framework for Specifying Spatiotemporal Objects.” In Proc. Intl. Workshop on Time Representation and Reasoning, 1999.
[CW83] F. Chin and C. A. Wang. “Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons.” IEEE Transactions on Computers, 32:1203–1207, 1983.
[Dan94] J. Dangermond. “ArcView Status and Direction.” ESRI ArcNews, 16(2):1–6, 1994.
[dBSW97] J. Van den Bercken, B. Seeger, and P. Widmayer. “A Generic Approach to Bulk Loading Multidimensional Index Structures.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), pages 406–415, 1997.
[dBvKOS97] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, editors. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin/ Heidelberg/New York, 1997.
[DG85] D. J. DeWitt and R. H. Gerber. “Multiprocessor Hash-Based Join Algorithms.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1985.
[DGVV97] F. Dumortier, M. Gyssens, L. Vandeurzen, and D. Van Gucht. “On the Decidability of Semi-Linearity for Semi-Algebraic Sets and Its Implications for Spatial Databases.” In Proc. ACM Intl. Symp. on Principles of Database Systems PODS), 1997.
[DKO+84] D. J. DeWitt, R. H. Katz, F. Olken, L. D. Shapiro, M. Stonebraker, and D. A. Wood. “Implementation Techniques for Main Memory Database Systems.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1984.
[DPS98] T. Devogele, C. Parent, and S. Spaccapietra. “On Spatial Database Integration.”International Journal of Geographical Information Science, 12(4), 1998.
[DRSM93] B. David, L. Raynal, G. Schorter, and V. Mansart. “GeO2: Why Objects in a Geographical DBMS?” In [AO93], pages 264–276, 1993.
[DSS98] T. Dalamagas, T. K. Sellis, and L. Sinos. “A Visual Database System for Spatial and Non-spatial Data Management.” In Proc. Intl. Conf. on Visual Database Systems (VDB), pages 105–122, 1998.
[Dum97] P. Dumolard. “Multiscale Statistical Spatial Data Bases.” In I. Bowler and C. Laurent, editors, Common Agriculture Policy and the Regions. INRA Editions, Paris, 1997.
[DW96] L. Daniel and A. Whitener. Inside Map Info Professional. OnWord Press, Santa Fe, 1996.
[Ede83] H. Edelsbrunner. A New Approach to Rectangle Intersections. Int. J. Computer Mathematics, 13:209–229, 1983.
[Ede87] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin/Heidelberg/New York, 1987.
[EF91] M. Egenhofer and R. D. Franzosa. “Point-Set Topological Spatial Relations.” International Journal of Geographical Information Systems, 5(2):161–174, 1991.
[Ege89] M. Egenhofer. “A Formal Definition of Binary Topological Relationships.” In Proc. Intl. Conf. on Foundations of Data Organization and Algorithms (FODO), pages 457–472, 1989.
[Ege94] M. Egenhofer. “Spatial SQL: A Query and Presentation Language.” IEEE Transactions on Knowledge and Data Engineering (TKDE), 6:86–95, 1994.
[Ege96] M. Egenhofer. “Spatial-Query-by-Sketch.” In Proc. IEEE Intl. Symposium on Visual Languages (VL’96), 1996.
[Ege97] M. Egenhofer. “Consistency Revisited.” GeoInformatica, 1(4), 1997.
[EGSV98] M. Erwig, R. H. Guting, M. Schneider, and M. Vazirgiannis. “Abstract and ¨ Discrete Modeling of Spatio-temporal Data Types.” In Proc. Intl. Symp. on Geographic Information Systems, pages 131–136, 1998.
[EGSV99] M. Erwig, R. H. Guting, M. Schneider, and M. Vazirgiannis. “Spatio- ¨ temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases.” GeoInformatica, 3(3):269–296, 1999.
[EH90] M. Egenhofer and J. R. Herring. “A Mathematical Framework for the Definition of Topological Relationships.” In Proc. Intl. Symp. on Spatial Data Handling (SDH), vol. 2, pages 803–813, 1990.
[EKS97] M. Ester, H. P. Kriegel, and J. Sander. “Spatial Data Mining: A Database Approach.” In [SV97], pages 47–66, 1997.
[EN94] R. Elmasri and S. Navathe. Fundamentals of Database Systems, 2d Ed., Benjamin/Cummings, Redwood City, CA, 1994.
[ESRa] ESRI, Inc. “Getting Started with SDE Version 3.0.” URL: www.esri.com/software/sde/pdfs/getstart.pdf.
[ESRb] ESRI, Inc. URL:
www.esri.com/software/arcinfo/arcsde/index.html (SDE home page).
[ESR96] ESRI. ArcInfo Version 7 Manual, Redwood, CA, 1996.
[ESR01] ESRI, Inc. URL: www. esri.com/software/arcview/ (ArcView home page).
[Fal86] C. Faloutsos. “Multiattribute Hashing Using Gray Codes.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1986.
[Fal88] C. Faloutsos. “Gray Codes for Spatial Match and Range Queries.” IEEE Transactions on Software Engineering, 14(10), 1988.
[FB74] R. A. Finkel and J. L. Bentley. Quad-Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica, 4:1–9, 1974.
[FB97] S. Fa¨ız and P. Boursier. “Geographic Data Quality: From Assessment to Exploitation.” Cartographica, 33(1):33–40, 1997.
[FGNS00] L. Forlizzi, R. H. Guting, E. Nardelli, and M. Schneider. “A Data Model and ¨
Data Structures for Moving Object Databases.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 2000.
[FK86] A. Frank and W. Kuhn. “Cell Graphs, a Provable Correct Method for the Storage of Geometry.” In Proc. Intl. Symp. on Spatial Data Handling (SDH),1986.
[FK94] C. Faloutsos and I. Kamel. “Beyond Uniformity and Independence: Analysis of R-Trees Using the Concept of Fractal Dimension.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), 1994.
[FNTW90] K. Y. Fung, T. M. Nicholl, R. E. Tarjan, and C. J. Van Wyck. “Simplified
Linear-Time Jordan Sorting and Polygon Clipping.” Information Processing Letters, 35(2):85–92, 1990.
[FP95] L. De Floriani and E. Puppo. “Hierarchical Triangulation for Multiresolution Surface Description.” ACM Transactions on Graphics, 14(4):363–411, 1995.
[FPM00] L. De Floriani, E. Puppo, and P. Magillo. “Applications of Computational Geometry to Geographical Information Systems.” In J. R. Sack and J. Urrita, editors, Handbook of Computational Geometry, pages 333–388. Elsevier Science, 2000.
[FR89] C. Faloutsos and S. Roseman. “Fractals for Secondary Key Retrieval.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), pages 247–252,1989.
[Fra82] A. Frank. “Mapquery: Data Base Query Language for Retrieval of Geometric Data and Their Graphical Representation.” ACM Computer Graphics, 16(3):199–207, 1982.
[Fra92] A. Frank. “Qualitative Spatial Reasoning About Distances and Directions in Geographic Space.” Journal of Visual Languages and Computing, 3(4):343–371, 1992.
[Fra95] A. Frank, editor. Geographic Information Systems: Materials for a Post-graduate Course. Vols. 4–6 of GeoInfo. Technical University of Vienna, Department of Geoinformation, 1995.
[Fre87] M. Freeston. “The BANG File: A New Kind of Grid File.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1987.
[Fre95] M. Freeston. “A General Solution of the n-dimensional B-Tree Problem.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1995.
[FSR87] C. Faloutsos, T. Sellis, and N. Roussopoulos. “Analysis of Object Oriented Spatial Access Methods.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 426–439, 1987.
[FT94] A. Frank and S. Timpf. “Multiple Representations for Cartographic Objects in a Multi-Scale Tree: An Intelligent Graphical Zoom.” ACM Computer Graphics, 18(6):823–829, 1994.
[G93] O. Gunther. “Efficient Computation of Spatial Joins.” In ¨ Proc. IEEE Intl. Conf. on Data Engineering (ICDE), pages 50–59, 1993.
[Gae95] V. Gaede. Optimal Redundancy in Spatial Database Systems. In [HE95], No. 951 in LNCS, pages 96–116, 1995.
[Gar82] I. Gargantini. “An Effective Way to Represent Quadtrees.” Communications of the ACM, 25:905–910, 1982.
[GB90] O. Gunther and A. Buchmann. “Research Issues in Spatial Databases.” ¨ SIGMOD Record (ACM Special Interest Group on Management of Data), 19(4):61–68, 1990.
[GBC98] G. Graefe, R. Bunker, and S. Cooper. “Hash Joins and Hash Teams in Microsoft SQL Server.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), pages 86–97, 1998.
[GEFK99] M. Goodchild, M. Egenhofer, R. Fegeas, and C. Kottman, editors. Interoperating Geographic Information Systems. Kluwer Academic Publishers, New York,1999.
[GG89] M. Goodchild and S. Gopal, editors. Accuracy of Spatial Databases. Taylor and Francis, London, 1989.
[GG98] V. Gaede and O. Gunther. “Multidimensional Access Methods.” ¨ ACM Computing Surveys, 30(2), 1998.
[GI99] R. Grossi and G. F. Italiano. “Efficient Cross-Trees for External Memory.” In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization. DIMACS, Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1999.
[GJ98] M. Goodchild and R. Jeansoulin, editors. Data Quality in Geographic Information: From Error to Uncertainty. Hermes, Paris, 1998.
[GJPT78] M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. “Triangulating a Simple Polygon.” Information Processing Letter, 7(4):175–180, 1978.
[GK96] D. Goldin and P. Kanellakis. “Constraint Query Algebras.” Constraints, 1(1/2):45–83, 1996.
[GKS00] R. Guting, M. Koubarakis, and T. Sellis, editors. ¨ Spatiotemporal Databases: The Chorochronos Approach. Springer-Verlag, Berlin/Heidelberg/New York, 2000. (http://www.dbnet.ece.ntua.gr/˜choros/).
[GLL98] Y. J. Garcia, M. A. Lopez, and S. T. Leutenegger. “On Optimal Node Splitting for R-Trees.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1998.
[GM95] S. C. Guptill and J. L. Morrison, editors. Elements of Spatial Data Quality. Elsevier Science, Amsterdam, 1995.
[GMUW00] H. Garcia-Molina, J. D. Ullman, and J. Widom. Database System Implementation. Prentice Hall, Englewood Cliffs, NJ, 2000.
[GO97] J. E. Goodman and J. O’Rourke. Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton, 1997.
[GOP+98] O. Gunther, V. Oria, P. Picouet, J.-M. Saglio, and M. Scholl. “Benchmarking ¨ Spatial Joins a la Carte ` .” In Proc. Intl. Conference on Scientific and Statistical Database Management (SSDBM), 1998.
[GPL99] R. H. Guting, D. Papadias, and F. H. Lochovsky, editors. ¨ Proc. Intl. Symposium on Large Spatial Databases (SSD). Vol. 1651 of Lecture Notes in Computer Science, Hong Kong. Springer-Verlag, Berlin/Heidelberg/New York, 1999.
[GR93] O. Gunther and W. F. Riekert. “The Design of GODOT: An Object- ¨ Oriented Geographic Information System.” IEEE Data Engineering Bulletin, 16(3):4–9, 1993.
[GR94] V. Gaede and W. F. Riekert. “Spatial Access Methods and Query Processing in the Object-Oriented GIS GODOT.” In Proc. of the AGDM’94 Workshop, pages 40–52. Netherlands Geodetic Commission, 1994.
[Gra93] G. Graefe. “Query Evaluation Techniques for Large Databases.” ACM Computing Surveys, 25(2):73–170, 1993.
[GRS98a] S. Grumbach, P. Rigaux, and L. Segoufin. “Spatio-temporal Data Handling with Constraints.” In Proc. ACM Intl. Symp. on Geographic Information Systems (ACM-GIS), 1998.
[GRS98b] S. Grumbach, P. Rigaux, and L. Segoufin. “The System for Complex Spatial Queries.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 213–224, 1998.
[GRS00] S. Grumbach, P. Rigaux, and L. Segoufin. “Manipulating Interpolated Data Is Easier Than You Thought.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 2000.
[GRSS97] S. Grumbach, P. Rigaux, M. Scholl, and L. Segoufin. “: A Spatial Constraint Database.” In Proc. Intl. Workshop on Database Programming Languages (DBPL), pages 38–59, 1997.
[GRS00] S. Grumbach, P. Rigaux, M. Scholl, and L. Segoufin. “The Prototype.” In [KLP00], 2000.
[GS87] R. H. Guting and W. Schilling. “A Practical Divide-and-Conquer Algorithm ¨ for the Rectangle Intersection Problem.” Information Sciences, 42:95–112, 1987.
[GS91] O. Gunther and H.-J. Schek, editors. ¨ Proc. Intl. Symposium on Design and Implementation af Large Spatial Databases (SSD). Vol. 525 of Lecture Notes in Computer Science, Zurich. Springer-Verlag, Berlin/Heidelberg/New York, 1991.
[GS93] R. H. Guting and M. Schneider. “Realms: A Foundation for Spatial Data ¨ Types in Database Systems.” In [AO93], 1993.
[GS95] R. H. Guting and M. Schneider. “Realm-Based Spatial Data Types: The ¨ ROSE Algebra.” The VLDB Journal, 4(2):243–286, 1995.
[GS97a] S. Grumbach and J. Su. “Finitely Representable Databases.” Journal of Computer and System Sciences, 55(2), 1997.
[GS97b] S. Grumbach and J. Su. “Queries with Arithmetical Constraints.” Theoretical Computer Science, 171(1), 1997.
[GST94] S. Grumbach, J. Su, and C. Tollu. “Linear Constraint Query Languages: Expressive Power and Complexity.” In Logic and Computational Complexity, 1994. LNCS 960.
[GTVV93] M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. “External-Memory Computational Geometry.” In Proc. IEEE Intl. Symp. on Foundations of Computer Sciences, pages 714–723, 1993.
[Gun88] O. G ¨ unther. ¨ Efficient Structures for Geometric Data Management. SpringerVerlag, Berlin/Heidelberg/New York, LNCS 337, 1988.
[Gun89] O. G ¨ unther. “The Design of the Cell Tree: An Object-Oriented Index Struc- ¨ ture for Geometric Databases.” In Proc. IEEE Intl. Conf. on Data Engineering, pages 598–605, 1989.
[Gun98] O. G ¨ unther. ¨ Environmental Information Systems. Springer-Verlag, Berlin/ Heidelberg/New York, 1998.
[Gut84] A. Guttman. “R-Trees: A Dynamic Index Structure for Spatial Searching.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 45–57,1984.
[Gut88] R. H. G ¨ uting. “Geo-relational Algebra: A Model and Query Language for ¨ Geometric Database Systems.” In Proc. Intl. Conf. on Extending Data Base Technology (EDBT), pages 506–527, 1988.
[Gut89] R. H. G ¨ uting. “Gral: An Extensible Relational Database System for Geomet- ¨ ric Applications.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1989.
[Gut94] R. H. G ¨ uting. “An Introduction to Spatial Database Systems.” ¨ The VLDB Journal, 3(4), 1994.
[GW87] O. Gunther and E. Wong. “A Dual Space Representation for Geometric ¨ Data.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1987.
[GY86] D. H. Greene and F. E. Yao. “Finite-Resolution Computational Geometry.” In IEEE Conf. on Foundations of Computer Science, pages 143–152, 1986.
[HE95] J. R. Herring and M. Egenhofer, editors. Proc. Intl. Symposium on Large Spatial Databases, (SSD). Vol. 951 of Lecture Notes in Computer Science, Portland, Maine. Springer-Verlag, Berlin/Heidelberg/New York, 1995.
[Her87] J. R Herring. “TIGRIS: Topologically InteGRated Information System.” In Proc. Intl. Symp. on Computer-Assisted Cartography (Auto-Carto 8), pages 282–291, 1987.
[HJR97a] Y.-W. Huang, N. Jing, and E. A. Rundensteiner. “A Cost Model for Estimating the Performance of Spatial Joins Using R-Trees.” In Proc. Intl. Conference on Scientific and Statistical Database Management (SSDBM), 1997.
[HJR97b] Y.-W. Huang, N. Jing, and E. A. Rundensteiner. “Spatial Joins Using R-Trees: Breadth-First Traversal with Global Optimizations.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1997
[HJR97c] Y.-W. Huang, M. C. Jones, and E. A. Rundensteiner. “Improving Spatial Intersect Joins Using Symbolic Intersect Detection.” In [SV97], 1997.
[HM83] S. Hertel and K. Mehlorn. “Fast Triangulation of Simple Polygons.” In Proc. Intl. Conf. on Foundations of Computer Theory, LNCS No. 158, pages 207–218. Springer-Verlag, Berlin/Heidelberg/New York, 1983.
[HP92] E. Horowitz and M. Papa. “Polygon Clipping: Analysis and Experiences.” In J. D. Ulmann, editor, Theoretical Studies in Computer Sciences. Academic Press, New York, 1992.
[HS92] E. G. Hoel and H. Samet. “A Qualitative Comparison Study of Data Structures for Large Line Segment Databases.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 205–214, 1992.
[HS93] Z. Huang and P. Svensson. “Neighborhood Query and Analysis with GeoSAL, a Spatial Database Language.” In [AO93], pages 413–436, 1993.
[HS98] G. R. Hjaltason and H. Samet. “Incremental Distance Join Algorithms for Spatial Databases.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1998.
[HT97] T. Hadzilacos and N. Tryfona. “An Extended Entity-Relationship Model for Geographic Applications.” SIGMOD Record (ACM Special Interest Group on Management of Data), 26(3), 1997.
[ISO00] ISO. URL: www.statkart.no/isotc211/, 2000.
[Jag90a] H. V. Jagadish. “On Indexing Line Segments.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), pages 614–625, 1990.
[Jag90b] H. V. Jagadish. “Spatial Search with Polyhedra.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), pages 311–319, 1990.
[Jea99] R. Jeansoulin. “Uncertainty Handling and Revision of the Geographic Information.” In Proc. of the 5th EC-GIS Workshop, 1999.
[JM95] R. Jeansoulin and C. Mathieu. “A Modal Logic for Spatial Hypothesis.” In Proc. Joint European Conference on GIS, 1995.
[Kei85] J. M. Keil. “Decomposing a Polygon into Simpler Components.” SIAM Journal of Computing, 14(4):799–817, 1985.
[KF93] I. Kamel and C. Faloutsos. “On Packing R-Trees.” In Proc. Intl. Conf. on Information and Knowledge Management (CIKM), 1993.
[KF94] I. Kamel and C. Faloutsos. “Hilbert R-Tree: An Improved R-Tree Using Fractals.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1994.
[KGT99] G. Kollios, D. Gunopulos, and V. J. Tsotras. “On Indexing Mobile Objects.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), 1999.
[KH95] K. Koperski and J. Han. “Discovery of Spatial Association Rules in Geographic Information Databases.” In [HE95], pages 47–66, 1995.
[Kin93] L. C. Kinsey. Topology of Surfaces. Springer-Verlag, Berlin/Heidelberg/New York, 1993.
[Kir95] P. Kirschenhofer. “The Mathematical Foundation of Graphs and Topology for GIS.” In [Fra95], 1995.
[KKR90] P. C. Kanellakis, G. Kuper, and P. Z. Revesz. “Constraint Query Languages.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), pages 299–313, 1990.
[KKR95] P. Kanellakis, G. Kuper, and P. Revesz. “Constraint Query Languages.” Journal of Computer and System Sciences, 51(1):26–52, 1995. A shorter version appeared in PODS’90.
[KKT92] D. G. Kirkpatrick, M. M. Klawe, and R. E. Tarjan. “Polygon Triangulation in O(n log log n) Time with Simple Data Structures.” Discrete and Computational Geometry, 7:329–346, 1992.
[KLP00] G. Kuper, L. Libkin, and J. Paradaens, editors. Constraint Databases. SpringerVerlag, Berlin/Heidelberg/New York, 2000.
[KN96] E. Knorr and R. Ng. “Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining.” in IEEE Transactions on Knowledge and Data Engineering (TKDE), 8:884–896, 1996.
[Knu73] D. E. Knuth. The Art of Computer Programming, vol. 1. Addison-Wesley, Reading, MA, 1973.
[Kou97] M. Koubarakis. “The Complexity of Query Evaluation in Indefinite Temporal Constraint Databases.” Theoretical Computer Science, 171(1/2), 1997.
[KPJE95] M. Kavouras, D. Paradissis, J. Jansa, and R. Ecker. “Data Sources for GIS.” In [Fra95], 1995.
[KPV95] B. Kuijpers, J. Paredaens, and J. Van den Bussche. “Lossless Representation of Topological Spatial Data.” In [HE95], pages 1–13, 1995.
[KPV97] B. Kuijpers, J. Paradaens, and J. Van den Bussche. “On Topological Elementary Equivalence of Spatial Databases.” In Proc. Intl. Conf. on Database Theory (ICDT), pages 432–446, 1997.
[KRSS98] G. Kuper, S. Ramaswamy, K. Shim, and J. Su. “A Constraint-Based Spatial Extension to SQL.” In Proc. ACM Intl. Symp. on Geographic Information Systems (ACM-GIS), 1998.
[KRVV96] P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff, and J. S. Vitter. “Indexing for Data Models with Constraints and Classes.” Journal of Computer and System Sciences, 52(3), 1996.
[KS91] C. P. Kolovson and M. Stonebraker. “Segment Indexes: Dynamic Indexing Techniques for Multi-dimensional Interval Data.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 138–147, 1991.
[KS97] N. Koudas and K. C. Sevcik. “Size Separation Spatial Join.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1997.
[KV99] B. Kuijpers and J. Van den Bussche. “On Capturing First-Order Topological Properties of Planar Spatial Databases.” In Proc. Intl. Conf. on Database Theory (ICDT), pages 187–198, 1999.
[Lan92] G. Langran. Time in Geographic Infomation Systems. Taylor and Francis, London, 1992.
[Lau98] R. Laurini. “Spatial Multidatabase Topological Continuity and Indexing: A Step Towards Seamless GIS Data Interoperability.” International Journal of GIS, 12(4), 1998.
[Lau00] R. Laurini. Information Systems for Urban Planning: A Hypermedia Cooperative Approach. Taylor and Francis, London, 2000.
[LB83] Y-D Liang and B. A. Barsky. “An Analysis and Algorithm for Polygon Clipping.” Communications of the ACM, 26(11):868–877, 1983.
[LEL96] S. Leutenegger, J. Edgington, and M. Lopez. “STR: A Simple and Efficient Algorithm for R-Tree Packing.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), 1996.
[LG98] P.-A. Larson and G. Graefe. “Memory Management During Run Generation in External Sorting.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 472–483, 1998.
[LP86] G. E. Langran and T. K. Poiker. “Integration of Name Selection and Name Placement.” In Proc. Intl. Symp. on Spatial Data Handling (SDH), pages 50– 64, 1986.
[LPL97] F. Lecordix, C. Plazanet, and J.-P. Lagrange. “A Platform for Research in Generalization: Application to Caricature.” GeoInformatica, 1(2), 1997.
[LPV93] T. Larue, D. Pastre, and Y. Viemont. “Strong Integration of Spatial Domains ´ and Operators in a Relational Database System.” In [AO93], pages 53–72,1993.
[LR95] M.-L. Lo and C. V. Ravishankar. “Generating Seeded-Trees from Data Sets.”In [HE95], 1995.
[LR96] M.-L. Lo and C. V. Ravishankar. “Spatial Hash-Joins.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 247–258, 1996.
[LR98] M.-L. Lo and C. V. Ravishankar. “The Design and Implementation of Seeded Trees: An Efficient Method for Spatial Joins.” IEEE Transactions on Knowledge and Data Engineering (TKDE), 10(1), 1998. First published in SIGMOD’94.
[LS90] D. B. Lomet and B. Salzberg. “The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.” ACM Transactions on Database Systems, 15(4):625–658, 1990.
[LT92] R. Laurini and D. Thompson. Fundamentals of Spatial Information Systems. No. 37 in the A.P.I.C. series. Academic Press, New York, 1992.
[Mai95] M. Mainguenaud. “Modeling the Network Component of a Geographical Information System.” International Journal of Geographical Information Systems, 9(6), 1995.
[McC85] E. McCreight. “Priority Search Trees.” SIAM Journal of Computing, 14:257–276, 1985.
[MGR99] D. Maguire, M. Goodchild, and D. Rhind. Geographic Information Systems. 2d ed., 2 vols. Longman Scientific and Technical, London, 1999.
[MK89] A. Margalit and G. D. Knott. “An Algorithm for Computing the Union, Intersection, or Difference of Two Polygons.” Computers and Graphics, 13(2):167–183, 1989.
[MKB94] M. Molenaar, O. Kufoniyi, and T. Bouloucos. “Modeling Topologic Relationships in Vector Maps.” In Proc. Intl. Symp. on Spatial Data Handling (SDH),1994.
[MLW95] J.-C. Muller, J.-P. Lagrange, and R. Weibel, editors. GISs and Generalization: Methodological and Practical Issues. Taylor and Francis, London, 1995.
[MO86] F. Manola and J. Orenstein. “Toward a General Spatial Data Model for an Object-Oriented DBMS.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1986.
[Mol95] M. Molenaar. “Spatial Concepts as Implemented in GIS.” In [Fra95], 1995.
[Mom00] B. Momjian. PostgreSQL, Introduction and Concepts. Addison-Wesley, Reading, MA, 2000. See http://postgresql.org.
[Mor85] S. Morehouse. “ArcInfo: A Geo-Relational Model for Spatial Information.” In Proc. Intl. Symp. on Computer-Assisted Cartography (Auto-Carto 7), pages 388–397, 1985.
[Mor89] S. Morehouse. “The Architecture of ARC/INFO.” In Proc. Intl. Symp. on Computer-Assisted Cartography (Auto-Carto 9), pages 266–277, 1989.
[MP78] D. E. Muller and F. P. Preparata. “Finding the Intersection of Two Convex Polyhedra.” Theoretical Computer Science, 7(2):217–236, 1978.
[MP90] M. Mainguenaud and M. A. Portier. “CIGALES: A Graphical Query Language for Geographical Information Systems.” In Proc. Intl. Symp. on Spatial Data Handling (SDH), 1990.
[MP94] C. Bauzer Medeiros and F. Pires. “Databases for GIS.” SIGMOD Record (ACM Special Interest Group on Management of Data), 23(1):107–115, 1994.
[MP99] N. Mamoulis and D. Papadias. “Integration of Spatial Join Algorithms for Joining Multiple Inputs.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1999.
[MPS+00] I. Mirbel, B. Pernici, T. K. Sellis, S. Tserkezoglou, and M. Vazirgiannis. “Checking the Temporal Integrity of Interactive Multimedia Documents.” VLDB Journal, 9(2):111–130, 2000.
[MS88] H. G. Mairson and J. Stolfi. “Reporting and Counting Intersections Between Two Sets of Line Segments.” Theoretical Foundations of Computer Graphics and CAD, F40. NATO ASI Series. Springer-Verlag, Berlin/Heidelberg/New York, 1988.
[MTT99] Y. Manolopoulos, Y. Theodoridis, and V. Tsotras. Advanced Database Indexing. Kluwer, Academic Publishers, New York, 1999.
[Mul94] K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
[NCG00] NCGIA URL. www.ncgia.org, 2000.
[NH94] R. Ng and J. Han. “Efficient and Effective Clustering Methods for Spatial Data Mining.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), pages 144–155, 1994.
[NHS84] J. Nievergelt, H. Hinterger, and K. C. Sevcik. “The Grid File: An Adaptable Symmetric Multikey File Structure.” ACM Trans. on Database Systems, 9(1):38–71, 1984.
[NP82] J. Nievergelt and F. P. Preparata. “Plane-Sweep Algorithms for Intersecting Geometric Figures.” Communications of the ACM, 25(10):739–747, 1982.
[NST99] M. A. Nascimento, J. R. O. Silva, and Y. Theodoridis. “Evaluation of Access Structures for Discretely Moving Points.” In Intl. Workshop on Spatio-Temporal Database Management (STDBM), LNCS 1678, 1999.
[Num95] J. Numes. “General Concepts of Space and Time.” In [Fra95], 1995.
[NW97] J. Nievergelt and P. Widmayer. “Spatial Data Structures: Concepts and Design Choices.” In [vKNRW97], pages 153 and 198, 1997.
[OCON82] J. O’Rourke, C.-B. Chien, T. Olson, and D. Naddor. “A New Linear Algorithm for Intersecting Convex Polygons.” Computer Graphics and Image Processing, 19:384–391, 1982.
[OGD00] OGDI. URL: www.ogdi.org/faq/faq-web.asp, 2000.
[OGI00] OGIS. URL: www.ogis.com, 2000.
[OM84] J. Orenstein and T. H. Merrett. “A Class of Data Structures for Associative Searching.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), pages 181–190, 1984.
[OM88] J. Orenstein and F. Manola. “PROBE: Spatial Data Modeling and Query Processing
in an Image Database Application.” IEEE Transactions on Software Engineering, 14(5):611–628, 1988.
[O’N94] P. E. O’Neil. Database: Principles, Programming, Performance. Morgan Kaufmann,
San Francisco, 1994.
[Ooi90] B. C. Ooi. Efficient Query Processing in a Geographic Information System. LNCS No. 471. Springer-Verlag, Berlin/Heidelberg/New York, 1990.
[O’R94] J. O’Rourke. Computational Geometry in C. Cambridge University Press, New York, 1994.
[Ora00] Oracle. URL:
oradoc.photo.net/ora81/doc/inter.815/a67295/toc.htm, 2000.
Oracle8i Spatial User’s Guide and Reference, Release 8.1.5.
[Ore86] J. A. Orenstein. “Spatial Query Processing in an Object-Oriented Database System.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 326–336, 1986.
[Ore89] J. A. Orenstein. “Redundancy in Spatial Databases.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1989.
[Ore90] J. A. Orenstein. “A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1990.
[OSDD89] B. C. Ooi, R. Sack-Davis, and K. J. McDonell. “Extending a DBMS for Geographic Applications.” In Proc. Intl. Conf. on Data Engineering, pages 590–597, 1989.
[OW86] T. Ottmann and D. Wood. “Space-Economical Plane Sweep Algorithms.” Comp. Vision Graphics and Image Processing, 34, 1986.
[P86] C. H. Papadimitriou. The Theory of Database Concurrency Control. Computer Science Press, Rockville, MD, 1986.
[PBR98] C. Plazanet, N.-M. Bigolin, and A. Ruas. “Experiments with Learning Techniques for Spatial Model Enrichment and Line Generalization.” GeoInformatica, 2(4), 1998.
[PD96] J. M. Patel and D. J. DeWitt. “Partition Based Spatial-Merge Join.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 259–270, 1996.
[PE97] D. Papadias and M. Egenhofer. “Hierarchical Spatial Reasoning About Direction Relations.” GeoInformatica, 1(3), 1997.
[Peu84] D. J. Peuquet. “A Conceptual Framework and Comparison of Spatial Data Models.” Cartographica, 21(4):66–113, 1984.
[PJT00] D. Pfoser, C. S. Jensen, and Y. Theodoridis. “Novel Approaches in Query Processing for Moving Objects.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 2000.
[Ple97] B. Plewe. GIS On-Line: Information Retrieval, Mapping, and the Internet. OnWord Press, (Delmar, Publishers, Albany NY), 1997.
[PM97] A. Papadopoulos and Y. Manolopoulos. “Performance of Nearest Neighbor Queries in R-Trees.” In Proc. Intl. Conf. on Database Theory (ICDT), 1997.
[PMT99] D. Papadias, N. Mamoulis, and Y. Theodoridis. “Processing and Optimization of Multi-Way Spatial Joins Using R-Trees.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), 1999.
[Pre79] F. P. Preparata. “An Optimal Real-Time Algorithm for Planar Convex Hulls.” Communications of the ACM, 22:402–405, 1979.
[PRS99] A. Papadopoulos, P. Rigaux, and M. Scholl. “A Performance Evaluation of Spatial Join Processing Strategies.” In [GPL99], 1999.
[PS85] F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.
[PS94] D. Papadias and T. K. Sellis. “Qualitative Representation of Spatial Knowledge in Two-Dimensional Space.” VLDB Journal, 3(4), 1994.
[PS95] D. Papadias and T. K. Sellis. “A Pictorial Query-by-Example Language.” Journal of Visual Languages and Computing, 6(1):53–72, 1995.
[PSTW93] B. Pagel, H. Six, H. Toben, and P. Widmayer. “Toward an Analysis of Range Query Performance.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), pages 214–221, 1993.
[PSV99] C. H Papadimitriou, D. Suciu, and V. Vianu. “Topological Queries in Spatial Databases.” Journal of Computer and System Sciences, 58(1):29–53, 1999.
[PTSE95] D. Papadias, Y. Theodoridis, T. K. Sellis, and M. Egenhofer. “Topological Relations in the World of Minimum Bounding Rectangles: A Study with RTrees.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 92–103, 1995.
[PVV94] J. Paredaens, J. Van den Bussche, and D. Van Gucht. “Toward a Theory of Spatial Database Queries.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), pages 279–288, 1994.
[PYK+97] J. M. Patel, J. Yu, N. Kabra, K. Tufte, B. Nag, J. Burger, N. E. Hall, K. Ramasamy,
R. Lueder, C. Ellman, J. Kupsch, S. Guo, D. J. DeWitt, and J. F. Naughton. “Building a Scalable Geo-spatial DBMS: Technology, Implementation, and Evaluation.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 336–347, 1997.
[Qua98] T. Quatrani. Visual Modeling with Rational Rose and UML. Addison-Wesley, Reading, MA, 1998.
[Ram97] R. Ramakrishnan. Database Management Systems. McGraw-Hill, New York, 1997.
[Ram00] S. Ramaswamy. “Theory and Practice of I/O-Efficient Algorithms for Constraint Databases.” In [KLP00], 2000.
[RBP+91] J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorensen. ObjectOriented Modeling and Design. Prentice Hall, Englewood Cliffs, NJ, 1991.
[RKV95] N. Roussopoulos, S. Kelley, and F. Vincent. “Nearest Neighbor Queries.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 1995.
[RL85] N. Roussopoulos and D. Leifker. “Direct Spatial Search on Pictorial Databases Using Packed R-Trees.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 17–26, 1985.
[Rob81] J. T. Robinson. “The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 10–18, 1981.
[Rot91] D. Rotem. “Spatial Join Indices.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), 1991.
[RS95] P. Rigaux and M. Scholl. “Multi-scale Partitions: Application to Spatial and Statistical Databases.” In [HE95], pages 170–183, 1995.
[RSHN97] L. Relly, H.-J. Schek, O. Henricsson, and S. Nebiker. “Physical Database Design for Raster Images in Concert.” In [SV97], 1997.
[Rua98] A. Ruas. “A Method for Building Displacement in Automated Map Generalization.” International Journal of Geographical Information Science, 12(8), 1998.
[Sam90a] H. Samet. Applications of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.
[Sam90b] H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.
[Sch97a] S. Schirra. “Precision and Robustness in Geometric Computations.” In [vKNRW97], pages 255 and 287, 1997.
[Sch97b] M. Schneider. Spatial Data Types for Database Systems: Finite Resolution Geometry for Geographic Information Systems. Vol. 1288 of Lecture Notes in Computer Science. Springer-Verlag, New York, 1997.
[SDMO87] R. Sack-Davis, K. J. McDonell, and B. C. Ooi. “GEOQL: A Query Language for Geographic Information Systems.” In Australian and New Zealand Association for the Advancement of Science Congress, 1987.
[SE89] J. Star and J. Estes. Geographic Information Systems: An Introduction. Prentice Hall, Englewood Cliffs, NJ, 1989.
[Sed83] R. Sedgewick. Algorithms. Addison-Wesley, Reading, MA, 1983.
[Sei91] R. Seidel. “A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons.” Computational Geometry, 1(1), 1991.
[SEM98] A. R. Shariff, M. Egenhofer, and D. Mark. “Natural-Language Spatial Relations Between Linear and Areal Objects: The Topology and Metric of EnglishLanguage Terms.” Intl. Journal of Geographical Information Science, 12(3),1998.
[SGR96] M. Scholl, G. Grangeret, and X. Rehs ´ e. Point and Window Queries with ´ Linear Spatial Indices: An Evaluation with O2.” Technical Report CS/TR-007, Cedric/CNAM, 1996. Available at ftp://sikkim.cnam.fr/reports/.
[SH74] I. E. Sutherland and G. W. Hogdman. “Reentrant Polygon Clipping.” Communications of the ACM, 17(1):33–42, 1974.
[SH76] M. I. Shamos and D. Hoey. “Geometric Intersection Problems.” In IEEE Conf. on Foundations of Computer Science, 1976.
[Sha99] J. Sharma. “Oracle8i Spatial: Experiences with Extensible Databases.” An Oracle technical white paper, Oracle Corp., Redwood City, CA, May 1999.
[SJLL00] S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. “Indexing the Positions of Continuously Moving Objects.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, 2000.
[SKS98] A. Silberschatz, H. F. Korth, and S. Sudarshan. Database System Concepts. McGraw-Hill, New York, 1998.
[SL95] S. Servigne and R. Laurini. “Updating Geographic Databases Using MultiSource Information.” In Proc. ACM Intl. Symp. on Geographic Information Systems (ACM-GIS), 1995.
[SM99] J.-M. Saglio and J. Moreira. “Oporto: A Realistic Scenario Generator for Moving Objects.” In Proc. Intl. Conf. on Databases and Expert Applications (DEXA), pages 426–432, 1999. Extended version to appear in GeoInformatica.
[SML94] SmallWorld, Ltd. SmallWorld GIS 2, London, 1994.
[SML00] SmallWorld, Ltd. URL: www.smallworld-systems.co.uk/, 2000. Small World presentation.
[SPV00] S. Spaccapietra, C. Parent, and C. Vangenot. “GIS Databases: From Multiscale to Multirepresentation.” In Intl. Symp. on Abstraction, Reformulation, and Approximation (SARA), 2000.
[SR86] M. Stonebraker and L. A. Rowe. “The Design of Postgres.” In Proc. ACM SIGMOD Intl. Symp. on the Management of Data, pages 340–355, 1986.
[SRF87] T. Sellis, N. Roussopoulos, and C. Faloutsos. “The R+Tree: A Dynamic Index for Multi-dimensional Objects.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), pages 507–518, 1987.
[SRG83] M. Stonebraker, B. Rubenstein, and A. Guttman. “Application of Abstract Data Types and Abstract Indices to CAD Data Bases.” In Proc. ACM/IEEE Conf. on Engineering Design Applications, pages 107–113, 1983.
[SRH90] M. Stonebraker, L. Rowe, and M. Hirohama. “The Implementation of Postgres.” IEEE Transactions on Knowledge and Data Engineering (TKDE), 2(1):125–142, 1990.
[Sto86] M. Stonebraker. “Inclusion of New Types in Relational Data Base Systems.” In Proc. Intl. Conf. on Data Engineering, pages 262–269, 1986.
[SU00] J.-R. Sack and J. Urrutia, editors. Handbook of Computational Geometry. Elsevier Science, Amsterdam, 2000.
[SUPL00] S. Servigne, T. Ubeda, A. Puricelli, and R. Laurini. “A Methodology for Spatial Consistency Improvement of Geographic Databases.” GeoInformatica, 4(1):7–34, 2000.
[SV89] M. Scholl and A. Voisard. “Thematic Map Modeling.” In [BGSW89], pages 167–192. Springer-Verlag, Berlin/Heidelberg/New York, 1989.
[SV92] M. Scholl and A. Voisard. “Object-Oriented Database Systems for Geographic Applications: An Experiment with O2.” Chapter 28 of [BDK92].
[SV97] M. Scholl and A. Voisard, editors. Proc. Intl. Symposium on Large Spatial Databases (SSD). Vol. 1262 of Lecture Notes in Computer Science, Berlin. Springer-Verlag, Berlin/Heidelberg/New York, 1997.
[SV98] L. Segoufin and V. Vianu. “Querying Spatial Databases via Topological Invariants.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), 1998.
[SVP+96] M. Scholl, A. Voisard, J.-P. Peloux, L. Raynal, and P. Rigaux. SGBD G´eographiques. International Thomson Publishing, Paris, 1996.
[SW88] H. Six and P. Widmayer. “Spatial Searching in Geometric Databases.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), pages 496–503, 1988.
[SWCD97] A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. “Modeling and Querying Moving Objects.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), pages 422–432, 1997.
[TC200] The CEN TC287 Standard. URL:
forum.afnor.fr/afnor/work/afnor/gpn2/z13c/public/web/english/pren.htm, 2000.
[TIG00] TIGER. URL: www.census.gov/geo/www/tiger/, 2000.
[Til80] R. B. Tilove. “Set Membership Classification: A Unified Approach to Geometric Intersection Problems.” IEEE Transactions on Computers, C-29(10), 1980.
[TJ99] N. Tryfona and C. S. Jensen. “Conceptual Modeling for Spatiotemporal Applications.” GeoInformatica, 3(3):245–268, 1999.
[Tom90] C. D. Tomlin. Geographic Information Systems and Cartographic Modeling. Prentice Hall, Englewood Cliffs, NJ, 1990.
[TS96] Y. Theodoridis and T. K. Sellis. “A Model for the Prediction of R-Tree Performance.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS),1996.
[TSN99] Y. Theodoridis, J.R.O. Silva, and M. A. Nascimento. “On the Generation of Spatiotemporal Datasets.” In [GPL99], 1999.
[TSPM98] Y. Theodoridis, T. Sellis, A. N. Papadopoulos, and Y. Manolopoulos. “Specifications for Efficient Indexing in Spatiotemporal Databases.” In Proc. Intl. Conference on Scientific and Statistical Database Management (SSDBM), 1998.
[TSS98] Y. Theodoridis, E. Stefanakis, and T. K. Sellis. “Cost Models for Join Queries in Spatial Databases.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), 1998.
[TUW98] J. Tayeb, O. Ulusoy, and O. Wolfson. “A Quadtree Based Dynamic Attribute Indexing Method.” Computer Journal, 41:185–200, 1998.
[TvW88] R. E. Tarjan and C. J. van Wyk. “An O(n log log n) Time Algorithm for Triangulating a Simple Polygon.” SIAM Journal of Computing, 17(1):143–178, 1988.
[Ull88] J. D. Ullman. Principles of Database and Knowledge-Base Systems, Vol. 1. Computer Science Press, New York, 1988.
[Ull89] J. D. Ullman. Principles of Database and Knowledge-Base Systems, Vol. 2. Computer Science Press, New York, 1989.
[Val87] P. Valduriez. “Join Indices.” ACM Trans. on Database Systems, 12(2):218–246, 1987.
[Vck99] A. Vckovski, editor. Proc. Intl. Workshop on Interoperating Geographic Information Systems (INTEROP). Vol. 1580 of Lecture Notes in Computer Science, Springer-Verlag, Berlin/Heidelberg/New York, 1999.
[VD01] A. Voisard and B. David. “A Database Perspective on Geospatial Data Modeling.” IEEE Transactions on Knowledge and Data Engineering, 2001. To appear.
[VGV95] L. Vandeurzen, M. Gyssens, and D. Van Gucht. “On the Desirability and Limitations of Linear Spatial Database Models.” In [HE95], pages 14–28, 1995.
[VGV96] L. Vandeurzen, M. Gyssens, and D. Van Gucht. “On Query Languages for Linear Queries Definable with Polynomial Constraints.” In Proc. Intl. Conf. on Principles and Practice of Constraint Programming, LNCS 1118, pages 468–481, 1996.
[Vit84] J. S. Vitter. “Faster Methods for Random Sampling.” Communications of the ACM, 27(7), 1984.
[Vit98] J. S. Vitter. “External Memory Algorithms.” In Proc. ACM Intl. Symp. on Principles of Database Systems (PODS), 1998.
[vK97] M. van Kreveld. “Digital Elevation Models and TIN Algorithms.” In [vKNRW97], pages 37–78, 1997.
[vKNRW97] M. van Kreveld, J. Nievergelt, T. Roos, and P. Wiedmayer, editors. Algorithmic Foundations of Geographic Information Systems. No. 1340 in LNCS. SpringerVerlag, Berlin/Heidelberg/New York, 1997.
[Vko98] A. Vckovski, editor. Intl. Journal of Geographic Information Science, Vol. 12. Taylor and Francis, London, 1998. Special issue on interoperability in GIS.
[vOV91] P. van Oosterom and T. Vijlbrief. “Building a GIS on Top of the Open DBMS Postgres.” In Proc. Eur. Conf. on Geographic Information Systems (EGIS), pages 775–787, 1991.
[vOvdB89] P. van Oosterom and J. van den Bos. “An Object-Oriented Approach to the Design of Geographic Information Systems.” In [BGSW89], pages 255–270,1989.
[VTS98] M. Vazirgiannis, Y. Theodoridis, and T. K. Sellis. “Spatio-temporal Composition and Indexing for Large Multimedia Applications.” In ACM Springer Multimedia Systems, 6(4):284–293, 1998.
[Wei85] K. Weiler. “Edge-Based Data Structures for Solid Modeling in Curved-Surface Environments.” IEEE Computer Graphics and Applications, 5(1):21–40, 1985.
[WHM90] M. Worboys, H. Hearnshaw, and D. Maguire. “Object-Oriented Data and Query Modelling for Geographical Information Systems.” In Proc. Intl. Symp. on Spatial Data Handling (SDH), 1990.
[WJ98] R. Weibel and C. B. Jones. “Computational Perspectives on Map Generalization.” GeoInformatica, 2(4):307–314, 1998.
[Wor94] M. F. Worboys. “A Unified Model of Spatial and Temporal Information.” Computer Journal, 37(1), 1994.
[Wor95] M. Worboys. GIS: A Computing Perspective. Taylor and Francis, London, 1995.
[WXCJ98] O. Wolfson, B. Xu, S. Chamberlain, and L. Jiang. “Moving Object Databases: Issues and Solutions.” In Proc. Intl. Conference on Scientific and Statistical Database Management (SSDBM), 1998.
[XEKS98] X. Xu, M. Ester, H.-P. Kriegel, and J. Sander. “A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases.” In Proc. IEEE Intl. Conf. on Data Engineering (ICDE), pages 324–331, 1998.
[YdC95] T. S. Yeh and B. de Cambray. “Time as a Geometric Dimension for Modeling the Evolution of Entities: A 3D Approach.” In Proc. Intl. Conf. on Integrating Geographical Information Systems and Environmental Modeling, 1995.
[YM98] C. T. Yu and W. Meng. Principles of Database Query Processing for Advanced Applications. Morgan Kaufmann, San Francisco, 1998.
[ZC95] K. Zeitouni and B. de Cambray. “Topological Modeling for 3D GIS.” In Intl. Conf. on Computers in Urban Planning and Urban Management, 1995.
[ZS98] G. Zimbrao and J. M. Souza. “A Raster Approximation for the Processing of Spatial Joins.” In Proc. Intl. Conf. on Very Large Data Bases (VLDB), 1998.
[ZSI00] H. Zhu, J. Su, and O. H. Ibarra. “Toward Spatial Joins for Polygons.” In Proc. Intl. Conference on Scientific and Statistical Database Management (SSDBM), 2000.
[Zub88] R. B. Zubiaga. “On the Intersection of Two Planar Polygons.” Computers and Graphics, 12:401–403, 1988.
Full Text
Buy
ليست هناك تعليقات:
إرسال تعليق