This article presents an efficient and totally unsupervised content-based similarity search method for multimedia data objects represented by high-dimensional feature vectors. The assumption is that the similarity measure is applicable to feature vectors of arbitrary length. During the offline process, different sets of features are selected by a generalized version of the Laplacian Score in an unsupervised way for individual data objects in the database. Online retrieval is performed by ranking the query object in the feature spaces of candidate objects. Those candidates for which the query object is ranked highly are selected as the query results. The ranking scheme is incorporated into an automated query expansion framework to further improve the semantic quality of the search result. Extensive experiments were conducted on several datasets to show the capability of the proposed method in boosting effectiveness without losing efficiency.

Numerous applications in different fields, such as spatial databases, multimedia databases, data mining, and recommender systems, may benefit from efficient and effective aggregate similarity search, also known as aggregate nearest neighbor (AggNN) search. Given a group of query objects Q, the goal of AggNN is to retrieve the k most similar objects from the database, where the underlying similarity measure is defined as an aggregation (usually sum or max) of the distances between the retrieved objects and every query object in Q. Recently, the problem was generalized so as to retrieve the k objects which are most similar to a fixed proportion of the elements of Q. This variant of aggregate similarity search is referred to as “flexible AggNN”, or FANN. In this work, we propose two approximation algorithms, one for the sum variant of FANN, and the other for the max variant. Extensive experiments are provided showing that, relative to state-of-the-art approaches (both exact and approximate), our algorithms produce query results with good accuracy, while at the same time being very efficient.

Neighborhood graphs are an essential component of many established methods for content-based image retrieval and automated image annotation. The performance of such methods relies heavily on the semantic quality of the graphs, which can be measured as the proportion of neighbors sharing the same class label as their query images. In this paper, we propose a new framework for the efficient construction of K-nearest neighbor (K-NN) graphs based on nearest-neighbor descent (NN-Descent), in which selective sparsification of object feature vectors is interleaved with neighborhood refinement operations in an effort to improve the semantic quality of the result. A local variant of the Laplacian Score is used to identify noisy features with respect to individual images, whose values are then set to 0 (the global mean value after standardization). We show through extensive experiments that our graph construction method is able to increase the proportion of semantically-related images over unrelated images within the neighbor sets.

In data mining applications such as subspace clustering or feature selection, changes to the underlying feature set can require the reconstruction of search indices to support fundamental data mining tasks. For such situations, multi-step search approaches have been proposed that can accommodate changes in the underlying similarity measure without the need to rebuild the index. In this paper, we present a heuristic multi-step search algorithm that utilizes a measure of intrinsic dimension, the generalized expansion dimension (GED), as the basis of its search termination condition. Compared to the current state-of-the-art method, experimental results show that our heuristic approach is able to obtain significant improvements in both the number of candidates and the running time, while losing very little in the accuracy of the query results.