Thursday, August 23, 2007

Treemap Widget in Dojo GFX

Last week I was working on implementing 'bin packing' algorithm and visualizing output on 2D plane, using DOJO toolkit. At the time of this post it's available here:

It shows categories of footprint and descendant items. Implemented in dojo gfx (SVG/VML).

Some information on bin packing:

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, and creating file backup in removable media.

Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires O(n log n) time. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.


Got an idea to use the treemap widget in Ganglia project.
It contains two rationales:
a) use treemap to visualize metrics, so it is more compact and doesn't poll every X amount of time.
b) use client-side code to render readings and be more compact way to display multiple parameters

In the following demo I used dojo toolkit (version 0.9) and php:

Dojo's SVG support is still experimental though (i think it is a wrapper interface for both SVG implementations).

I'm planning on implementation of another approach which uses curves instead of rectangles (based on Voronoi tesselations).

No comments:

Cloud Computing Google Group