fastWKendall: an efficient algorithm for weighted Kendall correlation

摘要

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(nlog n)$$ O ( n log n ) time and O ( n ) space complexity. This is an improvement to the state-of-the-art $$O(n^2)$$ O ( n 2 ) time requirement. The proposed method can be incorporated to perform conventional sequential similarity measurement and cluster analysis much more rapidly. This is important for analysis of huge-volume datasets, such as genome databases, streaming stock market data, and publicly available huge datasets on the Internet. The code which is implemented in R is available for public access.