Image clustering is to derive a salient grouping of images such that similar ones are placed in the same cluster, which is useful in many applications. In this paper, we propose a constrained clustering algorithm, which leverages the collected user query log to guide the clustering process. Our method models a set of images as a graph and randomly contracts two vertices into a meta vertex iteratively with regarding to their similarity until the desired number of image groups has been reached. The experimental results demonstrate the superiority of our proposal.

Nowadays’ image retrieval techniques focus on modifying a query contour based on the relative correlations of relevant images. The spatial relationship between the relevant images and all the other images in database (i.e. the directional information) is not explored and utilized well. From the aspect of feature space, when a user selects relevant images, the direction to the potential relevant images is implicitly expressed. In this paper, we propose a Dynamic Directional Navigation (DDN) system to explore the directional information and navigate in the data space to find similar images. Multiple queries will be used when the relevant images point to different directions. The experiment results indicate that our technique can address the semantic gap well in Content-Based Image Retrieval (CBIR) and achieves better precision and recall than the previous techniques.

Data clustering is a difficult problem due to the complex and heterogeneous natures of multidimensional data. To improve clustering accuracy, we propose a scheme to capture the local correlation structures: associate each cluster with an independent weighting vector and embed it in the subspace spanned by an adaptive combination of the dimensions. Our clustering algorithm takes advantage of the known pairwise instance-level constraints. The data points in the constraint set are divided into groups through inference; and each group is assigned to the feasible cluster which minimizes the sum of squared distances between all the points in the group and the corresponding centroid. Our theoretical analysis shows that the probability of points being assigned to the correct clusters is much higher by the new algorithm, compared to the conventional methods. This is confirmed by our experimental results, indicating that our design indeed produces clusters which are closer to the ground truth than clusters created by the current state-of-the-art algorithms.

We examine the problem of efficient distance-based similarity search over high-dimensional data. We show that a promising approach to this problem is to reduce dimensions and allow fast approximation. Conventional reduction approaches, however, entail a significant shortcoming: The approximation volume extends across the dataspace, which causes overestimation of retrieval sets and impairs performance. This paper focuses on a new criterion for dimensionality reduction methods: bounded approximation. We show that this requirement can be accomplished by a novel nonlinear transformation scheme that extracts two important parameters from the data. We devise two approximation formulations, namely, rectangular and spherical range search, each corresponding to a closed volume around the original search sphere. We discuss in detail how we can derive tight bounds for the parameters and prove further results, as well as highlight insights into the problems and our proposed solutions. To demonstrate the benefits of the new criterion, we study the effects of (un)boundedness on approximation performance, including selectivity, error toleration, and efficiency. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.

In this paper, we propose Local and Global Structures Preserving Projection (LGSPP), which is to find a small set of projection directions so as to properly preserve the local and global structures for a given set of data. Specifically, for each point in the dataset, its local neighborhood is extracted as well as a set of sampled points far away from this point, which characterize the global structure. The embedding minimizes the distances of the points in each local neighborhood while dispersing them far apart from their corresponding remote points. In this way, the local-global relationships between data points are well kept.

To enable efficient similarity search in large databases, many indexing techniques use a linear transformation scheme to reduce dimensions and allow fast approximation. In this reduction approach the approximation is unbounded, so that the approximation volume extends across the dataspace. This causes over-estimation of retrieval sets and impairs performance.This paper presents a non-linear transformation scheme that extracts two important parameters specifying the data. We prove that these parameters correspond to a bounded volume around the search sphere, irrespective of dimensionality. We use a special workspace-mapping mechanism to derive tight bounds for the parameters and to prove further results, as well as highlighting insights into the problems and our proposed solutions. We formulate a measure that lower-bounds the Euclidean distance, and discuss the implementation of the technique upon a popular index structure. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.