ClusterTree: Integration of cluster representation and nearest neighbor search for image databases

In this paper, we present the ClusterTree, a new approach to representing clusters generated by any existing clustering approach. Our cluster representation is highly adaptive in any type of clusters. A cluster is decomposed into several subclusters and represented as the union of the subclusters. The subclusters can be further decomposed. The decomposition can help isolate the most related groups within the clusters. ClusterTree incorporates the cluster presentation into the index structure to achieve effective and efficient retrieval, it is well accepted that other existing indexing algorithms degrade rapidly when dimensionality goes higher. ClusterTree can support the retrieval of the most related nearest neighbors effectively and efficiently without having to linearly scan the high dimensional dataset. We also discuss a dynamic clustering approach by exploiting the representation of clusters. We present the detailed analysis of this approach and justify it extensively by experiments.