Spatial Database Systems
The Geojournal libraryPublished 1 January 2007
Citations74
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The decision to write this book was motivated by a number of factors. First, although several useful textbooks on spatial databases have recently been published, this is an area of spatial information
Keywords
Computer ScienceSocial Sciences
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
Communications of the ACMMultidimensional binary search trees used for associative searching
7,467 Citations1975Jon Bentley
The multidimensional binary search tree (or k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements.
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
The R*-tree: an efficient and robust access method for points and rectangles
4,176 Citations1990Norbert Beckmann, Hans‐Peter Kriegel +2 more
The R*-tree is designed which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory which clearly outperforms the existing R-tree variants.
ACM Computing SurveysMultidimensional access methods
1,591 Citations1998Volker Gaede, Oliver Günther
The class of point access methods, which are used to search sets of points in two or more dimensions, are presented and a discussion of theoretical and experimental results concerning the relative performance of various approaches are discussed.
Nearest neighbor queries
1,408 Citations1995Nick Roussopoulos, Stephen Kelley +1 more
This paper presents an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalizes it to finding the k nearest neighbors.
Very Large Data BasesThe R+-Tree: A Dynamic Index for Multi-Dimensional Objects
1,263 Citations2018Timos Sellis, Nick Roussopoulos +1 more
A variation to Guttman’s Rtrees (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced and analytical results indicate that R+-Trees achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles.
ACM Transactions on Database SystemsThe Grid File
1,149 Citations1984J. Nievergelt, Hans Hinterberger +1 more
This work discusses in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
Communications of the ACMA product perspective on total data quality management
898 Citations1998Richard Y. Wang
The purpose of this TDQM methodology is to deliver highquality information products (IP) to information consumers and aims to facilitate the implementation of an organization’s overall data quality policy formally expressed by top management.
The VLDB JournalAn introduction to spatial database systems
717 Citations1994Ralf Hartmut G�ting
This work surveys data modeling, querying, data structures and algorithms, and system architecture for spatial database systems, with the emphasis on describing known technology in a coherent manner, rather than listing open problems.
Lecture notes in computer scienceReasoning about binary topological relations
625 Citations1991Max J. Egenhofer
A new formalism is presented to reason about topological relations based upon the nine intersections of boundaries, interiors, and complements between two objects that is applicable as a foundation for an algebra over topological Relations.
Modeling and querying moving objects
610 Citations2002A. Prasad Sistla, Ouri Wolfson +2 more
This work proposes a data model for representing moving objects in database systems called the Moving Objects Spatio-Temporal (MOST) data model, and devise an algorithm for processing FTL queries in MOST.
Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases
588 Citations1998Max J. Egenhofer
Efficient processing of spatial joins using R-trees
575 Citations1993Thomas Brinkhoff, Hans‐Peter Kriegel +1 more
This paper presents a first detailed study of spatial join processing using R-trees, particularly R*-tree, and presents several techniques for improving its execution time with respect to both, CPU- and I/O-time.
Lecture notes in computer scienceA small set of formal topological relationships suitable for end-user interaction
503 Citations1993Eliseo Clementini, Paolino Di Felice +1 more
The first method is an extension of the geometric point-set approach by taking the dimension of the intersections into account, which results in a very large number of different topological relationships for point, line, and area features.
Minds at UW (University of Wisconsin)Generalized Search Trees for Database Systems
467 Citations1995Joseph M. Hellerstein, Jeffrey F. Naughton +1 more
The Generalized Search Tree is introduced, an index structure supporting an extensible set of queries and data types and providing all the basic search tree logic required by a database system, thereby unifying disparate structures such as B+-tree and R-trees in a single piece of code and opening the application of search trees to general extensibility.
ACM SIGMOD RecordSpatial query processing in an object-oriented database system
398 Citations1986Jack Orenstein
IEEE Transactions on Knowledge and Data EngineeringSpatial SQL: a query and presentation language
376 Citations1994Max J. Egenhofer
The spatial query language has been designed as a minimal extension to the interrogative part of SQL and distinguishes from previously designed SQL extensions by: the preservation of SQL concepts; the high-level treatment of spatial objects; and the incorporation of spatial operations and relationships.
The Computer JournalA Unified Model for Spatial and Temporal Information
356 Citations1994Mike Worboys
A unified generic model for information which is referenced to two spatial dimensions and two temporal dimensions (database and event times) is discussed.
Lecture notes in computer scienceRanking in spatial databases
355 Citations1995Gı́sli R. Hjaltason, Hanan Samet
An algorithm for ranking spatial objects according to increasing distance from a query object is introduced and analyzed, which is well suited for k nearest neighbor queries, and has the property that k needs not be fixed in advance.
Partition based spatial-merge join
345 Citations1996Jignesh M. Patel, David J. DeWitt
PBSM (Partition Based Spatial-Merge), a new algorithm for performing spatial join operation that is especially effective when neither of the inputs to the join have an index on the joining attribute, is described.
Lecture notes in computer scienceA formal definition of binary topological relationships
337 Citations1989Max J. Egenhofer
A formal definition of spatial relationships is necessary to clarify the users' diverse understanding of spatial relationship and to actually deduce relationships among spatial objects.
IEEE Transactions on Software EngineeringPROBE spatial data modeling and query processing in an image database application
273 Citations1988Jack Orenstein, Frank Manola
An overview of PROBE is provided, focusing on the facilities for dealing with spatial and temporal data, and how thePROBE database system and simple application-specific object classes combine to efficiently support PROBe's spatial data model.
Topological relations in the world of minimum bounding rectangles
253 Citations1995Dimitris Papadias, Timos Sellis +2 more
The topological information that Minimum Bounding Rectangle-based data structures convey about the actual objects they enclose is studied, using the concept of projections, and the results are applied to R-trees and their variations, R+-t trees and R*-tree in order to minimise disk accesses for queries involving topological relations.
Incremental distance join algorithms for spatial databases
242 Citations1998Gı́sli R. Hjaltason, Hanan Samet
Two new spatial join operations, distance join and distance semi-join, are introduced where the join output is ordered by the distance between the spatial attribute values of the joined tuples.
International Journal of Geographical Information SystemsResearch Paper
241 Citations1994Max J. Egenhofer, Eliseo Clementini +1 more
It is shown how the 4-intersection model is suitable for a multi-level treatment of topological relations, at the least detailed level of which the relation between the generalized regions prevails.
Multi-step processing of spatial joins
226 Citations1994Thomas Brinkhoff, Hans‐Peter Kriegel +2 more
This paper presents a complete approach of spatial join processing on complex spatial objects that is based on three steps and reduces the total execution time of the spatial join by factors.
Effective Project Management
221 Citations2019Robert K. Wysocki
The VLDB JournalRealm-based spatial data types: The ROSE algebra
209 Citations1995Ralf Hartmut Güting, Markus Schneider
The ROSE algebra is described within a polymorphic type system and interacts with a DMBS data model and query language through an abstractobject model interface and an example integration of ROSE into the object-oriented data model O2 and its query language is presented.
Spatial hash-joins
207 Citations1996Ming-Ling Lo, Chinya V. Ravishankar
This work examines how to apply the hash-join paradigm to spatial joins, and defines a new framework for spatial hash-joins, which outperforms current spatial join algorithms based on tree matching by a wide margin.
Very Large Data BasesThe LSD tree: spatial access to multidimensional and non-point objects
203 Citations1989Andreas Henrich, H.-W. Six +1 more
The paging algorithm for the binary tree directory is interesting in its own right because a practical solution for the problem of how to page a (multidimensional)b inary tree without access to degeneration is presented.
Supporting fine-grained data lineage in a database visualization environment
200 Citations2002Allison Woodruff, Michael Stonebraker
This paper proposes a novel method to support fine-grained data lineage that lazily computes the lineage using a limited amount of information about the processing operators and the base data, and introduces the notions of weak inversion and verification.
Research Portal (King's College London)Scalable Sweeping-Based Spatial Join
180 Citations1998Lars Arge, Octavian Procopiuc +3 more
This paper considers the filter step of the spatial join problem, for the case where neither of the inputs are indexed, and presents a new algorithm, Scalable Sweeping-Based Spatial Join (SSSJ), that achieves both efficiency on real-life data and robustness against highly skewed and worst-case data sets.
Lecture notes in computer scienceGeo-relational algebra: A model and query language for geometric database systems
172 Citations1988Ralf Hartmut Güting
The user's conceptual model of a database system for geometric data should be simple and precise, easy to learn and understand, with clearly defined semantics, and efficiently implementable.
Finite-resolution computational geometry
163 Citations1986Daniel Greene, F. Frances Yao
This paper forms criteria for a satisfactory solution to the discrete version of the problem of finding all intersections of a collection of line segments, and designs an interface between the continuous domain and the discrete domain which supports certain invariants.
Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations
162 Citations1997Yun-Wu Huang, Ning Jing +1 more
The experimental results indicate that BFRJ with global optimizations can outperform the competitor by a significant margin (up to 50%) and this work was supported in part by the University of Michigan ITS Research Center of Excellence grant.
Spatial joins using seeded trees
159 Citations1994Ming-Ling Lo, Chinya V. Ravishankar
This paper develops a technique that uses intermediate linked lists during tree construction and significantly speeds up the tree construction process and the CPU penalties incurred are also lower except when seed-level filtering is used.
Fast nearest neighbor search in high-dimensional space
156 Citations2002Stefan Berchtold, Bernhard Ertl +3 more
This work precomputes the result of any nearest neighbor search which corresponds to a computation of the voronoi cell of each data point, which is based on a precomputation of the solution space and demonstrates the high efficiency for uniformly distributed as well as real data.
Analysis of object oriented spatial access methods
153 Citations1987Christos Faloutsos, Timos Sellis +1 more
It is shown how the transformation of objects to higher dimensions [HINR83] can be effectively used as a tool for the analysis of R- and R+- trees and derive formulas for R-trees and compare the two methods analytically.
Lecture notes in computer scienceA topological data model for spatial databases
150 Citations1990Max J. Egenhofer, Andrew U. Frank +1 more
A spatial data model is proposed which is based upon the mathematical theory of simplices and simplicial complexes from combinatorial topology and introduces completeness of incidence and completenessof inclusion as an extension to the closed world assumption.
Client-Server Paradise
146 Citations1994David J. DeWitt, Navin Kabra +3 more
The current version of Paradise, uses a client-server architecture and provides an extended-relational data model for modeling GIS applications that supports an extended version of SQL and provides a graphical user interface for querying and browsing the database.
Concurrency and recovery in generalized search trees
141 Citations1997Marcel Kornacker, C. Mohan +1 more
This paper presents general algorithms for concurrency control in tree-based access methods as well as a recovery protocol and a mechanism for ensuring repeatable read isolation outside the context of B-trees.
A Generic Approach to Bulk Loading Multidimensional Index Structures
141 Citations1997Jochen Van den Bercken, Bernhard Seeger +1 more
This paper presents a generic algorithm for bulk loading which is applicable to a broad class of index structures and shows that the I/O performance of the generic algorithm meets the lower bound of external sorting.
Lecture notes in computer scienceEfficient Structures for Geometric Data Management
139 Citations1988Oliver Günther
A dual approach to detect polyhedral intersections in arbitrary dimensions and an approximation scheme to represent arbitrary curved shapes are presented.
Efficient computation of spatial joins
136 Citations2002Oliver Günther
A class of tree structures, called generalization trees, that can be applied efficiently to compute spatial joins in a hierarchical manner are described.
IEEE Transactions on Knowledge and Data EngineeringCCAM: a connectivity-clustered access method for networks and network computations
132 Citations1997Shashi Shekhar, Duen‐Ren Liu
Experiments with network computations on the Minneapolis road map show that CCAM outperforms existing access methods, even though the proposed modifications also substantially improve the performance of existing spatial access methods.
Size separation spatial join
124 Citations1997Nick Koudas, Kenneth C. Sevcik
A new algorithm to compute the spatial join of two or more spatial data sets, when indexes are not available on them, is introduced and relatively simple cost estimation formulas that can be exploited by a query optimizer are shown.
IEEE Transactions on Knowledge and Data EngineeringThe DASDBS project: objectives, experiences, and future prospects
124 Citations1990Hans‐Jörg Schek, H.-B. Paul +2 more
A retrospective of the Darmstadt database system project, also known as DASDBS, is presented, aimed at providing data management support for advanced applications, such as geo-scientific information systems and office automation.
The DEDALE system for complex spatial queries
121 Citations1998Stéphane Grumbach, Philippe Rigaux +1 more
DEDALE is presented, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects that generalizes the constraint database model of [KKR90].
Gral: an extensible relational database system for geometric applications
119 Citations1989Ralf Hartmut Güting
The central concept is to use languages based on many-sorted algebra to represent queries as well as query execution plans that leads to a simple and clean extensible system architecture that eases the task of an application developer by providing a uniform framework, and also simplifies rule-based optimization.
Comparison of approximations of complex objects used for approximation-based query processing in spatial database systems
112 Citations2002Thomas Brinkhoff, H.-P. Kriegel +1 more
Results indicate that, depending on the complexity of the objects and the type of queries, the approximations five-corner, ellipse and rotated bounding box clearly outperform the boundingbox.
Lecture notes in computer scienceSpatial Data Types for Database Systems
110 Citations1997Markus Schneider
Very Large Data BasesTechniques for Design and Implementation of Efficient Spatial Access Methods
104 Citations1988Bernhard Seeger, Hans‐Peter Kriegel
This paper presents a classification of existing spatial access methods and shows that they use one of the following three techniques: clipping, overlapping regions, and transformation, and suggests a hybrid method combining the techniques of overlapping regions and transformation.
Building a scaleable geo-spatial DBMS
102 Citations1997Jignesh M. Patel, Curt J. Ellmann +13 more
A number of new techniques for parallelizing geo-spatial database systems are presented and their implementation in the Paradise object-relational database system is discussed.
Spatial join indices
92 Citations2002Doron Rotem
Algorithms based on grid files as the underlying spatial index are presented for spatial joins in databases which store images, pictures, maps and drawings, and it is shown that the size of the index and its maintenance cost are relatively small.
Lecture notes in computer scienceThematic map modeling
92 Citations1990Micheł Scholl, Agnès Voisard
The model presented here is a first step toward a high level spatial query language adapted to the manipulation of thematic maps and provides the designer of geographic databases with a database query language extensible and customizable.
Tioga-2: a direct manipulation database visualization environment
84 Citations2002Alex Aiken, Junzhou Chen +2 more
The paper reports on user experience with Tioga, a DBMS centric visualization tool developed at Berkeley, and designs Tioga-2 as a direct manipulation system that is more powerful and much easier to program.
Information SystemsComposite regions in topological queries
80 Citations1995Eliseo Clementini, Paolino Di Felice +1 more
The paper introduces a two-level formal model suitable for representing topological relationships among composite regions inside a spatial query language with the purpose of answering topological queries on complex geographic objects.
GeoInformaticaData Partitioning for Parallel Spatial Join Processing
79 Citations1998Xiaofang Zhou, David J. Abel +1 more
A framework combining the data-partitioning techniques used by most parallel join algorithms in relational databases and the filter-and-refine strategy for spatial operation processing is proposed for parallel spatial join processing.
Lecture notes in computer scienceRealms: A foundation for spatial data types in database systems
78 Citations1993Ralf Hartmut Güting, Markus Schneider
A realm as a general database concept is a finite, dynamic, user-defined structure underlying one or more system data types associated with a DBMS to enforce geometric consistency on object creation or update.
Algorithms for Querying by Spatial Structure
71 Citations1998Dimitris Papadias, Nikos Mamoulis +1 more
A flexible framework is described which permits the representation of configurations in different resolution levels and supports the automatic derivation of similarity measures and three algorithms for structural query processing which integrate constraint satisfaction with spatial indexing (R-trees) are proposed.
ACM Transactions on Database SystemsRule-based optimization and query processing in an extensible geometric database system
70 Citations1992Ludger Becker, Ralf Hartmut Güting
This paper shows in particular how the special processing techniques of a geometric database systems, such as spatial join methods and geometric index structures, can be integrated into query processing and optimization of a relational database system.
High-Concurrency Locking in R-Trees
67 Citations1995Marcel Kornacker, Douglas Banks
A solution to the problem of concurrent operations in R-trees, a dynamic access structure capable of storing multidimensional and spatial data by assigning sequence numbers to nodes that let us reconstruct the "lineage" of a node at any point in time.
Lecture notes in computer scienceImplementation of the ROSE algebra: Efficient algorithms for realm-based spatial data types
63 Citations1995Ralf Hartmut Güting, Thomas de Ridder +1 more
The implementation of the ROSE algebra is described, providing data structures for the types and new realm-based geometric algorithms for the operations, and the main techniques used are (parallel) traversal of objects, plane-sweep, and graph algorithms.
Lecture notes in computer scienceMulti-Scale partitions: Application to spatial and statistical databases
61 Citations1995Philippe Rigaux, Michel Scholl
This work proposes a model which allows: (i) database querying without exact knowledge of the data abstraction level, (ii) the computation of multiple representations of data, one per abstractionlevel, and (iii) its application to the computations of statistical summaries.
Lecture notes in computer scienceExtending a DBMS with spatial operations
59 Citations1991Walid G. Aref, Hanan Samet
A data architecture that matches the requirements for efficient processing of spatial queries in the extended database environment is proposed and provides an equal opportunity for both the spatial components and the non-spatial components of the data to participate in query processing and optimization.
Beyond Icons: Towards New Metaphors for Visual Query Languages for Spatial Information Systems
58 Citations1992Bernd T. Meyer
Lecture notes in computer scienceGeo-SAL: A query language for spatial data analysis
57 Citations1991Per Svensson, Zhexue Huang
This chapter discusses query languages, which focus on the retrieval and modification of data from a database to a user or a host program.
Cartography and Geographic Information SystemsExtending SQL for Graphical Display
48 Citations1991Max J. Egenhofer
GPL contains commands to direct the display of objects, spatial context, the query window, map scale, etc, which lets users formulate separately queries and display specifications, which are integrated during query processing so that complex graphic descriptions can be formulated in a language similar to SQL.
Extending a DBMS for geographic applications
48 Citations2003Beng Chin Ooi, R.S. Davis +1 more
A method is presented for extending a conventional DBMS (database management system) for geographic applications where the interface language SQL is augmented to allow formulation of queries involving both spatial and nonspatial selection criteria.
Lecture notes in computer scienceSpatial join strategies in distributed spatial DBMS
48 Citations1995David J. Abel, Beng Chin Ooi +3 more
The problems of spatial joins between sites are examined, and spatial join processing strategies used in a heterogeneous spatial database system are presented.
International Journal of Geographical Information SystemsSIRO-DBMS SIRO-DBMS: a database tool-kit for geographical information systems
47 Citations1989David J. Abel
A prototype geographical database tool-kit, SIRO-DBMS, which provides some spatial data types and spatial access methods as external attachments to a kernel relational database management system, is described.
A Raster Approximation For Processing of Spatial Joins
45 Citations1998Geraldo Zimbrão, Jano Moreira de Souza
A new algorithm for computing joins with grid files
43 Citations2002Ludger Becker, Klaus Hinrichs +1 more
It is shown that the CPU cost of the join algorithm is successfully reduced by introducing an inner join, and a comparison with the hash join algorithm and a join algorithm on k-d trees for equijoins is based on a cost model developed for query processing with grid files.
Information SciencesA practical divide-and-conquer algorithm for the rectangle intersection problem
42 Citations1987Ralf Hartmut Güting, W. Schilling
A divide-and-conquer algorithm is developed which solves the problem directly rather than by solving two subproblems, treats special cases elegantly, and has a simple implementation.
Distance-associated join indices for spatial range search
38 Citations2003Wei Lü, Jiawei Han
The analysis and performance study shows that distance-associated spatial join indices substantially improve the performance of spatial queries, and different structures are best suited for different applications.
Lecture notes in computer scienceMonet and its geographical extensions: A novel approach to high performance GIS processing
36 Citations1996Peter Boncz, Wilko Quak +1 more
Monet is described, a novel database system, designed to get maximum performance out of today's workstations and symmetric multiprocessors.
Information SystemsAbstract data types for the logical modeling of complex data
35 Citations1991Marinella Gargano, Enrico Nardelli +1 more
This paper proposes a logical data model for complex data by using abstract data types for domains specification and an extended relational algebra, and introduces the parameterized type Geometry(S), which allows the representation of complex aggregated data.
Lecture notes in computer scienceManipulating spatial data in constraint databases
32 Citations1997Alberto Belussi, Elisa Bertino +1 more
This paper extends the model and the algebra to directly deal with the set of points represented by a generalized tuple (a spatial object), retaining at the same time the ability of expressing all computations that can be expressed by other constraint database languages.
Dynamic granular locking approach to phantom protection in R-trees
29 Citations2002Kaushik Chakrabarti, Sharad Mehrotra
The paper presents a dynamic granular locking approach to phantom protection in R trees, and provides the first solution to the phantom problem in multidimensional access methods based ongranular locking.
Lecture notes in computer scienceThe DASDBS GEO-Kernel, concepts, experiences, and the second step
29 Citations1990Andreas Wolf
The DASDBS GEO-Kernel is a combined approach using a new powerful data model for the description of storage structures and a set-oriented user interface with an Object Buffer and extensibility to achieve a closer connection to the application programs.
Towards a Formal Model for Multiresolution Spatial Maps.
28 Citations1995Enrico Puppo, Giuliana Dettori
Integrated query processing strategies for spatial path queries
26 Citations2002Yun-Wu Huang, Jing Ning +1 more
This paper proposes and implements the resulting four integrated query processing strategies, utilizing state-of-the-art technologies such as spatial joins for intersect computation, R-tree access structure for spatial overlap searching, and spatial clustering for efficient path searching.
Very Large Data BasesApplication of DBMS to land information systems
23 Citations1981Andrew U. Frank
Land Information Systems shall be used to store data on objects in space to get a map drawn on a CRT screen; the typical query is therefore a two-dimensional range query which yields all the data needed to draw the map.
Lecture notes in computer scienceDeduction and deductive databases for geographic data handling
22 Citations1993Alia I. Abdelmoty, M. Howard Williams +1 more
Deduction in the database is used to support the natural representation of complex spatial object structures in single and multi-layered Geographic DataBases (GDB), inference of implicit spatial relationships, and the manipulation of multiple resolution spatial representations.
Lecture notes in computer scienceOrthogonal polygons as bounding structures in filter-refine query processing strategies
19 Citations1997Cláudio Esperança, Hanan Samet
It is shown that the use of non-trivial orthogonal polygons (i.e., with more than four vertices) is of benefit when a spatial index is used in the filter step for processing spatial queries such as point-in-object and windowing.
The Alps at your fingertips: virtual reality and geoinformation systems
16 Citations2002Renato Pajarola, Thomas Ohler +3 more
This work describes a prototype system, called ViRGIS (Virtual Reality GIS), that integrates two system platforms: a client that runs the VR component interacts via a (local or wide area) network with a server that runs an object-oriented database containing geographic data.
Lecture notes in computer scienceImproving spatial intersect joins using Symbolic Intersect Detection
16 Citations1997Yun-Wu Huang, Matthew Jones +1 more
This work introduces a novel technique, called Symbolic Intersect Detection (SID), which detects most of the true hits during a spatial intersect join by scrutinizing symbolic topological relationships between candidate polygon pairs and boosts performance by detecting true hits early during the refinement step, thus avoiding expensive polygon intersect computations.
GraphDB: A Data Model and Query Language for Graphs in Databases
15 Citations1994Ralf Hartmut Güting
The GraphDB model allows for an explicit representation of graphs by partitioning object classes into simple classes, link classes, and path classes whose objects can be viewed as nodes, edges and explicitly stored paths of a graph.
Lecture notes in computer scienceA general and efficient implementation of geometric operators and predicates
13 Citations1997Edward P. F. Chan, Jimmy N. H. Ng
A plane-sweep algorithm that can be easily modified to realize efficiently a set of frequently used line-region and region-region geometric operators and predicates and can be generalized nicely to r regions, where r>2.
Computers & GraphicsInteractive graphic data processing in cartography
5 Citations1985Matthäus Schilcher
Both hardware and software concepts for the SICAD interactive graphic system for cartography are presented and explained using practical examples.
…