An Incremental Updating Method for Clustering-Based High-Dimensional Data Indexing

Content-based information retrieval (CBIR) of multimedia data is an active research topic in intelligent information retrieval field. To support CBIR, high-dimensional data indexing and query is a challenging problem due to the inherent high dimension of multimedia data. Clustering-based indexing structures have been proved to be efficient for high-dimensional data indexing. However, most clustering-based indexing structures are static, in which new data cannot be inserted by just modifying the existing clusters or indexing structures. To resolve this problem, a two-level indexing method, called IASDS plus IPAT method, is developed in this paper. At the IASDS level, clusters and the corresponding subspaces can be incrementally updated, while the indexing structures within the clusters can be incrementally updated at the IPAT level. Furthermore, the proposed IASDS plus IPAT method is able to balance indexing efficiency and query accuracy by choosing an appropriate number of children nodes. The experimental results show that the IASDS plus IPAT method is very efficient for updating clusters and indexing structures with newly inserted data, and that its query accuracy is only slightly degraded while its query time is almost the same in comparison with the similar indexing structure built by non-incremental method.