Similar articles

Abstract: The boom of Internet and multimedia technology leads to the explosion of multimedia information, especially image, which has created an urgent need of quickly retrieving similar and interested images from huge image collections. The content-based high-dimensional indexing mechanism holds the key to achieving this goal by efficiently organizing the content of images and storing them in computer memory. In the past decades, many important developments in high-dimensional image indexing technologies have occurred to cope with the ‘curse of dimensionality’. The high-dimensional indexing mechanisms can mainly be divided into three categories: tree-based index, hashing-based index, and visual words based inverted index. In this paper we review the technologies with respect to these three categories of mechanisms, and make several recommendations for future research issues.

[1]Ai, L., Yu, J., Guan, T., 2012. Soft Assignment: Improving Image Representation in Content-Based Image Retrieval. 13th Pacific-Rim Conf. on Multimedia, p.801-810.

[2]Anan, C.S., Hartley, R., 2008. Optimised KD-Trees for Fast Image Descriptor Matching. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, p.1-8.

[3]Andoni, A., Indyk, P., 2006. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. IEEE Symp. on Foundations of Computer Science, p.459-468.

[4]Andoni, A., Indyk, P., 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117-122.

[5]Arya, S., Mount, D.M., 1993. Algorithm for Fast Vector Quantization. Data Compression Conf., p.381-390.

[6]Avrithis, Y., Kalantidis, Y., 2012. Approximate Gaussian Mixtures for Large Scale Vocabularies. European Conf. on Computer Vision, p.15-28.

[7]Babenko, A., Lempitsky, V., 2012. The Inverted Multi-index. IEEE Conf. on Computer Vision and Pattern Recognition, p.3069-3076.

[8]Beckman, N., Kriegel, H.P., Schneider, R., Seeger, B., 1990. The R*-Tree: an Efficient and Robust Access Method for Points and Rectangles. ACM Int. Conf. on Management of Data, p.322-331.

[9]Beis, J.S., Lowe, D.G., 1997. Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, p.1000-1006.

[10]Belkin, M., Niyogi, P., 2001. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. Advances in Neural Information Processing Systems (NIPS), p.585-591.

[11]Bentley, J.L., 1975. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517.

[12]Berchtold, S., Keim, D.A., Kriegel, H.P., 1996. The X-Tree: an Index Structure for High-Dimensional Data. Int. Conf. on Very Large Data Bases, p.28-39.

[13]Biship, C.M., 2006. Pattern Recognition and Machine Learning. Springer, Heidelberg, p.430-455.

[14]Blei, D.M., Ng, A.Y., Jordan, M.I., 2003. Latent Dirichlet allocation. J. Mach. Learn. Res., 3(3):993-1022.

[15]Brandt, J., 2010. Transform Coding for Fast Approximate Nearest Neighbor Search in High Dimensions. IEEE Conf. on Computer Vision and Pattern Recognition, p.1815-1822.

[16]Bu, J., Tan, S., Chen, C., Wang, C., Wu, H., Zhang, L., He, X., 2010. Music Recommendation by Unified Hypergraph: Combining Social Media Information and Music Content. ACM Int. Conf. on Multimedia, p.391-400.

[17]Buhler, J., 2002. Provably Sensitive Indexing Strategies for Biosequence Similarity Search. Annual Int. Conf. on Computational Molecular Biology, p.90-99.

[18]Burkhard, W.A., Keller, R.M., 1973. Some approaches to best-match file searching. Commun. ACM, 16(4):230-236.

[19]Caetano, T.J., Traina, A., Seeger, B., Faloutsos, C., 2000. Slim-Trees: High Performance Metric Trees Minimizing Overlap Between Nodes. Int. Conf. on Extending Database Technology, p.51-65.

[20]Cai, Y., Tong, W., Yang, L., Hauptmann, A.G., 2012. Constrained Keypoint Quantization: Towards Better Bag-of-Words Model for Large-Scale Multimedia Retrieval. Int. Conf. on Multimedia Retrieval, p.1-8.

[21]Chemudugunta, C., Smyth, P., Steyvers, M., 2006. Modeling General and Specific Aspects of Documents with a Probabilistic Topic Mode. Advances in Neural Information Processing Systems (NIPS), p.1-8.

[22]Chen, D., Tsai, S., Chandrasekhar, V., Takacs, G., Chen, H., Vedantham, R., Grzeszczuk, R., Girod, B., 2011. Residual Enhanced Visual Vectors for On-Device Image Matching. 45th Asilomar Conf. on Signals, Systems and Computers, p.850-854.

