It seems once again I got ahead of myself. The improved testing suite, Osmium, has been hit by a significant flaw. The results yielded for the Octree implementation greatly differs from what is expected, so much so that a fair comparison to the MGF approximation cannot be achieved.
To summarise the observations: layouts using the Octree approximation are achieved approximately 8x quicker than our own MGF approximation, however (following the rules of the universe), the quality of those drawings is very poor (some would suggest that there is no layout, instead materialising as a messy ball of vertices and edges). The cause is yet to be confirmed, but the behaviour was not in previous versions. Unfortunately, rolling back to such versions provides an unfair comparison of algorithms, as many of the underlying algorithms have been replaced to better suit the clustering.
Although this is an issue I would prefer to resolve, time is not permitting and so I will continue with an analysis of the MGF results for our Technical Report (comparison against other work was carried out before the introduction of clustering, so its not too big of an issue to omit such comparison at this stage - although it would be preferable).
As for other work, I have continued to make small contributions to my very very draft thesis outline (although at the moment its more accurate to say "contributions to my desktop") and have been plotting out ideas for the dynamic/online graph drawing. I have also finished my secondary collection of literature (specific to our next piece of work), so am preparing to make my way through them to find what I can/cant/shouldn't use and look for any ideas for improvements.
Not much else to say for now but the deadline for the RDA2 form is looming and the amount of work I have left is starting to look more and morel like a mountain - guess that's what I get for being lazy, heh.
Monday, 27 August 2012
Wednesday, 15 August 2012
Refreshment
Well, its been an eventful few days and unfortunately, this leads to a lengthy blog post. But not to worry, a TL:DR has been included at the bottom! So feel free to skip the bulky part if limited for time, or are just lazy, like me, as I expect to be when re-reading this in my future. By the way, hello Carl...
I have made good progress on most writing related items, and am currently re-reading and editing (if and where required) my attempts at an RDA2 report, technical report and to some extent, thesis material. It should be noted that the RDA2 report is short (currently only a page) and non-technical, involving no knowledge of my work - its more of a research-only peice which mentions what ive done, i.e. literature survey processes etc.
The technical report, I was still unsure about. All (most) items regarding the Multilevel Global Forces work, without clustering, has been written and undergoing the same checks. The results for the clustering though, they were a nuisance. Not only did they not match my expected results, for example, a clustering of 2 vertices should have given me drawings of similar quality and similar runtime to those in standard edge contraction - but they did not (yet the octree results did return expected results).
After some lengthy work on the testing suite, I finally found the answer to my doubts. The bad results had been due to conflicting movements. For context, when a level has been given a layout in the MGF algorithm, a post-order search of the tree is carried out to update the coarser graphs with updated coordinates of the finer graphs, and so, keeping the approximation tree up to date. This is similar to a process required to keep the octree up to date, but is not required in the multilevel paradigm alone. In my haste to progress with the clustering, I had rewritten some code without thinking twice about it.
Well instead of updating the coordinates in the tree, I was actually adding them to the already existing coordinates previously computed. This generated awful layouts, and when coupled with a different but similar issues, increased runtime too. Having fixed this, layouts now look much better and re-testing of the clustering has begun (another lengthy process but worth the more accurate results).
In addition to this fix and the reports, I begun thinking towards the MPhil to PhD viva and what might be expected of me. It is then I made a horrible realisation: people might want to see this Testing Suite ive been bragging about. Therefore, I have spent the majority of my time over the past few days, cleaning the test suite and ensuring everything is in working order. In this clean up, I have resolved so many undiscussed bugs it is not true, and have even cleared up some of the theory behind the work (values of K, repulsive forces and viewing sizes etc). This new suite lead me to the discovery of my clustering issue, and will now be a prototype system to a finished product, should my work go that far.
Now if anyone is thinking like me, they'll be screaming "you have bigger things to worry about - dynamics for instance". My argument to this is that if I hadn't done it now, I might not have found time towards the end, or even worse, I would have forgotten everything about the code (admittedly an issue I had now) and may never have fixed my bug with clustering.
TLDR:
I have made good progress on most writing related items, and am currently re-reading and editing (if and where required) my attempts at an RDA2 report, technical report and to some extent, thesis material. It should be noted that the RDA2 report is short (currently only a page) and non-technical, involving no knowledge of my work - its more of a research-only peice which mentions what ive done, i.e. literature survey processes etc.
The technical report, I was still unsure about. All (most) items regarding the Multilevel Global Forces work, without clustering, has been written and undergoing the same checks. The results for the clustering though, they were a nuisance. Not only did they not match my expected results, for example, a clustering of 2 vertices should have given me drawings of similar quality and similar runtime to those in standard edge contraction - but they did not (yet the octree results did return expected results).
After some lengthy work on the testing suite, I finally found the answer to my doubts. The bad results had been due to conflicting movements. For context, when a level has been given a layout in the MGF algorithm, a post-order search of the tree is carried out to update the coarser graphs with updated coordinates of the finer graphs, and so, keeping the approximation tree up to date. This is similar to a process required to keep the octree up to date, but is not required in the multilevel paradigm alone. In my haste to progress with the clustering, I had rewritten some code without thinking twice about it.
Well instead of updating the coordinates in the tree, I was actually adding them to the already existing coordinates previously computed. This generated awful layouts, and when coupled with a different but similar issues, increased runtime too. Having fixed this, layouts now look much better and re-testing of the clustering has begun (another lengthy process but worth the more accurate results).
In addition to this fix and the reports, I begun thinking towards the MPhil to PhD viva and what might be expected of me. It is then I made a horrible realisation: people might want to see this Testing Suite ive been bragging about. Therefore, I have spent the majority of my time over the past few days, cleaning the test suite and ensuring everything is in working order. In this clean up, I have resolved so many undiscussed bugs it is not true, and have even cleared up some of the theory behind the work (values of K, repulsive forces and viewing sizes etc). This new suite lead me to the discovery of my clustering issue, and will now be a prototype system to a finished product, should my work go that far.
Now if anyone is thinking like me, they'll be screaming "you have bigger things to worry about - dynamics for instance". My argument to this is that if I hadn't done it now, I might not have found time towards the end, or even worse, I would have forgotten everything about the code (admittedly an issue I had now) and may never have fixed my bug with clustering.
TLDR:
- More progress reading and editing the various documents for RDA2 (MPhil to PhD transfer)
- Fixed bug causing the horrors that were my results for clustering
- Running fresh tests for clustering, ETA 2 days, then finally an end to the MGF business
- Cleaned and re-programmed much of the Testing Suite, now codenamed Osmium [Alpha] - formerly WeaponX (more of a personal nickname for it... if you can think of anything better, let me know!)
- All algorithms are in a "default" mode, allowing for any graphs to be input in Chaco format, and requiring no (or little) changes to the settings/code
Wednesday, 8 August 2012
Deep into the Work Load
Probably time for another update.
I am making my way through the work load I discussed in my last post, albeit slowed by my discovery of yet another MMO (this time it's S4League). I have made some good progress with the Technical Report and am currently awaiting some further results to confirm some analysis (and remove doubt). It should be noted, making things in excel uniform and pretty for a report is the most time consuming and tedious task I have known this week.
Further to the technical report, I have been filling out my RDA2 form (though there's not much to fill out), I have been checking over my literature review/survey in preparation of finalising it for inclusion in my Thesis skeleton, and as a final push, begun implementation of the Veldhuizen dynamic graph drawing technique.
There is still much to do, but I am slowly coming closer to reaching my aim for work to be completed by the next Research Committee Meeting (which I have now been told requires all forms be submitted by September 9th).
I will hopefully update again later this week or early next. Aim for then? completion of the Technical Report if I'm lucky... for now, good night!
I am making my way through the work load I discussed in my last post, albeit slowed by my discovery of yet another MMO (this time it's S4League). I have made some good progress with the Technical Report and am currently awaiting some further results to confirm some analysis (and remove doubt). It should be noted, making things in excel uniform and pretty for a report is the most time consuming and tedious task I have known this week.
Further to the technical report, I have been filling out my RDA2 form (though there's not much to fill out), I have been checking over my literature review/survey in preparation of finalising it for inclusion in my Thesis skeleton, and as a final push, begun implementation of the Veldhuizen dynamic graph drawing technique.
There is still much to do, but I am slowly coming closer to reaching my aim for work to be completed by the next Research Committee Meeting (which I have now been told requires all forms be submitted by September 9th).
I will hopefully update again later this week or early next. Aim for then? completion of the Technical Report if I'm lucky... for now, good night!
Thursday, 2 August 2012
Olympic Work Load!
So goes another week of "work", which is unfortunately slower than anticipated. As mentioned previously, I am writing my technical report, which other than explanation of results, is going well. I have cut down much of my unnecessary literature (though most of it can be used in the Literature Survey/Review in my thesis) but am struggling to discuss the results of my experimentation.
I am aware its "good" to question my own work, but I'm starting to think there is such a thing as "too much questioning". I find myself questioning my own methodologies and as consequence, I am becoming unsure of my results. Unfortunately my doubts have to be suspended due to the lack of time I can spend on this (arguably I've wasted too much time already).
Awareness of your own work is damn annoying.
I will still aim for the end of the week, but once again my work load is increasing (oddly by my own expectations) - with the next Research Commitee Meeting two months away, I am expecting them to request any RDA forms before the 9th September. By this time, I would ideally like my Technical Report complete (an end to my work with the MGF algorithm for static graphs) and an implementation of Veldhuizens dynamic work. Additionally, I suspect they would also like to see evidence of me having started my thesis.
We shall see, still a few weeks away but time is starting to slip by ever more quickly. As always though, I do like a challenge!
P.S. GO TEAM GB!
I am aware its "good" to question my own work, but I'm starting to think there is such a thing as "too much questioning". I find myself questioning my own methodologies and as consequence, I am becoming unsure of my results. Unfortunately my doubts have to be suspended due to the lack of time I can spend on this (arguably I've wasted too much time already).
Awareness of your own work is damn annoying.
I will still aim for the end of the week, but once again my work load is increasing (oddly by my own expectations) - with the next Research Commitee Meeting two months away, I am expecting them to request any RDA forms before the 9th September. By this time, I would ideally like my Technical Report complete (an end to my work with the MGF algorithm for static graphs) and an implementation of Veldhuizens dynamic work. Additionally, I suspect they would also like to see evidence of me having started my thesis.
We shall see, still a few weeks away but time is starting to slip by ever more quickly. As always though, I do like a challenge!
P.S. GO TEAM GB!
Subscribe to:
Posts (Atom)