1901248 - Compute a better bandwidth for the KDE graph

Status: NEW

(Testing :: PerfCompare, enhancement)

Description

[Julien Wajsberg [:julienw]]

Currently we simply use "stddev" as the bandwidth, but this isn't correct and produces graphs that are too smoothed to be useful.

According to resources I could find, the Sheather and Jones algorithm seems to be one to use for cases like us (see https://aakinshin.net/posts/kde-bw/).

With a quick search I couldn't find a javascript implementation but I found other ones:
C++: https://www.umiacs.umd.edu/labs/cvl/pirl/vikas/Software/optimal_bw/optimal_bw_code.htm (albeit LGPL)
Julia: https://github.com/rasmushenningsson/KernelDensitySJ.jl (MIT)

There may be implementation that I haven't found though. If we manage to implement it it could be good to contribute it back to fast-kde.

Comment 1

[Julien Wajsberg [:julienw]]

Thanks to the wikipedia page, I found this other interesting paper: https://espace.library.uq.edu.au/view/UQ:120006
I haven't read it yet, but I think this is also related to Sheather and Jones.

Comment 2

[Julien Wajsberg [:julienw]]

Python implementation: https://kdepy.readthedocs.io/en/latest/bandwidth.html#the-improved-sheather-jones-algorithm
https://github.com/tommyod/KDEpy/blob/f907fc7617d234d3663d850fca9a63040addccf9/KDEpy/bw_selection.py#L128-L207

Now I hesitate between directly using KDEpy on the treeherder side, reporting the bandwidth value in the results, or reimplementing it in JS.

Comment 3

[Julien Wajsberg [:julienw]]

padenot ran a benchmark simulating the computation for many rows, this ended up being ~300ms on his machine.
(tried on my machine => 200ms)

It may be too much, this is approximately the same time as a call for the browsertime framework on some mozilla-central revisions.

So the JS route might be better, where we'd compute it only on demand when showing the graph.

Comment 4

[Julien Wajsberg [:julienw]]

A simplified version of the Shear and Jones algorithm has been implemented in https://github.com/mozilla/perfcompare/pull/903