Progressive Transmission of Vector Map Data over the World Wide Web.
Within distributed computing environments, access to very large geospatial datasets often suffers from slow or unreliable network connections. To allow users to start working with a partially delivered dataset, progressive transmission methods are a viable solution. While incremental and progressive methods have been applied successfully to the transmission of raster images over the World Wide Web, and, in the form of prototypes, of triangular meshes, the transmission of vector map datasets has lacked a similar attention. This paper introduces a solution to the progressive transmission of vector map data that allows users to apply analytical GIS methods to partially transmitted data sets. The architecture follows a client-server model with multiple map representations at the server side, and a thin client that compiles transmitted increments into a topologically consistent format. This paper describes the concepts, develops an architecture, and discusses implementation concerns.
Figure

1: Roads belonging to different layers.
In the second case, the file is composed of a single layer and entities having different
semantic and thematic meaning coexist in it. In this case, it is assumed that the original
composing set of entities has been overlayed, i.e., there are no intersections between pairs
of entities stored in the file.
paper mill
river
major road
lake
creek
minor roadA
minor roadB
(a)
paper mill river lake
creek creek mouth
major road
bridge intersection AB
minor roadA minor roadB
(b)

Figure

2: (a) A collection of spatial entities with the following pairwise intersections:
minor road A and minor road B; creek and (the boundary of) lake; river and major road;
(b) an overlay algorithm has been applied to the set of entities in (a).
For example, in Figure 2(a) a map is shown where intersections between entities occur. In
order to obtain an overlayed set, some entities must be added to the vector file storing the
map, namely the intersection point between minor road A and minor road B (intersection
AB), the intersection point between creek and lake (creek mouth), and the intersection
region between river and major road (bridge). Such a file, shown in Figure 2(b), can be
generated by applying an overlay algorithm to the set of entities in Figure 2(a) (Bentley
and Ottman 1979, Chazelle and Edelsbrunner 1992).
Overlay operations are always required when a query involving entities whose thematic
information is stored over two or more different layers must be performed. For example,
given a layer representing the hydrography of Italy and a layer describing the set of
Italian regions, we may want to perform queries such as, ?Which regions are traversed by
the river Po?? Map overlay is a complex operation and it is computationally expensive.
Thus, if the purpose of the vector file utilization is querying, it is more convenient to keep
an already overlayed set of entities instead of performing an overlay operation every time
a query is formulated. In the case of progressive transmission, if the client requires the
downloading for query purposes, he more likely expects to be provided with a ready-to-
use file instead of having to perform expensive preprocessing operations on it, such as
map overlay.
On the other side, keeping separated thematic layers in the same file prevents
segmentation of entities. For instance, each road in Figure 1 is fragmented into two
branches after the detection of the intersection point, if the overlayed approach is
adopted. This splitting is not necessary if two distinct layers, one for major roads and one
for minor roads, are maintained. Using this second approach, a smaller amount of entities
is stored. Furthermore, a higher degree of granularity in the transmission can be obtained.
With reference to the above example, the major road network and the minor road network
can be extracted from the file and transmitted separately, even if they are included in the
same level of detail. In conclusion, the adoption of either the overlayed or the separated
layers approach depends on whether the priority is mainly querying or visualization,
respectively.
In this paper, we consider vector files composed of a single layer of overlayed entities
composing a map. In this case, the most commonly used mathematical model is the cell
complex. We describe this concept in the next section.
2.3.2 Cell-Complexes
Cell complexes are commonly used as underlying mathematical models for vector maps
(Bertolotto et al. 1994; Egenhofer et al. 1989; Frank and Kuhn 1986; G ting and
Schneider 1995; Worboys 1992) as they provide a sound theoretical basis for the
formalization of spatial entities and relations contained in a map.
More formally, we define a map as an overlayed set of points, simple lines and (possibly
multiply connected) regions. A (Euclidean) cell complex is defined as a collection of
cells that are homeomorphic to disks. Each cell has a dimension and its boundary is
composed of cells of lower dimension. Pairs of cells in the complex are either completely
disjoint or they meet along their boundary. A complex is said to be n-dimensinal if n is
the maximum dimension of its cells.
The correspondence between entities in a map and cells in a two-dimensional cell
complex is straightforward: cells in a cell complex describe entities of a map. Points are
represented as 0-cells, lines as 1-cells, and regions as 2-cells. The interior and boundary
properties of cells in a cell complex model topological relations among entities in a map
(see Bertolotto (1998) for a more detailed description).
Several data structures for cell complexes have been defined in the computational
geometry and GIS literature (De Floriani et al. 1993; Frank and Kuhn 1986; Preparata
and Shamos 1985). In particular, topological data structures must encode both entities
and their mutual topological relations (Egenhofer and Franzosa 1991).
3. Challenges in Progressive Vector Map Data Transmission
As shown in the previous section, progressive transmission of raster data is relatively
simple. For example, if the purpose of the transmission is visualization, just adding pixels
to an incomplete image generates a more refined version of it. Available compression
mechanisms are also very effective.
When the purpose of the transmission is object manipulation, a vector representation is
required. Except for the particular case of triangular meshes for which effective
compression methods have been defined (see previous section), progressive vector
transmission is still challenging. Our focus is on vector map data, for which effective
compression mechanisms are currently lacking. Indeed, the set of spatial objects that need
to be represented in a map depends on its level of detail. In this context, the term detail
refers both to the amount of entities contained in the file and to the information stored
about such entities, e.g., their geometry (Goodchild and Proctor 1997). Therefore,
changes of detail can be caused by the addition or elimination of some entities, as well as
by the refinement or coarsening of the representation of existing entities (e.g., change of
dimension or shape).
Decreasing the level of detail of a vector map is a complex and time-consuming process
called generalization whose automation and on-line application are still open
problems. In fact, it relies on cartographic principles whose complete formalization is still
lacking (see Weibel and Dutton (1999) for a survey). Automated solutions have only
been proposed for sub-problems and are based on heuristic methods (e.g., the Douglas-Peucker
algorithm (1973)). Therefore, the process still requires interaction between semi-automatic
solutions and expert cartographers.
A critical issue in map generalization is preservation of consistency (e.g., constraints on
overlappings) while decreasing the level of detail (Robinson et al. 1984; McMaster and
Shea 1992; M?ller et al. 1995; Weibel and Dutton 1999). For example, random
subsampling of objects to be eliminated or to be simplified does not usually generate a
consistent representation at coarser detail. In Figure 3 and 4, examples are shown where
random subsampling generates topological inconsistencies across different
representations.
paper mill river lake
creek creek mouth
major road
bridge intersection AB
minor roadA minor roadB
paper mill river lake
creek creek mouth
major road
bridge intersection AB
minor roadA minor roadB

