From nobody@cse.Buffalo.EDU Wed Nov 25 14:20 EST 1998 From: nobody@cse.Buffalo.EDU Date: Wed, 25 Nov 1998 14:20:19 -0500 (EST) To: techreps@cs.buffalo.edu Subject: techrep: POST request Content-Type: text Content-Length: 1818 ContactPerson: azhang@cse.buffalo.edu Remote host: mekab.cs.buffalo.edu Remote ident: gsesfah ### Begin Citation ### Do not delete this line ### %R 98-08 %U 98-08.ps %A Yu, Dantong %A Chatterjee, Surojit %A Sheikholeslami, Gholamhosein %A Zhang, Aidong %T Efficiently Detecting Arbitrary Shaped Clusters in Very Large Datasets with High Dimensions %D November 1, 1998 %I Department of Computer Science and Engineering, SUNY Buffalo %K Data clustering, hash table, wavelet transform, very large databases %X Multimedia databases typically contain data with very high dimensions. Finding interesting patterns in these databases poses a very challenging problem because of the scalability,lack of domain knowledge and complex structures of the embedded clusters. High dimensionality adds severely to the scalability problem. It has been shown that the wavelet-based clustering technique, WaveCluster, is very efficient and effective in detecting arbitrary shape clusters and eliminating noisy data for low dimensional data. In this paper, we introduce {\it HiperWave}, an approach to applying wavelet-based techniques for clustering high dimensional data. Using a hash-based data structure, our approach makes intelligent use of available resources to discover clusters in the dataset. We demonstrate that the cost of clustering can be reduced dramatically yet maintaining all the advantages of wavelet-based clustering. This hash-based data representation can be applied for any grid-based clustering approaches. Finally, we introduce a quantitative metric to measure the quality of the resulting clusters. The experimental results show both effectiveness and efficiency of our method on high dimensional datasets.