Fast algorithms for a space-time concordance measure

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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\tau $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">τ</mi> </math> </EquationSource> </InlineEquation> the original implementation of the concordance measure relied on a brute force <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$O(n^2)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> algorithm which has limited its use to modest sized problems. Several new algorithms have been devised which move this run time to <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$O(n log(n) +np)$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>l</mi> <mi>o</mi> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>n</mi> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math> </EquationSource> </InlineEquation> where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$p$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>p</mi> </math> </EquationSource> </InlineEquation> 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. Copyright Springer-Verlag Berlin Heidelberg 2014