Figure

3: Random elimination of some entities (e.g., bridge) results in topologically
incorrect representations: the two branches of major road and river have incomplete
boundaries.
paper mill river lake
creek creek mouth
major road
bridge intersection AB
minor roadA minor roadB
paper mill river lake
creek creek mouth
major road
bridge intersection AB
minor roadA minor roadB

Figure

4: Selection of a random subset of entities, namely, major road and river (but not
bridge), to coarsen their representation generates a topologically incorrect representation:
topological relations between major road and bridge (and between river and bridge) are
not consistent across levels.
Consistency is an essential property for the usability of data (e.g., for analysis and
querying purposes). Therefore, ad hoc techniques and operators need to be applied.
Unfortunately, the majority of proposed methods do not intrinsically provide consistency
and thus a posteriori checks are required in order to adjust the result when some
inconsistency has been introduced.
During progressive transmission, consistent datasets need to be transmitted to the client
site, where there is no way to discover inconsistencies. Thus, consistency must be
checked for on the server site either implicitly by adopting generalization operators that
preserve it or by means of a posteriori checks on the generalized datasets.
In the following section we propose a solution to progressive vector map data
transmission.
4. A Client-Server Architecture for Progressive Vector Transmission
In this section we present a distributed client-server architecture that enables progressive
transmission of vector data. This work extends our previous research on progressive
vector transmission presented in Bertolotto and Egenhofer (1999). The solution we
propose meets the architectural requirements for the design of contemporary information
systems, involving both heterogeneity of data and processes. In fact, as different tasks are
better performed by different system components, distributed environments represent the
natural direction for which future generation systems are heading. This direction is in
accordance with the exponential network growth and the global connectivity reached in
the last few years. As a consequence, and thanks to the technological improvements
recently obtained, some of the old systems and, in general, newly developed systems, are
being redesigned and embedded into distributed environments (see, for example,
Hofmann (1999); Kramer et al. (1997); Kumar et al. (1999)).
To enable the progressive transmission of vector files, we pre-compute and store a
sequence of consistent representations at lower levels of detail on the server site. Such
representations are transmitted in order of increasing detail to the client upon request

Figure

5).
level 4
level 4 level 3 level 3
level 2
level 1
client server

Figure

