Rich Media Retrieval on the Web C a Multi-level Indexing Approach

Rich Media Retrieval on the Web C a Multi-level Indexing Approach


Jian Zhai1       Jun Yang1       Qing Li1           Liu Wenyin2      Bo Feng1


1Dept. of Computer Engineering and Information Technology

2Dept. of Computer Science

City University of Hong Kong, HKSAR, China


jian.zhai@student.cityu.edu.hk yangjun@acm.org {itqli,csliuwy}@cityu.edu.hk itfeng@cityu.edu.hk


ABSTRACT

Rich media is experiencing a breathtaking growth in recent years. Because of the potentially very large index size, it is hard to adopt and adapt content-based method to search rich media files on the Web. In this work, we describe a multi-level indexing method to solve this problem. Specifically, we propose a novel technique of indexing rich media at different levels in a large collection. Query examples are presented to show that our approach can find more relevant rich media files and filter out noise data more effectively than traditional search engines without notable loss in efficiency.

Keywords

rich media retrieval, multi-level index, XML representation.

1.     INTRODUCTION

Rich media is a new media format that usually integrates with audio, video, hypertext, graphic, vector objects, animations, and user interactions. For example, SMIL [1], Flash [2], and PowerPoint [3] are all instances of rich media. According to the latest statistics, the three major rich media formats, SMIL, Flash, and PowerPoint, are supported by 99%, 98%, and 96% [4] of the web browsers worldwide, respectively.

However, there are still many difficulties when we try to implement a practical content-based rich media retrieval system in the Web environment. Though Google can retrieve the content of PowerPoint and PDF files, it is shown by the latest statistics that these two types of files account for only 5% of all rich media files on the Web. [4]

Particularly, the index size would be too massive if we had simply applied traditional indexing techniques on top of the hundreds of thousands of rich media files (approximately 9,537,000 files, according to Googles search result) appeared on the Web, not to mention the fact that this number keeps increasing these years. As a result, the gigantic index size entails tremendous calculation in the retrieval process.

To solve this problem, we make use of the vector based information of rich media to reduce the size of indices. The extracted feature is quite small in size but can still precisely capture the characteristics of the original rich media file. Also, several similar rich media files can share the same feature vector, which exactly outlines the characteristics of the group of rich media files. In addition, we provide a multi-level indexing approach as another means to solve the large index size problem. With properly designed data structure and algorithm, the computational complexity of finding the matched results is relatively low.

2.     KEY METHODS

In our model, five levels are provided at which rich media files are indexed. From the top to bottom, they are domain level, category level, semantic level, structural level, and featured level, respectively.

Ÿ    Domain level index is the highest level of index in our model. Its function is similar to that of the web site directory of Yahoo! i.e., indicating the subject or topic of the media file. Index at domain level cannot be changed.

Ÿ    Category level index specifies the categories of rich media files. Indices are subject to change as the result of user feedbacks, as in the case of many existing retrieval systems. . Its classification is more fine-grained than Domain level index and can be modified according to newly inserted indices.

Ÿ    Semantic level index emphasizes the semantics of rich media files. This level and below are created automatically.

Ÿ    Structural level index focuses on the internal characteristics of rich media files.

Ÿ    Feature level is the lowest level for index of rich media files. At this level, the index describes the main objects existing in the rich media files.

At each level, the indices are all mapped to a numeric range. The query keyword is also converted to a query id by a lexicon. ª Then the remaining query can be processed in the same way as the traditional (database) multi-level index operations.

Figure 1. The systematic view of multi-level index

The organization of the multi-level index is shown in Figure 1. Each item in rich media library (Records) includes the URL and several character ids.

3.     APPLICATION

In order to make the abstract approach idiographic, we have implemented a prototype system to validate our algorithm. To illustrate our approach of multi-level indexing method, we present a four-tier architecture to address the representation, indexing, retrieval, and query specification of rich media files. As shown in Figure 2, the architecture is constituted by representation module, indexing module, retrieval module and user interface from bottom to top.

