Brunel University Research Archive (BURA) >
Research Areas >
Electronic and Computer Engineering >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/2571

Title: Computationally efficient algorithms for the two-dimensional Kolmogorov-Smirnov test
Authors: Lopes, RHC
Hobson, PR
Reid, ID
Keywords: Statistical tests
Kolmogorov-Smirnov
Algorithms
Computer science
Publication Date: 2008
Publisher: IOP
Citation: Journal of Physics: Conference Series. 120(2008) 042019, Jun 2008
Abstract: Goodness-of-fit statistics measure the compatibility of random samples against some theoretical or reference probability distribution function. The classical one-dimensional Kolmogorov-Smirnov test is a non-parametric statistic for comparing two empirical distributions which defines the largest absolute difference between the two cumulative distribution functions as a measure of disagreement. Adapting this test to more than one dimension is a challenge because there are 2^d-1 independent ways of ordering a cumulative distribution function in d dimensions. We discuss Peacock's version of the Kolmogorov-Smirnov test for two-dimensional data sets which computes the differences between cumulative distribution functions in 4n^2 quadrants. We also examine Fasano and Franceschini's variation of Peacock's test, Cooke's algorithm for Peacock's test, and ROOT's version of the two-dimensional Kolmogorov-Smirnov test. We establish a lower-bound limit on the work for computing Peacock's test of Omega(n^2.lg(n)), introducing optimal algorithms for both this and Fasano and Franceschini's test, and show that Cooke's algorithm is not a faithful implementation of Peacock's test. We also discuss and evaluate parallel algorithms for Peacock's test.
URI: http://bura.brunel.ac.uk/handle/2438/2571
DOI: http://dx.doi.org/10.1088/1742-6596/120/4/042019
Appears in Collections:Electronic and Computer Engineering
Dept of Electronic and Computer Engineering Research Papers

Files in This Item:

File Description SizeFormat
CHEP07-jpconf8_119_042019.pdf2.22 MBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.