Tiling heuristics and evaluation metrics for treemaps with a target node aspect ratio

Sammanfattning: Treemaps are a popular space-filling visualization of hierarchical data that maps an attribute of a datum, or a data aggregate, to a proportional amount of area. Assuming a rectangular treemap consisting of nested rectangles (also called tiles), there are multiple possible valid tiling arrangements. A common criterion for optimization is aspect ratio. Nevertheless, treemaps usually consist of multiple rectangles, so the aspect ratios need be aggregated. The basic definition of aspect ratio (width divided by height) cannot be meaningfully aggregated. Given this, a definition of aspect ratio that does not differentiate height from width was suggested. This definition allows for meaningful aggregation, but only as long as there are no large differences in the data distribution, and the target aspect ratio is 1:1. Originally, a target aspect ratio of 1:1 was deemed to be axiomatically ideal. Currently, perceptual studies have found an aspect ratio of 1:1 to lead to the largest area estimation error. However, with any other target this definition of aspect ratio cannot be meaningfully aggregated. This thesis suggests a correction that can be applied to the current metric and would allow it to be meaningfully aggregated even when there are large value differences in the data. Furthermore, both the uncorrected and corrected metrics can be generalized for any target (i.e. targets other than 1:1). Another issue with current evaluation techniques is that algorithm fitness is evaluated through Monte Carlo trials. In this method, synthetic data is generated and then aggregated to generate a single final result. However, tiling algorithm performance is dependant on data distribution, so a single aggregateresult cannot generalize overall performance. The alternative suggested in this thesis is visual cluster analysis, which should hold more general predictive power.All of the above is put into practice with an experiment. In the experiment, a new family of tiling algorithms, based on criteria derived from the results of the perceptual tests in literature,is compared to the most popular tiling algorithm, Squarify. The results confirm that there are indeed vast but consistent value fluctuations for different normal distributions. At least for a target aspect ratio of 1.5, the new proposed algorithms are shown to perform better than Squarify for most use cases in terms of aspect ratio.