HistoryPaper: A Magazine-Style Layout of Representative
Web Pages Extracted From Browsing History
Chica Matsueda
Ochanomizu University
2-1-1 Otsuka, Bunkyo-ku
Tokyo, 112-8610 Japan
coco@itolab.is.ocha.ac.jp
ABSTRACTWeb browsing history of people who use internet everyday represents processes they learned. Visualizationof summarized browsing history can contribute to learn
what we did. This paper proposes HistoryPaper, a system to extract representative Web pages from browsing
history of users, and arranges them like a newspaper.
The system helps users to remember what they did ina particular day. HistoryPaper ﬁrstly clusters browsed
Web pages based on their contents. Then, it calculates
the priority of Web pages from search terms and ralityof accessed Web pages, and selects the representative
page of each cluster. HistoryPaper arranges the representative pages by utilizing a layout algorithm following
the magazine style applied in many news sites. This paper presents the numeric evaluation of the layout results
to demonstrate the reasonableness of the algorithm.
INTRODUCTION

Life log is a popular word in the recent information
technology ﬁeld due to the growth of wearable devices.
Sensing data including position and acceleration arerecorded as unconscious life logs, while users consciously
record other kinds of life logs such as dailies. Unconscious life logs can be continuously recorded without
any labor of users; however, limited types of information can be stored due to functionality of the devices
or equipments. On the other hand, recording conscious
life logs requires continuous labor.
Web browsing history has both advantages of unconsciously and consciously recorded life logs. We do notconsciously record the browsing history, while it contains fruitful information representing behavior and knowledge of the users. Also, we expect that reﬂection ofbrowsing history corresponds to the reﬂections of actions of particular days or previously studied knowledgeof the users.
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. Request permissions from permissions@acm.org.
VINCI’15, August 24–26, 2015, Tokyo, Japan.
Copyright 2015 ACM 978-1-4503-3482-2...$15.00
DOI:http://dx.doi.org/10.1145/10.1145/2801040.2801044