5: Representations at different levels of detail are maintained on the server and
transmitted to the client in order of increasing detail.
Besides providing temporary versions of the data on which preliminary operations can be
performed, in this way, the user can realize during the process that the detail of the
currently displayed representation is good enough for her purpose and so she can decide
to interrupt the downloading of more detailed representations (stored in larger files).
Therefore, both time and disk space can be saved.
An interesting property of some techniques for progressive transmission of raster data
(e.g., interleaving techniques) is the fact that they only transmit increments (i.e., sets of
new pixels) at each step. Such increments are added to the currently displayed image to
improve its resolution without requiring the transmission or downloading of another
complete image file.
Since vector files can be very large, it would be useful to speed up the transmission in a
similar way to reduce network traffic. However, increments between two consecutive
levels of detail of a vector dataset can be complex sets of entities that are added to the
level at finer detail to refine the representation of a set of entities at the lower level. The
integration of such increments with the currently downloaded or displayed representation
is a non-trivial task if consistency between different representations must be preserved.
From a purely graphical point of view, a major requirement for spatial analysis consists
of providing a method for combining the results of several queries into a unique graphical
representation. Therefore, the system should allow the addition or elimination of
representation layers from the current display. However, in the case of progressive
transmission, the user may be interested in more than a visual inspection of the data. She
may want to analyze and work with a consistent dataset. A vector file is usually
composed not only of a set of points, lines, and polygons, but also of a set of spatial
relations linking such entities. Thus, suitable overlaying and integration techniques must
be applied not only at the graphical level, but also at the data level to include the
computation of spatial relations between newly introduced entities and preserved entities
(see Section 8.2).
Our solution for progressive vector map transmission relies on a distributed client-server
architecture, with a server provided with methods for building, manipulating, and
transmitting a sequence of map representations at different levels of detail; and a thin
client provided with a set of operations for visualizing as well as updating and integrating
the transmitted levels.
In summary, the following functionalities are required:
? on the server site: a preprocessing task must be performed in order to build a
sequence of map representations at different levels of detail, as well as a progressive
transmission technique must be developed to send the different levels one at a time;
and
? on the client site: a mechanism must be built in order to have different graphic layers
so that the displayed representation is complete at each step (corresponding to the
transmission of a given level of detail), and an integration algorithm must be
developed and implemented for reconstructing the dataset corresponding to the
displayed representation.
Thus, the major issues involved in the process are:
? the definition of a model for consistent multiple map representations;
? the definition of a transmission technique;
? the development of a graphic interface and a dynamic visualization tool for displaying
different layers corresponding to different levels of detail (during transmission); and
? the development of algorithms to compile transmitted increments into a topologically
consistent format for the reconstruction of intermediate levels of detail.
In this paper, we deal with modeling aspects involved in progressive vector map
transmission, disregarding the mainly graphical issues. In particular, in next section we
describe a model for multiple map representations.
5. Multiple Map Representations for Progressive Transmission
In this section we describe a model that was initially presented in Puppo and Dettori
(1995) and then further formalized in Bertolotto (1998). The model consists of a
sequence of map representations of a given area, each corresponding to a different level
of detail. Such sequence can be stored on the server and sent progressively to the client
upon request (as described in Section 4). In Bertolotto (1998) a set of generalization
operators have been defined and shown to be minimal and sufficient to generate
consistent transformations of maps. Only topological changes (e.g., changes of
dimension, complexity, etc.) are possible by applying such operators: metric and
semantic changes are not being taken into account. An example of topological changes in
a map is shown in Figure 6.
river river
bridge

Figure

Topological changes between two different levels of detail in a map: at higher
level (left) the river is represented as a region split into two branches by a bridge
(represented as a line); at lower level (right) the bridge is not represented and the set of
entities representing the river are reduced to a single line.
The set of operators defined is the following:
contraction of an open line (including its endpoints) to a point

Figure

7(a)).
Region contraction: contraction of a simply connected region (with its boundary) to
a point (Figure 7(b)).
Region thinning: a region (and its bounding lines) is reduced to a line (Figure 7(c)).
? Line merge: fusion of two lines sharing an endpoint into a single line (Figure 7(d)).
Region merge: fusion of two regions sharing a boundary line into a single region

Figure

7(e)).
elimination of an isolated point inside a region (Figure 7(f)).
elimination of a line inside a region (Figure 7(g)).
(a) (b) (c)
(d) (e)

Figure

