TEXMEX
TEXMEX Research Team
Efficient Exploitation of Multimedia Documents
Exploration, Indexing, Navigation, and Access to Very Large Databases

Post-doc proposal - February 2014

Post-doctoral position in Efficient techniques inspired from genomic for unsupervised multimedia motif discovery / Techniques efficaces inspirées de la génomique pour la découverte non supervisée de motifs multimédias

About Inria and the position

Inria is a public research body, established in 1967, dedicated to computational sciences. Combining computer sciences with mathematics, Inria's 3,500 researchers strive to invent the digital technologies of the future, integrating basic research with applied research to solve real problems. Inria Rennes-Bretagne-Atlantique is one of the eight sites of Inria, with a workforce of about 600 people. The center brings together 33 research teams centered around four major scientific topics (networks and systems; software engineering and symbolic computation; man-machine interaction, images, data, knowledge; simulation and optimization of complex systems) with applications in many fields.

The post-doc position implements a collaboration between two research teams at Inria Rennes-Bretagne-Atlantique, namely TexMex and GenScale, both in the broad topic of data and knowledge. On the one hand, research activities in TexMex are dedicated to multimedia content analysis, addressing a variety of research questions regarding the description, indexing, structuring, comparison and mining of all kinds of multimedia data at a very large scale. On the other hand, GenScale is a bioinformatics research team, focusing on methodological research at the interface between computer science and genomic. The main objective of the group is the design of scalable, optimized and parallel algorithms for processing huge amounts of genomic data.

Scientific context

Multimedia motif discovery consists in finding all occurrences of repeated patterns, called motifs, within multimedia content in a totally unsupervised manner. Contrary to multimedia search, the discovery scenario is performed without prior knowledge on the motifs to find. Typical examples of repeating patterns are advertisements in a TV stream or songs in a radio stream. In these examples, variability between occurrences of a motif is limited. Motif discovery naturally extends to variable motifs, e.g., words within speech data. The main challenges of multimedia motif discovery are obviously efficiency, i.e., the capacity to process very large amounts of data in a reasonable time, and robustness, i.e., the ability to deal with variability between occurrences of a motif.

In essence, multimedia motif discovery is very similar to motif discovery in DNA and genome sequences, a problem that has received tremendous attention. However, very different approaches have been considered in the two domains, mostly because of the very different nature of the data.

In the multimedia field, motif discovery is either seen as an indexing problem (see, e.g., [1]) or implements costly pattern matching techniques (see, e.g., [2]). Content descriptors are indexed, via an index or a hash table, to enable fast retrieval of the nearest neighbor of a point (an image or an audio frame). Post-processing techniques, often computationally demanding, are used to ensure temporal consistency and find the query.

In bioinformatics, efficient algorithms have been proposed for motif discovery such as BLAST [3] or PLAST [4] exploit the specificity of DNA data, taking advantage of their symbolic nature to index short sequences of symbols (3 to 4 consecutive symbols), called n-grams. Distortions between occurrences of a motif follow rules specific to genomic (e.g., gaps in motifs), permitting an efficient implementation of the discovery problem.

The mission of the postdoc will be to explore how efficient motif discovery techniques from the field of genomic can be transposed to the multimedia field, taking into account the peculiarities of image and sound data.

Position

The selected candidate will conduct research with the objective of applying and adapting algorithms from genomic to the efficient search of motifs in multimedia data, building on recent work in the field of multimedia [5,6], on theoretical advances in approximate pattern matching [7] and on existing technology in GenScale [4]. Research questions to address are for instance (but not limited to): How to quantize multimedia data in a meaningful manner? How to handle a large alphabet of symbols in BLAST-like approaches? Are short n-grams meaningful for multimedia? How to exploit the semantics of symbols in multimedia? How to account for multimedia-specific temporal distortions? Research activities will rely on experimental validations with reference data sets, considering a number of key tasks (TV and radio data, speech data) for which state-of-the-art methods already exists, thus easing comparison with existing technology.

Work will be carried out within the TexMex team, in tight interaction with the GenScale team, in collaboration with Guillaume Gravier (multimedia content analysis), Laurent Amsaleg (multimedia indexing and mining) and Dominique Lavenier (genomic, symbolic data mining). The candidate will take advantage of TexMex's expertise in multimedia content representation, indexing and sequence alignment, including previous seminal work on motif discovery. At the same time, he will benefit from GenScale's know-how, technology and software in large scale motif discovery in symbolic data.

Research activities undertaken are expected to have impact in the multimedia signal processing community, significantly contributing advances in multimedia motif discovery, as well as in the data mining community, widening the range of techniques for symbolic sequence mining.

Profile

The successful candidate should hold a Ph. D. in one the following domain: multimedia content analysis, multimedia information retrieval, sequential data mining, genomic motif discovery. Prior experience in multimedia signal processing (e.g., image processing, speech processing) is not a prerequisite but should be compensated by a strong background in sequential pattern mining, preferably applied to genomic. Strong programming skills are required, with good knowledge of the C and C++ languages.

Salary

Salary will be 2,621 EUR gross income (about 2,127 EUR take-home salary), including social benefits.

Bibliography:

  1. J. Yuan, G. Gravier, S. Campion, X. Li and H. Jégou. Efficient Mining of Repetitions in Large-Scale TV Streams with Product Quantization Hashing. Proc. ECCV Workshop on Web-scale Vision and Social Media, 2012.
  2. A. Muscariello, G. Gravier and F. Bimbot. Unsupervised motif acquisition in speech via seeded discovery and template matching combination. IEEE Transactions on Audio, Speech, and Language Processing, 20(7):2031-2044, 2012.
  3. S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Journal of molecular biology, 215(3):403-410, 1990.
  4. D. Lavenier.PLAST: parallel local alignment search tool for database comparison. BMC bioinformatics, 10(1), 2009.
  5. J. J. Burred. Genetic motif discovery applied to audio analysis. Proc. IEEE Intl. Conf. on Acoustics, Speech and Signal Processing, 2012.
  6. L. S. de Oliveira, Z. do Patrocínio Jr., S. Jamil F. Guimarães and G. Gravier. Searching for near-duplicate video sequences from a scalable sequence aligner. Proc. IEEE International Symposium on Multimedia, 2013.
  7. R. Tavenard and L. Amsaleg. Improving the Efficiency of Traditional DTW Accelerators. Irisa Research Report, Nov. 2011.

How to apply?

Send an extended CV + motivation letter + list of publications to: