fastWKendall: an efficient algorithm for weighted Kendall correl...

The Kendall correlation is a non-parametric method that measures the strength of dependence between two sequences. Like Pearson correlation and Spearman correlation, Kendall correlation is widely applied in sequence similarity measurements and cluster analysis. We propose an efficient algorithm, fastWKendall, to compute the approximate weighted Kendall correlation in O(n log n) time and O(n) space complexity. This is an improvement to the state-of-the-art O(n2) time requirement. The proposed met