7: Generalization operators.
These operators have been formalized by means of functions between the cell complexes
describing the original and the resulting map (Bertolotto 1998).
For example, in Figure 7(a), if l is the line on the left, p?and p??are its endpoints, and p
is the point on the right, the line contraction operator is formalized by the function
lc:C? C?, where C and C' are cell complexes, such that:
lc(p?)=lc(p?)?l=c(l) =p (1)
and
"e?C,e?p?,p?,?l,lc (e)= e (2)
Equation (2) states that all entities in C other than l, p?and p??are preserved.
Furthermore, constraints on mappings of topological relations must be fulfilled. For
instance, all lines in the map having an endpoint in either p?or p??are transformed into
lines of C?having an endpoint in p. A complete description of such constraints can be
found in Bertolotto (1998).
Contractions and thinning operators correspond to a decrease of dimension for a group of
entities, merge operators group two entities of the same dimension into a single one,
while abstraction operators correspond to the elimination of some lower-dimensional
entity from a region. These operators are called atomic, because they perform minimal
changes, i.e., they modify minimal sets of entities and preserve the others. By composing
functions corresponding to such operators, complex map transformations can be defined.
As outilined in Section 3, in the case of progressive transmission between two remote
sites, the preservation of consistency is a major issue, and it must be guaranteed by the
server as the client has no way to control it. When the previously described operators are
used, consistency is automatically guaranteed. In fact it has been shown that they
represent a minimal and sufficient set of functions that generate (by composition) only
consistent transformations for decreasing the level of detail of a map (Bertolotto 1998). In
particular, they allow to generate all map transformations that preserve the boundary of
entities and whose inverse image preserves connectivity (i.e., they do not allow to model
aggregation of non-connected entities3). Topological relations are thus consistently
transformed. Therefore, all multiple representation sequences built on the basis of such
operators are intrinsically consistent.
The model for a multiple representation sequence can be formalized as follows: let M bethe map at higher level of detail (stored on the server) and let f1, f2,., fk be an ordered
sequence of map transformations, i.e., a sequence of functions obtained as compositions
of atomic operators; let f1: M0?M1, f2: M1?M2,., fk: Mk-?1 Mkbe such that
f=fkfk-1. f2f1: M0?Mk
is a transformation of maps. The sequence M0 ,., Mk is composed of maps corresponding
to less and less detailed representations of the same area, and it is called a multiple
representation sequence (see Figure 8 for an example).

Figure

8: A multiple representation sequence with three levels of detail.
3 The formalization of aggregation of disjoint entities is traditionally a difficult issue, as this operation
might generate semantic and topological inconsistency. A tentative solution generates a fictitious ?shell?
containing the entities to be aggregated. However, this method has the drawback of forcing an arbitrary
partition (Dettori and Puppo 1996).
6. Encodings for Efficient Transmission
The efficiency of the model presented in Section 5 can be improved by defining
encodings that avoid redundancy between levels and by adding to it intra-level links to
allow navigation and browsing across levels. These issues are discussed in Section 6.1
and Section 6.2.
6.1 Data Structure
An important issue relates to the efficient storing of multiple map representations. Some
entities are preserved throughout the levels. Such entities should be stored only once in
the sequence instead of redundantly encoding them at each level. If such representations
are to be transmitted through the Web, reducing the amount of information to be
exchanged is highly useful. A straightforward way to avoid redundancy is storing the
entire set of entities only for the coarsest level, while all subsequent levels just record
newly introduced entities and more refined representations of entities present in previous
levels (i.e., the increments). This way transmission is also sped up; however, by not
storing the complete set of entities corresponding to each transmitted level, the problem
arises of defining algorithms for reconstructing the vector file corresponding to an
intermediate level, once the transmission has been terminated, to use, manipulate, and
query it. The problem lies in the computation of the spatial relations between newly
introduced entities and preserved entities. This problem does not occur if the purpose of
the transmission is just visualization. In such a case, only techniques for overlaying
graphical layers are necessary.
In the following we describe a structure for encoding a sequence M0 ,., Mk of multiple
representations in which entities are stored only once to avoid unnecessary duplications.
Such a structure is defined inductively on the basis of the inverse image of entities inside
each map (Puppo and Dettori 1995). More formally, for 1 ?i?k, given a submap Mi, j of a
map Mi , we consider each entity e of Mi, j such that its inverse image through fi contains
more than one entity in Mi-1 , i.e., e is not a preserved entity, its representation is more
detailed in Mi-1 . Mi-1,p= fi-1(e) is a submap of Mi-1 . The set of submaps of Mi-1
corresponding to all inverse images of entities in Mi that contain more than one entity
form level i-1. In this way, the map at the coarsest level (i.e., Mk ) is completely stored,
while only increments are stored for intermediate levels. In Figure 9 we show an example
of this encoding structure for the multiple representation sequence of Figure 8. Note that
entities that are preserved across different levels are represented only at the coarsest level
in which they appear (they are drawn as dashed in the intermediate levels in which they
are not stored explicitly).

