### Abstract

We study an agglomerative clustering problem motivated by visualizing disjoint glyphs (represented by geometric shapes) centered at specific locations on a geographic map. As we zoom out, the glyphs grow and start to overlap. We replace overlapping glyphs by one larger merged glyph to maintain disjointness. Our goal is to compute the resulting hierarchical clustering efficiently in practice. A straightforward algorithm for such spatial agglomerative clustering runs in On
^{2}
log n time, where n is the number of glyphs. This is not efficient enough for many real-world datasets which contain up to tens or hundreds of thousands of glyphs. Recently the theoretical upper bound was improved to Onα(n) log
^{7}
n time [10], where α(n) is the extremely slow growing inverse Ackermann function. Although this new algorithm is asymptotically much faster than the naive algorithm, from a practical point of view, it does not perform better for n ≤ 10
^{6}
. In this paper we present a new agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice.

Language | English |
---|---|

Title of host publication | Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments |

Place of Publication | Philadelphia |

Publisher | Society for Industrial and Applied Mathematics (SIAM) |

Pages | 174-185 |

Number of pages | 12 |

ISBN (Electronic) | 978-1-61197-549-9 |

DOIs | |

State | Published - 2019 |

Event | 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 - San Diego, United States Duration: 7 Jan 2019 → 8 Jan 2019 |

### Conference

Conference | 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 |
---|---|

Country | United States |

City | San Diego |

Period | 7/01/19 → 8/01/19 |

### Fingerprint

### Cite this

*Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments*(pp. 174-185). Philadelphia: Society for Industrial and Applied Mathematics (SIAM). DOI: 10.1137/1.9781611975499.14

}

*Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments.*Society for Industrial and Applied Mathematics (SIAM), Philadelphia, pp. 174-185, 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, United States, 7/01/19. DOI: 10.1137/1.9781611975499.14

**A practical algorithm for spatial agglomerative clustering.** / Castermans, Thom; Speckmann, Bettina; Verbeek, Kevin.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A practical algorithm for spatial agglomerative clustering

AU - Castermans,Thom

AU - Speckmann,Bettina

AU - Verbeek,Kevin

PY - 2019

Y1 - 2019

N2 - We study an agglomerative clustering problem motivated by visualizing disjoint glyphs (represented by geometric shapes) centered at specific locations on a geographic map. As we zoom out, the glyphs grow and start to overlap. We replace overlapping glyphs by one larger merged glyph to maintain disjointness. Our goal is to compute the resulting hierarchical clustering efficiently in practice. A straightforward algorithm for such spatial agglomerative clustering runs in On 2 log n time, where n is the number of glyphs. This is not efficient enough for many real-world datasets which contain up to tens or hundreds of thousands of glyphs. Recently the theoretical upper bound was improved to Onα(n) log 7 n time [10], where α(n) is the extremely slow growing inverse Ackermann function. Although this new algorithm is asymptotically much faster than the naive algorithm, from a practical point of view, it does not perform better for n ≤ 10 6 . In this paper we present a new agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice.

AB - We study an agglomerative clustering problem motivated by visualizing disjoint glyphs (represented by geometric shapes) centered at specific locations on a geographic map. As we zoom out, the glyphs grow and start to overlap. We replace overlapping glyphs by one larger merged glyph to maintain disjointness. Our goal is to compute the resulting hierarchical clustering efficiently in practice. A straightforward algorithm for such spatial agglomerative clustering runs in On 2 log n time, where n is the number of glyphs. This is not efficient enough for many real-world datasets which contain up to tens or hundreds of thousands of glyphs. Recently the theoretical upper bound was improved to Onα(n) log 7 n time [10], where α(n) is the extremely slow growing inverse Ackermann function. Although this new algorithm is asymptotically much faster than the naive algorithm, from a practical point of view, it does not perform better for n ≤ 10 6 . In this paper we present a new agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice.

UR - http://www.scopus.com/inward/record.url?scp=85065203522&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975499.14

DO - 10.1137/1.9781611975499.14

M3 - Conference contribution

SP - 174

EP - 185

BT - Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments

PB - Society for Industrial and Applied Mathematics (SIAM)

CY - Philadelphia

ER -