Source-linked AI summary
Tag-Cloud Drawing: Algorithms for Cloud Visualization
Owen Kaser, Daniel Lemire
TL;DR
Standard inline HTML can waste space and does not account for known relationships between tags. The paper develops typesetting- and EDA-inspired algorithms for inline and nested-table layouts, reporting visually improved, tighter clouds and efficient implementation. It also identifies limitations in the models and differences between tag placement and EDA placement.
Problem
Standard inline HTML is poorly suited to tag clouds because varied tag sizes waste space, and typical layouts do not represent relationships between tags.
Method
The paper develops typesetting-inspired inline-text algorithms and EDA-based nested-table placement algorithms for compact, relationship-aware tag-cloud layouts.
Results
The resulting layouts are reported as visually improved and tighter, while min-cut placement outperforms greedy approaches and compaSS on semantic-tag proximity.
Takeaways & Limitations
Tag-cloud display can be addressed with algorithms adapted from automatic typesetting and electronic design automation.
Takeaways & Limitations
The inline cloud-badness model omits symmetry, tag similarities, and coloring optimization; EDA placement also differs in input sizes and runtime requirements.
Abstract
from arXiv · showhide
Tag clouds provide an aggregate of tag-usage statistics. They are typically sent as in-line HTML to browsers. However, display mechanisms suited for ordinary text are not ideal for tags, because font sizes may vary widely on a line. As well, the typical layout does not account for relationships that may be known between tags. This paper presents models and algorithms to improve the display of tag clouds that consist of in-line HTML, as well as algorithms that use nested tables to achieve a more general 2-dimensional layout in which tag relationships are considered. The first algorithms leverage prior work in typesetting and rectangle packing, whereas the second group of algorithms leverage prior work in Electronic Design Automation. Experiments show our algorithms can be efficiently implemented and perform well.
1. INTRODUCTION
The paper targets inefficient and unattractive tag-cloud layouts in simple HTML, while also seeking to place related tags near one another. It introduces two algorithmic solution families: EDA-based placement for compact clustering and typesetting-inspired layout preserving reading order.
- Motivation: The paper assumes associated tags should be placed near one another.This adds relationship-aware organization to the display objective.
- Motivation: Tag clouds support navigation and retrieval but standard inline HTML wastes space and creates large white-space clumps, especially with varied tag sizes.The problem is particularly relevant to small-display devices and tight HTML designs.
- Approach: Min-cut placement adapts an EDA floorplanning algorithm to minimize area and cluster related tags using nested HTML tables.Its unconventional layout does not place tags on ordinary text lines.
- Approach: A hybrid of Knuth-Plass text justification and book placement produces a tighter, visually improved cloud while preserving left-to-right, top-to-bottom order.This solution retains a conventional appearance.
2. RELATED WORK
Related work spans tag-cloud layout, graph drawing, and HTML presentation, but tag-cloud drawing itself has received comparatively little attention. Prior approaches cluster, filter, search, or reshape clouds, while broader HTML-layout work improves tables and CSS text presentation.
- Tag-cloud research: Tag clouds became popular through Flickr and later appeared on sites including Technorati and del.icio.us.They are commonly associated with folksonomies and social software.
- Graph drawing: Graph drawing seeks understandable and visually pleasing two-dimensional graph representations using criteria such as few edge crossings, symmetry, and orthogonality.These criteria provide relevant context for relationship-aware tag-cloud layouts.
- Tag-cloud research: Prior tag-cloud methods cluster similar tags, discard or dynamically remove less significant tags, add search indexes, or use circular layouts.These approaches modify grouping, content, searchability, or overall geometry.
- HTML layout: HTML-layout research has shown that special-purpose algorithms can improve table appearance, while CSS work continues to improve text layout.The paper positions its simple-HTML focus within this broader effort.
3. BACKGROUND
The paper draws on automatic typesetting and EDA placement as foundations for tag-cloud optimization. Typesetting supplies line-breaking methods, while EDA supplies placement heuristics for computationally difficult two-dimensional arrangements.
- Typesetting: Automatic typesetting aims to fit text quickly and attractively, with even spacing between words.This motivates adapting text-layout methods to inline tag clouds.
- Typesetting: Browser-style greedy line breaking is online and fast but can frequently produce suboptimal solutions.Knuth-Plass instead computes an optimal line arrangement with dynamic programming and O(n^2) time.
- Typesetting: The Knuth-Plass approach applies directly only when tag order is fixed and all tags have equal height.Tag clouds complicate this setting because tags can vary in height and be reordered or colored.
- EDA: EDA placement and floorplanning assign circuit modules to chip locations while avoiding overlap and satisfying shape or aspect-ratio constraints.The paper uses this domain as an algorithmic source for tag-cloud placement.
- EDA: Placement is typically NP-hard, so EDA uses heuristics such as force-directed methods, simulated annealing, and min-cut placement.Min-cut is selected because the paper envisions on-the-fly server-generated clouds.
4. MODELS FOR CLOUD OPTIMIZATION
The paper defines separate optimization models for inline text and arbitrary two-dimensional placement. The inline model evaluates line badness, while the table-based model minimizes occupied area and can additionally penalize separation of related tags.
- Model scope: The paper considers two aesthetic models: tags as inline text and tags arranged in nested HTML tables.The second model supports arbitrary two-dimensional placement.
- Inline text: An inline-text cloud is a paragraph of inline HTML elements where each tag remains on one line and tag dimensions are primarily fixed.Cloud width is constrained by page layout, while cloud height is treated as free.
- Inline text: Inline line badness combines excess horizontal white space with penalties for tags shorter than the tallest tag on the line.It depends only on the set of tag dimensions, not their exact alignment or ordering across lines.
- Inline text: Overall inline-cloud badness may be defined as the sum of squared line badnesses, which penalizes solutions containing very bad lines.The model also discusses unsquared sums and maximum-badness alternatives.
- Arbitrary placement: For arbitrary placement, the model constrains width, discourages height and white-space clumps, and prefers close proximity for strongly related tags.Tags may optionally be slightly deformed while approximately preserving area.
- Arbitrary placement: The arbitrary-placement objective can minimize occupied area and separately measure spatial non-proximity using weighted tag relationships and Euclidean distance.Graph and hypergraph representations offer alternative ways to encode co-occurrence relationships, although the paper argues for graphs.
5. SOLUTIONS
The paper uses different algorithms for inline and arbitrary tag-cloud layouts: typesetting and packing methods for line breaking, and EDA-inspired min-cut placement for two-dimensional layouts. These methods support relationship-aware placement, nested-table rendering, and efficient floorplan sizing, while retaining tag-specific constraints such as fixed width and no rotation.
- Inline text: Inline layouts use greedy, dynamic-programming, and tag-reordering algorithms to reduce whitespace while preserving line-based presentation.The greedy method runs in O(n); reordering is difficult because the optimal ordering problem is NP-hard.
- Inline text: The optimal tag-ordering search space is impractical for clouds of 100 tags, since 100! ≈9.33 × 10^158 possible orders exist.The authors therefore assess order heuristics through random shuffling and packing methods rather than exhaustive search.
- Min-cut placement: Arbitrary placement uses recursive min-cut bipartitioning that balances groups while minimizing relationships crossing between them.External directional connections can be represented with dummy tags, and the Fiduccia–Mattheyses heuristic gives O(m log n) runtime under stated assumptions.
- Slicing floorplans: Recursive bipartitioning produces a slicing tree whose internal horizontal or vertical cuts assign tags to nested placement areas.Each internal node corresponds to a 2-element HTML table, with nested tables representing nonleaf subtrees.
- Floorplan sizing: Floorplan sizing can stretch or squash tags while approximately preserving total area, and slicing-floorplan sizing runs in Θ(s log s) time.General floorplan sizing remains intractable, while the implementation forbids 90-degree tag rotation and constrains cloud width rather than height.
6. EXPERIMENTAL RESULTS
Experiments evaluated inline-text and arbitrary-placement algorithms on ZoomClouds and Project Gutenberg tag clouds. Results show fast inline optimization, competitive packing heuristics, and min-cut’s advantage when semantic proximity matters.
- Experimental setup: The evaluation used 65 ZoomClouds clouds and 80 Project Gutenberg clouds, with tag relationships derived from word co-occurrences in the e-books.ZoomClouds clouds averaged 94 tags; Gutenberg tests retained k = 20, 50, 100, and 200 tags.
- Inline-text results: Inline-text optimization averaged well under 1 ms per cloud for all algorithms except random shuffling, while greedy algorithms ran under 0.2 ms.The measurements used 5000 tests on a 140-tag del.icio.us cloud, and the code was not particularly speed-optimized.
- Inline-text results: For l1 badness, FFDHW was the clear winner, improving over weight-sorted algorithms by 24% on ZoomClouds and 15% on Project Gutenberg.With l2 badness, dynamic programming improved over greedy by 7%, while FFDH and FFDHW improved over dynamic programming by 1% or 2%.
- Arbitrary-placement results: Variable tag aspect ratios reduced compaSS area by approximately 12% but required more than 6 seconds on large clouds.The comparison was not fully fair for three aspect variations because compaSS assumes identical areas for each variation.
- Arbitrary-placement results: Min-cut used more area than sorted greedy packing but outperformed greedy approaches and compaSS when semantic proximity was evaluated.Min-cut explicitly groups strongly related tags, whereas the competing tight-packing methods do not consider tag relationships.
7. CONCLUSIONS
The paper identifies unresolved limitations in browser implementation, cloud-badness modeling, tag similarity, coloring, and clustering evaluation for tag-cloud layouts.
- Browser-based implementations remain future work because practical use may require client-side ECMAScript for browser-specific display information.
- The in-line cloud-badness model is incomplete because it ignores basic symmetry issues and tag similarities.Inferring an interesting similarity measure from existing tag clouds may be difficult.
- Tag-cloud coloring remains open to optimization, while clustering related tags needs a better assessment metric.Optimizing a new clustering metric would likely require substantial changes to an existing EDA tool.