Subquadratic approximation algorithms for clustering problems in high dimensional spaces

One of the central problems in information retrieval, data mining, computational biology, statistical analysis, computer vision, geographic analysis, pattern recognition, distributed protocols is the question of classification of data according to some clustering rule. Often the data is noisy and even approximate classification is of extreme importance. The difficulty of such classification stems from the fact that usually the data has many incomparable attributes, and often results in the question of clustering problems in high dimensional spaces. Since they require measuring distance between every pair of data points, standard algorithms for computing the exact clustering solutions use quadratic or nearly quadratic running time; i. e. , O (dn 2\ (d) ) time where n is the number of data points, d is the dimen- Computer Science Department, University of Toronto. Part of this work was done while visiting Bell Communications Research. y Bell Communications Research, MCC-1C365. . .