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

详细信息    查看全文

• 作者：Yuanhui Xiao ^{xiao_yuanhui@hotmail.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Kolmogorov&ndash ; Smirnov test ; Brute force algorithm
• 刊名：Computational Statistics & Data Analysis
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：105
• 期：Complete
• 页码：53-58
• 全文大小：382 K

文摘

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)$O\left(n\right)$ times more efficient than the brute force algorithm, where n$n$ is the sum of the two sample sizes. The proposed algorithm is parallel and can be generalized to higher dimensional spaces.