Map Adaptation for Users of Mobile Systems

Figure 1: Extract From Class Model For Representation Of Maps

2.1 Selection of Information

As mentioned in section 1, there is a need for users to select specific information to be displayed. Current solutions for web based applications fall into three broad categories:

• Specific types of data may be restricted. This restriction is generally implemented as a binary selection on the client application, e.g., the "no images" selection commonly found on web browsers.
• A weighting is defined for a specific encoding format (e.g., GIF = 0.9, JPEG = 0.8) or text language (e.g., French = 0.8, English = 0.5) to indicate the user's preference or capability of the user's device. These weights are generally used in a selection mechanism provided with the data request [7,8,9].
• A standard transcoding may be applied to data in order to provide it in a particular format, or to meet device restrictions. Commonly image size and colour depth are adjusted to meet the needs of restricted client devices. These transcoders are generally implemented as in-network proxies offering transcoding for a small range of target devices [6].

These techniques suffer from significant limitations, particularly for the class of applications we are studying. Where structured data are being used, selection according to the data's encoding format is unlikely to fully capture the user's needs. In web browsing it may be sufficient to say that one prefers particular languages, or that one dislikes images. However, for a vector map, format selection based on encoding format does not perform a meaningful selection. Where a large amount of information is contained within one encoding format it is desirable to be able to express preferences related to the semantics of the information, i.e., display roads but not contour lines where both may have the same encoding format.

As the range of device capability and tasks expands, it is undesirable for content providers to be obliged to provide many different versions of their content, each adjusted to a small range of devices or users. However, the user is best served by data which is finely adjusted to their needs. A mechanism for content negotiation which allows for general specification of requirements is needed. Many other proposals for media selection in response to context or resource constraints are applied to each element of the data separately [7]. This per-element selection limits the range of possible trade-offs, and does not allow for consideration of the interaction of the various data elements within the whole document presentation.

The network link capacity may also restrict the amount of data which can be transferred in a reasonable time, leading to long and variable delays between a request for a map tile or web page and its display. For many tasks timely data provision is key. A data selection mechanism should therefore enable deadlines to be met by restricting the data selected. Deadlines may be due to a number of factors, such as the user's patience, and the need for timely display due to movement. The first case is a simple one experienced for many applications, and often cited as a source of irritation in web browsing. The second is most relevant during mobile use, where a map segment must be displayed in advance of needing it, e.g., in a car, a navigator prefers to understand the layout of a junction in advance of reaching it, in order that the driver can be given clear directions. Conversely, old data may give out-of-date information, as congestion can change quite rapidly on roads. Deadline-based selection may be achieved in a similar manner to the selection according to display capability and the user's requirements and must be performed in conjunction with user preferences. For more capable devices the network connection may be the most significant limiting factor in selecting data.

We are addressing the use of map data, both general and specialised, in specific tasks. The restriction of the domain gives the user a clear means of identifying what information is relevant. The restriction of the data allows standardised descriptions of the semantics of the content to be developed. Similar techniques may be applied to less restricted domains, once suitable and commonly understood task and data descriptions are developed. Where the user base and information are well controlled, such as licensed databases or corporate networks, the definition of the tasks and descriptions is also clearer, these techniques can be extended to other information retrieval problems.

3.1 Interaction Process

In summary, the process of retrieving data, illustrated in figure 2, is:

1. The application makes a request to the QoS manager. The QoS manager requests the meta data.
2. The server's response describes the various elements of the data, and the variants of those elements it has to offer. The server, when responding with meta data, may make a provisional reservation of resources, based on the variants offered. In cases of high load it may adjust its offer.
3. Any intermediate nodes (proxies) append to the meta data and pass it on. The addition advertises their capability to modify the data (e.g., add traffic information, compress data, or text language translation).
4. The client receives the meta data, and makes a selection amongst the variants. It reserves sufficient resources locally to support the request.
5. The request is then passed back, the proxies and any low-level resource management capable network elements also making reservations. The server then adjusts its reservation to reflect the chosen variants.
6. The data requested is returned to the client, passing through any proxies whose services were selected.

