Nikolaos Koutroumanis, Petros Karampas, Alexandros Karakasidis, Nikos Mamoulis, Panos Vassiliadis
Computing the correlation of two attributes in a large dataset is an important problem, with many applications, including exploratory analytics and dimensionality reduction. Among the well-known correlation measures, Kendall’s tau is the most robust one, as it is immune from parametric assumptions and outliers. On the other hand, computing Kendall’s tau for large-scale data becomes challenging (i) due to the superlinear cost of the state-of-the-art algorithm and (ii) because all data need to be memory-resident for e!cient processing. In this paper, we address the problem via a geometric approach that partitions the data in the cells of a grid, and exploits the relative position of the cells to compute correlation information en masse. Our approach facilitates parallel and distributed computation of Kendall’s correlation; we propose a scalable algorithm in this direction. Finally, we propose an e!cient approximate algorithm with a provable error bound, which derives accurate results by a single pass over the grid statistics. Our experimental evaluation demonstrates the e!ciency and scalability of our grid-based techniques compared to the state-of-the-art algorithm.
Nikolaos Koutroumanis, Petros Karampas, Alexandros Karakasidis, Nikos Mamoulis, Panos Vassiliadis. Scalable Grid-based Computation of Kendall's Tau Correlation. Proc. VLDB, 19(5), pages: 876-888, 2026