Takayuki Itoh
Ochanomizu University
2-1-1 Otsuka, Bunkyo-ku
Tokyo, 112-8610 Japan
itot@is.ocha.ac.jp
This paper presents “HistoryPaper”, a system whichdisplays sets of Web pages corresponding to the summaries of the browsing history of the particular days.
The technique extracts important Web pages in thebrowsing history of the day, and represents the sets of
Web pages like a newspaper on the Web.
There have been several services which display representative Web pages representing the interest of the users.
Paper.li (http://paper.li/) is one of the typical services,which displays sets of Web pages shared on social networking services such as Twitter or Facebook. Paper.li
applies the magazine-style design to arrange the setsof Web pages, to realize the quick overview of userinterested Web pages. However, Paper.li aims the allin-one display of already shared Web pages, while we
focus on summarization of browsing history and realtime layout of Web pages with magazine-style design.
MAGAZINE-STYLE WEB SITESMagazine-style design is a recent popular style of Web
sites, which divides the windows of Web browsers into
rectangular subregions, and frames the text and images
into the subregions, as shown in Figure 1. This design
is reasonable when we would like to show various contents in a single page like magazines or newspapers, andtherefore many Web sites currently apply this design.
Magazine-style design is a kind of informal design name.
There is no standard theoretical deﬁnitions of magazinestyle at least in our survey. This section describes ourown deﬁnition of magazine-style design based on our observation of Web sites as the Web design which satisﬁes
the following conditions:
Condition 1: Divide the window spaces into 2, 3, or 4of vertically-long subspaces, and then frame the Web
pages into the subregions.
Condition 2: Assign independent areas to each of Web
pages based on their importance, and place the important Web pages in the upper-left part of the window.
Condition 3: Unify the aspect ratios of the rectangular subregions.
Condition 4: Arrange the equally sized and shaped

Containing a vertically-long image

Containing a horizontally-long image

Figure 1.
Example of a Web page applying themagazine-style design.
(The New York Times,
http://www.nytimes.com/)

No image (text only)

rectangular subregions adjacently.
We measured the sizes and aspect ratios of rectangularsubregions in the magazine-style news Web site 2 toverify [Condition 3]. Figure 2 shows the distribution of
the measured aspectratios.
We deﬁned the ideal aspect ratios of the rectangularsubregions as shown in Table 1 based on the result. In
this deﬁnition, we suppose one or no image is displayedin each of the subregions. We also suppose that theimage is displayed in the upper or left side of the subregions.

Figure 2. Aspect ratios of rectangular subregions inmagazine-style new Web sites.

gorithm which satisﬁes the above conditions.
Table 1. Ideal aspect ratios defined in this study.

With image

Without

width/height (image position)
0.9 (upper)
1.6 (left)
3.0 (left)
3.8 (left)
1.0
3.8
5.0

We also observed the same Web sites to verify [Condition 4]. As a result, we found that approximately 95%
of the Web pages are arranged adjacently with equally
sized and shaped Web pages.
This paper presents an automatic Web page layout al2
The New York Times (http://www.nytimes.com/)，
The
New
Yorker(http://www.newyorker.com/)，
Japan
Today
(http://www.japantoday.com/),skyNEWS(http://news.sky.com/),
BBCNEWS(http://www.bbc.com/news/)

REPRESENTATIVE WEB PAGE SELECTION

HistoryPaper automatically selects multiple representative Web pages browsed on a particular day, and displays in a Web browser window. This section describes
the processing ﬂow to select representative Web pages.
Our technique ﬁrstly calculates the importance of Web
pages browsed in a particular day. There have been
several studies on selection of appropriate number ofrepresentative text to summarize the large collectionsof documents. Lin et al. [5] presented that tf-idf based
representative text selection brings satisfactory document summarization results. We learned this knowledge to develop an algorithm for representative Web
page selection. The presented technique implemented
for HistoryPaper ﬁrstly applies a clustering algorithm
to the Web pages based on the similarity of their contents, and then selects most important Web pages fromeach of the clusters. We can summarize the activity of
the users on a particular day by displaying the selectedWeb pages.
Clustering of Browsed Web Pages

HistoryPaper ﬁrstly divides all the Web pages browsed
on a particular day into n clusters. It speciﬁes n (between 6 and 12 in our implementation) based on thesizes of Web browser windows and the number of browsed
pages on the day in advance.
The following is the brief description of the clustering
process.
1. Convert the contents of Web pages into Bag-of-Words
vectors.
2. Apply a dimension reduction to the Bag-of-Words
vectors. Our implementation applies Latent Semantic Analysis (LSA) for the dimension reduction.
3. Apply k-means clustering method to the dimensionreduced vectors.
Importance Estimation for Web Pages

The presented technique then calculate the importanceof the Web pages pp by applying the following equation:
pp = pa q + pb m + pc mq

Here, nc denotes the number of Web pages in a particular cluster, and pp (k) denotes the importance of thek-th Web page in the cluster calculated by the equation(1). The value cp is used to calculate the areas of Web
pages in magazine-style layout.
MAGAZINE-STYLE LAYOUT

This section describes our algorithm to place the selected representative Web pages mimicking magazinestyle layout. There have been several techniques on layout of multiple Web pages applying optimization techniques [4]; however, there have been few studies onmagazine-style-speciﬁc layout for multiple Web pages.
Preliminary Experiment

We tested Squariﬁed Treemap [1] for the layout of Web
pages before the development of the magazine-style layout algorithm. Squariﬁed Treemap divides a rectangular region into a set of nearly-square subregions, whileareas of the subregions can be freely speciﬁed. Figure
3 shows an example of rectangle layout by Squariﬁed
Treemap assigning speciﬁc areas to the subregions. We
applied the implementation of Squariﬁed Treemap provided by d3.js.

(1)

where,• m is the total number of keywords used for search
query in the day and contained in the current Web
page.
• q = mwp /mall is the valuableness of the current Web
page, where mwp is the number of accesses to thecurrent Web pages in the day, and mall is the total
number of accesses to the all Web pages in the day.
• pa , pb , and pc are experimentally deﬁned constantreal values.
This deﬁnition is based on our heuristics that Web pages
are important if they satisfy one or more of the following
conditions:• they are browsed over and over in the day, even though
they are not usually well browsed.
• they contain many keywords used for search queries.
The technique selects the Web pages which has the maximum pp value in each of the clusters as the representatives.
Importance Estimation for Clusters

The technique then calculates the importance of clusters cp by the following equation.

cp =

nc

k=1

pp (k)(2)

Figure 3. Example applying Squarified Treemap.

As a result, we found the following problems on the rectangle layout by Squariﬁed Treemap after testing withseveral sets of Web pages.
• Squariﬁed Treemap may generate too small subregions. In other words, it is not always visually preferable to assign the exact importance value cp as theareas of the subregions. Rather, we would like to
ﬂexibly adjust their areas to realize visually preferable layout.
• Squariﬁed Treemap may generate small number ofvery thin rectangles while others are well-shaped.
This section describes a new algorithm mimicking magazinestyle layout while solving the above mentioned problems.

Data StructureThis section deﬁnes the variables related to clusters of
Web pages as follows.
• R: The set of all clusters.
• Ri : The i-th cluster.
• G: The set of all cluster groups.
• Gi : The i-th cluster group.
• C: A set of arbitrary cluster groups Gi ,Gj ,...
• S: Set of Web pages which can be described as either
R，G，Gi ，or C.

(2) After grouping(1) Before grouping
cp

typeR

45
32
30
20
11
10
5
2
1

true
true
true
false
false
false
false
false
false

G1
G2
G3
G4
G5
G6

cp

typeR

45
32&30
20
11&10
5
2&1

true
true
false
false
false
false

Figure 4. Grouping of clusters.

Also, this section deﬁnes the following variables.
• |S|: The number of Web pages contained in S.

Area Assignment for Clusters• areaS : Total area in the display space occupied by
Web pages in S.

The technique then calculates the areas of rectangularregions which are to be assigned to Web pages fromtheir importance values cp . Here, we do not directly
apply cp as relative values of areas. Instead, we deﬁned
the areas of the rectangular subregions as the following
equation.

• priorityS : Sum of the values cp of the Web pages inS.
• ratioS : Ideal aspect ratio of the rectangle occupied
by S. See Table 1.
• typeR : Boolean value which denotes the existence ofan image in R.
• W : Width of the browser window space.

areaRi =priority Ri W H
Wmin Hmin priority R

 α1
(4)

• Wmin : Minimum value of width assigned to Web
pages.

Here, α is a constant real value (1.3 in our implementation) to control the ﬂexibleness of the area assignment. This equation avoids to generate too small subregions, and therefore solves the ﬁrst problem of Squariﬁed Treemap discussed in our preliminary experiment.

• Hmin : Minimum value of height assigned to Web
pages.

Figure 5 illustrates an example of the set of areas ofcluster groups illustrated in Figure 4(2).

• H: Height of the browser window space.

Here, we suppose that the browser window is not scaled
or scrolled during the usage of this technique.
Cluster Grouping

The technique groups clusters based on their importance values cp , so that it can adjacently display theclusters which have similar cp values as similarly-sizedrectangles. Two clusters Ri and Rj would belong to thesame group if they satisfy the following equation:
cpj ≤ (cpi × 1.2)

(3)

where cpi and cpj are the importance value of clusters Ri
and Rj respectively. The technique does not apply theabove equation, if Ri has already belonged to anothergroup, or boolean values of the two clusters are diﬀerent.
Figure 4 shows an illustration of the grouping process.
Figure 4(1) depicts the list of original importance values, and Figure 4(2) depicts the grouping result. Thissection describes the generated groups G1 ....GnG , wherenG denotes the number of cluster groups. This grouping
process contributes to satisfy [Condition 4].

G1
G2
G3
G4
G5
G6

cp

areaRi

typeR

45
32&30
20
11&10
5
2&1

27
20&18
12
7&6
3
2&1

true
true
false
false
false
false

Figure 5. Calculation of areas for representative Web
pages.

Web Page Layout

The technique then divides the Web browser window
into multiple rectangular subregions according to theareas calculated by the equation (4), and ﬁnally maps
the representative Web pages. Figure 6 illustrates thelayout algorithm described in this section.

G1
G2
G3
G4
G5
G6

cp

areaRi

typeR

45
32&30
20
11&10
5
2&1

20
15&15
11
7&7
4
3&2

true
true
false
false
false
false

I(a)

2. Specify the cluster group Stop which has the largest
area in S. Calculate the areas of clusters in Stop , andtentatively place the clusters at the upper-left endof the empty region of the display space taking into
account their aspect ratios ratioStop .
• Figure 6 (I(a) and I(b)) shows illustrations of thetentative layout of G1 (corresponding to Stop )with two choices of the aspect ratio.

I(b)

20

Firstly place G1.

20

Firstly place G1.

11

G3 is preferable.
Error |10-11|=133

G2 is preferable.
Error |33-30|=3

I(a) is selected due to the smaller error.

II(a)

II(b)

20

20

11

11

III(a)

III(b)

20

Place G2.
30
Too narrow.

11

20

30

11

23

Place G2.

G4 & G5 is preferable.
Error |23-18|=5
G4 + G5 = 7+7+4=18
III(a) is selected.
Place G4, G5 & G6.

V

IV
20

15 Deform G2.

20

15

14

11

15

11

15

4
5

VII

VI
20
11

15

7
7

15

4
5

20
11

15

7
7

15

4
2
3

Figure 6. Illustration of our magazine-style layout algorithm.

Following is the processing ﬂow of our layout algorithm.
1. Let S = G, rectW = W ，and rectH = H.

• If the width of the blank region at the right end
is smaller than Wmin , the algorithm extends thewidth of Stop to ﬁll the right end of the blank.
Similarly, the algorithm extends the height ofStop to ﬁll the bottom of the blank, if the heightof the blank region at the bottom is smaller than
Hmin . Figure 6(III(a)) depicts an example ofnarrow blank at the bottom, and Figure 6(IV)depicts after the expansion of the rectangles.

3. Calculate the area of the blank region below the tentatively placed rectangles. Rectangular regions painted
in sky blue in Figure 6(I(a)(b)) and Figure 6(III(a)(b))
are such blank regions. Repeat this process for each of
the tentative layout results, and ﬁnally select the layout result which errors of areas between the selectedcluster group and the blank region is the smallest.
At this moment, our algorithm extracts the candidates of cluster groups to be placed at the sky blue
regions. This section describes the set of candidate
cluster groups as Sopt .
• In the example illustrated in Figure 6(I), G3 isselected for the layout in Figure 6 (I(a)), and G2
is selected for the layout in Figure 6 (I(b)). In
this case G2 or G3 corresponds to Sopt . Layout
in Figure 6 (I(a)) is then selected, because theerror of areas is smaller.
This process is also applied to the empty regions after
left end of the display space has been ﬁlled. Figure6(III) depicts an example of this situation after left
end of the display space has been ﬁlled by G1 and G3 .
G2 is selected from Sopt as Stop , and placed at theupper-left end of the empty space with two choices ofaspect ratios, as shown in Figure 6(III(a)) and Figure6(III(b)).
4. Deform the placed rectangles to gather their right end
edges. Figure 6(II(a)) illustrates the rectangles before
the deformation, and Figure 6(II(b)) illustrates after
the deformation. The technique gathers the edges sothat the rectangles satisfy the equation areabef ore =areaaf ter , where areabef ore is sum of the areas ofrectangles before the deformation, and areaaf ter issum of the areas of rectangles after the deformation.
5. Apply the following process if Sopt is not cleared.
(a) Let rectW = WStop , and rectH = rectH − HStop .

(b) If |Sopt | ≥ 3:
Apply 2. and 3., replacing |Sopt | as S. This
process applies the nested magazine-style layout
to the rectangular subregions.
(c) If |Sopt | < 3;
Apply 7., replacing |Sopt | as S. As a result, G4
in Figure 6(V) is divided into two recrangles, as
depicted in Figure 6(VI).
(d) Clear Sopt when its all cluster groups are placedin the display space.
6. Apply the following process to S if Sopt is cleared.
(a) Let rectW = rectW − WStop .
(b) If |S| ≥ 3:
Apply 2. and 3. As a result, the process generates a series of rectangles illustrated in Figure6(III(a)(b)).
(c) If |S| < 3:
Apply 7. As a result, the process ﬁlls the rightend regions as illustrated in Figure 6(V).
7. (a) If S corresponds to Gi :Horizontally or vertically subdivide into |S| rectangles, and select the one of the results whichbrings the better aspect ratios.
(b) If S corresponds to C:
Horizontally or vertically subdivide, and apply
the following process replacing each of Ci as S.
• Apply 2. and 3. if |S| ≥ 3.
• Apply 7. if |S| < 3.

RESULTSWeb Page Selection

This section introduces an example of Web page selection result from the browsing history of the ﬁrst author.
Table 2 shows the list of the selected Web pages, wherecp denotes their importance.

cp
399
243
239
199
107
90
72
57
16

Table 2. Web page selection result.

Title of Web pages
2D bin packing with JavaScript and canvas
Output of log ﬁles in Android
Packing algorithms (Kyoto university)
Port check
Meaning of “heuristic”
Packing algorithm and complexity
Approximation of rectangle packing
Questions on the rental server
FINAL FANTASY Oﬃcial song

LayoutFigure 7 shows an example of Web page layout result
by HistoryPaper. The set of Web pages is same as applied in Figures 3 and 4. We can observe that HistoryPaper roughly divides the window into vertically-longsubregions, and then divides into well-shaped rectangles
which Web pages are mapped. We can also observe thatsimilarly-sized sets of rectangles are adjacently placed.
This example demonstrates HistoryPaper realizes thelayout of Web pages mimicking magazine-style.

Here, we limit the maximum number of candidate layouts (2 in our implementation)in 3., because this layout problem is NP-hard. We estimate the complexity
as O(|R|lmax ) where lmax is the maximum number oflayouts, while the complexity would be O(|R||R| ) if we
do not limit the maximum number of candidate layouts.
The above algorithm roughly divides the display space
into vertically-long subregions to satisfy [Condition 1],
and ﬁnally generates rectangular subregions assigning
importance-based areas to them to satisfy [Condition 2].
The grouping process contributes to satisfy [Condition3], and ﬂexible aspect ratio selection satisﬁes [Condition
4].
In the layout results, many of important Web pages areplaced in the upper-left side of the display space: it isgenerally a good property because many people ﬁrstly
look at the upper-left part of the windows.
Representative Web Page Display

HistoryPaper ﬁnally maps the representative Web pages
into the rectangular subregions. HistoryPaper displays
the title of Web pages, URL, and the summarized text
in each of the rectangular subregions. We apply the leadtechnique [2][6] which extracts important sentences inthe beginning of the documents to generate the summarized text.

Figure 7. Example of the layout result by HistoryPaper.
(Upper)Layout result. (Lower)Web pages mapped to therectangular subregions of the layout result. Remaarkthat left three columns are formed from the layout result.
The right end column just shows a list of search query
terms.

Evaluation of Layout

We numerically compared the layout results of HistoryPaper and Squariﬁed Treemap. We deﬁned the evaluation functions as follows, where ri denotes the aspectratio of the i-th rectangle.
1. Calculate Dratio , the diﬀerence between the ideal aspect shown in Table 1 and the actual aspect ratio, byapplying the equation (5).
Here, x is either 0.9, 1.6, 3.0, or 3.8, if the Web page
contains images. Otherwise, x is either 1.0, 3.8, or
5.0.
n

2
Dratio =1 − (min{f (x, i)})(5)
i=0where,⎧x⎪⎨f (x, i) = ri
⎪
⎩ ri
x

this experiment, we prepared the following three implementations of the representative Web page selection
process:(a): Selection as presented in this paper(b): Random selection from browsing histories(c): Random selection from clusters of Web pages
We then asked them the following two questions:
1. Did you have anything to remember your past actions or previously discovered knowledge while using
HistoryPaper?
2. Which result brought from the three implementations
was the best result for you?

(x > ri )(x ≤ ri )2. Calculate Wratio , the worst value of the diﬀerence
between ideal and actual aspect ratios, by applying
the equation (6).
Wratio = max{Dratio (i), i = 1, 2, · · · , n}(6)

We determine that the layout is better if Dratio andWratio are smaller.
Comparison of Layout Results

This section shows the numeric comparison of layout
results between HistoryPaper and Squariﬁed Treemap.
We compared the following three implementations inthis experiment:• Squariﬁed Treemap without area adjustment by equation (4)• Squariﬁed Treemap with area adjustment• HistoryPaper
Figure 8 shows examples of the layout results applying
the same set of Web pages, and values of Dratio andWratio .
The result suggests Squariﬁed Treemap may occasionally generate thin rectangles in the lower-right ends ofthe display spaces. Therefore, Wratio sometimes gets
extremely bad while using Squariﬁed Treemap. Though
this problem can be improved by the area adjustment
applying the equation (4), this result demonstrates HistoryPaper obtained better Dratio and Wratio values comparing with Squariﬁed Treemap.
User Evaluation

This section introduces our user evaluation with 10 student participants in master’s course. We asked them touse HistoryPaper for one hour while observing the visualization results with their own browsing histories. For

As a result, 9 of the participants answered that they remembered something while using HistoryPaper for theﬁrst question. This result suggests that the concept ofHistoryPaper is eﬀective for the reﬂection of their past
Web browsing. For the second question, 8 of the participants selected (a), while other 2 participants selected(b). The 2 participants mentioned that it was enjoyable if HistoryPaper displayed several unexpected Web
pages, and therefore random selection seemed better.
We would like to reﬂect this comments to make HistoryPaper more enjoyable and satisfactory.
CONCLUSIONSThis paper presented HistoryPaper, a system which selects sets of important Web pages browsed on a particular day, and displays the sets of Web pages by utilizing a
new layout algorithm mimicking magazine-style layout.
HistoryPaper visualizes the summary of users’ daily activity and acquired knowledge. This paper introduced
the comparison of layout results by HistoryPaper andSquariﬁed Treemap to demonstrate the eﬀectiveness ofthe presented layout algorithm.
As a future work, we would like to discuss how to evaluate beauty of the layout results, which is diﬃcult toessentially evaluate by our current criteria Dratio andWratio . Also, we would like to observe and measure
the actual magazine-style Web sites more carefully, andevaluate the layout results of HistoryPaper by comparing with the actual Web sites.
REFERENCES

1. Bruls, M., Huizing, K., Van Wijk, J. J., Squariﬁed
treemaps, Data Visualization 2000, 33-42 (2000).
2. Edmundson, H. P., New methods in automatic
extracting, Journal of the ACM (JACM), 16(2),264-285 (1969).
3. Genest, P. E., Lapalme, G., Nerima, L., Wehrli, E.,
du Langage, T., A symbolic summarizer for the
update task of tac 2008, The First Text Analysis
Conference (2008).

Proposed technique

Deformed Squarified Treemap

Figure 8. Comparison of layout results.

4. Gonzalez, J., Rojas, I., Pomares, H., Salmeran, M.,
Merelo, J. J. Web newspaper layout optimization
using simulated annealing, IEEE Transactions on
Systems, Man, and Cybernetics, Part B:
Cybernetics, 32(5), 686-691 (2002).
5. Lin, C. Y., Hovy, E., Identifying topics by position,
Fifth Conference on Applied Natural Language
Processing: Association for Computational
Linguistics, 283-290 (1997).
6. Litvak, M., Last, M., Friedman, M., A new
approach to improving multilingual summarization
using a genetic algorithm. 48th Annual Meeting of
the Association for Computational Linguistics:
Association for Computational Linguistics, 927-936(2010).
7. Wartenberg, C., Holmqvist, K., Daily Newspaper
Layout - Designers Predictions of Readers Visual
Behaviour - A Case Study, Lund University
Cognitive Studies, 126, 1101-8453 (2005).

Squarified Treemap