slinnarsson
commented
8 years ago One thing to remember is that I would like the tiles to not be simply uniformly colored, but to actually show single cells. That is, if there’s a tile deep down which represents 200 cells, it might be a 20x10 pixel rectangle (or, say 40x20) and each pixel would have an intensity given by the expression of some gene in those cells.
Recall that we have an expression matrix (loom file) with ~25,000 rows (genes) and, say, 200,000 columns (cells). There would be a total of 25,000 different treemaps, one per gene. The layout would be the same for all of them, but the pixel intensities would be different. So one challenge is how to (efficiently) take a single row of data from the matrix and paint it onto the tiles of the treemap, while still being able to zoom in and out by clicking on tiles. One solution would be to have off-canvas bitmaps for each tile, paint them with data for the given gene, then draw them onto the canvas.
On 13 Aug 2016, at 18:31, Job van der Zwan notifications@github.com<mailto:notifications@github.com> wrote:
As mentioned in #15https://github.com/linnarsson-lab/Loom/issues/15:
Paper on how to make squarified treemaps:
http://www.win.tue.nl/~vanwijk/stm.pdfhttp://www.win.tue.nl/%7Evanwijk/stm.pdf
Found on the page for this jQuery based implementation:
Recharts also has a react-implementation of a treemap, but it sadly comes with too much baggage to be directly usable:
http://recharts.org/examples/#CustomContentTreemap
However, it has made me think about how to implement the data structure underlying the treemap.
Here is how Recharts does it. It is an easy-to-read but not very efficient lay-out of the data:
const data = [ { name: 'data', children: [ { name: 'Data', size: 20544 }, { name: 'DataList', size: 19788 }, { name: 'DataSprite', size: 10349 }, { name: 'EdgeSprite', size: 3301 }, { name: 'NodeSprite', size: 19382 }, { name: 'render', children: [ { name: 'ArrowType', size: 698 }, { name: 'EdgeRenderer', size: 5569 }, { name: 'IRenderer', size: 353 }, { name: 'ShapeRenderer', size: 2247 }, ], }, { name: 'ScaleBinding', size: 11275 }, { name: 'Tree', size: 7147 }, { name: 'TreeBuilder', size: 9930 }, ], }, ];
The tree is built up out of an array of objects (just one in this example), which can contain more arrays of objects.
Each object has a name, and either a size or an array of children; if no size is present it's calculated by looping over the children. The treemap is built up recursively that way.
This is intuitive, but what's more efficient is to have an objects of arrays:
const data = { names: [ 'data' ], sizes: [ 110583 ], children: [ { names: [ 'Data', 'DataList', 'DataSprite', 'EdgeSprite', 'NodeSprite', 'render', 'ScaleBinding', 'Tree', 'TreeBuilder', ], sizes: [ 20544, 19788, 10349, 3301, 19382, 8867 , 11275, 7147, 9930, ], children: [ null, null, null, null, null, { names: [ 'ArrowType', 'EdgeRenderer', 'IRenderer', 'ShapeRenderer', ], sizes: [ 698, 5569, 353, 2247, ], children: null, }, null, null, null, ], }, ], };
It may not be directly obvious why this is more efficient. Compare looking up the names of children before and after. Before, we had to:
- dereference the object from the array,
- dereference the name String from the object
- dereference the next object,
- dereference the name, etc.
In the second version, we:
- dereference the array of names once, then
- loop over the array to dereference every name string.
Aside from the initial array dereferencing, we skip an object dereference for per child.
Same with the sizes array. First of all, there's no reason to calculate the size for the nodes every time, since the data is fixed anyway. Just calculate it once and store it in the sizes array; if we want to display two nesting levels of a tree that goes ten levels deep that saves us pointless recursion. Second of all, JS engines are smart enough to detect if an array has only integers, and creates a fast, dense array. This is even more memory- and cache friendly. Heck, we could even go nuts and use a TypedArray.
Another benefit of this split is that quite often we only care about the sizes. The output of Recharts' treemap itself is actually a good illustration of this:
[image]https://cloud.githubusercontent.com/assets/259840/17644150/6df3ab7a-617f-11e6-8f69-3bf849b03e29.png
We don't care about the names of deeply nested objects! With this set-up we can just loop over the sizes array to fill a square and then for each sub-tile recurse over children.
(aside: this treemap is trying to pack its contents as squares, which has all kinds of issues, as explained in the paper by Van Wijk)
That leaves the children array. Again, the benefit of separating this from the size array is that we only need to loop over it if we want to display deeper levels.
However, for this recursion we still need to check for every entry if it's a leaf or a node. Applying the same optimisation trick as before to separate leaves and nodes fixes that:
const data = { nodeNames: [ 'data' ], nodeSizes: [ 110583 ], nodeChildren: [ { leafNames: [ 'Data', 'DataList', 'DataSprite', 'EdgeSprite', 'NodeSprite', 'render', 'ScaleBinding', 'Tree', 'TreeBuilder', ], leafSizes: [ 20544, 19788, 10349, 3301, 19382, 8867 , 11275, 7147, 9930, ], nodeNames: [ 'render' ], nodeSizes: [ 8867 ], nodeChildren: [ { leafNames: [ 'ArrowType', 'EdgeRenderer', 'IRenderer', 'ShapeRenderer', ], leafSizes: [ 698, 5569, 353, 2247, ] }, ], }, ], };
Admittedly, neither of these are as human-readable compared to the first data structure. However, it's more efficient for computers. Also, it's not going to be made by humans, it's going to be computer-generated.
Note that the examples given here do not show off the benefits best - these are bigger when there are more leaves and children for every node. However, it should be noted the worst case scenario for this scheme (one child per node, many levels deep) no worse than the original scheme, and every other scenario is better.
BONUS CONTENT: my shitty sketches of these three schemes
[2016-08-13 18 04 25-2]https://cloud.githubusercontent.com/assets/259840/17644290/79727cd0-6182-11e6-9930-60f807c12ca8.jpg
[2016-08-13 18 04 38-2]https://cloud.githubusercontent.com/assets/259840/17644291/79761bce-6182-11e6-99b4-0311b71d1008.jpg
[2016-08-13 18 07 55-2]https://cloud.githubusercontent.com/assets/259840/17644289/79720552-6182-11e6-9533-76ecf32dc686.jpg
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/linnarsson-lab/Loom/issues/43, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AKKagzeFe3kbBbmU0WzotcXS4XXyGbL_ks5qffF7gaJpZM4Jjtbs.
JobLeonard
As mentioned in #15:
Recharts also has a react-implementation of a treemap, but it sadly comes with too much baggage to be directly usable:
However, it has made me think about how to implement the data structure underlying the treemap.
Here is how Recharts does it. It is an easy-to-read but not very efficient lay-out of the data:
The tree is built up out of an array of objects (just one in this example), which can contain more arrays of objects.
Each object has a name, and either a size or an array of children; if no size is present it's calculated by looping over the children. The treemap is built up recursively that way.
This is intuitive, but what's more efficient is to have an objects of arrays:
It may not be directly obvious why this is more efficient. Compare looking up the names of children before and after. Before, we had to:
In the second version, we:
Aside from the initial array dereferencing, we skip an object dereference for per child.
Same with the sizes array. First of all, there's no reason to calculate the size for the nodes every time, since the data is fixed anyway. Just calculate it once and store it in the sizes array; if we want to display two nesting levels of a tree that goes ten levels deep that saves us pointless recursion. Second of all, JS engines are smart enough to detect if an array has only integers, and creates a fast, dense array. This is even more memory- and cache friendly. Heck, we could even go nuts and use a
TypedArray.Another benefit of this split is that quite often we only care about the sizes. The output of Recharts' treemap itself is actually a good illustration of this:
We don't care about the names of deeply nested objects! With this set-up we can just loop over the
sizesarray to fill a square and then for each sub-tile recurse overchildren.(aside: this treemap is trying to pack its contents as squares, which has all kinds of issues, as explained in the paper by Van Wijk)
That leaves the children array. Again, the benefit of separating this from the size array is that we only need to loop over it if we want to display deeper levels.
However, for this recursion we still need to check for every entry if it's a leaf or a node. Applying the same optimisation trick as before to separate leaves and nodes fixes that:
Admittedly, neither of these are as human-readable compared to the first data structure. However, it's more efficient for computers. Also, it's not going to be made by humans, it's going to be computer-generated.
Note that the examples given here do not show off the benefits best - these are bigger when there are more leaves and children for every node. However, it should be noted the worst case scenario for this scheme (one child per node, many levels deep) no worse than the original scheme, and every other scenario is better.
BONUS CONTENT: my shitty sketches of these three schemes