Timezone: »

Hierarchical Clustering of Data Streams: Scalable Algorithms and Approximation Guarantees
Anand Rajagopalan · Fabio Vitale · Danny Vainstein · Gui Citovsky · Cecilia Procopiuc · Claudio Gentile

Thu Jul 22 05:40 AM -- 05:45 AM (PDT) @

We investigate the problem of hierarchically clustering data streams containing metric data in R^d. We introduce a desirable invariance property for such algorithms, describe a general family of hyperplane-based methods enjoying this property, and analyze two scalable instances of this general family against recently popularized similarity/dissimilarity-based metrics for hierarchical clustering. We prove a number of new results related to the approximation ratios of these algorithms, improving in various ways over the literature on this subject. Finally, since our algorithms are principled but also very practical, we carry out an experimental comparison on both synthetic and real-world datasets showing competitive results against known baselines.

Author Information

Anand Rajagopalan (Google)
Fabio Vitale (University of Lille & INRIA Lille)
Danny Vainstein (Tel-Aviv University)
Gui Citovsky (Google)
Cecilia Procopiuc (Google)
Claudio Gentile (Google Research)

Related Events (a corresponding poster, oral, or spotlight)