Detail

Compressed sensing for media search engines

A number of information exploration applications have recently emerged providing access to rich media, e.g., Flickr, YouTube and Wikipedia. These applications are used for both entertainment and professional purposes. The success of these applications is closely related to the users’ role in the information-processing chain: users generate content, metadata and provide valuable feedback concerning information relevance. Systems collect vast amounts of user interaction data such as queries, click data, annotations, comments and new content. These diverse sources of information create two critical challenges to traditional indexing and search techniques: (1) mining the relevant information from a large number of sources and (2) matching the user query to the extracted information.
The main hypothesis of this project is that compressed sensing techniques will define the new state-of-the-art for multimedia information retrieval. This hypothesis is supported by two facts. The first fact is related to the L1 minimization criterion: rich media applications need to handle information with a large number of variables, and sparse models, as the ones computed by compressed sensing techniques, can indeed reduce the number of information sources. The second fact is related to the large-scale resources available that allow the inference of a sparse representation of media documents. This corresponds to the prior knowledge about the problem domain structure that allows working in under-sampling conditions (sub-Nyquist).
To investigate this hypothesis, we identified three main objectives that shall be described next.
The first objective addresses high-dimensional indexing methods. The computational complexity of seeking an index increases with the data dimensionality. Compressed sensing methods will be researched to compute a sparse representation of media for fast indexing and retrieval.
The second objective addresses the mining (or extraction) of relevant (structured) information from data. Compressed sensing algorithms are especially useful in this problem. The large number of sources involved in the inference of information/facts is one of the highly praised advantages of compressed sensing.
The third objective: active learning search for matching the user search intentions. Automated analysis and categorization of user queries can direct users to an “educated query” that might be closer to the user intentions. Compressed sensing techniques will be applied as an online learning algorithm to categorize user queries and compute an improved search rank.
A search engine will be implemented and released as open-source as dissemination and demonstrator of the research activities of the project (algorithms and statistical models).