Results for CaS collection decomposition

In order to allow a quick analysis of the XML file produced by the Collection-aware Segmentation (CaS) algorithm, I wrote a simple XSL transformation that shows CaS results in an easily readable format.

For instance, here you can take a look at the result of decomposing the Flat-Thin Components cluster from Purdue's ESB with CaS.

CAS name change

From discussions with colleagues from SMG at IMATI-Ge, we concluded that the name originally given to the decomposition algorithm was not the most appropriate. Indeed, it might lead to some confusion and misinterpretation. Therefore, we decided to change the algorithm name to "Collection-Aware Segmentation".

In practice it is not so bad

After making some changes in the CAS algorithm and improving the prototype (basically, I write its core from scratch) I could study its behavior with larger collections. The results were positive because the growth of the shape pool is far below the simulated worst case. Indeed, after the third iteration the number of segments to add to shape pool decreases and within seventh iteration is very low. The chart bellow illustrates exactly this.

Shape pool growth (using a set of 273 models extracted from ESB)

CAS shape pool segment growth

As I was expecting, the context-aware segmentation (CAS) approach can potentially led to an exponential growth of the number of segments in the shape pool. Theoretically, if all the branches of the segmentation tree are expanded, after seven iterations the number of segments can grow so much that will be impossible to store in memory all their signatures. The charts below illustrate the worst case for two distinct collections with one and eight hundred models respectively.

Number of segments in shape pool

Memory necessary to store segment signatures

Writing CAS/HFP on XML file

Since I will now test the CAS/HFP algorithm with larger collections, I needed to devise a way to store the segmentation in order to be able to re-use it without having to process it again. Thus, I have implemented a feature that allows writing to (and reading from) a XML file the segmented collection. Moreover, the computed signatures for segments and corresponding similarities are also saved. Below is an excerpt of a XML file describing a collection decomposition.

Excerpt of XML decomposition file.