Figure

9: An example of encoding structure for the multiple representation sequence of

Figure

8.
6.2 Adding Intra-Level Links
In this section we enrich a multiple representation sequence with links that connect
different representations of the same entities at different levels. We call such links intra-level
links or vertical links, since they provide the sequence with a hierarchical structure.
Keeping intra-level links facilitates the reconstruction of a representation at a given level
of detail and it allows us to know which are the entities that are being modified at
subsequent levels and which ones are preserved.An example of intra-level links joining
different representations of a river and a bridge at different levels in a multiple
representation sequence is shown in Figure 10.
level 3 river
level 2 river
bridge
river
level 1
bridge

Figure

10: Intra-level links joining different representations of a river and a bridge in a
multiple map representation sequence.
Intra-level links also allow for hierarchical spatial reasoning. In particular, in a querying
environment, the user can be interested in retrieving information at different detail.
Although a lower level of detail can be sufficient for processing a given query,
sometimes a more detailed answer is required. Maintaining intra-level links allows for
efficient navigation and browsing across the levels without having to query entire levels.
A query is initially performed at the lowest level and the result can be evaluated
according to a given user-defined criteria. If the outcome of the evaluation is satisfactory,
there is no need to query against a more detailed dataset. Otherwise, the intra-level links
are followed in order to find a satisfactory answer. Usually only links between entities
that belong to consecutive levels are kept. By combining them, also links between non-consecutive
levels can be obtained.
For the model described in Section 5, links between entities in consecutive levels are
formalized by means of the transformation functions defining the sequence (obtained as
compositions of atomic operators). Such functions perform generalizations of maps. The
inverse operation, i.e., the refinement of maps, can be formalized by ?inverting? such
functions. Although these functions are not injective, in Bertolotto (1998), the inverse
image of an entity in the co-domain of atomic generalization functions between cell
complexes representing maps has been characterized in such a way that an entity can be
refined through a small number of operations. Let p, l, and r denote a point, a line and a
region, respectively. It has been shown that the inverse image of a region can only be one
of the following sets:
? {r,r?,l} (i.e., the domain of operator region merge),
? {r,p} (i.e., the domain of operator point abstraction),
? {r,l} (i.e., the domain of operator line abstraction).
The inverse image of a line can only be one of the following sets:
? {p,l,l?} (i.e., the domain of operator line merge),
(i.e., the domain of operator region thinning).
Finally, the inverse image of a point can only be one of the following sets:
? {r,l,p} (i.e., the domain of operator region contraction),
(i.e., the domain of operator line contraction).
Therefore, we can define the inverse of generalization operators (defined in Section 5) as
follows:
? Point-region expansion: expansion of a point into a region (with its boundary)
p? {r,l,p?} (3)
expansion of a point into a line (with its endpoints)
p? {l,p?,p?}? (4)
? Line-region expansion: expansion of a line into a region (with its boundary)
l? {r,l?,l?}? (5)
splitting of a line into two lines sharing an endpoint
l? {l?,l?,?p} (6)
Region split: splitting of a region into two regions sharing a bounding line
r? {r?,r?,?l} (7)
insertion of an isolated point inside a region
r? {r?,p} (8)
insertion of a line inside a region
Basically, the inverse operations of contractions and thinning are expansions of an entity
into a set of entities including some higher dimensional entity. The inverse of merging is
splitting an entity into two entities of the same dimension, while the inverse of
abstracting an entity from a region is the insertion of an entity inside a region.
As for generalization operators, these refinement operators only perform minimal
changes. Thus, for example, in the line split operator, endpoints of line l are mapped onto
the corresponding endpoints of lines l?and l??(Figure 11).
p" p"
l"
l p
l'
p'                                                              p'

Figure

11: Endpoints of line l are preserved by line split.
On the basis of refinement operators, i.e., by considering inverse images of entities, we
enrich the model defined in Section 5 and encoded by means of the structure defined in
Section 6.1 with intra-level links. The resulting model has a tree-like organization. The
root is the map at the coarsest level of detail Mk . Each submap Mi-1,p that corresponds to
the inverse image of some entity e belonging to a submap Mi, j at level i in the sequence
is stored as a node and is called a child of M . An arc between M and M is
established and labeled e. The child relationship represents the refinement of a submap,
while the parent relationship represents generalization of a submap.
In

Figure

12 the example of Figure 9 has been enriched with intra-level links.
e
e"

