State-of-the-art object retrieval systems are mostly based on the bag-of-visual-words representation which encodes local appearance information of an image in a feature vector. An image object search is performed by comparing query object’s feature vector with those for database images. However, a database image vector generally carries mixed information of the entire image which may contain multiple objects and background. Search quality is degraded by such noisy (or diluted) feature vectors. To tackle this problem, we propose a novel representation, pseudo-objects – a subset of proximate feature points with its own feature vector to represent a local area, to approximate candidate objects in database images. In this paper, we investigate effective methods (e.g., grid, G-means, and GMM–BIC) to estimate pseudo-objects. Additionally, we also confirm that the pseudo-objects can significantly benefit inverted-file indexing both in accuracy and efficiency. Experimenting over two consumer photo benchmarks, we demonstrate that the proposed method significantly outperforms other state-of-the-art object retrieval and indexing algorithms.