A fast algorithm for two-dimensional Kolmogorov-Smirnov two sample tests

作者：Xiao Yuanhui^*

来源：Computational Statistics & Data Analysis, 2017, 105: 53-58.

DOI：10.1016/j.csda.2016.07.014

• Kolmogorov-Smirnov test
• Brute force algorithm

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.

• 出版日期2017-1