Figure

12: Adding intra-level links results in a tree-like structure. Arcs are labeled with
the corresponding refined entities.
In the following section, an example of a multiple representation sequence and its
efficient encoding is described.
7. An Example
In this section, we describe an example of a multiple representation sequence with four
levels of detail (Figure 13). The coarsest level (level 4) contains the hydrographic map of
a given geographic area. This level includes the following set of entities {river, creek,
paper mill, lake, creek mouth}, such that river and creek are represented by lines, paper
mill and creek mouth (i.e., the intersection between creek and lake) are points, and lake is
a region. In level 3, the road network covering the same area is also represented: major
road, minor road A, minor road B, intersection AB, and bridge are added. The first three
entities are represented by lines. Intersection AB is the intersection point between minor
road A and minor road B, while bridge is the intersection point between major road and
river. Therefore, minor road A, major road and river are represented at this level as lines
split into two segments. Level 2 corresponds to a refinement in the representation of
paper mill, that is now a region, river, for which the thickness is shown (in both the
branches composing it), and bridge, that is now a line. All other entities are preserved,
i.e., their representation at this level does not change. Finally, the fully detailed map at
level 1 refines the shape of paper mill and shows the thickness of the two segments of
line that comprise major road, thus implying a transformation of bridge from line to
region.
In order to build such a sequence of representations to be stored on the server site, we
apply the generalization operators described in Section 5. For example, to obtain level 3
from level 2, the following operators are applied:
region thinning of river,
line contraction of bridge, and
region contraction of paper mill.

Figure

