Modifying iDistance for a Fast CHAMELEON with Application to Patch based Image Segmentation

Xiaochun Wang, Xia L. Wang, and Don M. Wilkes


CHAMELEON clustering algorithm, high-dimensional index structure, kNN search, image segmentation


CHAMELEON clustering algorithm partitions a data set into a large number of sub-clusters and then discovers genuine clusters by repeatedly merging two sub-clusters whose relative inter-connectivity and relative closeness are the highest among all the sub-clusters until a predefined number of clusters are reached. However, it requires construction of a k-nearest neighbor graph in its first stage. Existing multi-dimensional indexes such as R-tree and kd-tree have been shown to be inefficient for k-nearest neighbor search in high-dimensional databases. This paper presents a faster k-nearest neighbor search algorithm for such purposes by modifying a high-dimensional index structure called iDistance. Experimental results show our approach outperforms the state-of-the-art approaches on several data sets and can make CHAMELEON algorithm more efficient when used in two patch based image segmentation tasks.

Important Links:

Go Back