Writing · Visualisation · 5 min read
Drawing a graph that's too big to draw
Spatial indexes, culling, level of detail and a single event listener: the unglamorous techniques that make a huge biological network feel instant.
Biological pathway maps are big. A single map can hold thousands of genes, compounds and reactions, and the questions people ask of them are interactive ones: where does this gene sit, what's connected to it, how does expression change along the path. They want to pan, zoom, hover and click, and they want the map to keep up.
Making large KEGG pathway maps fast enough to explore is one of the most satisfying problems I've worked on. Very little of the speed in work like this comes from a faster drawing library. It comes from drawing, checking and listening to far less, using a handful of techniques that apply to any big interactive visualisation.
1Stop comparing everything with everything
Drawing a map involves a lot of "does this overlap that?". Labels mustn't collide, nodes need room, and a click has to land on the right thing. The obvious way to answer is to compare every pair. For n items that's n(n − 1)/2 comparisons, so five thousand nodes means about twelve and a half million checks, every time anything moves.
A spatial index fixes this by remembering where things are. A quadtree splits the plane into four, then splits again wherever a square holds too many items. To find what overlaps a label, you look only in the squares that label touches, and most of the map is never examined. An R-tree does the same with nested bounding boxes and copes better with rectangles of very different sizes. Either way, the cost of a question stops depending on the size of the whole map.
this probe –whole map –
2Only draw what's on screen
The second technique sounds too obvious to mention, and it's skipped constantly: don't draw what nobody can see. At any moment the viewport shows a small part of a big map, and everything outside it can be skipped. Finding what's inside is, again, a spatial index query.
Zoomed out, the opposite problem appears. Everything is visible, but individual nodes are a pixel wide and their labels are unreadable smudges, so drawing them in full is pure cost. Level of detail means drawing a simpler version when the detail can't be seen: clusters instead of nodes, no labels below a legible size, short straight edges instead of every one. Zoom in and the detail returns, but by then most of the map is off screen.
drawn –frame –
3One listener, not ten thousand
The last technique is about memory rather than speed. The easy way to make nodes interactive is to give each one its own event handler, a hover listener holding a closure over that node's data. With thousands of nodes that's thousands of objects, and if the map re-renders without removing the old handlers, every re-render adds thousands more. Memory climbs until something gives, and in a long-lived dashboard something always does.
Event delegation replaces all of them with a single listener on the container. When the pointer moves, that listener asks the spatial index which node is underneath, and shows the tooltip for that one. There's nothing per node left to leak, so memory stays flat however often the map redraws.
listeners –memory –
Tooltips are a classic place for leaks, because they're created and destroyed constantly and they hold references to the data they describe. I once diagnosed one in the tooltip rendering of a production Shiny dashboard. Fixing it cut the app's memory use by 90% and ended the disconnects its users had been hitting, and nobody had to change how they used it.
4Fast enough to stop noticing
There's a point in interactive work where speed stops being a feature and becomes the absence of friction. When a map answers in a few milliseconds, people stop waiting for it and start thinking with it. None of these techniques is new and none is clever. Together they're the difference between a visualisation people tolerate and one they actually use.