Adaptive nearest neighbor search for relevance feedback in large image databases

ABSTRACT

Relevance feedback is often used in refining similarity retrievals in image and video databases. Typically this involves modification to the similarity metrics based on the user feedback and recomputing a set of nearest neighbors using the modified similarity values. Such nearest neighbor computations are expensive given that typical image features, such as color and texture, are represented in high dimensional spaces. Search complexity is a ciritcal issue while dealing with large databases and this issue has not received much attention in relevance feedback research. Most of the current methods report results on very small data sets, of the order of few thousand items, where a sequential (and hence exhaustive search) is practical. The main contribution of this paper is a novel algorithm for adaptive nearest neigbor computations for high dimensional feature vectors and when the number of items in the databse is large. The proposed method exploits the correlations between two consecutive nearest neighbor searches when the underlying similarity metric is changing, and filters out a significant number of candidates ina two stage search and retrieval process, thus reducing the number of I/O accesses to the database. Detailed experimental results are provided using a set of about 700,000 images. Comparision to the existing method shows an order of magnitude overall imporovement.

REFERENCES

• 1: J.R. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Jam, and CF. Shu, "The virage image search engine: An open framework for image management," In Proceedings of SPIE, Storage and Retrieval for Still Image and Video Databases IV, pages 76--87, San Jose, CA, USA, February 1996..
• 2: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 3: Independent Quantization: An Index Compression Technique for High-Dimensional Data Spaces, Proceedings of the 16th International Conference on Data Engineering, p.577, February 28-March 03, 2000
• 4: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Proceedings of the 15th International Conference on Data Engineering, p.440, March 23-26, 1999
• 5: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Vector approximation based indexing for non-uniform high dimensional data sets, Proceedings of the ninth international conference on Information and knowledge management, p.202-209, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354820]
• 8: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 9: Yoshiharu Ishikawa , Ravishankar Subramanya , Christos Faloutsos, MindReader: Querying Databases Through Multiple Examples, Proceedings of the 24rd International Conference on Very Large Data Bases, p.218-227, August 24-27, 1998
• 10: C. Meilhac and C. Nastar, ""Relevance feedback and category search in image databases," Proceedings of IEEE Intemational Conference on Multimedia Computing and Systems, pp. 512-517, Florence, Italy, 7-11 June 1999.
• 11: MPEG-7 Visual part of experimentation Model Version 8.0, ISO/IEC JTCl/SC29/WGll #N3673, La Baule, October 2000.
• 12: MPEG-7 Description of Color/Texture core experiments, ISOlIEC JTCl/SC29/WGll #N2929, Melbourne, Australia, October 1999.
• 13: W. Niblack, R. Barber, and et al., "The QBIC project: Querying images by content using color, texture and shape," Proceedings of the SPIE - The International Society for Optical Engineering, vol.1908, (Storage and Retrieval for Image and Video Databases, San Jose, CA, USA, 23 Feb. 1993.) 1993, p. 173-87.
• 14: A. L. Ratan, 0. Maron, W. E. L. Grimson and T. Lozano- Perez, "A Framework for learning query concepts in image classification," Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages 423-43 1, 1999.
• 15: Y. Rui, T. Huang, "Optimizing Learning in Image Retrieval", Proc. Int. Conf. on Computer Vision, pp. 236-243, 2000.
• 16: Y. Rui, T. S. Huang, and S. Mehrotra, "Content-based image retrieval with relevance feedback in MARS," in Proc. of IEEE Int. Conf. on Image Processing '97, pages 815--818, October 1997.
• 17: H. D. Tagare, Increasing retrieval efficiency by index tree adaptation, Proceedings of the 1997 Workshop on Content-Based Access of Image and Video Libraries (CBAIVL '97), p.28, June 20-20, 1997
• 18: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 19: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996
• 20: P. Wu, "Search and Indexing of Large Image/Video Databases," Ph. D Thesis, Dept. Electrical and Computer Engineering, University of California, Santa Barbara, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design

Keywords:
nearest neighbor search, relevance feedback, similarity retrieval