[23]Chen, Y., Guan, T., Wang, C., 2010. Approximate nearest neighbor search by residual vector quantization. Sensors, 10(12):11259-11273.

[24]Ciaccia, P., Patella, M., Zezula, P., 1997. M-Tree: an Efficient Access Method for Similarity Search in Metric Spaces. Int. Conf. on Very Large Data Bases, p.426-435.

[25]Conway, J.H., Sloane, N.J.A., 1982. Fast quantizing and decoding algorithm for lattice quantizers and codes. IEEE Trans. Inf. Theory, 28(2):227-232.

[26]Datar, M., Immorlica, N., Indyk, P., Mirrokni, V., 2004. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. 20th Annual Symp. on Computational Geometry, p.253-262.

[27]Dong, W., Charikar, M., Li, K., 2008. Asymmetric Distance Estimation with Sketches for Similarity Search in High-Dimensional Spaces. Proc. 31st Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.123-130.

[28]Douze, M., Ramisa, A., Schmid, C., 2011. Combining Attributes and Fisher Vectors for Efficient Image Retrieval. IEEE Conf. on Computer Vision and Pattern Recognition, p.745-752.

[29]Elsayed, E., Lin, J., Oard, D.W., 2008. Pairwise Document Similarity in Large Collections with MapReduce. 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies, p.265-268.

[30]Fonseca, M.J., Jorge, J.A., 2003. Indexing High-Dimensional Data for Content-Based Retrieval in Large Databases. 8th Conf. on Database Systems for Advanced Applications, p.267-274.

[31]Frey, B.J., Dueck, D., 2007. Clustering by passing messages between data points. Science, 315(5814):972-976.

[32]Friedman, J.H., Bentley, J.L., Finkel, P.A., 1977. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3(3):206-209.

[33]Georgescu, B., Shimshoni, I., Meer, P., 2003. Mean Shift Based Clustering in High Dimensions: a Texture Classification Example. Proc. 9th IEEE Int. Conf. on Computer Vision, p.456-463.

[34]Gionis, A., Indyk, P., Motwani, R., 1999. Similarity Search in High Dimensions via Hashing. Int. Conf. on Very Large Data Bases, p.518-529.

[35]Gordo, A., Perronnin, F., 2011. Asymmetric Distances for Binary Embeddings. IEEE Conf. on Computer Vision and Pattern Recognition, p.729-736.

[36]Gray, R.M., Neuhoff, D.L., 1998. Quantization. IEEE Trans. Inf. Theory, 44(6):2325-2383.

[37]Guttman, A., 1984. R-trees: a dynamic index structure for spatial searching. ACM SIGMOD Rec., 14(2):47-57.

[38]He, J., Radhakrishnan, R., Chang, S.F., Bauer, C., 2011. Compact Hashing with Joint Optimization of Search Accuracy and Time. IEEE Conf. on Computer Vision and Pattern Recognition, p.753-760.

[39]Heo, J.P., Lee, Y., He, J., Chang, S.F., Yoon, S.E., 2012. Spherical Hashing. IEEE Conf. on Computer Vision and Pattern Recognition, p.2957-2964.

[40]Indyk, P., Motwani, R., 1998. Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. 30th Annual ACM Symp. on Theory of Computing, p.604-613.

[41]Jagadish, H.V., Ool, B.C., Tan, K.L., Yu, C., Zhang, R., 2005. iDistance: an adaptive B⁺-tree based indexing method for nearest neighbor search. ACM Trans. Database Syst., 30(2):364-397.

[42]Jain, M., Jegou, H., Gros, P., 2011. Asymmetric Hamming Embedding: Taking the Best of Our Bits for Large Scale Image Search. 19th ACM Int. Conf. on Multimedia, p.1441-1444.

[43]Jegou, H., Douze, M., Schmid, C., 2008a. Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search. European Conf. on Computer Vision, p.304-317.

[44]Jegou, H., Amsaleg, L., Schmid, C., Gros, P., 2008b. Query-Adaptative Locality Sensitive Hashing. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, p.825-828.

[45]Jegou, H., Douze, M., Schmid, C., 2009a. Packing Bag-of-Features. IEEE Int. Conf. on Computer Vision, p.2357-2364.

[46]Jegou, H., Douze, M., Schmid, C., 2009b. Recent advances in large scale image search. emerging trends in visual computing, LNCS, 5416:305-326.

