20th International Conference on Data Engineering (ICDE'04)
Substructure Clustering on Sequential 3d Object Datasets
Boston, Massachusetts
March 30-April 02
ISBN: 0-7695-2065-0
In this paper, we will look at substructure clustering of sequentail 3d objects. A sequential 3d object is a set of points located in a three dimensional space that are linked up to form a sequence. Given a set of sequential 3d objects, our aim is to find significantly large substructures which are present in many of the sequential 3d objects. Unlike traditional subspace clustering methods in which objects are compared based on values in the same dimension, the matching dimensions between two 3d sequential objects are affected by both the translation and rotation of the objects and are thus not well defined. Instead, similarity between the objects are judge by computing a structural distance measurement call rmsd(Root Mean Square Distance) which require proper alignment (including translation and rotation) of the objects. As the computation of rmsd is expensive, we proposed a new measure call ald(Angel Length Distance) which is shown experimentally to approximate rmsd. Based on ald, we define a new clustering model called sCluster and devise an algorithm for discovering all maximum sCluster in a 3d sequentail dataset. Experiments are conducted to illustrate the efficiency and effectiveness of our algorithm.