Gap-Measure Tests with Applications to Data Integrity Verification

Abstract

In this paper we propose and examine gap statistics for assessing uniform distribution hypotheses. We provide examples relevant to data integrity testing for which max-gap statistics provide greater sensitivity than chi-square (${\chi }^2$), thus allowing the new test to be used in place of or as a complement to ${\chi }^2$ testing for purposes of distinguishing a larger class of deviations from uniformity. We establish that the proposed max-gap test has the same sequential and parallel computational complexity as ${\chi }^2$ and thus is applicable for Big Data analytics and integrity verification.