Fully dynamic hierarchical diameter k-clustering and k-center

2019/08/07 by Schmidt, Melanie, Sohler, Christian · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1908.02645

Abstract

We develop dynamic data structures for maintaining a hierarchical k-center clustering when the points come from a discrete space \1,…,Δ\^d. Our first data structure is for the low dimensional setting, i.e., d is a constant, and processes insertions, deletions and cluster representative queries in log^O(1) (Δn) time, where n is the current size of the point set. For the high dimensional case and an integer parameter ℓ > 1, we provide a randomized data structure that maintains an O(d ℓ)-approximation. The amortized expected insertion time is O(d² ℓ log n log Δ). The amortized expected deletion time is O(d² n^1/ℓ log² n log Δ). At any point of time, with probability at least 1-1/n, the data structure can correctly answer all queries for cluster representatives in O(d ℓ log n log Δ) time per query.

Cited by

• Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond

Related

• Fully Dynamic k-Center Clustering in Doubling Metrics
• Optimal Fully Dynamic k-Centers Clustering
• Fully Dynamic Consistent k-Center Clustering
• Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
• Nearly Optimal Dynamic k-Means Clustering for High-Dimensional Data