Tag Cloud Algorithm/Logic/Formula

I wanted to implement a very efficient tag cloud generator. Initially I thought it’s a simple task, but realized making it efficient is a bit challenging. I came up with a bunch of ideas on how to do that and then searched on the web to find if there are any articles related to it. I noticed that most of them talk about how to divide the data into buckets, using some sort of a formula including logarithms etc. There are bits and pieces of code here and there, but somehow nothing excited me. So, let me put together some of my thoughts on this.

A tag cloud requires a tag and a number associated with that tag. That number is usually a metric. What’s so special about a tag cloud? Typically information in business applications is presented as a table which can then be sorted. So, at any time, user can sort by the name of the entity in the report or by the metric of that entity. For example, by customer name or the dollar amount spent by the customer. However, what a tag cloud offers is the ability to get the ordering of both the entity and the metric in a single visual representation. This is done by laying out the data in the order of the entity but changing the size/color intensity of that entity based on the metric value. As a result, while the user can scan top to bottom (and left to right) for alphabetical ordering of the entities, user can also scan for the font-size/color intensity at the same time. So, an extra sort is avoided to gather the ordering for each. Ofcourse, for precise details, one has to sort either for the entity or the metric explicitly.

Now, the next question is, how to vary this size/intensity metric? Is some linear interpolation sufficient enough? Does it have to be logarithmic? This to a large extent depends on the data distribution. If the difference between the highest value and the least value of the metric is so large (o(10^n)), then logirthmic interpolation may help. However, sometimes it may not be worth showing every entity in the tag cloud. Just the top N entities are good enough. If we go with the top N approach, then max and the min of the top N entities may not be that wide spread and in this case a linear interpolation should suffice.

One reason I would caution against using a logarithmic interpolation is that it’s expensive to compute and if you are doing it real-time and with huge volume, then that’s going to be CPU intensive. So, try using the topN and linear interpolation.

Next, in the linear interpolation, how do we set the min and max boundaries for the font size/color intensity? I notice that Amazon.com for example, is ranging it’s font sizes between 80% and 280%. So, the lowest tag in the cloud would get a font size of 80% and the highest tag 280%. I have decided to go with the following formula

150*(1.0+(1.5*m-maxm/2)/maxm)

This nicely gives a font size from 75% to 300% as the metric changes from a potential 0 to maxm. Check Tag Cloud Generator for this formula in action.

Ok, if we go with this topN approach, then the next question is how do we get this top N? For this, one has to invariably write a SQL statement. Something like

“select entity,metric from fact order by metric desc” which gives all the entities.

One can refine this to restrict only to the topN by doing the following

“select entity,metric from fact ordre by metric desc limit 0,<n>” where you can plugin a particular number suitable for your application.

Now, with the above SQL, we obtained the Top N entities. However, we want them in alphabetical order as that’s how we want to display the cloud. How do we do this? One approach is to fetch them all first and then do a sort in the middle-tier. Depending on the size of the N and the number of middle tiers you have, you have to chose doing this in middle tier vs database. Assuming you have a single middle tier server, then perhaps doing in the database (also a single server) may not be bad. So, the above SQL will refine to

“select * from (select entity,metric from fact order by metric desc limit 0,<n> ) order by entity”

In the above configuration of a single mt and db server, chosing to do this in database gives the advantage of not having to create an array of records in the middle-tier for doing the sort as the sort is done in the database itself (which I am assuming has more optimal sorting strategies). So, one can just loop through the result set and output the entities.

However, there is one small problem with this. By sorting the TopN alphabetically in the database itself, we don’t have the max metric value. If we don’t have the max metric value, how do we then really calculate the size/intensity? So, does it mean I have to get the results set into an array first and then scan through to get the max? Then that defeats the purpose of double sorting in the database as mentioned above.

With Oracle, it’s possible to use Analytical functions and get the max of the entire set as a column in the query. But hae, most guys out there are using MySQL for their web apps. Isn’t it? So, what next?

That’s when I thought of using the javascript to do the fontsize calculation on the client side! Yes, the idea is, loop through the results set and generate the HTML code.
And in due process maintain the max value and output it as a javascript variables that will be used in the client side computation. Now, when the tags are generated as links, make use of the link’s title attribute to capture the metric value. Like the title may read “some description: “.

Now, in the javascript, you can loop through each of the link, compute the font size, and set it for the link. A snippet of that function would look like

function processCloud(id,max) {
var cloud = getElement(id);
if(!cloud) return;
var tags = cloud.getElementsByTagName("a");
for(var i=0;i<tags.length;i++) {
var tag = tags[i];
var title = tag.getAttribute("title");
var f = title.substring(title.indexOf(":")+1);
var fontSize = (150.0*(1.0+(1.5*f-max/2)/max))+"%";
tag.style.fontSize = fontSize;
}
}


Here, getElement is a utility function that gets the element from the document based on a given id. So, your tag cloud can be placed in a div element with an id and that’s the id you pass to the processCloud function along with the max value that is computed as part of generating the html.

That’s it. This essentially does the following optimizations

1. Since we first sort by metric and limit only the top N elements, there is no need to bring in all the elements into the middle tier.
2. Since we then sort the data by name, there is no need to create an array in the middle tier and do the sort.
3. Finally, since the fontsize/intensity calculation is pushed to the client side, there is no need to create an array in the middle tier.

That’s all there is. Hope this helps in your application!