2011 · 152 citations · 19 references
ComputingComputer ScienceComputer SystemsDistributed SystemsParallel AlgorithmsParallel ComputingCluster ManagementData ParallelismData PartitioningDistributed ComputingDistributed Data ProcessingScalable Algorithm DesignClustering For Large-scale DataData Partitioning StrategiesData-intensive ComputingMapreduceMapreduce AlgorithmsNetwork Cost FunctionsPartition OptimizationPartitioning Strategies
Given a very large moderate-to-high dimensionality dataset, how could one cluster its points? For datasets that don't fit even on a single disk, parallelism is a first class option. In this paper we explore MapReduce for clustering this kind of data. The main questions are (a) how to minimize the I/O cost, taking into account the already existing data partition (e.g., on disks), and (b) how to minimize the network cost among processing nodes. Either of them may be a bottleneck. Thus, we propose the Best of both Worlds -- BoW method, that automatically spots the bottleneck and chooses a good strategy. Our main contributions are: (1) We propose BoW and carefully derive its cost functions, which dynamically choose the best strategy; (2) We show that BoW has numerous desirable features: it can work with most serial clustering methods as a plugged-in clustering subroutine, it balances the cost for disk accesses and network accesses, achieving a very good tradeoff between the two, it uses no user-defined parameters (thanks to our reasonable defaults), it matches the clustering quality of the serial algorithm, and it has near-linear scale-up; and finally, (3) We report experiments on real and synthetic data with billions of points, using up to 1,024 cores in parallel. To the best of our knowledge, our Yahoo! web is the largest real dataset ever reported in the database subspace clustering literature. Spanning 0.2 TB of multi-dimensional data, it took only 8 minutes to be clustered, using 128 cores.
19
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Automatic subspace clustering of high dimensional data for data mining applications
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos et al. · 1998 · 2.4K citations
Fast algorithms for projected clustering
Charų C. Aggarwal, Joel L. Wolf, Philip S. Yu et al. · ACM SIGMOD Record · 1999 · 903 citations · Full text