[Veijonen et al., 1994] describe the prototype VIPÊ designed at VTT for automatic page layout of electronic news distribution. Pagination methods applied were derived from advertisement pagination system previously designed at VTT [Ylä-Jääski and Ahonen, 1990].
The initial goal of VIPÊ pagination had been defined as pagination
of articles with all kinds of sizes and rectangular shapes. However,
the requirement of any article sizes had been relaxed and problem
space considerably discretized to reduce it. Instead of allowing any
article sizes starting from any location on the page, a sparse grid
(typically 
grid for an A4 page) had been defined and
article sizes were accordingly modularized. Division into columns was
natural, since in a typical newspaper the text usually resides in
columns of equal width. The horizontal divisions, usually into 4-6
horizontal sections, were artificial (see Fig. 3).
They had been adopted not only to discretize the search space but also
to ensure tranquility of the layouts. The resulting pages indeed were
tranquil, often even dull, and occasionally resulted in quite a lot of
wasted space.
The contents of each article were first paginated into several different modularized shapes--- article forms---by rough article layouting. All these alternative forms were then passed on to pagination, which selected at most one of them to a page. Due to the modularization, the form often contained also empty space. The grid thus had three effects: it reduced state space, ensured that the pages would not look too irregular and at the same time compromized some empty space.
Figure: a) A layout with five columns. b) A modularized layout
with 5x5 modules.
Figure: a) An intermediate page layout of four columns, with two
articles a1 and a2 already on the page. Two maximal
regions, r1 and r2 can be identified on the layout, based
on the article end lines. b) The same situation represented by a graph.
The pagination engine had been rather straightforwardly borrowed from a version of VIP paginating newspaper display advertisements. The pagination method might be described as "heuristic best-first forward search utilizing branch-and-bound technique". The algorithm proceeds by searching through a graph which is expanded at time of need to selected directions. In the graph, leafs represent solutions proposed by the algorithm, i.e. finished layouts where nothing else can be added. Inner nodes represent states between insertions of new articles. The empty space on a page is represented by empty regions which are maximal rectangular areas of empty space, calculated from the end lines of articles on the page (see Fig. 4). In the state graph, transition from a father to a child carries out the following operations:
Figure: A sample selection of articles ready to be
paginated onto the layout depicted in Fig. 4. The
articles have been ordered with a heuristic rule: first into
descending order by width, and next the articles with the same number
of columns into descending order by height.
Figure: The region-box combinations created in state n.
To cut down the search tree, an upper limit has been defined for
the amount of article combinations to create. The branching is
done mainly in the beginning, and at later stages only one branch
is typically created and proceeded.
Next, a number up to a dynamically decided upper limit of region-box- combinations will be expanded to create new nodes of the search graph by inserting the box combinations to the regions (see Fig. 6). Each node produced by this method is expanded further until no more articles can be added on the page. Finally, the best page according to given criteria is selected.
The heuristics of the method reside in the ordering of empty regions and article combinations supposedly into best-first order. Heuristics often help, but since available material greatly affects the task, it is possible that also good paths are cut out by the control mechanisms that reduce the state space by cutting the number of paths examined. When there is little material to start with, the loss of paths may result in pages with too much empty space, even when an acceptable solution exists. Developing a good set of heuristic rules that works well with different kinds of input data is a tedious and time-consuming task.
The VIPÊ prototype described in 5.3.1 was extended and developed further:
In this experiment, the modularized article forms and grid were replaced with variable article sizes and free location on the page. After the modifications, wasted space on the page decreased. Unfortunately, pages sometimes became uglier, because now the horizontal lines on the page could start very close to each other (see Fig. 7 for an example).
Figure: An example of a page where two horizontal lines (the
thick ones) defined by article borders are disturbingly close to each
other.
Therefore, to restore some of the lost tranquility of the pages, the positions of horizontal article borders needed to be controlled in another way. This was carried out by implementing a strict rule in the selection of possible article locations (regions), so that solutions with borders starting too close to each other were abandoned.
It is an interesting question how much control the future reader wants to have on the content, and on the visual presentation, or whether he/she prefers to only receive a pre-designed thought-out publication with no individual control on its design. It is probable that there exist readers at both ends of the spectrum. Furthermore, different kinds of publications or situations where information must be presented visually, may call for different amounts of control over the results. The following discussion on user control of the results is applicable both to a situation where the pagination results are controlled by the publisher, and to a situation when the pagination takes place individually for each user, guided by his/her choices.
Giving user more control over the results of the pagination is a two-edged sword. On one hand, the user often wants to control the results (if he/she cares enough to spend time and think about it; sometimes the default result is fine). On the other hand, if the user is given several switches to turn, he/she expects the system to change its behavior in certain ways in return. Actually, he/she has some representation of what the range of generally possible results of the pagination process might be, and would like the system to change within this range, depending in some logical way on the choices he/she makes. It is also obvious that no combination of user choices should result in malfunctioning or total failure.
All this, however, is not easily obtainable in a complex system depending heavily on the given data. To fully attain the goals, the following would be needed: 1. A behavioral model of the input-output-relation of the process itself with any given parameter combination and the usual data, and 2. A mental model of the expectations of the user.
The overall goal is to translate the mental model and expectations of the user into effects on the system behavior via given input lines. This may be achieved in one of three ways: either by the designer's thorough understanding of both the user and the system in advance, or by the user learning the system behavior and its response to different parametric alterations, or by the system learning about the user's mental model and adjusting to it.
The last case is the most interesting, since it is both user-friendly and does not depend as much on the system designer's guesses about the user's mental models. However, it was beyond the scope of this work to try to define a proper mental model of the user, or to design a learning control interface. However, some control capabilities that seemed useful were selected and implemented into VIPÊ . The emphasis was on studying the existing pagination system and on enabling control in the first place by finding out how and where to guide its rather implicit pagination heuristics.
Three controls were implemented with which the user was able to guide the selection of the best layout. This kind of controls might be used in a traditional newspaper by the publisher to give an individual flavor to the publicatioon. Giving the user means to decide on strict rules about the pagination results would not have been wise, since sometimes no allowed solution might be found. Thus, the controls were of the nature "weigh this optimization goal more than that" or "completely disregard this goal". The user's wishes were taken into account when selecting between a group of rather good layouts. The implemented controls let the user specify values for the following parameters:
Figure: Example of effects of user control on whether to
weigh minimization of empty space (on the left) or maximization of
priority value (on the right). Priorities are marked with
numbers 1--3 in the article boxes, highest priority being 1.
, where w is the weight defined by the
user, m is the user-defined desired number and x the actual number
of articles on the page. The control does not guarantee reaching the
desired number. The effects of these selections are most profound when the user only wants one of them to work. In the test runs, if all goals were simultaneously attempted, mediocre results were achieved. This follows a general rule of thumb in optimization: one has to choose what is important and what is not.