Content-based Image Retrieval (CBIR) systems consider only a pairwise analysis, i.e., they measure the similarity between pairs of images, ignoring the rich information encoded in the relations among several images. However, the user perception usually considers the query specification and responses in a given context. In this scenario, re-ranking methods have been proposed to exploit the contextual information and, hence, improve the effectiveness of CBIR systems. Besides the effectiveness, the usefulness of those systems in real-world applications also depends on the efficiency and scalability of the retrieval process, imposing a great challenge to the re-ranking approaches, once they usually require the computation of distances among all the images of a given collection. In this paper, we present a novel approach for the re-ranking problem. It relies on the similarity of top-k lists produced by efficient indexing structures, instead of using distance information from the entire collection. Extensive experiments were conducted on a large image collection, using several indexing structures. Results from a rigorous experimental protocol show that the proposed method can obtain significant effectiveness gains (up to 12.19% better) and, at the same time, improve considerably the efficiency (up to 73.11% faster). In addition, our technique scales up very well, which makes it suitable for large collections. © 2013 Elsevier Inc. All rights reserved.265 91104Almeida, J., Leite, N.J., Torres, R.S., Comparison of video sequences with histograms of motion patterns (2011) IEEE Int. Conf. Image Processing (ICIP'11), pp. 3673-3676Almeida, J., Rocha, A., Torres, R.S., Goldenstein, S., Making colors worth more than a thousand words (2008) ACM Int. Symp. Applied Computing (ACM-SAC'08), pp. 1180-1186Almeida, J., Torres, R.S., Leite, N.J., BP-tree: An efficient index for similarity search in high-dimensional metric spaces (2010) ACM Int. Conf. Information and Knowledge Management (CIKM'10), pp. 1365-1368Almeida, J., Valle, E., Torres, R.S., Leite, N.J., DAHC-tree: An effective index for approximate search in high-dimensional metric spaces (2010) J. Inform. Data Manage., 1 (3), pp. 375-390Baeza-Yates, R.A., Cunto, W., Manber, U., Wu, S., Proximity matching using fixed-queries trees (1994) Annual Symp. Combinatorial Pattern Matching (CPM'94), Vol. 807 of Lecture Notes in Computer Science, pp. 198-212Bozkaya, T., Özsoyoglu, Z.M., Indexing large metric spaces for similarity search queries (1999) ACM Trans. Database Syst., 24 (3), pp. 361-404Burkhard, W.A., Keller, R.M., Some approaches to best-match file searching (1973) Commun. ACM, 16 (4), pp. 230-236Chávez, E., Navarro, G., Baeza-Yates, R.A., Marroquín, J.L., Searching in metric spaces (2001) ACM Comput. Surv., 33 (3), pp. 273-321Ciaccia, P., Patella, M., Zezula, P., M-tree: An efficient access method for similarity search in metric spaces (1997) Int. Conf. Very Large Data Bases (VLDB'97), pp. 426-435Datta, R., Joshi, D., Li, J., Wang, J.Z., Image retrieval: Ideas, influences, and trends of the new age (2008) ACM Comput. Surv., 40 (2), pp. 51-560Elmasri, R.A., Navathe, S.B., (2005) Fundamentals of Database Systems, , Addison-Wesley Longman Publishing Co., IncFagin, R., Kumar, R., Sivakumar, D., Comparing top k lists (2003) ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pp. 28-36Ferreira, C.D., Dos Santos, J.A., Da Torres S, R., Gonçalves, M.A., Rezende, R.C., Fan, W., Relevance feedback based on genetic programming for image retrieval (2011) Pattern Recogn. Lett., 32 (1), pp. 27-37Gaede, V., Günther, O., Multidimensional access methods (1998) ACM Comput. Surv., 30 (2), pp. 170-231Geusebroek, J.M., Burghouts, G.J., Smeulders, A.W.M., The amsterdam library of object images (2005) Int. J. Comput. Vis., 61 (1), pp. 103-112Gopalan, R., Turaga, P., Chellappa, R., Articulation-invariant representation of non-planar shapes (2010) 11th European Conference on Computer Vision (ECCV'2010), 3, pp. 286-299Huang, J., Kumar, R., Mitra, M., Zhu, W.J., Zabih, R., Image indexing using color correlograms (1997) IEEE Int. Conf. Computer Vision and Pattern Recognition (CVPR'97), pp. 762-768Jagadish, H.V., Mendelzon, A.O., Milo, T., Similarity-based queries (1995) ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems (PODS'95), pp. 36-45Kontschieder, P., Donoser, M., Bischof, H., Beyond pairwise shape similarity analysis (2009) Asian Conference on Computer Vision, pp. 655-666Latecki, L.J., Lakmper, R., Eckhardt, U., Shape descriptors for non-rigid shapes with a single closed contour (2000) IEEE Conference on Computer Vision and Pattern Recognition (CVPR'2000), pp. 424-429Ling, H., Jacobs, D.W., Shape classification using the inner-distance (2007) IEEE Trans. Pattern Anal. Mach. Intell., 29 (2), pp. 286-299Ling, H., Yang, X., Latecki, L.J., Balancing deformability and discriminability for shape matching (2010) European Conference on Computer Vision (ECCV'2010), 3, pp. 411-424Lu, H., Ooi, B., Tan, K., Efficient image retrieval by color contents (1994) Int. Conf. Applications of Databases (ADB'94), Vol. 819 of Lecture Notes in Computer Science, pp. 95-108Park, G., Baek, Y., Lee, H.K., Re-ranking algorithm using post-retrieval clustering for content-based image retrieval (2005) Inform. Process. Manage., 41 (2), pp. 177-194Pass, G., Zabih, R., Miller, J., Comparing images using color coherence vectors (1996) ACM Int. Conf. Multimedia (ACM-MM'96), pp. 65-73Pedronette, D.C.G., Da S Torres, R., Shape retrieval using contour features and distance optimization (2010) International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISAPP'2010), 1, pp. 197-202Pedronette, D.C.G., Da Torres S, R., Exploiting clustering approaches for image re-ranking (2011) J. Vis. Lang. Comput., 22 (6), pp. 453-466Pedronette, D.C.G., Da S Torres, R., Exploiting contextual spaces for image re-ranking and rank aggregation (2011) ACM International Conference on Multimedia Retrieval (ICMR'11), pp. 131-138Pedronette, D.C.G., Da S Torres, R., Image re-ranking and rank aggregation based on similarity of ranked lists (2011) Computer Analysis of Images and Patterns (CAIP'2011), 6854, pp. 369-376Perronnin, F., Liu, Y., Renders, J.M., A family of contextual measures of similarity between distributions with application to image retrieval (2009) IEEE Conference on Computer Vision and Pattern Recognition (CVPR'2009), pp. 2358-2365Ramakrishnan, R., Gehkre, J., (2003) Database Management Systems, , McGraw-Hill Co., IncVan Rijsbergen, C.J., (1979) Information Retrieval, , Butterworth-Heinemann LondonRocha, A., Almeida, J., Nascimento, M.A., Torres, R., Goldenstein, S., Efficient and flexible cluster-and-search approach for CBIR (2008) Int. Conf. Advanced Concepts for Intelligent Vision Systems (ACIVS'08), Vol. 5259 of Lecture Notes in Computer Science, pp. 77-88Rui, Y., Huang, T., Ortega, M., Mehrotra, S., Relevance feedback: A power tool for interactive content-based image retrieval (1998) IEEE Trans. Circ. Syst. Video Technol., 8 (5), pp. 644-655Rui, Y., Huang, T.S., Chang, S.F., Image retrieval: Current techniques, promising directions, and open issues (1999) J. Vis. Commun. Image Representation, 10 (1), pp. 39-62Da Torres S, R., Falcão, A.X., Content-based image retrieval: Theory and applications (2006) Rev. Inform. Teórica Apli., 13 (2), pp. 161-185Dos Santos, J.A., Ferreira, C.D., Da Torres S, R., Gonçalves, M.A., Lamparelli, R.A., A relevance feedback method based on genetic programming for classification of remote sensing images (2011) Inform. Sci., 181 (13), pp. 2671-2684Schwander, O., Nielsen, F., Reranking with contextual dissimilarity measures from representational bregmanl k-means (2010) International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISAPP'2010), 1, pp. 118-122Stehling, R.O., A compact and efficient image retrieval approach based on border/interior pixel classification (2002) ACM Int. Conf. Information and Knowledge Management (CIKM'02), pp. 102-109Swain, M.J., Ballard, B.H., Color indexing (1991) Int. J. Comput. Vis., 7 (1), pp. 11-32Tao, D., Tang, X., Li, X., Wu, X., Asymmetric bagging and random subspace for support vector machines-based relevance feedback in image retrieval (2006) IEEE Trans. Pattern Anal. Mach. Intell., 28 (7), pp. 1088-1099Tian, X., Tao, D., Hua, X.S., Wu, X., Active reranking for web image search (2010) IEEE Trans. Image Process., 19 (3), pp. 805-820Traina, Jr.C., Traina, A.J.M., Faloutsos, C., Seeger, B., Fast indexing and visualization of metric data sets using slim-trees (2002) IEEE Trans. Knowl. Data Eng., 14 (2), pp. 244-260Uhlmann, J.K., Satisfying general proximity/similarity queries with metric trees (1991) Inform. Process. Lett., 40 (4), pp. 175-179Vieira, M.R., Traina, Jr.C., Chino, F.J.T., Traina, A.J.M., DBM-tree: Trading height-balancing for performance in metric access methods (2006) J. Braz. Comput. Soc., 11 (3), pp. 37-52Wang, J., Li, Y., Bai, X., Zhang, Y., Wang, C., Tang, N., Learning context-sensitive similarity by shortest path propagation (2011) Pattern Recogn., 44 (1011), pp. 2367-2374Webber, W., Moffat, A., Zobel, J., A similarity measure for indefinite rankings (2010) ACM Trans. Inform. Syst., 28 (4), pp. 201-2038Wu, S., Crestani, F., Methods for ranking information retrieval systems without relevance judgments (2003) ACM Symposium on Applied Computing (SAC'03), pp. 811-816Yang, X., Bai, X., Latecki, L.J., Tu, Z., Improving shape retrieval by learning graph transduction (2008) European Conference on Computer Vision (ECCV'2008), 4, pp. 788-801Yang, X., Koknar-Tezel, S., Latecki, L.J., Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval (2009) IEEE Conference on Computer Vision and Pattern Recognition (CVPR'2009), pp. 357-364Yang, X., Latecki, L.J., Affinity learning on a tensor product graph with applications to shape and image retrieval (2011) IEEE Conference on Computer Vision and Pattern Recognition (CVPR'2011), pp. 2369-2376Yang, X., Prasad, L., Latecki, L.J., Affinity learning with diffusion on tensor product graph (2013) IEEE Trans. Pattern Anal. Mach. Intell., 35 (1), pp. 28-38Yang, Y., Nie, F., Xu, D., Luo, J., Zhuang, Y., Pan, Y., A multimedia retrieval framework based on semi-supervised ranking and relevance feedback (2012) IEEE Trans. Pattern Anal. Mach. Intell., 34 (4), pp. 723-742Yianilos, P.N., Data structures and algorithms for nearest neighbor search in general metric spaces (1993) ACM/SIGACT-SIAM Int. Symp. Discrete Algorithms (SODA'98), pp. 311-321Zezula, P., Amato, G., Dohnal, V., Batko, M., (2005) Similarity Search: The Metric Space Approach, , Springer-Verlag, Inc