[47]Jegou, H., Douze, M., Schmid, C., 2009c. Searching with Quantization: Approximate Nearest Neighbor Search Using Short Codes and Distance Estimators. Technical Report RR-7020, INRIA. Available from http://hal.inria.fr/docs/00/41/07/67/PDF/RR-7020.pdf

[48]Jegou, H., Douze, M., Schmid, C., Perez, P., 2010a. Aggregating Local Descriptors into a Compact Image Representation. IEEE Conf. on Computer Vision and Pattern Recognition, p.3304-3311.

[49]Jegou, H., Douze, M., Schmid, C., 2010b. Improving bag-of-feature for large scale image search. Int. J. Comput. Vis., 87(3):316-336.

[50]Jegou, H., Douze, M., Schmid, C., 2011. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1):117-128.

[51]Jegou, H., Perronnin, F., Douze, M., Sanchez, J., Perez, P., Schmid, C., 2012. Aggregating local image descriptors into compact codes. IEEE Trans. Pattern Anal. Mach. Intell., 34(9):1704-1716.

[52]Joly, A., Buisson, O., 2011. Random Maximum Margin Hashing. IEEE Conf. on Computer Vision and Pattern Recognition, p.873-880.

[53]Katayama, N., Satoh, S., 1997. The SR-Tree: an Index Structure for High-Dimensional Nearest Neighbor Queries. Int. Conf. on Management of Data, p.369-380.

[54]Ke, Y., Sukthankar, R., Huston, L., 2004. Efficient Near-Duplicate Detection and Sub-image Retrieval. ACM Int. Conf. on Multimedia, p.869-876.

[55]Kulis, B., Darrell, T., 2009. Learning to Hash with Binary Reconstructive Embeddings. Advances in Neural Information Processing Systems (NIPS), p.1-9.

[56]Kulis, B., Grauman, K., 2009. Kernelized Locality-Sensitive Hashing for Scalable Image Search. IEEE 12th Int. Conf. on Computer Vision, p.2130-2137.

[57]Kuo, Y.H., Chen, K.T., Chiang, C.H., Hsu, W.H., 2009. Query Expansion for Hash-Based Image Object Retrieval. 17th Int. Conf. on Multimedia, p.65-74.

[58]Kuo, Y.H., Lin, H.T., Cheng, W.H., Yang, Y.H., Hsu, W.H., 2010. Unsupervised Auxiliary Visual Words Discovery for Large-Scale Image Object Retrieval. IEEE Conf. on Computer Vision and Pattern Recognition, p.905-912.

[59]Lepetit, V., Lagger, P., Fua, P., 2005. Randomized Trees for Real-Time Keypoint Recognition. IEEE Conf. on Computer Vision and Pattern Recognition, p.775-781.

[60]Li, D., Yang, L., Hua, X.S., Zhang, H.J., 2010. Large-Scale Robust Visual Codebook Construction. Int. Conf. on Multimedia, p.1183-1186.

[61]Lin, K.I., Jagadish, H.V., Faloutsos, C., 1994. The TV-tree: an index structure for high-dimensional data. VLDB J., 3(4):517-542.

[62]Liu, L., Wang, L., Liu, X., 2011. In Defense of Soft-Assignment Coding. IEEE Int. Conf. on Computer Vision, p.2486-2493.

[63]Liu, W., Wang, J., Ji, R., Jiang, Y.G., Chang, S.F., 2012. Supervised Hashing with Kernels. IEEE Conf. on Computer Vision and Pattern Recognition, p.2074-2081.

[64]Liu, X., Mu, Y., Lang, B., Chang, S.F., 2012. Compact Hashing for Mixed Image-Keyword Query over Multi-label Images. 2nd ACM Int. Conf. on Multimedia Retrieval, p.1-8.

[65]Lowe, D.G., 1999. Object Recognition from Local Scale-Invariant Features. IEEE Int. Conf. on Computer Vision, p.1150-1157.

[66]Lowe, D.G., 2004. Distinctive image feature from scale-invariant keypoints. Int. J. Comput. Vis., 60(2):91-100.

[67]Lv, Q., Josephson, W., Wang, Z., Charikar, M., Li, K., 2007. Efficient Indexing for High-Dimensional Similarity Search. 33rd Int. Conf. on Very Large Data Bases, p.950-961.

[68]Matei, B., Shan, Y., Sawhney, H.S., Tan, Y., Kumar, R., Huber, D., Hebert, M., 2006. Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation. IEEE Trans. Pattern Anal. Mach. Intell., 28(7):1111-1126.

