InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method to Improve Treemap Layouts with Multiple Refinement Passes

IP.com Disclosure Number: IPCOM000228736D
Publication Date: 2013-Jul-02
Document File: 5 page(s) / 126K

Publishing Venue

The IP.com Prior Art Database


This disclosure describes an optimization pass for treemap layouts. It is aimed at improving elongated items that often appear when the last items are being laid out. The pass consist of moving all items of the last block into the previous and moving back items from the (last - N) for N > 1 block to the (last - (N + 1)) block as long as it improves the situation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 01 of 5

Method to Improve Treemap Layouts with Multiple Refinement Passes

I.1 Context

This disclosure addresses the area of interactive data visualization, more particularly treemap visualization. Treemaps http://www.cs.umd.edu/hcil/treemap-history/, http://en.wikipedia.org/wiki/Treemapping, are a display technique allowing to present a hierarchy of data items in a very compact way. This disclosure presents a method to improve layouts with one or more refinement passes after the initial layout. These passes improve the layout of items that tend to have a bad aspect ratio due to the nature of the layout algorithm.

I.2 Problem

    A common approach in creating layouts for treemaps is to stack items (either horizontally or vertically) in a block as long as some condition is met (e.g. the average aspect ratio is improved when a new block is added). Although this approach gives good results for most of the blocks in the final layout it often happens (especially when data is sorted) that the last block has a very bad aspect ratio. This results in various thin blocks scattered over the layout which are barely readable or usable for interaction.

This problem is clearly shown in the next figure which shows cities in the state New Jersey. Apparently adding the last city to the first last column did not meet the algorithm criterion and therefore it was added to a newly added block, resulting in a very tall item for which the label cannot be read and which is hard to interact with using a mouse.

I.3 Related art

http://citeseerx.ist.psu.edu/viewdoc/download?doi= pdf One approach for obtaining layouts with better aspect ratios is the squarified treemap layout algorithm. This method uses the resulting aspect ratio as measure to decide whether the next elements should be stacked horizontally or vertically in order to produce a layout where as many items as possible reach an aspect ratio of one. http://citeseerx.ist.psu.edu/viewdoc/download?doi= pdf Another approach is the ordered treemap where a pivot item is chosen according to a pivot selection strategy. If the number of items is greater than four, the area is divided into four squares, one of which will contain the pivot item and the other ones the remaining items.

Page 02 of 5

I.4 Remaining issue

    Both above described methods give fairly good results in terms of the aspect ratio of the items in the final layout. However, both fail to preserver the strict ordering of the items.

Our method consists of making an additional pass over the blocks that have been laid out using any treemap algorithm, and improving the last blocks by pushing back items from a block to the previous block. Additionally we treat the last block specially, as it tends to become elongated when data is sorted from large to small by moving all items in this block to the previous block. Considering that:

- When data is sorted from small to large the small items already have a reaso...