14 illustrates the structure described in Section 6.1 for the efficient encoding of
the multiple representation sequence of Figure 13. The set of entities in level i (for
corresponds to the increment with respect to level i+1. Entities that are present
at both level i+1 and i, and whose representation is refined at level i, are highlighted at
level i. An example is provided by river, that at level 4 is represented by a single line,
while at level 3 is composed of two segments joined by bridge.
Level 4 is completely represented, i.e., all entities together with their spatial relations are
stored in the encoding structure. For instance, the information that creek mouth is an
endpoint of creek is maintained. The set of spatial relations that are explicitly stored
depends on the particular data structure adopted to encode each map in vector format
(e.g., the extended DCEL structure defined in De Floriani et al. (1993)). Among the
entities present at level 3, only river (fragmented into two segments) and the newly
introduced entities (major road, bridge, minor road A, minor road B, and intersection
are encoded, as well as their spatial relations. At level 2, the only changes are the
refinement of paper mill, river and bridge. Only these entities and their relations are
represented. Similarly, at level 1, the encoding structure includes just paper mill, bridge
and the two segments composing major road. Intra-level links are also maintained
between different representations of the same entities at consecutive levels.
paper mill lake
river creek creek mouth
level 4
paper mill
lake
river creek creek mouth
major road level 3
intersection AB
bridge
minor road A
minor road B
paper mill
lake
river creek creek mouth
major road
bridge intersection AB
minor road A
minor road B
level 2
paper mill
lake
river creek creek mouth
major road
intersection AB
bridge
minor road A
minor road B
level 1

Figure

13: A multiple map representation sequence with four levels of detail.
paper mill lake
river creek creek mouth
level 4
river
level 3
major road
intersection AB
bridge
minor road A
minor road B
paper mill
river
bridge
level 2
paper mill
major road
bridge
level 1

Figure

14: Efficient encoding of the sequence represented in Figure 13.
8. Discussion and Implementation Issues
In Section 5 we have described a model for multiple map representations that can be used
for progressive transmission of map data over the WWW. The model is built on the basis
of a set of operators that perform topological changes on a map. Although such operators
have the interesting property of preserving topological consistency, they only modify the
topology of the map. However, in real implementations also changes in the geometric
shape of objects are commonly required, such as simplifications of lines (Douglas and
Peucker 1973). We are currently investigating the possibility of extending our model to
include this kind of operations. Changes depending on the semantic of objects should also
be allowed. The incorporation of semantic aspects is another goal of our current research.
A model for generating multiple map representations based on the Douglas-Peucker
algorithm and used for progressive transmission over the WWW has been described in
Section 2.2 (Buttenfield 1999). However, such a model has the drawback of not
guaranteeing the preservation of consistency. Furthermore, it only deals with line
simplification operations and does not allow other kinds of commonly used map
generalization operations (McMaster and Shea 1992).
Finally, as underlined in Section 2, a well known question related to the generation of
multiple map representations is the following: ?How many and what are the levels of
detail to be generated and stored?? The answer to this question strongly depends on the
application and on the particular task. For an implementation of our model, we plan to
analyze typical queries from different application fields to detect what the best levels of
detail are to provide satisfactory answers. Also, as underlined by Buttenfield (1989), it is
possible to detect the range of resolution at which some geographic processes become
evident. Such considerations will help decide what levels of detail need to be stored on
the server site.
In the following sections we discuss in more detail issues related to the implementation of
the model for progressive transmission proposed in this paper. In particular, we consider
the data transmission technique adopted (Section 8.1) and the reconstruction of datasets
corresponding to intermediate levels of detail downloaded on the client site (Section 8.2).
8.1 Transmission of Different Levels of Detail
In the solution we propose, the process of transmitting a multiple representation sequence
between two remote sites presents a few critical points. We assume to have a dataset d on
the server and a sequence of multiple representations of d corresponding to k levels of
detail, such that the higher the level, the less detailed the representation. We denote such
sequence by mr(d,k). We consider a transmission model in which the user is attempting to
download progressively the dataset d. Each level of detail corresponds to a separate
package. As described in Section 4, the process starts with the server transmitting the
representation corresponding to the first level of detail (i.e., the coarsest). We can
formalize such process by means of a binary operation t that takes a sequence mr(d,k) and
an integer i, with 1 performs the transmission of the representation
corresponding to level i in the sequence. Thus, the first step in the transmission process
can be denoted by
Upon completion of the transmission of the first package, the server continues the
transmission of the subsequent representations in order of increasing detail until the user
decides to stop the process. We indicate this sequence of steps with
In order to avoid unnecessary repetitions for storage saving purposes, in the encoding
structure for the model described in Section 6.1, given a representation corresponding to
a level i (0<i<k) of detail in the sequence, only the entities that have been modified are
stored at level i-1. Not only this model saves space on the server site, but it also speeds up
the transmission to the client site, i.e., it minimizes network traffic. On the server site the
coarsest representation mr((d,k),k) is completely stored, while only portions of the
subsequent representations (increments) are stored in the subsequent levels. Thus, the
size of the transmitted packages is reduced. On the client site, a new buffer is used to
store the increments to be integrated with the previously transmitted representation. From
a graphical point of view, such a buffer can be used as a graphic layer to be superimposed
on the previous one in order to completely display the representation at the new level of
detail. From a more operational point of view, ad hoc integration techniques must be
developed (such as for reconstruction of the topology of the dataset, discussed in next
section).
A further way to increase the granularity of the transmission is to send subparts of the
increments that are topologically disjoint (corresponding to nodes in the tree) as separate
packages. This way, topological consistency is still preserved and even smaller packages
are transmitted. Also, the user would have the possibility to decide to increase the detail
of only some subparts of the map (i.e., to decide to download only the subtrees
corresponding to the interesting areas), thus generating a representation at ?variable?
detail (the so-called selective transmission). Entities belonging to different levels of detail
would coexist in the representation reconstructed on the client site. We are currently
investigating this interesting aspect.
An important issue concerns the transmission of intra-level links. As discussed in Section
6.2, during query processing, multiple representation sequences benefit from the addition
of intra-level links between different representations of the same entity at different levels
of detail. A query is first performed at the coarsest level; if the result is unsatisfactory,
intra-level links can be followed to find a better answer. In this way we do not need to
query the entire following level. Furthermore, as discussed in next section, intra-level
links facilitate the reconstruction of the intermediate levels. Thus, such links must be
encapsulated in the transmitted packages, in the form of pointers, in addition to the new
entities to be displayed in the overlayed buffers. Each transmitted entity maintains a
reference to (the ID of) its parent in the previous level.
8.2 Reconstruction of a Dataset
Once the user at the client site decides to stop the transmission process, because the level
of detail of the currently displayed representation is good enough, the dataset
corresponding to that intermediate representation must be reconstructed. Such a dataset is
not stored explicitly (i.e., as an independent representation level) on the server either.
Thus, on the client site, integration operations are needed to compile a consistent
representation at a given level of detail from the collection of displayed layers.
Operations for deleting entities in the previous layers as well as for adding new sets of
entities (belonging to newer layers) to substitute them are needed on the client site.
Furthermore, spatial relations between newly introduced entities and preserved entities
must be computed. This operation can be very time consuming.
For the hierarchical model we consider, i.e., the sequence of multiple representations
described in Sections 5 and 6.1, enriched with vertical links (Section 6.2), a complete
representation corresponding to a given level of detail can be obtained by means of a visit
of the tree. The visit includes all nodes up to the desired level: entities contained in a
given node are deleted and replaced by the set of entities corresponding to the child of
such node (i.e., its refinement). The visit of the tree can be performed on the client site as
vertical links are transmitted together with increments (i.e., nodes in the tree) in the form
of pointers (as discussed in the previous section).
Due to the intrinsic consistency properties of the model (in terms of preservation of
topology), topological relations between two entities e and e?at level i can be
reconstructed on the basis of relations between entities that are parents of e and e?at the
preceding level.
As an example, we consider the sequence of multiple map representations shown in

Figure

13. Such a sequence is stored on the server and transmitted progressively. For
each transmitted level, the client receives only the increments and the intra-level links. In
this example, only level 4 is completely represented. Therefore, intermediate levels must
be reconstructed on the client site. For instance, to reconstruct level 3 from level 4 and
the increment between levels 4 and 3 (including: the refinement of river; the new entities
bridge, major road, minor road A, minor road B, and intersection AB; and the set of
spatial relations among them), the following operations must be performed:
? the line representing river at level 4 must be substituted by the two segments that
share bridge as an endpoint;
bridge, major road, minor road A, minor road B, and intersection AB must be added
as new entities; and
? the complete set of spatial relations for level 3 are reconstructed in a straightforward
way as union of the set of relations between preserved entities (stored at level 4) and
the set of relations between newly introduced entities (included in the increment
package).
9. Conclusions
This paper discusses the need for progressive vector transmission, by which a user is
provided with coarser versions of the data while she is downloading a large vector file
from a remote site. This process presents inherent challenges. Extracting a consistent
representation at a lower level of detail from a vector map dataset is a complex and time-consuming
operation that cannot be performed on-line during progressive transmission.
A solution is to pre-compute, on the basis of sound cartographic principles, a sequence of
multiple representations of the data to be stored on the server site. Each representation,
corresponding to a different level of detail, is transmitted separately. This solution has the
obvious drawback of requiring preprocessing. However, multiple representations can be
utilized to define structured digital libraries of summaries of geospatial data. Such
organization enables efficient access and manipulation of such data over the WWW.
Our contribution is a solution to vector map data transmission, based on a distributed
architecture. A model generating multiple map representations (Puppo and Dettori 1995;
Bertolotto 1998) that can be used for progressive transmission is described. The model is
built by applying a set of generalization operators that perform atomic topological
changes on vector maps. The defined operators guarantee the preservation of consistency
(Bertolotto 1998), an essential property for the usability of generalized data. Our future
goal is to extend such a model to include metric and semantic aspects as well as to
develop alternative models and to compare them in terms of storage and transmission
costs. The development of efficient encoding strategies plays a central role in this
framework.
In a more general setting, we are planning the design of a heterogeneous and distributed
geographic information system integrating data in different formats (e.g., raster, vector,
and textual) and retrieved from different sources. The system will include distributed
Internet archives in the form of digital libraries of generalized geospatial data for fast and
efficient use. Different formats of the same data will be automatically chosen by the
system to perform different tasks on the basis of efficiency. For example, rasterized
(scanned) versions of maps will be provided to the user for mainly visual purposes while
the corresponding vector versions will be progressively transmitted if actual object
manipulation is required. Several aspects will be integrated in the data including spatial,
temporal and semantic aspects to allow a wide range of operations and analysis.
Another essential requirement of contemporary information systems is related to the
concept of interoperability, i.e., the capability of autonomous systems to exchange data
and to handle processing requests by means of a common understanding of processes and
requests (Sondheim et al. 1999). This can be achieved if common representation models
are used (UCGIS 1996). In GIS, data modeling plays a central role in the framework of
interoperability, as agreement at the representation level is critical for exchanging
geospatial data. Therefore, the design and implementation of our comprehensive Internet-based
archive, will meet interoperability and standardization requirements as defined by
the OpenGIS Consortium (OGC 1996a and 1996b).
10.


--R



http://king.
Fractals Everywhere





















Fractal Image Compression: Theory and Application to Digital Images



Digital Image Processing










Generalization in Digital Cartography


(eds.), Taylor and Francis

OGC (OpenGIS Consortium)
Computational Geometry: An Introduction

Elements of Cartography

The Design and Analysis of Spatial Data Structures
Applications of Spatial Data Structures



UCGIS (University Consortium for Geographic Information Science)






--TR

--CTR
Alexander Kolesnikov , Alexander Akimov, Distortion-constrained compression of vector maps, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
Qiang Han , Michela Bertolotto, A multi-level data structure for vector maps, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA
progressive transmission;multiple representations;vector map data