[69]Motwani, R., Naor, A., Panigraphy, R., 2008. Lower bounds on locality sensitive hashing. SIAM J. Discr. Math., 21(4):930-935.

[70]Mu, Y., Sun, J., Han, T.X., Cheong, L.F., Yan, S., 2010. Randomized Locality Sensitive Vocabularies for Bag-of-Features Model. European Conf. on Computer Vision, p.748-761.

[71]Mu, Y., Chen, X., Chuan, T.S., Yan, S., 2011. Learning Reconfigurable Hashing for Diverse Semantics. Proc. 1st ACM Int. Conf. on Multimedia Retrieval, p.1-8.

[72]Nister, D., Stewenius, H., 2006. Scalable Recognition with a Vocabulary Tree. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, p.2161-2168.

[73]Norouzi, M., Fleet, D.J., 2011. Minimal Loss Hashing for Compact Binary Codes. 28th Int. Conf. on Machine Learning, p.353-360.

[74]Norouzi, M., Punjani, A., Fleet, D.J., 2012. Fast Search in Hamming Space with Multi-index Hashing. IEEE Conf. on Computer Vision and Pattern Recognition, p.3108-3115.

[75]Panigraphy, R., 2006. Entropy Based Nearest Neighbor Search in High Dimensions. 17th Annual ACM-SIAM Symp. on Discrete Algorithm, p.1186-1195.

[76]Pauleve, L., Jegou, H., Amsaleg, L., 2010. Locality sensitive hashing: a comparison of hash function types and querying mechanisms. Pattern Recogn. Lett., 31(11):1348-1358.

[77]Perronnin, F., Dance, C., 2007. Fisher Kernels on Visual Vocabularies for Image Categorization. IEEE Conf. on Computer Vision and Pattern Recognition, p.1-8.

[78]Philbin, J., Chum, O., Isard, M., Sivic, J., Zisserman, A., 2007. Object Retrieval with Large Vocabularies and Fast Spatial Matching. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, p.1-8.

[79]Philbin, J., Chum, O., Michael, I., Sivic, J., Zisserman, A., 2008. Lost in Quantization: Improving Particular Object Retrieval in Large Scale Image Databases. IEEE Conf. on Computer Vision and Pattern Recognition, p.1-8.

[80]Philbin, J., Isard, M., Sivic, J., Zisserman, A., 2010. Descriptor Learning for Efficient Retrieval. European Conf. on Computer Vision, p.677-691.

[81]Robinson, J.T., 1981. The K-D-B-Tree: a Search Structure for Large Multidimensional Dynamic Indexes. ACM SIGMOD Int. Conf. on Management of Data, p.10-18.

[82]Rui, Y., Huang, T.S., 1999. Image retrieval: current techniques, promising directions, and open issues. J. Vis. Commun. Image Represent., 10(1):39-62.

[83]Salakhutdinov, R., Hinton, G., 2007a. Semantic Hashing. SIGIR Workshop on Information Retrieval and Application of Graphical Models, p.1-8.

[84]Salakhutdinov, R., Hinton, G., 2007b. Learning a Nonlinear Embedding by Preserving Class Neighborhood Structure. 11th Int. Conf. on Artificial Intelligence and Statistics, p.412-419.

[85]Salakhutdinov, R., Hinton, G., 2009. Semantic hashing. Int. J. Approx. Reason., 50(7):969-978.

[86]Sellis, T.K., Roussopoulos, N., Faloutsos, C., 1987. The R⁺-Tree: a Dynamic Index of Multi-dimensional Objects. Int. Conf. on Very Large Data Bases, p.507-518.

[87]Shao, J., Wu, F., Ouyang, C., Zhang, X., 2012. Sparse spectral hashing. Pattern Recogn. Lett., 33(3):271-277.

[88]Sivic, J., Zisserman, A., 2003. Video Google: a Text Retrieval Approach to Object Matching in Video. Proc. 9th IEEE Int. Conf. on Computer Vision, p.1470-1477.

[89]Skopal, T., 2004. Pivoting M-Tree: a Metric Access Method for Efficient Similarity Search. Annual Int. Workshop on Databases, Texts, Specifications and Objects (Dateso), p.27-37.

[90]Skopal, T., 2007. Unified framework for fast exact and approximate search in dissimilarity spaces. ACM Trans. Database Syst., 32(4), Article 29, p.1-47.

