All examples By author By category About

rpgove

Speeding up KDE heatmaps with Barnes-Hut quadtrees

Performance comparison of a brute force kernel density estimation (KDE) heatmap vs. a Barnes-Hut quadtree KDE heatmap.

This example creates an array of node positions at every tick of a force-directed algorithm. Then it generates two heatmaps from all of the collected node positions.

The Barnes-Hut approximation is markedly faster and looks the same when there are many points. When there is a very small number of points, the extra cost of constructing the quadtree makes the Barnes-Hut heatmap slower. But after just a few ticks, there are enough points that the Barnes-Hut heatmap is much, much faster.

In data visualization, the Barnes-Hut approximation is often used for speeding up force-directed graph layouts, but it has many other potential uses, such as this example here.

See also: