iMetaSearch Minimum Spanning Tree

Groups in iMetaSearch are based on finding groups of similar search results. In order to find groups, the SVD algorithm in the previous group is run on the search. This maps results into high dimensional space with the property that similar results tend to end up close to each other. In order to turn this information into groups the following steps are performed:

1) A minimum spanning tree is calculated for all the results in the space. By definition, this means all the results are linked together into a tree with the shortest links possible.

2) The links of the minimum spanning tree are broken one at a time, starting with the longest link and progressing down to the shortest link. Each broken link splits the group of results into two smaller groups, and the larger of the two smaller groups is always sorted to the left. Then the largest link in each of those two groups is broken in the same way and so on, until only groups of size 2 or less remain.

3) The number of groups set by the cluster slider control determines how many links are broken, and thus how many groups are shown. Fewer broken links mean a smaller number of larger groups. More broken links mean a larger number of smaller groups.

The result of this series of steps is that the results are divided into groups. Results are initially sorted by group when a search is first displayed and can also be sorted by clicking the Group column header.

The Group of Results section has a list of all groups. The description in ech row has 3 index words/phrases that describe the group. Clicking the checkbox of a group marks the main result of that group, and updates the relevance bars of all groups, results, and words instantly.