Publication View

Scaling Clustering Algorithms to Large Databases (1998)

Abstract

Practical clustering algorithms require multiple data scans to achieve convergence. For large databases, these scans become prohibitively expensive. We present a scalable clustering framework applicable to a wide class of iterative clustering. We require at most one scan of the database. In this work, the framework is instantiated and numerically justified with the popular K-Means clustering algorithm. The method is based on identifying regions of the data that are compressible, regions that must be maintained in memory, and regions that are discardable. The algorithm operates within the confines of a limited memory buffer. Empirical results demonstrate that the scalable scheme outperforms a sampling-based approach. In our scheme, data resolution is preserved to the extent possible based upon the size of the allocated memory buffer and the fit of current clustering model to the data. The framework is naturally extended to update multiple clustering models simultaneously...

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=?doi=10.1.1.38.7927
Source	ftp://ftp.research.microsoft.com/pub/tr/tr-98-37.ps
Publisher	AAAI Press
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Type	text
Language	English
Relation	10.1.1.133.4884, 10.1.1.138.7286, 10.1.1.13.4395, 10.1.1.52.4829, 10.1.1.44.5872, 10.1.1.8.1159, 10.1.1.2.1014, 10.1.1.50.4591, 10.1.1.54.3561, 10.1.1.45.9020, 10.1.1.44.5847, 10.1.1.34.4329, 10.1.1.13.8650, 10.1.1.18.3739, 10.1.1.13.9802, 10.1.1.6.2778, 10.1.1.33.574, 10.1.1.44.4060, 10.1.1.15.4774, 10.1.1.36.64, 10.1.1.25.3782, 10.1.1.108.9085, 10.1.1.15.2457, 10.1.1.40.1222, 10.1.1.28.9344, 10.1.1.22.8074, 10.1.1.43.5114, 10.1.1.40.5330, 10.1.1.35.7613, 10.1.1.101.2607, 10.1.1.19.6629, 10.1.1.36.3405, 10.1.1.10.745, 10.1.1.14.7992, 10.1.1.36.304, 10.1.1.19.7967, 10.1.1.22.2543, 10.1.1.114.8600, 10.1.1.37.4310, 10.1.1.38.9908, 10.1.1.33.2182, 10.1.1.140.1704, 10.1.1.12.6944, 10.1.1.18.9066, 10.1.1.58.8548, 10.1.1.1.5567, 10.1.1.30.1071, 10.1.1.42.2431, 10.1.1.19.3094, 10.1.1.122.2898, 10.1.1.111.2909, 10.1.1.127.8545, 10.1.1.14.8083, 10.1.1.28.7564, 10.1.1.45.8975, 10.1.1.1.6473, 10.1.1.10.8305, 10.1.1.14.6840, 10.1.1.36.4798, 10.1.1.85.866, 10.1.1.123.7215, 10.1.1.1.5317, 10.1.1.29.3646, 10.1.1.65.4722, 10.1.1.96.2553, 10.1.1.111.7164, 10.1.1.129.8552, 10.1.1.9.1586, 10.1.1.11.877, 10.1.1.12.9114, 10.1.1.26.7606, 10.1.1.61.1671, 10.1.1.73.5431, 10.1.1.30.4881, 10.1.1.58.2138, 10.1.1.72.9872, 10.1.1.117.629, 10.1.1.29.1493, 10.1.1.58.8052, 10.1.1.101.8199, 10.1.1.22.9979, 10.1.1.64.450, 10.1.1.7.1373, 10.1.1.75.8989, 10.1.1.78.5024, 10.1.1.80.6273, 10.1.1.87.7732, 10.1.1.96.9381, 10.1.1.98.4708, 10.1.1.116.4507, 10.1.1.6.7874, 10.1.1.102.1340, 10.1.1.103.5588, 10.1.1.105.8353, 10.1.1.105.9377, 10.1.1.109.5005, 10.1.1.11.9264, 10.1.1.12.1922, 10.1.1.18.2397, 10.1.1.24.2361, 10.1.1.33.1465, 10.1.1.37.6767, 10.1.1.40.6445, 10.1.1.43.3383, 10.1.1.65.5185, 10.1.1.66.2594, 10.1.1.67.6630, 10.1.1.140.2541, 10.1.1.77.6461, 10.1.1.80.2982, 10.1.1.80.6618, 10.1.1.80.9828, 10.1.1.83.6670, 10.1.1.84.843, 10.1.1.85.3087, 10.1.1.85.5980, 10.1.1.85.6798, 10.1.1.86.413, 10.1.1.87.7747, 10.1.1.88.4485, 10.1.1.88.6908, 10.1.1.89.1023, 10.1.1.89.6844, 10.1.1.90.2441, 10.1.1.90.4060, 10.1.1.90.8000, 10.1.1.90.8922, 10.1.1.92.1239, 10.1.1.92.9138, 10.1.1.93.1692, 10.1.1.93.7655, 10.1.1.94.3955, 10.1.1.94.7049, 10.1.1.95.2031, 10.1.1.95.2266, 10.1.1.96.9361, 10.1.1.98.1658, 10.1.1.99.7945, 10.1.1.111.6347, 10.1.1.113.9885, 10.1.1.113.9889, 10.1.1.115.8375, 10.1.1.117.2840, 10.1.1.118.246, 10.1.1.119.68, 10.1.1.119.7920, 10.1.1.122.2920, 10.1.1.122.7191, 10.1.1.123.2995, 10.1.1.127.1624, 10.1.1.127.5592, 10.1.1.127.9739, 10.1.1.128.8686, 10.1.1.135.9187, 10.1.1.136.6363, 10.1.1.139.4817, 10.1.1.50.8528, 10.1.1.27.9353, 10.1.1.35.9868, 10.1.1.43.1492, 10.1.1.33.555, 10.1.1.29.8579, 10.1.1.33.9399, 10.1.1.28.1355, 10.1.1.21.596, 10.1.1.16.3328, 10.1.1.17.6594, 10.1.1.13.1410, 10.1.1.14.1541, 10.1.1.6.8781, 10.1.1.7.1924, 10.1.1.10.7534, 10.1.1.3.4213, 10.1.1.3.4896, 10.1.1.4.1900, 10.1.1.5.2574, 10.1.1.5.7425, 10.1.1.5.8970, 10.1.1.58.3049, 10.1.1.58.3738, 10.1.1.1.4366, 10.1.1.1.4976, 10.1.1.58.8251, 10.1.1.60.8853, 10.1.1.140.1515