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.
Original 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 | |
Publication status | 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/Territory | United States |
City | San Diego |
Period | 7/01/19 → 8/01/19 |