×

A fast algorithm for two-dimensional Kolmogorov-Smirnov two sample tests. (English) Zbl 1466.62219

Summary: By using the brute force algorithm, the application of the two-dimensional two-sample Kolmogorov-Smirnov test can be prohibitively computationally expensive. Thus a fast algorithm for computing the two-sample Kolmogorov-Smirnov test statistic is proposed to alleviate this problem. The newly proposed algorithm is \(O(n)\) times more efficient than the brute force algorithm, where \(n\) is the sum of the two sample sizes. The proposed algorithm is parallel and can be generalized to higher dimensional spaces.

MSC:

62-08 Computational methods for problems pertaining to statistics
62G10 Nonparametric hypothesis testing

Software:

Quicksort; XCVMTest
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burr, E. J., Small-sample distribution of the two-sample cramér-von Mises criterion for small equal samples, Ann. Math. Statist., 34, 1, 95-101, (1963) · Zbl 0129.32802
[2] Fasano, G.; Franceschini, A., A multidimensional version of the Kolmogorov-smirnovtest, Mon. Not. R. Astron. Soc., 225, 155-170, (1987)
[3] Hájek, J.; Šidàk, Z., Theory of rank tests, (1967), Academic Press New York · Zbl 0161.38102
[4] Hoare, C. A.R., Algorithm 64: quicksort, Commun. ACM, 4, 7, 321, (1961)
[5] Lopes, R.H.C., Reid, I., Hobson, P.R., The two-dimensional Kolmogorov-Smirnovtest, in: XI International Workshop on Advanced Computing and Analysis Techniques in Physical Research, Amsterdam, the Netherlands, 2007.
[6] Peacock, J. A., Two-dimensional goodness-of-fit testing in astronomy, Mon. Not. R. Astron. Soc., 202, 625-627, (1983)
[7] Xiao, Y.; Gordon, A.; Yakovlev, A., A C++ program for the cramér-von Mises two-sample test, J. Stat. Softw. (Amer. Statist. Assoc.), 17, 8, (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.