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

ABSTRACT

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

Keywords

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

1. =20 INTRODUCTION

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

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

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

2. =20 KEY=20 METHODS

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

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

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

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

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

Ÿ = Feature level is=20 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=20 numeric=20 range. The query keyword is also = converted=20 to a query id by a lexicon. = ª Then the remaining query can be processed in = the same=20 way as the=20 traditional=20 (database) multi-level index operations.

Figure 1. = The=20 systematic view of multi-level index

The organization of the multi-level index is = shown in=20 =20 APPLICATION

In order to make the abstract approach = idiographic, we=20 have implemented a prototype system to validate our algorithm. To = illustrate our=20 approach of multi-level indexing method, we present a four-tier = architecture to=20 address the representation, indexing, retrieval, and query specification = of rich=20 media files. As shown in Figure=20 2.=20 The 4 tier architecture of rich media retrieval = system

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

In our experiment, we don=A1=AFt realize a = crawler. The=20 testing data is achieved from Google search = with=20 =A1=B0.swf=A1=B1 in the link = area.

4. =20 QUERY=20 EXAMPLE

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

4.1 =20 Accuracy=20 Test

The selected rich media file for testing is a = Flash=20 shooting game =20 Noise=20 Filter Test

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

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

4.3 =20 Response Time=20 Test

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

Table 1. Test results for=20 speed

Input keyword

Number of movies found =

Scratch time (in = second)

Stop = level

Multi-level = indexing

Non-multi-level=20 indexing

age of empire

1,940

0.58

lion king

1,060

0.32

football

17,300

0.56

birthday card

89,400

0.66

classic music

4,340

0.47

Samsung

740

0.27

yesterday once = more

780

0.22

Mp3

115,600

0.71

Jacky Chan

343

0.20

abasdfdaas

0.02

0.1

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

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

5. =20 CONCLUSION AND FUTURE=20 WORK

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

6. =20 Acknowledgement

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

7001384).

7. =20 REFERENCES

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

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

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

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

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

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