3.2 Meta Data

Document authors (or their agents) describe the structure of the document's elements and their variants, and the objectively measurable attributes of the variants. Each element of the document can be represented by one of a set of variants, and/or refer to a more specialised element. Variants represent data with a similar purpose, but differing characteristics. For instance, features may be presented with different minimum feature sizes, corresponding to the level of detail presented at different map scales in the paper world. So, a change in scale can affect both feature inclusion, and detail in the description of features. For instance, roads may be presented in variants which show progressively more detail such as small bends. Variants may also be used to encode data in different formats, e.g., maps may be presented using vectors or rasters. In addition meta data will describe system-level properties, such as size (bytes).

An element can be described as containing other elements, to enable the description of the various components of a structured document. For instance road information on a map may be represented by the basic road definition, and an optional contained representation for the labels identifying the road. More detailed basic representations might contain further contained elements, e.g., boundaries of the road (e.g. wall, hedge, open).

In general, new elements should be introduced to contain semantically different information, and variants should be used to offer different quality versions of the data. Variants are units of data which may be individually requested. There need not be a 1:1 relationship between element instances and variants. Meta data describes the instances and relationships such as those shown in figure 3, of the class model, as described in figure 1.

Figure 3 illustrates four variants (roads1v, mways1v, mways2v, m1v), each of which represents the "M1" motorway, and in all but one case other feature instances as well. If one were only interested in the "M1" motorway, one of these variants would be selected for retrieval from the server, and any possible elimination of unwanted features made locally. Instances of elements may be anonymous, such as for "Minor Road" and "Road Label", where the name is "*". This notation describes a container element for all instances of the type, without the need to explicitly identify each one. This is useful where there is no clear identity for many small features, or in order to trade smaller meta data for expressive power.

3.3 User Specifications

The user (or their agents) define their preferences for element types (what semantic part it plays in the document, e.g., road, vegetation, administrative boundaries); various media encoding formats (such as text, image, vector-map, etc.); how they perceive the quality of the presented data to vary according to its attributes, including limits of tolerance for low quality and of perceived improvement for high quality; and goals in the presentation, e.g., download time.

Users specify their preference for elements of a particular type by associating a weight with the type, for instance, to describe a preference for displaying information about roads rather than rivers. The following type, value pairs define the default weight for any type to be 0.1, for roads to be 0.4 and for major-roads to be 0.7. Higher numbers indicate stronger preference.

type=*: weight=0.1
type=road: weight=0.4
type=major-road: weight=0.7

The types are structured through specialisation, and one weight definition may supersede another where one defines a weight for a general type, and another for a more specific type. Based on the above preferences, the following 3 element types would be allocated weights as shown below. A minor-road takes the default weight for roads, and vegetation takes the default for all other types. A variant representing several elements takes the highest weight of those elements.

type=major-road => weight=0.7
type=minor-road => weight=0.4
type=vegetation => weight=0.1

The encoding format weight defines a preference for different syntactic representations of data in a similar manner to the type weight. We have limited the data encoding format to NTF (a vector format for maps) in our current work, and so we shall not discuss the use of this weighting further here.

Preferences for different variant representations of an element are defined using a utility function applied to the parameters of the variants, similar to that in [11]. For example, a low resolution picture will be very grainy, a medium resolution picture will display well, but a high resolution picture will be too large for the screen size, requiring scrolling to view it. To capture the effect of these limitations the perceived utility function would be defined in terms of the resolution parameter of the picture variants. We describe our use of utility functions in more detail in section 3.4.

The utility function is associated with parameters, which are generally specific to an encoding format. In the case of maps, we have an encoding format specific handler that understands meta data relating to survey scale. Differing scales imply differing levels of detail in the representation. For maps, the utility function may relate to both encoding format and type, e.g.:

(encoding format=map/*, type=*, parameter=scale): uf=uf_gen_scale
(encoding format=map/*, type=road, parameter=scale): uf=uf_important_scale

In this example uf_gen_scale may describe the scale as acceptable over a wide range, but for uf_important_scale the utility returned may fall off much faster with increasing scale. An element of type road, or any sub-type would take the more specific utility function, "uf_important_scale".

For parameter based utility, the encoding format must be at least partly known, as parameters are specific to an encoding format, e.g., survey scale is only a meaningful parameter for map data. When defining utility functions applicable to a general encoding format, e.g., "parameter = "scale" for encoding format = "map/*", it is not necessary to re-specify that definition for more specialized formats, e.g., "map/ntf", unless different behaviour is required.

The number of utility functions can be minimised by operating at the most general encoding format level available. A default utility for an encoding format and/or type is given, to support the case where no measured parameters are available. For default utility the greater of the utilities due to encoding format and type is taken. It should be clear that these utility functions do not say anything about the perceived importance of roads within a map.

If one were navigating it is likely that the "road" data would have a high type weighting. However, a tourist might be less interested in the detail of the road than in historical monuments and restaurants, so loading unnecessary detail would delay the loading of more important information over a wireless network, and clutter the display. Utility functions over parameters can aid in describing these preferences. When defining user preferences it is important to be clear whether one is describing the importance of a feature (type weighting) or the effect of the representation quality on the perception of the data (utility function over parameters of a variant).

The final part of the specification is rather simpler. This part describes goals, or constraints, over the document retrieval. To date the only goal we have worked with is a download deadline. Where bandwidth is limited with respect to the download deadline this has the effect of constraining the variants selected. We describe our process for selecting variants in section 3.5.

In figure 4 we illustrate a user specification, giving type and encoding format weights, a deadline, and utility functions to be applied over the scale parameter for different types, and a single function to be applied over the survey date. The type weight specifications describe a preference for road features over water features, etc. Here the most specific weight for a motorway is for road, which is a super-type of motorway. The utility functions over scale may describe a perception that the loss of utility with increasing scale is greater for topographical details than for roads. For instance, a hiker will want considerable detail to navigate safely through an area with cliffs, whereas a loss of precision in the description of a road is less likely to be dangerous. Similarly the utility function over the survey date would indicate that up-to-date data are to be preferred.

Our use of weights and utility functions may lead to a somewhat complex description of requirements, which are inappropriate for "average" users to create or edit. However, we believe that having specialist rule creators provide rules for users who possibly only select between a few sets of rule classes would be an appropriate solution. A selection of utility function combinations due to device and task might be abstracted by a higher level user interface. In the context of the map viewer application we have been developing, the restricted problem domain assists in the specification of effective preferences. The selection of utility functions, weightings and goals should be context dependant. Thus the need for context aware resource management, and the possibility of context-dependant applications raises the need for some automated system-wide context awareness. Task, device and location awareness are our immediate focus.

Further examples of how we envisage context to affect utility functions, weightings and goals are given below:

• When the cost of the link is great, such as for mobile phones, goals can be defined to reduce cost. Possibly correlating cost to overall utility. The assumption being that one is prepared to pay for more interesting data.
• Location and proximity information may cause changes in behaviour. For instance, "in the car" may be identified as placing some urgency about fetching map data. Utility functions, encoding format and type weightings may also be varied to achieve more suitable data presentation.
• When using a screen of restricted colour capability, the utility functions over colour depth may reflect this. Rather than taking the user's limit for perception of colour depth, the screen's ability to render colour defines the limit.
• When driving a car, audio data (or text which can be rendered as speech) may be preferred over visual data. Where data has to be graphical, key information will be rendered as highly important, but detail will quickly be described as unimportant, to avoid distraction.

3.4 Utility Functions

A key part of the selection process is the calculation of utility scores for variants. We shall now illustrate a simple slope utility function. Other functions describing "s" curves, or which indicate an optimum value range may also be used. To illustrate the use of utility functions based on types of data, we shall illustrate possible variations from our example map. For in-car navigation various features are relevant. For roads, one might define utility functions relating to scale as depicted by the solid line in figure 5. Here a lot of detail makes the map harder to read, while a large scale is often still useful. For hikers, there might be less of a tolerance for the loss of detail of bigger scales, but more time to read and use the greater detail of the smaller scales. The dashed line in figure 5 illustrates this different perceived utility. Our illustrative graphs are not based on user studies, but show intuitive trends we might expect.

Figure 5: Example Utility Functions for Scale

Our use of utility functions is similar to their use in rating utility of more common multimedia encoding formats. As the size of an image increases its utility may rise, in general. One might qualify this specification to have utility fall off once the image started to become larger than the display could show at one time. This general utility function might be overridden for types of image such as icons and logos, in order to load images whose size is appropriate to the display (unless it is actually the logo one in interested in). Other formats may require discrete functions, for instance, over the language of text, e.g., a native English speaker may give a high rating to "english", and a rating of 1 to their local english dialect, e.g. "english/uk". Second languages would return a rather lower value, and languages of which one has no understanding would return zero. This use of weights has a similar effect to the explicit weightings found in some other approaches, although the mechanism is more general.

A discussion of the use of utility functions across multiple media dimensions to control QoS adaptation is described in [11]. The model they describe concentrates on providing QoS for a video stream. Our approach contrasts with this in concentrating on multi-element media. In our case we have two dimensions for trade-off: we may select sub-sets of information to be represented, based on the semantic content of the information; and also between different representations of that information, based on the perceived utility of the representations.

The variant may take a utility function on each parameter understood. Specifications may not always match all parameters. Where variant handling of parameters, or utility function specification for a parameter, or meta data for a parameter are not available, that parameter is ignored. The following information is used to calculate the utility of a variant:

• Parameter utility limits: at what point do changes make no perceived difference (as good as it can be, or too bad to be worth considering). From these values, the correlation between value and utility may be inferred.
• Utility / parameter function rate: how does utility vary with respect to the parameter's value.

The utility ratings for the various parameters are combined to derive a final overall intrinsic utility , ui , score for the variant. As each parameter utility value, u(p), has been normalised to between zero and one, we simply multiply all utility values together for each variant. The use of a product function has the benefit that any variant which is unacceptable in some aspect (zero utility) registers as a wholly unacceptable variant. The comparison may need adjustment when comparing between encoding formats which have different numbers of parameters. The effect of successive multiplications will be to degrade the utility reported in comparison to another encoding format for which fewer parameters have utility functions defined. We suggest that some value, say the mean of the various u(p) values, is taken and used to provide a comparable number of parameter utilities for the product.

The utility rating is then scaled according to the media encoding format, wm , and type of element, wk . We call this the adjusted utility for the parameter (see below).The adjustment allows for preferences to be described between forms of representation and parts of a structured document. Note that any change in the utility function due to encoding format and type still results in a utility function returning between zero and one.

3.5 Selection Process

We require that our system choose between an arbitrary number of alternative representations of a compound document, each element of which may vary, e.g., a map page may consist of roads, contours, water features, etc. Each of these may be built up from basic information and additional detail. It is likely that more than one of the offered variants for any element would be acceptable in principle.

It is, however, desirable to provide the best possible presentation, which would be context dependant. The selected variants should maximise overall utility, and present data in a consistent and predictable manner. In addition, other goals may have to be met, such as a deadline for the map download. We may derive the deadline from the estimated utility of the data: how "interesting" it is may determine how long we are prepared to wait for it to download.

Initially the highest utility variant representing each element is selected. Where multiple variants have the same utility the one which makes the smallest resource load is chosen. The selection function makes a note of the selections on the meta data graph, and provides a summary of the selected variants. From this selection the total resource requirements are calculated, and requested. The resource manager's admission function will take the resource requirements and goals (e.g., deadline) and test its resource model to see if the request can be admitted. If the admission request is accepted then the reservation model is updated, and the data requested. If rejected the resource shortfall is returned. The shortfall is incorporated into the goals, e.g., reduce data volume by 10kB.

If admission is denied, a search is then performed to satisfy the additional goal, while maintaining quality. For each element, its variants are ordered by descending utility. Where utility is zero, the variant is considered to have no value, and so is omitted from the selection entirely. Where an element has no variant any elements it includes are also omitted. Where contained elements which would be lost have a higher type weighting, the containing element is promoted, e.g., where road labels have a higher weighting than roads, the roads will be promoted to the weighting of the labels rather than be lost (degraded to zero utility). The roads and labels may be removed together if the degradation algorithm progresses to degrading the labels. It is likely that multiple solutions to the goal will exist, consisting of differing variant selections over the various elements. Our selection algorithm is designed to embody the following aims: To degrade the least interesting elements rather than more interesting ones; to maintain consistency between the presentation of elements of the same type; to incorporate utility due to format and parameters in the selection; to avoid loss of elements where possible; to cease degradation once the goals are met and then perform a test for potential improvements to regain lost utility, improving higher weighted elements first, and reversing element loss by preference. The algorithm is illustrated in figure 6.

While this approach will not (in general) result in the optimal use of available resources, it does seek to limit unnecessary adaptation. By grouping elements by type, degrading the least important elements by preference, and reinstating utility to the more important elements by preference once resource requirements are met, user satisfaction should be maintained, and consistent behaviour experienced. A more in-depth analysis of selection algorithms for resource management is presented in [12]. An illustration of the use of our selection technique is presented in section 4.

3.6 Resource Management and Monitoring

For wireless networks, where the underlying QoS is highly variable, monitoring feeds into the network resource models. As a model of effective parameters is built up, the admission function can provide more accurate guarantees. These models of resources will never provide a guarantee of resource parameters. However, by improving the accuracy, application level QoS management can improve the predictability of its behaviour.

Our resource management is provided with a simple time-sliced model. We have only implemented bandwidth management to date. Each time slice (100ms was used in the tests described here) has a capacity and one or more reservations associated with it. Resources are applied for as a data size, start time and end time. If the data / time is greater than the model of available bandwidth, the size difference required to satisfy this basic constraint is calculated, and returned with the rejection. Otherwise reservations are applied to each time slot in turn. Any shortfall, for instance where some other request already has reservations in that slot, is divided over the remaining slots. If the request can be fitted into the model, admission is granted. Otherwise the shortfall is returned, and the prospective reservation removed. At this time we have not implemented any interfacing from this application level model into lower level resource models, or network QoS control mechanisms. The technique presented relies on sufficiently large data loads to make accurate measurements. Further accuracy could be gained by making use of the measurements commonly performed within the network protocol stack, however our results are satisfactory at this time.

Resource monitoring is provided by the application. Each request (element request or meta data request) is supported by a thread which handles the connection establishment, reading from the buffer and timing. Once a minimum size of buffered data (or end of file) has been reached, the buffer is passed to the application. In the case of map data partial data may be parsed during data loading. Any data which the parser cannot use is pushed back to the loader. The application measures round trip time and effective bandwidth for the meta data load and the full collection of elements to be loaded. The round trip time is measured as:

Request and reply times are measured as the application calls the HTTP API's "get" method, and as the data is read from the buffer. The reply size is considered in calculating the round trip time, as a significant volume of data may be delivered in the first reply to the application. As a multi-part document may be loaded, the interaction of the various requests is hidden by considering the whole of a group of requests. The use of first request, first reply and last reply achieves this combination. The bandwidth is measured as:

These values are reported to the resource manager, and the models updated. Firstly, a decaying average model is updated at a given ratio of new to old value. Typically we use 10 to 20% new value. Secondly, a recent history is updated. We typically keep the values of the last four loads. A recent average is calculated. If this is found to be a long way from the decaying average value the decaying average is set to this average value. The difference might be less than one half or over double. This aims to provide a faster response to large changes in monitored values, or a large deviation from some initial assumption. We do not present tests of the responsiveness of this monitoring mechanism here.

Table 2: Experimental Data Set and Specification

Type Weight	Type Specified	No. of Elements	Total Size of Elements (Bytes)
.75	road	2	55820
.73	road-name	1	2189
.66	water	4	4922
.53	fence	1	92765
.50	building	3	65234
.41	topology	4	29537
.23	vegetation	6	7736
.10	survey	1	1053
.09	building-name	1	7594
.04	boundary	1	1386
.03	*	4	46755

We used an unmanaged viewer, based on the managed viewer as a control system. For each simulated network we used the managed viewer with a range of deadlines, and the unmanaged viewer. The deadlines used were a sub-set of 5,10,15,20,30,45, and 60 seconds.

We stopped performing tests with increasing times when we reliably loaded all elements at a lower time. We did not apply shorter deadlines where these deadlines had resulted in very low-quality selections (approaching failure to select any data) at a higher bandwidth model. In the results presented only the lowest one or two bandwidths tested for each deadline show data which we felt to have little actual value to a user.

The 10 loads at each bandwidth / deadline model were performed sequentially. For each new model the servlet environment was restarted, and an unmeasured load performed to allow it to initialise. At the start of each managed load the resource manager's history was cleared, and the bandwidth and round trip times set to the nominal bandwidth, and explicit delay in the simulation settings. While there was some adjustment to experienced rates and delays in the test series, the inclusion of the earlier tests does not significantly alter the results. The resource management and monitoring's ability to measure and adjust to change is not described here.

5.2 Deadline Satisfaction

We present here the results of the timings of map downloads in various conditions. It should be remembered that the goal of our selection algorithm was not optimum resource usage. The overall results are presented in figure 7, and a detailed view of these results for longer and shorter deadlines are presented in figure 8.

There are three key measures of our ability to meet deadlines in these results:

• For a given deadline, its result line should be below that time on the y axis.
• Where the unmanaged viewer can beat the deadline, the managed load time should be as close as possible to the unmanaged time.
• For the majority of cases, at a given deadline, the managed time should be below the unmanaged.

These three tests embody simple principles: firstly, if a deadline is to be specified it needs to be met most of the time to be meaningful. Times close to the deadline imply that the resources available are being taken advantage of, but are not a test of the quality of the selection. Secondly, while we expect the management to have some overhead, it should be minimised as far as possible. Thirdly, if management does not offer some advantage in the majority of cases, then its benefit is questionable.

In figure 7 we also note that the straightness of the line for the unmanaged browser indicates that the server is not meeting any limit in the system's ability to provide accurate inter-packet delays. At the 200kB/s simulation we are approaching two limits: firstly, the millisecond timing resolution of inter-packet delays, and secondly deadlines of sub-5 seconds start to become unrealistic for the class of applications we are considering. As can be seen from the results, we do in general satisfy these requirements. The variations from smooth lines seen in the timings, particularly at 2kB/s, can be attributed to the grainy nature of the selection algorithm and data set.

In summary, we find that for the volume of data involved, across the range of bandwidths modelled, the management technique is useful. The shorter deadlines are only applicable at higher bandwidths, and at higher network speeds the benefit of management is marginal. However, the overheads experienced are generally quite small, and the comparison of the managed download times to the unmanaged times at 20kB/s and below shows clear benefits. The question of how useful the data chosen are then presents itself, and shall be addressed below.

5.3 Data Utility

We now consider the quality of the results produced. Our application and specification tools lack the necessary user interface sophistication to make effective tools in a user study. However, by measuring factors in the selections made we believe we can draw some general conclusions about the quality of the data loaded. In the results presented some steps are seen, as for the timings. Again, these can be attributed in part to the grainy selection over the data set used. Repeating the tests over a number of map tiles, and with a more detailed specification would reduce some of these effects.

There are a variety of tests of data quality which might suggest themselves. Others such as [13,14] have used the premise that the volume of data corresponds to overall utility. It is true that there has to be some correlation, and for some data encoding formats they are more directly related than here. In general 10kB of data will provide a greater volume of information than 1kB, and where these represent to variants of some element it is likely that the 10kB version will have greater utility.

With reference to table 2 we can see that for any given rating of importance there are data elements small and large, at each end of the importance scale. However, the utility imparted to the user by 1kB of uninteresting data is unlikely to equal that imparted by 1kB of interesting data. The graph of data volume decaying with deadline and bandwidth model in figure 9 therefore illustrates successful selection to meet deadlines rather than giving any great insight into the quality of the data presented. We also see the overhead in terms of data volume, by comparing the total size of the unmanaged data with that of the complete loads under the managed presentation.

Figure 9: Total Data Size for Varying Bandwidth and Deadline

We then examined the selections in detail, to observe the effects of the different sized data and the specifications on the data presented. We present in figure 10 a binary selection indication for the different specification type weights. The results are for a typical selection for each deadline in the 10kB/s simulation. At this data rate we observed full selection only at 60s, and a progression through to a marginal selection at 5 and 10s. The results shown therefore cover the full range of overall presentation qualities. This representation is also rather easier to comprehend and make comparisons with than 7 small screenshots. From these results we see that the selection algorithm is behaving as expected: selecting higher type weight data in preference to lower weight data. These results are generally meaningful only in correlation with the specifications, and require a view of the data to fully understand (see tables 1 and 2). The variants for fence, building, and topology contain large volumes of data, which explains the jump observed around the selection of the corresponding elements.

Figure 10: Example Selections for 10kB/s Model

We see in these results that the less important types are quickly dispensed with. However, the most important types- roads, road names and water -all remain present in all but the final two stages. This loss corresponds to our experimental procedure of abandoning a deadline once the results became too degraded to be useful. We see that the 3rd, 7th, 8th and 10th (by type weight) elements are always included, being relatively small. In most cases, treating at most one type-level omission within the first three type levels as acceptable, we find that any given deadline from our range gives a selection of all (or nearly all) features at some point in the bandwidth range, and at least two degraded but useful results. For longer deadlines the complete result extends to higher bandwidths, for a sub 5% overhead in download time. So, each deadline is valid over at least one order of magnitude bandwidth model. While the unmanaged viewer always gives a complete result, at any modem rate connection (sub 5kB/s) the time taken to download exceeds all our tested deadlines.

Our approach differs from mathematical or data encoding based compression to achieve QoS management. Data size may in some way correlate to presentation quality. However, the quality is still acceptable (by our definition above) after the size has fallen to 30 to 50% of that at the complete presentation. An algorithm which degraded without regard to the impact on the user would, in general, loose quality even faster with respect to data volume, by indiscriminate degradation. For instance, for JPEG of sample maps degraded from a quality factor of 80 to one of 50 (approaching the limit where detail remained acceptable), the data size was still 60 to 70% of the higher quality version.

6.1 Meta Data and Adaptation

Unlike many other approaches, e.g. [7,9,14,15], no quality rating is provided by the authors of the data or meta data in our approach. The meta data provide only an objective description of the data. The QoS management applies its own utility rating to the data. Our approach places a burden of complexity on the user to specify their QoS requirements in detail. However, we believe that this complexity may be hidden from the average user through the use of parameterised specifications authored by specialists for particular classes of users and tasks. The content provider's loss of control is balanced by their ability to specify the type of data represented (which is often the underlying theme in justifications for abstract quality ratings by the provider), and to limit the variants provided. The benefit is in enabling users of diverse devices with diverse interests to access data, for a small overhead in the data provision process. The effort required to produce meta-data is significantly lower than that required to hand-tailor data.

[15] includes the use of a "role" in the context of adapting web pages, along with an "importance value". They suggest that the client may use these in allocating resource limits for data volume and screen area. Their motivation is the ability to describe data for modification (by proxies) to provide for display on restricted devices, in particular by splitting web pages into sub-pages. Our approach is more general, in that the relationships between the elements of the maps are not generally a matter of sequence which need to be satisfied in their display. Also, the rating of the elements is not included in the meta data. The issues of sequence discussed in work such as [15,16,17] is necessary to consider when applying these techniques to other application domains and media encoding formats.

6.2 Negotiation and Selection Techniques

The approach described supports a more general mechanism for selecting "important" data than the layered approach often adopted in media scaling, e.g., MPEG, and [18]. By addressing structured data where different semantic data or levels of representation are explicitly separated out, the improvement/degradation path can offer rather more choice than a sequence of layers. In the case of maps, it is also possible that a layer definition would not suit all users of the map.

One popular approach to limited resources is connection to the wider networked world through some transcoding mechanism, e.g. [6]. These commonly provide a fixed adaptation to known device characteristics. This approach is included in our model, through the use of intermediate nodes which advertise their capability through meta data. The advertisement has the advantage that use is not tied to particular classes of devices, and does not require separate effort to produce documents tailored to specific devices. This approach facilitates the use of emergent devices, while allowing specialised data to be used where the effort has been taken to provide it.

There is work on content selection being undertaken in various standards [7,9,8]. These approaches generally describe the hardware and software capabilities of devices, and limited preferences of users. The user preferences catered for are primarily binary switches or exact matches, e.g., for selecting language. The suggested interactions for applications such as web browsing are that the client sends a minimal specification at the start of a session (with a given server). These techniques suffer from a potential scalability problem, in that the server must hold a description of all recent clients, and perform selection, in addition to delivering data. These protocols also seem limited with respect to allowing a rich description of user preference in addition to device limitations, or describing perceived quality over parameters which may take a wide range of values, although it provides a clear means to express limitations, particularly with respect to devices.

CMIF [16] and SMIL [17] describe temporal and spatial behaviour of a presentation, and have similar constructs for describing multiple variants of media elements in a structured presentation. The selection may be subject to a test on various parameters of the system in SMIL. CMIF focuses on providing alternative content for various contexts or user abilities, as defined by the author. In both cases, the result is that the selection of alternatives is limited by the authored selection support. Our approach takes similar approaches to whole document adaptation, and supporting a range of alternatives for elements. However, we believe that our method offers a more flexible approach for emerging system and user classes.

Our approach to selecting data according to its properties has similarities to the approach in [13], based on a notion of abstraction. They describe an interplay of willingness to degrade data against urgency. Their approach assumes that the quality of the data can be inferred from its size. While this relationship may hold in the case of images, it is not true for all data. We do not regard the selection process as being solely about degrading data (a common starting point, e.g. [5,6]). The total data about a geographic area is likely to be overwhelming and contain much irrelevant information, in which case it is not the case that omission constitutes a degradation. Similarly we measure utility across the user's perception, rather than in relation to some ideal or original version, such as in [14].

6.3 Resource Management and Response to Context

We are interested in soft QoS management, under conditions where hard guarantees may be unrealistic. We also make no claims that our model of resource management can offer a firm guarantee of resource characteristics. However, in the context of highly variable resource characteristics a weak model of resource management and negotiation offers a practical solution, as long as the user and application designer are aware of its weakness. In [13] an overview of approaches to adaptability is presented, and a suggestion for linking perceived quality to deadline specification for web browsing is described. Their approach to deciding how to adapt is based on allocating percentages of the data the user is willing to use, for a given element. We believe our approach of rating the utility of variants by measurable parameters provides a finer degree of control than their assumption that any given proportion of data volume corresponds to a known (and acceptable) degradation in quality.

7.1 Future Work

As discussed, the work presented here is defined in terms of adapting vector maps. As the nature of data on the WWW becomes more highly structured, data production techniques more sophisticated, and meta data more readily available these techniques will become more applicable to the wider world of the Web. There are many issues to be resolved in this area. Our current interests include:

• Extending our map application to provide a fuller test-bed for our ideas. We have undertaken some work on using these techniques to adapt the presentation web pages. The integration of this, and other adaptive multimedia techniques to provide a multimedia map application is one goal of our work. In particular we are interested in integrating hyperlink data with the map data.
• The use of proxies and multiple data sources presents some interesting problems in selecting configurations of proxies, and in managing the view of the available options at the selection point. The use of intelligent caching, transcoding and dynamic data integration proxies also provides for a wider variety of selection options.
• The definition of easily extensible specifications, which may be varied according to context is necessary. This includes work on abstracting the specifications for the user, integrating partial specifications, and work on defining type vocabularies. Where media continue to contain much data within one file, such as images, the ability to describe an element as having a compound type is also necessary.
• Some user studies, and real-world testing will be undertaken, once the development of the application and user interface has progressed further.