An efficient indexing structure for multimedia data

ABSTRACT

In the last few years, the increase of online video has challenged research in the field of video information retrieval. Video search engines have become common on the Internet and require the use of powerful tools for fast access to data. However the representation of multimedia data as video shot or keyframe with visual features requires the use of a multidimensional space and indexing structures face the well known ``curse of dimensionality". In this paper, we propose a new indexing structure that combines a clustering algorithm using random projections and a recursive multidimensional indexing structure. In our experiments, we study the effeciency and the effectiveness of our indexing structure using visual features of video shots of TRECVID database. We compare our proposed structure with other state-of-the-art methods.

REFERENCES

• 1: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 2: N. O ŠConnor, E. Cooke, H. L. Borgne, M. Blighe, and T. Adamek. The acetoolbox: low-level audiovisual feature extraction for retrieval and classification. In The 2nd European Workshop on the Integration of Knowledge, Semantics and Digital Media Technologies (EWIMT 2005), London, United Kingdom pages 55--60, 2005.
• 3: Beng Chin Ooi , Kian-Lee Tan , Cui Yu , Stephane Bressan, Indexing the edges—a simple and yet efficient approach to high-dimensional indexing, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.166-174, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335219]
• 4: Heng Tao Shen , Beng Chin Ooi , Xiaofang Zhou, Towards effective indexing for very large video sequence database, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066240]
• 5: Alan F. Smeaton , Paul Over , Wessel Kraaij, Evaluation campaigns and TRECVid, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA [doi>10.1145/1178677.1178722]
• 6: Thierry Urruty, KpyrRec: a recursive multidimensional indexing structure, International Journal of Parallel, Emergent and Distributed Systems, v.23 n.3, p.235-245, June 2008 [doi>10.1080/17445760701536159]
• 7: T. Urruty, C. Djeraba, and D. A. Simovici. Clustering by random projections. In P. Perner, editor, Advances in Data Mining. Theoretical Aspects and Applications, 7th Industrial Conference, ICDM 2007, Leipzig, Germany, July 14--18 volume 4597 of Lecture Notes in Computer Science pages 107--119. Springer, 2007.
• 8: 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
• 9: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001
• 10: Rui Zhang , Beng Chin Ooi , Kian-Lee Tan, Making the Pyramid Technique Robust to Query Types and Workloads, Proceedings of the 20th International Conference on Data Engineering, p.313, March 30-April 02, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Experimentation, Performance

Keywords:
clustering, indexing structure, multimedia