# Massively-Parallel Heat Map Sorting and Applications To Explainable Clustering

arXiv: https://arxiv.org/abs/2309.07486 · HTML: https://mlsanity.com/paper/2309.07486/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 14 Sep 2023.

## Builds on (most cited first, 11 of 11)

- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Interpretability and Explainability: A Machine Learning Zoo Mini-tour](https://mlsanity.com/paper/2012.01805/) (2020)
- [Beyond Locality-Sensitive Hashing](https://mlsanity.com/paper/1306.1547/) (2013)
- [Shallow decision trees for explainable k-means clustering](https://mlsanity.com/paper/2112.14718/) (2021)
- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ℓp-Distances](https://mlsanity.com/paper/1710.01431/) (2017)
- [Parallel Graph Connectivity in Log Diameter Rounds](https://mlsanity.com/paper/1805.03055/) (2018)
- [Efficient Circuit Simulation in MapReduce](https://mlsanity.com/paper/1907.01624/) (2019)
- [Parameterized Edge Hamiltonicity](https://mlsanity.com/paper/1403.2041/) (2014)
- [On the Computational Complexity of MapReduce](https://mlsanity.com/paper/1410.0245/) (2014)
- [Set Cover in Sub-linear Time](https://mlsanity.com/paper/1902.03534/) (2019)

## Abstract (arXiv)

Given a set of points labeled with k labels, we introduce the heat map sorting problem as reordering and merging the points and dimensions while preserving the clusters (labels). A cluster is preserved if it remains connected, i.e., if it is not split into several clusters and no two clusters are merged. We prove the problem is NP-hard and we give a fixed-parameter algorithm with a constant number of rounds in the massively parallel computation model, where each machine has a sublinear memory and the total memory of the machines is linear. We give an approximation algorithm for a NP-hard special case of the problem. We empirically compare our algorithm with k-means and density-based clustering (DBSCAN) using a dimensionality reduction via locality-sensitive hashing on several directed and undirected graphs of email and computer networks.