[91]Skopal, T., Hoksza, D., 2007. Improving the Performance of M-Tree Family by Nearest-Neighbor Graphs. 11th East European Conf. on Advances in Databases and Information Systems, p.172-188.

[92]Skopal, T., Lokoc, J., 2008. NM-Tree: Flexible Approximate Similarity Search in Metric and Non-metric Spaces. 19th Int. Conf. on Database and Expert Systems Applications, p.312-325.

[93]Skopal, T., Lokoc, J., 2009. New dynamic construction techniques for M-tree. J. Discr. Algor., 7(1):62-77.

[94]Strecha, C., Bronstein, A.M., Bronstein, M.M., Fua, P., 2012. LDAHash: improved matching with smaller descriptors. IEEE Trans. Pattern Anal. Mach. Intell., 34(1):66-78.

[95]Tavenard, R., Jegou, H., Amsaleg, L., 2011. Balancing Clusters to Reduce Response Time Variability in Large Scale Image Search. 9th Int. Workshop on Content-Based Multimedia Indexing, p.19-24.

[96]Terasawa, K., Tanaka, Y., 2007. Spherical LSH for approximate nearest neighbor search on unit hypersphere. LNCS, 4619:27-38.

[97]Torralba, A., Murphy, K.P., Freeman, W.T., 2004. Sharing Features: Efficient Boosting Procedures for Multiclass Object Detection. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, p.762-769.

[98]Torralba, A., Fergus, R., Weiss, Y., 2008. Small Codes and Large Image Databases for Recognition. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, p.1-8.

[99]Torresani, L., Szummer, M., Fitzgibbon, A., 2010. Efficient Object Category Recognition Using Classemes. European Conf. on Computer Vision, p.776-789.

[100]Tuytelaars, T., Schmid, C., 2007. Vector Quantizing Feature Space with a Regular Lattice. IEEE 11th Int. Conf. on Computer Vision, p.1-8.

[101]van Gemert, J.C., Geusebroek, J.M., Veenman, C.J., Smeulders, A.W.M., 2008. Kernel codebooks for scene categorization. LNCS, 5304:696-709.

[102]van Gemert, J.C., Veenman, C.J., Smeulders, A.W.M., Geusebroek, J.M., 2010. Visual word ambiguity. IEEE Trans. Pattern Anal. Mach. Intell., 32(7):1271-1283.

[103]Wang, J., Kumar, S., Chang, S.F., 2010. Semi-supervised Hashing for Scalable Image Retrieval. IEEE Conf. on Computer Vision and Pattern Recognition, p.3424-3431.

[104]Wang, J., Kumar, S., Chang, S.F., 2012. Semi-supervised hashing for large scale search. IEEE Trans. Pattern Anal. Mach. Intell., 34(12):2393-2406.

[105]Weiss, Y., Torralba, A., Fergus, R., 2009. Spectral Hashing. Advances in Neural Information Processing Systems (NIPS), 21:1753-1760.

[106]Wengert, C., Douze, M., Jegou, H., 2011. Bag-of-Colors for Improved Image Search. 19th Int. Conf. on Multimedia, p.1437-1440.

[107]Wu, L., Hoi, S.C.H., Yu, N., 2009. Semantics-Preserving Bag-of-Words Models for Efficient Image Annotation. 1st ACM Workshop on Large-Scale Multimedia Retrieval and Mining, p.19-26.

[108]Zhang, D., Wang, J., Cai, D., Lu, J., 2010. Self-Taught Hashing for Fast Similarity Search. Proc. 33rd Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.18-25.

[109]Zhang, X., Li, Z., Zhang, L., Ma, W., Shum, H.Y., 2009. Efficient Indexing for Large Scale Visual Search. IEEE 12th Conf. on Computer Vision, p.1103-1110.

[110]Zhou, L., 2011. Research on Local Features Aggregating and Indexing Algorithm in Large-Scale Image Retrieval. Master Thesis, Huazhong University of Science and Technology, Wuhan, China, p.10-15 (in Chinese).

[111]Zhuang, Y., Zhuang, Y., Li, Q., Chen, L., Yu, Y., 2008. Indexing High-Dimensional Data in Dual Distance Spaces: a Symmetrical Encoding Approach. Proc. 11th Int. Conf. on Extending Database Technology, p.241-251.

[112]Zhuang, Y., Liu, Y., Wu, F., Zhang, Y., Shao, J., 2011. Hypergraph Spectral Hashing for Similarity Search of Social Image. ACM Int. Conf. on Multimedia, p.1457-1460.