Agglomerative clustering of growing squares

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
46 Downloads (Pure)

Abstract

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n(log n log log n)2) space, supports queries in worst case O(log3 n) time, and updates in O(log7 n) amortized time. This leads to an O(n α(n) log7 n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n2 log n) time algorithm.

Original languageEnglish
Title of host publication13th Latin American Theoretical INformatics Symposium (LATIN)
EditorsM.A. Bender, M. Farach-Colton, M.A. Mosteiro
Place of PublicationBerlin
PublisherSpringer
Pages260-274
Number of pages15
ISBN (Print)9783319774039
DOIs
Publication statusPublished - 1 Jan 2018
Event13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina
Duration: 16 Apr 201819 Apr 2018
Conference number: 13
http://latin2018.dc.uba.ar/

Publication series

NameLecture Notes in Computer Science
Volume10807
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues
Volume10807

Conference

Conference13th Latin American Theoretical INformatics Symposium (LATIN 2018)
Abbreviated titleLATIN 2018
CountryArgentina
CityBuenos Aires
Period16/04/1819/04/18
Internet address

Fingerprint

Data structures
Clustering
Disjoint
Visualization
Kinetic Data Structures
Dynamic Data Structures
Kinetics
Inverse function
Intersect
Data Structures
Update
Query

Cite this

Castermans, T., Speckmann, B., Staals, F., & Verbeek, K. (2018). Agglomerative clustering of growing squares. In M. A. Bender, M. Farach-Colton, & M. A. Mosteiro (Eds.), 13th Latin American Theoretical INformatics Symposium (LATIN) (pp. 260-274). (Lecture Notes in Computer Science; Vol. 10807), (Theoretical Computer Science and General Issues; Vol. 10807). Berlin: Springer. https://doi.org/10.1007/978-3-319-77404-6_20
Castermans, Thom ; Speckmann, Bettina ; Staals, Frank ; Verbeek, Kevin. / Agglomerative clustering of growing squares. 13th Latin American Theoretical INformatics Symposium (LATIN). editor / M.A. Bender ; M. Farach-Colton ; M.A. Mosteiro. Berlin : Springer, 2018. pp. 260-274 (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues).
@inproceedings{f3f584d4561140088efedb20cc777878,
title = "Agglomerative clustering of growing squares",
abstract = "We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n(log n log log n)2) space, supports queries in worst case O(log3 n) time, and updates in O(log7 n) amortized time. This leads to an O(n α(n) log7 n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n2 log n) time algorithm.",
author = "Thom Castermans and Bettina Speckmann and Frank Staals and Kevin Verbeek",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-77404-6_20",
language = "English",
isbn = "9783319774039",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "260--274",
editor = "M.A. Bender and M. Farach-Colton and M.A. Mosteiro",
booktitle = "13th Latin American Theoretical INformatics Symposium (LATIN)",
address = "Germany",

}

Castermans, T, Speckmann, B, Staals, F & Verbeek, K 2018, Agglomerative clustering of growing squares. in MA Bender, M Farach-Colton & MA Mosteiro (eds), 13th Latin American Theoretical INformatics Symposium (LATIN). Lecture Notes in Computer Science, vol. 10807, Theoretical Computer Science and General Issues, vol. 10807, Springer, Berlin, pp. 260-274, 13th Latin American Theoretical INformatics Symposium (LATIN 2018), Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_20

Agglomerative clustering of growing squares. / Castermans, Thom; Speckmann, Bettina; Staals, Frank; Verbeek, Kevin.

13th Latin American Theoretical INformatics Symposium (LATIN). ed. / M.A. Bender; M. Farach-Colton; M.A. Mosteiro. Berlin : Springer, 2018. p. 260-274 (Lecture Notes in Computer Science; Vol. 10807), (Theoretical Computer Science and General Issues; Vol. 10807).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Agglomerative clustering of growing squares

AU - Castermans, Thom

AU - Speckmann, Bettina

AU - Staals, Frank

AU - Verbeek, Kevin

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n(log n log log n)2) space, supports queries in worst case O(log3 n) time, and updates in O(log7 n) amortized time. This leads to an O(n α(n) log7 n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n2 log n) time algorithm.

AB - We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses O(n(log n log log n)2) space, supports queries in worst case O(log3 n) time, and updates in O(log7 n) amortized time. This leads to an O(n α(n) log7 n) time algorithm (where α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward O(n2 log n) time algorithm.

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

U2 - 10.1007/978-3-319-77404-6_20

DO - 10.1007/978-3-319-77404-6_20

M3 - Conference contribution

AN - SCOPUS:85045383916

SN - 9783319774039

T3 - Lecture Notes in Computer Science

SP - 260

EP - 274

BT - 13th Latin American Theoretical INformatics Symposium (LATIN)

A2 - Bender, M.A.

A2 - Farach-Colton, M.

A2 - Mosteiro, M.A.

PB - Springer

CY - Berlin

ER -

Castermans T, Speckmann B, Staals F, Verbeek K. Agglomerative clustering of growing squares. In Bender MA, Farach-Colton M, Mosteiro MA, editors, 13th Latin American Theoretical INformatics Symposium (LATIN). Berlin: Springer. 2018. p. 260-274. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). https://doi.org/10.1007/978-3-319-77404-6_20