Data Bubbles for Non-Vector Data: Speeding-up Hierarchical Clustering in Arbitrary Metric Spaces Jianjun Zhou and Jörg Sander   View Paper (PDF)   Return to Data Mining (Session B2) Abstract To speed-up clustering algorithms, data summa- rization methods have been proposed, which first summarize the data set by computing suitable representative objects. Then, a clustering algo- rithm is applied to these representatives only, and a clustering structure for the whole data set is de- rived, based on the result for the representatives. Most previous methods are, however, limited in their application domain. They are in general based on sufficient statistics such as the linear sum of a set of points, which assumes that the data is from a vector space. On the other hand, in many important applications, the data is from a metric non-vector space, and only distances be- tween objects can be exploited to construct effec- tive data summarizations. In this paper, we de- velop a new data summarization method based only on distance information that can be applied directly to non-vector data. An extensive per- formance evaluation shows that our method is very effective in finding the hierarchical cluster- ing structure of non-vector data using only a very small number of data summarizations, thus re- sulting in a large reduction of runtime while trad- ing only very little clustering quality. ©2004 Association for Computing Machinery