Fast algorithms for online construction of web tag clouds

摘要

In this paper tag cloud construction for web exposition is studied. Construction of a tag cloud must simultaneously solve at least three interdisciplinary engineering problems: modeling and controlling graphics aesthetics, solving discrete two-dimensional layout optimization problem, and all these must be done on computationally constrained browser platform. We analyze the design choices in the earlier tag cloud studies and provide a taxonomy of algorithmic approaches to tag cloud building. Then, the design requirements for tag clouds on websites are defined. We propose to quantify tag cloud aesthetics by use of a novel objective function based on the rules of typography. Tag cloud construction is formalized as a combinatorial optimization problem with an irregular objective function. A set of algorithms is proposed and evaluated on a collection of tag sets from popular web pages. The methods that meet constraints of the browser platform are chosen.