Muac is a fast algorithm (n log(n)) for calculating the 2 dimensional KS test for two samples. Python code is used to illustrate and test the algorithm. The timings in the plot below are for python code and show the relative performance for different algorithms. An ANSI C routine is also available - on my laptop (200 MHz pentium, running Linux), it reads, sorts and processes 20000 points in just over 2 seconds.
Every possible quadrant is tested to find the largest difference
between two collections of points. The naieve algorithm for this
code is n^3 - Muac does the same in n
log(n) (another popular algorithm, which only tests a
restricted number of quadrants centred on observed points, has a
naieve speed estimate of n^2).
The KS (Kolmogorov-Smirnov) test is a standard non-parametric test to compare the distribution of two populations of points. The 2 dimensional analogue is used in astronomy.
The following information is available:
- Download Muac and associated files as tarball (unix) or zipped archive. Some browsers may try and display the tarball rather than saving it to disk - if so, use "save link as a file", or similar, from your browser menus or right mouse button (sorry - I am trying to get the server here re-configured).
- Installation instructions.
- A description of the algorithm.
The name "Muac" is spanish for (the sound of a) "Kiss" (ie. KS) and is pronounced "mwak" (one syllable).
