Finding Generalized Projected Clusters In High Dimensional Spaces Charu C. Aggarwal and Philip S. Yu   View Paper (PDF)   Return to Research Sessions Abstract High dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. Recent research results indicate that in high dimensional data, even the concept of proximity or clustering may not be meaningful. We discuss very general techniques for projected clustering which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality. The subspaces are specific to the clusters themselves. This definition is substantially more general and realistic than currently available techniques which limit the method to only projections from the original set of attributes. The generalized projected clustering technique may also be viewed as a way of trying to redefine clustering for high dimensional applications by searching for hidden subspaces with clusters which are created by inter-attribute correlations. We provide a new concept of using extended cluster feature vectors in order to make the algorithm scalable for very large databases. The running time and space requirements of the algorithm are adjustable, and are likely to tradeoff with better accuracy. References Note: References link to DBLP on the Web. [1] Charu C. Aggarwal , Cecilia Magdalena Procopiuc , Joel L. Wolf , Philip S. Yu , Jong Soo Park : Fast Algorithms for Projected Clustering. SIGMOD Conference 1999 : 61-72 [2] Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan : Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications. SIGMOD Conference 1998 : 94-105 [3] Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft : When Is ''Nearest Neighbor'' Meaningful? ICDT 1999 : 217-235 [4] Chun Hung Cheng , Ada Wai-Chee Fu , Yi Zhang : Entropy-based Subspace Clustering for Mining Numerical Data. KDD 1999 : 84-93 [5] Martin Ester , Hans-Peter Kriegel , Jörg Sander , Xiaowei Xu : A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD 1996 : 226-231 [6] Christos Faloutsos , King-Ip Lin : FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995 : 163-174 [7] Aristides Gionis , Piotr Indyk , Rajeev Motwani : Similarity Search in High Dimensions via Hashing. VLDB 1999 : 518-529 [8] Sudipto Guha , Rajeev Rastogi , Kyuseok Shim : CURE: An Efficient Clustering Algorithm for Large Databases. SIGMOD Conference 1998 : 73-84 [9] Alexander Hinneburg , Daniel A. Keim : Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering. VLDB 1999 : 506-517 [10] Piotr Indyk , Rajeev Motwani : Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998 : 604-613 [11] Anil K. Jain , Richard C. Dubes: Algorithms for Clustering Data. Prentice-Hall 1988 [12] ... [13] Jon M. Kleinberg : Two Algorithms for Nearest-Neighbor Search in High Dimensions. STOC 1997 : 599-608 [14] Ron Kohavi , Dan Sommerfield : Feature Subset Selection Using the Wrapper Method: Overfitting and Dynamic Search Space Topology. KDD 1995 : 192-197 [15] Raymond T. Ng , Jiawei Han : Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994 : 144-155 [16] Kothuri Venkata Ravi Kanth , Divyakant Agrawal , Ambuj K. Singh : Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998 : 166-176 [17] Xiaowei Xu , Martin Ester , Hans-Peter Kriegel , Jörg Sander : A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases. ICDE 1998 : 324-331 [18] Tian Zhang , Raghu Ramakrishnan , Miron Livny : BIRCH: An Efficient Data Clustering Method for Very Large Databases. SIGMOD Conf. 1996 : 103-114 BIBTEX @inproceedings{DBLP:conf/sigmod/AggarwalY00,   author    = {Charu C. Aggarwal and                 Philip S. Yu},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Finding Generalized Projected Clusters In High Dimensional Spaces},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {70-81},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.