期刊
COMPUTATIONAL STATISTICS
卷 20, 期 1, 页码 51-62出版社
PHYSICA-VERLAG GMBH & CO
DOI: 10.1007/BF02736122
关键词
Kendall's tau; algorithm; O(n log n)
Traditional algorithms for the calculation of Kendall's τ between two datasets of n samples have a calculation time of O(n(2)). This paper presents a suite of algorithms with expected calculation time of O(n log n) or better using a combination of sorting and balanced tree data structures. The literature, e.g. Dwork et al. (2001), has alluded to the existence of O(n log n) algorithms without any analysis: this paper gives an explicit descriptions of such algorithms for general use both for the case with and without duplicate values in the data. Execution times for sample data are reduced from 3.8 hours to around 1-2 seconds for one million data pairs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据