Scalable Grid-based Computation of Kendall's τ Correlation
Proceedings of the VLDB Endowment · 01.01.2026 · 19 (5) · 876-888
DOI: 10.14778/3796195.3796202 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 05.05.2026. Verfasst von Nikolaos Koutroumanis und 4 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben.
Abstract (Originalsprache)
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 τ is the most robust one, as it is immune from parametric assumptions and outliers. On the other hand, computing Kendall's τ 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 efficient 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 efficient approximate algorithm with a provable error bound, which derives accurate results by a single pass over the grid statistics. Our experimental evaluation demonstrates the efficiency and scalability of our grid-based techniques compared to the state-of-the-art algorithm.
Zitieren
APA
Koutroumanis, N., Karampas, P., Karakasidis, A., Mamoulis, N., & Vassiliadis, P. (2026). Scalable Grid-based Computation of Kendall's τ Correlation. Proceedings of the VLDB Endowment, 19(5), 876-888. https://doi.org/10.14778/3796195.3796202
Vancouver
Koutroumanis N, Karampas P, Karakasidis A, Mamoulis N, Vassiliadis P. Scalable Grid-based Computation of Kendall's τ Correlation. Proceedings of the VLDB Endowment. 2026;19(5):876-888. doi:10.14778/3796195.3796202
BibTeX
@article{Koutroumanis2026,
author = {Koutroumanis, Nikolaos and Karampas, Petros and Karakasidis, Alexandros and Mamoulis, Nikos and Vassiliadis, Panos},
title = {Scalable Grid-based Computation of Kendall's τ Correlation},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {5},
pages = {876--888},
doi = {10.14778/3796195.3796202}
}
EUVIMED