Van Kreveld M., Nievergelt J., Roos T., Widmayer P. (eds.) Algorithmic Foundations of Geographic Information Systems
Подождите немного. Документ загружается.
cell. Its structure resembles the B+-tree, including restructuring operations that
propagate from the leaf level towards the root. Each data cell is the bounding
box of the rectangles associated with the corresponding block. Each directory
block maintains a rectangular subspace of the data space; its block cell is the
bounding box of the sub@aces of its children. As a consequence, on each level of
the tree, each stored rectangle lies entirely in at least one block cell; since block
cells will overlap in general, it may actually lie in more than one cell (in Fig. 14,
rectangles E and F lie in cells A and B, referenced by the root block). This fact
may distort geometric selectivity: In an exact match query, we cannot restrict
the search for E to either A or B, but instead we need to follow both paths (in
the worst case, with no hint as to which one is more likely). Since it is essential
for the R-tree to avoid excessive overlap of cells, many strategies of splitting an
overflowing block into two exist, ranging from the initial suggestion (Guttman
1984) to less or more sophisticated heuristics (Beckmann et al. 1990, Greene
1989) and even to optimal splits for a number of criteria (Becket et al. 1992,
Six et al. 1992). With the appropriate splitting strategy and extra restructuring
operations (Beckmann et al. 1990), the R-tree seems to be one of the most
efficient access structures for rectangles to date.
B
I
Level 0
C
(root)
root
D E F G H I J
A
B
--H"
E
C
C J Level 1
Fig. 14. Cells of an R-tree
For specific purposes, a number of variants of the R-tree have been proposed.
The R+-tree avoids overlapping directory cells by clipping rectangles as neces-
sary (Faloutsos et al. 1987, Sellis et al. 1987). It suffers, however, somewhat
from the inefficiency caused by forced splits propagating downwards, similar to
k-d-B-trees. For a static situation, in which almost no insertions or deletions
take place, and therefore queries dominate the picture, the R-tree can be packed
181
densely so as to increase effciency in time and space (Roussopoulos et al. 1985).
Ohsawa et al. (1990) combine the R-tree and quad tree cells.
6.4 Cells with Bounded Overlap: Multilayer Structures, R-File,
Guard File
Geometric selectivity increases with decreasing cell overlap. This has been the
starting point for a number of attempts to maintain rectangles with cells whose
overlap is under tight control
The multilayer technique. The basic idea is to cover the data space with
more than one partition. Each level of a hierarchical data structure, in which
the cells of a node's children are a partition of the cell of their parent, partitions
the data space or a subspace. Therefore, such a hierarchy naturally offers a set of
partitions with various degrees of refinement. Even though this set of partitions
has not been defined with the explicit goal of covering space several times, it can
be used nicely to store rectangles: Each rectangle is stored at the node as far
down as possible in the hierarchy whose cell encloses the rectangle. This principle
has been used in the quad-CIF tree and the MX-CIF quad tree (Abel et al. 1983,
Kedem 1982). With the explicit goal of creating a few partitions according to
the set of rectangles, Six et al. (1988) maintain each partition - called layer -
in an extra data structure. Care has to be taken to ensure that the partitions
of the different layers are actually different (Fig. 15); otherwise, the number of
partitions increases more than necessary, and in general efficiency deteriorates.
A fairly large number of split strategies that guarantees the partitions to be
quite different have been developed. It can be guaranteed that for storing a set
of small d-dimensional rectangles, d + 1 layers will always suffice - the technical
term "small" there has a precise rneaning (Six et al. 1988). Large rectangles
must be clipped, whenever there are few of them, such as in most cartographic
applications, clipping will not be harmful.
L..-J
[3
[3
Layer 1
Layer 2
Lwe r 3
Fig. 15. Cells of a three-l~yer grid file
182
In a multilayer data structure that uses a point data structure with a modified
split strategy for each layer, the layers are totally ordered, from lowest to highest.
A rectangle is associated with the lowest layer that has a cell of the partition
containing it entirely; in that layer, the rectangle is associated with that cell,
just like a point in the underlying point data structure. If there is no such layer,
either a new layer is created, or the rectangle is clipped at the boundaries of the
highest layer.
Note that the multitayer technique is generic in the sense that it allows any
one of a number of point data structures to be used for the layers. Experiments
with a multilayer grid file, for instance, show that the loss of efficiency as com-
pared with a standard (single layer) grid file for points is tolerable, with a certain,
but small, query overhead due to the fact that a directory for each layer needs
to be inspected. Experiments with multilayer dynamic z-hashing (Hutflesz et
al. 1992) show that the attempt to preserve global order makes range queries
extremely fast, far better than any other data structure, for data and queries
from cartography. In addition, the multilayer technique realizes the advantages
of recursive linear hashing (Ramamohanarao et al. 1984) over linear hashing
without the overhead, because there are several (recursive) layers anyway.
The R-file. Since the search parameters are the same for each layer of a mul-
tilayer structure (e.g. in a range query), it might be desirable to integrate all
the directories into one directory. This is exactly what the R-file (Hutflesz et
al. t990) does: It maintains a set of overlapping cells with one directory. The
cells are exactly of the same form as the rectangular regions in the BANG file,
with no rectangles cut out for subspaces. Similar to the quad-CIF tree, each
object is associated with the smallest cell that contains it (Fig. 16). Therefore,
unlike in the BANG file, where cells are disjoint rectilinear polygons with holes,
in the R-file cells overlap.
r---i
I---
L_J
II
-[3 ill'!
(a) (b) (c)
I
Fig. 16. R-file cells for insertion (a) and for searching (b), and grid file cells with
clipping (c)
There is a limit to the association of rectangles to cells in this way: If too
many rectangles intersect the split line of a cell in which they lie, they cannot
183
be distributed to other cells. In that case, a lower dimensional R-file stores these
rectangles; the one dimension in which all of these rectangles intersect the split
line can be disregarded. Fortunately, no extra data structure is needed for the
(d-1)-dimensionat R-file; instead, a simple skip of the corresponding dimension
in the cyclic turn through all dimensions will do. Experiments have shown the R-
file to be a very efficient data structure for cartographic data. It suffers, however,
from the disadvantage of being somewhat complicated to implement, with extra
algorithmic difficulties (but not inefficiencies) such as a forced split downwards.
Nevertheless, it is a good basis for a data structure that supports queries with
a requested degree of detail, all within a query range (Becker et al. 1991).
The guard file. The guard file (Nievergelt et al. 1993) is designed for
fat
objects, where fatness requires that the shape of an object is sufficiently close to
a sphere, in a precise, technical sense. The difficulties in maintaining arbitrary
spatially extended objects, as opposed to points, comes from the fact that an
object may intersect more than one cell of a space partition, that is, it may
intersect split lines. For fat objects, the idea is to place guard points (not lines)
in strategic positions, and then to distinguish objects according to the guards
they contain. Guards are the corners of the cells of some regular space partition.
Fig. 17 shows a radix tree partition, but other partitions such as triangular or
hexagonal ones work just as well.
~w
Fig. 17. A radix tree partition with guards at corner points
By imposing the radix tree as a hierarchy on the guards, range queries become
efficient: The level of a guard is the level of the largest cell of which the guard is
a corner point, with the root of the tree having the highest level. Any sufficiently
large, fat object must contain a guard. An object containing a guard (a
guarded
object) is stored with the highest level guard that it contains. A fat object
that contains no guard (an
unguarded
object) must be small; it is stored with
all intersecting cells of the partition at the leaf level of the radix tree. As a
consequence, a range query is carried out by inspecting the objects associated
with all guards in the query range and all cells intersecting the query range. For
184
long and skinny objects, clipping makes this data structure inefficient, but for fat
objects such as those often encountered in cartography, clipping is no problem.
The guard file, however, includes an additional step to trade storage space
for query time: An unguarded object is associated with exactly one cell of the
partition, namely the one into which its center (of gravity) falls. Hence, each
object is stored only a small, constant number of times, the number depending
only on the type of regular partition being used and the precise fatness require-
ment. In a range query, it is no longer sufficient to inspect the cells that intersect
the query range: Adjacent cells also need to be inspected. The neighborhood of
adjacent cells by which a query range must be extended depends entirely on how
fat the stored objects are: the fatter the objects, the smaller this neighborhood.
For various types of regular partitions and various bounds on the fatness (in a
precise, technical sense for arbitrary, convex geometric objects), the guard file is
easy to implement and efficient at the same time.
6.5 Conclusions Drawn from the Structures Surveyed
The set of spatial data structures and paradigms has grown to a respectable
size. A multitude of concepts serve as building blocks in the design of new spa-
tial data structures for specific purposes. A number of convincing suggestions
indicate that, for instance, these building blocks can be used in the design of
data structures for more complex settings. Becker (t992), Brinkhoff et al. (1993),
G/lather (1992b), Kriegel et al. (1992a), and Shaffer et al. (1990a), among others,
show how various kinds of set operations, such as spatial join, can be performed
efficiently by using a spatial index. For objects and operations going beyond
geometry, Ohler (1992) shows how to design access structures that involve non-
geometric attributes in a query. In a closer look to the needs of cartography,
a data structure of weighted geometric objects is proposed that efficiently sup-
ports queries with a varying degree of detail, as specified by the user (Becket et
al. 1991). For the special case in which the objects to be stored are the polygons
of a planar partition, and access to entire polygons (in containment queries with
points, for instance) as well as access to the polygon boundaries (for drawing
a map) is needed, there are suggestions that consider both external accesses
and main memory computations as important cost factors (Kriegel et al. 1992b,
Schiwietz et al. 1993); other suggestions aim at making queries efficient without
storing polygon boundaries twice (Becket 1993). In addition, hierarchical spatial
access structures can be designed to support queries into the past (Becket et
al. 1993, Charlton et al. 1990, Xu et al. 1990). It can be seen from this list that
even though a fair number of concepts of data access are readily available, it is
mosten often a considerable effort to bring any two of them together without
losing key features, especially efficiency.
All the arguments above concerning the efficiency of data structures are of
an intuitive nature. An average case analysis is rarely given (Ang et al. 1992,
Devroye 1986, Flajolet et al. 1986, Lindenbaum et al. 1995, Nelson et al. 1987,
Regnier 1985, Rottke et al. 1987 are notable exceptions), because a probability
185
model for sets of geometric objects and queries is very hard to get (Ambartzum-
jan et at. 1993, Harding et al. 1974, Matheron 1975, Santalo 1976, Stoyan et
al. 1987). Even experiments (Kriegel et al. 1989a, Shaffer et al. 1990b, Smith et
al. 1990) that clarify some of the efficiency aspects tend to reveal not too much
about the contribution of the building blocks of data structures to their over-
all efficiency. Some steps towards a clarification of what is the desired average
case efficiency and how to achieve it, with consequences for the data structure
design, have been taken (Henrich et al. 1991, Pagel et al. 1993b, Six et al. 1992,
Anget al. 1992, Pagel 1995), but many more are needed to shed enough light
on the inner workings of spatial data structures. In the meantime, the designer
and programmer of spatial data structures should be aware of the existing build-
ing blocks and use them with expertise and intuition, bringing them together
wherever possible.
7 Summary: Points to Consider When Choosing a Spatial
Data Structure
Let us conclude this bird's eye survey of the domain of spatial data structures
with a few concisely stated points of view and recommendations.
Spatial data differs from all other types of data in important respects. Objects
are embedded in a Euclidean space with its rich geometric structure, and most
queries involve proximity rather than intrinsic properties of the objects to be
retrieved. Thus data structures developed for conventional data base systems
are unlikely to be efficient.
The most important feature of a spatial data structure is a systematic, regular
organization of the embedding space. This serves as a skeleton that lets one
address regions of space in terms of invariant quantities, rather than merely
in relation to transient objects that happen to be stored. In particular, radix
partitions of the space are more widely useful than data-driven space partitions
based on comparative search.
The vast literature on spatial data describes a multitude of structures that
differ only in technical details. Theory has not progressed to the stage where it
can rank them in terms of efficiency. Performance comparisons representative of
a wide range of applications and data are difficult to design, and reported results
to this effect are often biased. Thus we are left to choose on the basis of common
sense and conceptual simplicity.
Whereas the choice of a spatial data structure does not require a lot of
detailed technical know-how, programming the computational geometry routines
that implement the fine filter of Section 4.3 is a different matter. Writing robust
and efficient procedures that intersect arbitrary polyhedra (say a query region
and an object) is a specialist's task that requires a different set of skills.
In conclusion, this survey is neither a "how-to" recipe book that describes
the multitude of data structures, nor a sales pitch ibr any one in particular. It
intends to be a thought-provoking display of the issues to ponder and to assess.
186
Our message places responsibility for a competent choice where it belongs, with
the programmer.
Acknowledgements
We are grateful to Martin Breunig, Thomas Ohler, Hanan Samet, Bernhard
Seeger, Matti Tikkanen and an unknown referee for comments on this survey
and interesting discussions.
References
Abel, D.J., J.L. Smith (1983): A data structure and algorithm based on a linear
key for a rectangle retrieval problem; Computer Vision, Graphics, and Image
Processing, Vol. 24, 1-13
Abel, D.J., D.M. Mark (1990): A comparative analysis of some two-dimensional
orderings; International Journal of Geographical Information Systems, Vol. 4,
No. 1, 21-31
Adelson-Velskii, G.M., Y.M. Landis (1962): An algorithm for the organization of
information, Doklady Akademia Nauk SSSR, Vol. 146, 263-266; English trans-
lation in: Soviet Math. 3, 1259-1263
Ambartzumjan, R.V., J. Mecke, D. Stoyan (1993): Geometrische Wahrschein-
tichkeiten und Stochastische Geometrie, Akademie Verlag, Berlin
Ang, C.-H., H. Samet (1992): Average storage utilization of a bucket method;
Technical Report, University of Maryland
Aref, W.G., H. Samet (1994): The spatial filter revisited. In Proc. 6th Int. Syrup. on
Spatial Data Handling, 190-208
Arge, L. (1996): Efficient external-memory data structures and applications;
PhD thesis, University of Aarhus, Denmark
Asano, T., D. Ranjan, T. Roos, P. Widmayer, E. Welzl (1995): Space filling
curves and their use in the design of geometric data structures, Proc. Second In-
tern. Symp. of Latin American Theoretical Informatics LATIN '95, Valparaiso,
Lecture Notes in Computer Science, Vol. 911, Springer-Verlag, 36-48
Bayer, R., C. McCreight (1972): Organization and maintenance of large ordered
indexes; Acta Informatica, Vol. 1, No. 3, 173-189
Bayer, R., Schkolnick, M. (1977): Concurrency of operations on B-trees, Acta
Informatica Vol. 1, 1-21
Becker, B. (1993): Methoden und Strukturen zur effizienten Verwaltung ge-
ometrischer Objekte in Geo-Informationssystemen, Dissertation, Mathematische
Fakult£t, Albert-Ludwigs-Universit£t, Freiburg, Germany
Becker, B., H.-W. Six, P. Widmayer (1991): Spatial priority search: An access
technique for scaleless maps, Proc. ACM SIGMOD International Conference on
the Management of Data, Denver, 128-137
Becker, B., P. Franciosa, S. Gschwind, T. Ohler, G. Thiemt, P. Widmayer (1992):
Enclosing many boxes by an optimal pair of boxes; Proc. 9th Annual Symposium
on Theoretical Aspects of Computer Science STACS, Cachan, Lecture Notes in
187
Computer Science, Vol. 577, 475-486
Becker, B., S. Gschwind, T. Ohler, B. Seeger, P. Widmayer (1993): On opti-
mal multiversion access structures; 3rd International Symposium on Advances
in Spatial Databases, Singapore, Lecture Notes in Computer Science, Vol. 692,
Springer-Verlag, 123-141
Becker, L. (1992): A new algorithm and a cost model for join processing with
grid files; Dissertation, Fachbereich EIektrotechnik und Informatik, Universitgt-
Gesamthochschule Siegen, Germany
Beckmann, N., H.-P. Kriegel, R. Schneider, B. Seeger (1990): The R*-tree: An
efficient and robust access method for points and rectangles; Proc. ACM SIG-
MOD International Conference on the Management of Data, Atlantic City, New
Jersey, 322-331
Bentley, J.L. (1975): Multidimensional binary search used for associative search-
ing; Communications of the ACM, Vol. 18, No. 9, 509-517
Blankenagel, G. (1991): Intervall-Indexstrukturen und externe Algorithmen flit
Nicht-Standard-Datenbanksysteme; Dissertation, FernUniversitgt Hagen
B finkhoff, T., H.-P. Kriegel~ B. Seeger (1993): Efficient processing of spatial joins
using R-trees; Proc. ACM SIGMOD International Conference on the Manage-
ment of Data, Washington D.C., 237-246
Brinkhoff, T. (1994): Der Spatial Join in Geo-Datenbanksystemen. Ph.D.thesis,
Ludwig- Maximilians-Universitgt Miinchen.
Brinkhoff, T. und H.-P. Kriegel (1994): The impact of global clustering on spatial
database systems. In Proc. 20th Int. Conf. on Very Large Data Bases, 168-179.
Brinkhoff, T., H.-P. Kriegel, and R. Schneider (1993): Comparison of approxi-
mations of complex objects used for approximation-based query processing in
spatial database systems. In Proc. 9th IEEE Int. Conf. on Data Eng., 40-49.
Brinkhoff, T., H.-P. Kriegel, R. Schneider, and B. Seeger (1994): Multi-step pro-
cessing of spatial joins. In Proc. ACM SIGMOD Int. Conf. on Management of
Data, 19'7-208.
Bruzzone, E., L. De Floriani, M. Pellegrini (1993): A hierarchical spatial index
for cell complexes; 3rd International Symposium on Advances in Spatial Data-
bases, Singapore, Lecture Notes in Computer Science, Vol. 692, Springer-Verlag,
105-122
Charlton, M.E., S. Openshaw, C. Wymer (1990): Some experiments with an
adaptive data structure in the analysis of space-time data; Proc. 4th Interna-
tional Symposium on Spatial Data Handling, Zurich, 1030-1039
Chazelle, B. (1990): Lower bounds for orthogonal range searching: I. The report-
ing case; J. ACM Vol. 37, No. 2, 200-212
Chen, L., R. Drach, M. Keating, S. Louis, D. Rotem, and A. Shoshani (1995):
Access to multidimensional datasets on tertiary storage systems. Information
Systems 20(2), 155-183.
Comer, D. (1979): The ubiquitous B-tree; ACM Computing Surveys, Vol. 11,
No. 2, 121-138
Crain, I.K. (1990): Extremely large spatial information systems: a quantita-
tive perspective; Proc. 4th International Symposium on Spatial Data Handling,
188
Zurich, 632-641
d'Amore, F., P.G. Franciosa (1993a): Separating sets of hyperrectangles, Inter-
national Journal of Computational Geometry and Applications, Vol. 3, No.2,
155-165
d'Amore, F., T. Roos, P. Widmayer (1993b): An optimal algorithm for com-
puting a best cut of a set of hyperrectangles, International Computer Graphics
Conference, Bombay
d'Amore, F., V.H. Nguyen, T. Roos, P. Widmayer (1995): On optimal cuts of
hyperrectangles, Computing, Ybl. 55, Springer-Verlag, 191-206
Devroye, L. (1986): Lecture notes on bucket Mgorithms; Birkh£user Vertag,
Boston
DrSge, G., H.-J. Schek, (1993): Query-adaptive data space partitioning using
variable-size storage clusters; 3rd International Symposium on Advances in Spa-
tial Databases, Singapore, Lecture Notes in Computer Science, Vol. 692, Springer-
Verlag, 337-356
DrSge, G. (1995): Eine anfrage-adaptive Partitionierungsstrategie flit Raumzu-
griffsmethoden in Geo-Datenbanken; Dissertation ETH Zurich Nr. 11172
Edelsbrunner, H. (1982): Intersection problems in computational geometry; Dis-
sertation, Technische Universit£t Graz
Enbody, R.J., H.C. Du (1988): Dynamic hashing schemes; ACM Computing Sur-
veys, Vol. 20, No. 2, 85-113
Evangelidis, G. (1994): The hB - Tree: A Concurrent and Recoverable Multi-
Attribute Index Structure. Ph.D. thesis, Northeastern University, Boston, MA.
Fagin, R., J. Nievergelt, N. Pippenger, H.R. Strong (1979): Extendible hashing-
a fast access method for dynamic files; ACM Transactions on Database Systems,
Vol. 4, No. 3, 315-344
Faloutsos, C. (1985): Multiattribute hashing using Gray codes; Proc. ACM SIG-
MOD International Conference on the Management of Data, Washington D.C.,
227-238
Faloutsos, C. (1988): Gray codes for partial match and range queries; IEEE
Transactions on Software Engineering, Vot. 14, 1381-1393
Faloutsos, C., S. Roseman (1989): Fractals for secondary key retrieval; Proc. 8th
ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, 247-
252
Falontsos, C., T. Sellis, N. Roussopoulos (1987): Analysis of object oriented
spatial access methods; Proc. ACM SIGMOD International Conference on the
Management of Data, San Francisco, 426-439
Finkel, R.A., J.L. Bentley (1974): Quad trees: A data structure for retrieval on
composite keys; Acta Informatica, Vol. 4, No. 1, 1-9
Flajolet P., C. Puech (1986): Partial match retrieval of multidimensional data;
Journal of the ACM, Vol. 33, No. 2, 371-407
Frank, A. (1981): Application of DBMS to land information systems; Proc. 7th
International Conference on Very Large Data Bases, Cannes, 448-453
Freeston, M.W. (1987): The BANG file: a new kind of grid file; Proc. ACM
SIGMOD International Conference on the Management of Data, San Francisco,
260-269
189
Freeston, M.W. (t989a): Advances in the design of the BANG file; Proc. 3rd
International Conference on Foundations of Data Organization and Algorithms,
Paris, Lecture Notes in Computer Science, Vol. 367, Springer-Verlag, Berlin,
322-338
Freeston, M.W. (1989b): A well-behaved file structure for the storage of spatial
objects; Symposium on the Design and Implementation of Large Spatial Data-
bases, Santa Barbara, Lecture Notes in Computer Science, Vol. 409, Springer-
Verlag, Berlin, 287-300
Freeston, M. (1995): A general solution of the n-dimensional B-tree problem. In
Proc. ACM SIGMOD Int~ Conf. on Management of Data, 80-91.
Gaede, V. (1995): Optimal redundancy in spatial database systems. In Proc. 4th
Int. Symp. on Spatial Databases (SSD'95).
Gaede, V., Giinther, O. (1996): Multidimensional access methods; manuscript~
Humboldt-Universit~t Berlin, Institut fiir Wirtschaftsinformatik
Goodchild, M.F. (1990): Spatial information science; Proc. 4th International
Symposium on Spatial Data Handling, Zurich, 3-12
Greene, D. (1989): An implementation and performance analysis of spatial data
access methods; Proc. 5th International Conference on Data Engineering, Los
Angeles, 606-615
Giinther, O. (1988): Efficient structures for geometric data management; Lecture
Notes in Computer Science, Vol. 337, Springer-Verlag, Berlin
Giinther, O. (1989): The design of the cell tree: An object oriented index struc-
ture for geometric databases; Proc. 5th International Conference on Data Engi-
neering, Los Angeles, 598-605
G/inther, O. (1992a): Evaluation of spatial access methods with oversize shelves;
Geographic Data Base Management Systems, ESPRIT Basic Research Series
Proceedings, Springer-Verlag, 177-193
Giinther, O. (1992b): Efficient computation of spatial joins; Technical Report
TR-92-029, International Computer Science Institute, Berkeley
Giinther, 0. (1993): Efficient computation of spatial joins. In Proc. 9th IEEE
Int. Conf. on Data Eng.
Giinther, O, J. Bilmes (1989): The implementation of the cell tree: design al-
ternatives and performance evaluation; GI-Fachtagung Datenbanksysteme fiir
Biiro, Technik nnd Wissenschaft, Informatik-Fachberichte, Vol. 204, Springer-
Verlag, Berlin, 246-265
G/luther, O., J. Bilmes (1991): Tree-based access methods for spatial databases:
implementation and performance evaluation; IEEE Transactions on Knowledge
and Data Engineering, Vol. 3, No. 3~ 342-356
G/inther, O., A. Buchmann (1990): Research issues in spatial databases; IEEE
CS Bulletin on Data Engineering, Vol. 13, No. 4, 35-42
G/inther, o., R. KSrstein, R. Miiller, and P. Schmidt (1995): The MMM project:
Acess to algorithms via WWW. In Proc. Third International World Wide Web
Conference. URL http.//www.igd.thg.de/www95.htmt.
Gfiting, R.H. (1989): Gral: An extensible relational database system for geomet-
190