All examples By author By category About

rpgove

Random Vertex Sampling vs. Barnes-Hut Approximation

A performance comparison of d3.forceManyBodySampled() in d3-force-sampled and the standard d3.forceManyBody() in d3-force. d3.forceManyBodySampled() tends to perform 2-3x faster than d3.forceManyBody() on common graph sizes. It achieves this performance improvement by using the Random Vertex Sampling algorithm instead of the Barnes-Hut approximation, and therefore it achieves linear runtime and space complexity. See d3-force-sampled and the research paper for more details:

Robert Gove. "A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts." Computer Graphics Forum 38, 3 (2019). Preprint PDF.