Fast algorithms for a space-time concordance measure

Sergio J. Rey

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper presents a number of algorithms for a recently developed measure of space-time concordance. Based on a spatially explicit version of Kendall's τ the original implementation of the concordance measure relied on a brute force O(n2) algorithm which has limited its use to modest sized problems. Several new algorithms have been devised which move this run time to O(n log(n) +np) where p is the expected number of spatial neighbors for each unit. Comparative timing of these alternative implementations reveals dramatic efficiency gains in moving away from the brute force algorithms. A tree-based implementation of the spatial concordance is also found to dominate a merge sort implementation.

Original languageEnglish (US)
Pages (from-to)799-811
Number of pages13
JournalComputational Statistics
Issue number3-4
StatePublished - Jun 2014


  • Autocorrelation
  • Rank correlation
  • Spatial concordance

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Computational Mathematics


Dive into the research topics of 'Fast algorithms for a space-time concordance measure'. Together they form a unique fingerprint.

Cite this