Figure 2. The 4 tier architecture of rich media retrieval system

To allow this architecture to support different types of rich media files, we only need to adapt/extend its representation module. Currently, our system only targets at Flash files because they account for the biggest portion of rich media on the Web (about 90%), although it is effectively applicable to the content-based retrieval of other rich media formats.

In our experiment, we dont realize a crawler. The testing data is achieved from Google search with .swf in the link area.

4.     QUERY EXAMPLE

We compared the performance of our system with other existing Web search engines, including Google and Flashkit.

4.1     Accuracy Test

The selected rich media file for testing is a Flash shooting game [6]. In this experiment, the keyword M4A1 gun (which is the name of a weapon in the game) was used as a query. In our test, the file is found and returned as the result expectedly.

Then we tried to search the same file using Google and FlashKit. It is shown that none of them find the file ones we are looking for. The reason is that our advanced method in multi-level index approach embeds a feature vector (such as M4A1) in the lexicon or even in the description field of index data, so that the required target can be located more accurately.

4.2     Noise Filter Test

When a user input shoot game as the searching keyword in FlashKit, more than 200 Flash movies were returned as the results but we can easily find that some of them are not a shooting game or not even a game.  Such noisy results should be filtered out in the desired scenario.

When we tried the same query in our system, the result is positive because actually there is no shoot game text object in this Flash movie, and our multi-level index mechanism is able to filter out such noise data.

4.3     Response Time Test

As an online content-based search engine, searching speed is an important aspect. In order to see how much the multi-level indexing algorithm can improve the searching speed, we carried out ten keyword-based experiments with and without the multi-level index algorithm being applied to the system. Table 1 gives the detailed comparisons.

Table 1. Test results for speed

Input keyword

Number of movies found

Scratch time (in second)

Stop level

Multi-level indexing

Non-multi-level indexing

age of empire

1,940

0.58

51

3

lion king

1,060

0.32

47

5

football

17,300

0.56

67

3

birthday card

89,400

0.66

82

4

classic music

4,340

0.47

53

4

Samsung

740

0.27

36

4

yesterday once more

780

0.22

37

5

Mp3

115,600

0.71

97

3

Jacky Chan

343

0.20

30

4

abasdfdaas

0

0.02

0.1

0

As shown above, when the multi-level index is not used the system, the query processing is based on a straightforward string comparison, which makes the response time too long to be acceptable in practice. In the case of using our multi-level indexing algorithm, the responding time is evidently shortened.

In fact, our response time is at the same level as Googles. By making use of the vector characteristics of rich media, our multi-level index method is moreover suitable for content based retrieval on rich media.

5.     CONCLUSION AND FUTURE WORK

We have presented an approach to content-based rich media retrieval using multi-level indexing method, and demonstrated its effectiveness through experimental studies. Admittedly, there are still some valuable research problems to be addressed in the future. Currently, Hoffman encoding is used in the lexicon, in which the efficiency bottleneck still exists. If the multi-level index is also applied to the lexicon, the efficiency may be improved. However, a fully-fledged algorithm is yet to be designed for maintaining the indices of the lexicon. Our future work will address this issue too.

6.     Acknowledgement

This work was partially supported by a grant from CityU (Project No.

7001384).

7.     REFERENCES

[1]     http://www.w3.org/AudioVideo/

[2]     http://www.macromedia.com/

[3]     http://www.microsoft.com/office/powerpoint/

[4]     http://www.copyright.gov/1201/comments/reply/090maddux.pdf.

[5]     Yannis Labrou and Tim Finin, Yahoo! as an Ontology - Using Yahoo! Categories to Describe Documents, Eighth International Conference on Knowledge and Information Management (CIKM-99), Kansas City, MO (October 1999).

[6]     http://www.geocities.com/fengbo8/cs.swf