Mario D¨oller, Dipl.-Ing.
THE MPEG-7 MULTIMEDIA DATABASE SYSTEM
(MPEG-7 MMDB)
DISSERTATION
zur Erlangung des akademischen Grades
Doktor der Technischen Wissenschaften
Universit¨at Klagenfurt
Fakult¨at f¨ur Wirtschaftswissenschaften und Informatik
1. Begutachter: a.o.Univ.-Prof. Dipl.-Inf. Dr. Harald Kosch
Institut: Institut f¨ur Informationstechnologie, Universit¨at Klagenfurt
2. Begutachter: o.Univ.-Prof. Dipl.-Ing. Dr. L´aszl´o B¨osz¨orm´enyi
Institut: Institut f¨ur Informationstechnologie, Universit¨at Klagenfurt
Oktober 2004
Ehrenw¨ortliche Erkl¨arung
Ich erkl¨are ehrenw¨ortlich, dass ich die vorliegende Schrift verfasst
und die mit ihr unmittelbar verbundenen Arbeiten selbst durchgef¨uhrt
habe. Die in der Schrift verwendete Literatur sowie das Ausmaß der mir
im gesamten Arb eitsvorgang gew¨ahrten Unterst¨utzung sind ausnahmslos
angegeben. Die Schrift ist noch keiner anderen Pr¨ufungsbeh¨orde vorgelegt
worden.
Word of Honour
I honestly declare that the thesis at hand and all its directly accompanying
work have been done by myself. Permission has been obtained for the use
of any copyrighted material appearing in this thesis and all such use is
clearly acknowledged. The thesis has not been presented to any other
examination board.
Unterschrift:
Klagenfurt, 2. November 2004
ii
Contents
List of Tables vii
List of Figures viii
I Related Work 1
1 Introduction 2
1.1 Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Legend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Basic Concepts of Content-Based Retrieval 8
2.1 CBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 CBR Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Multimedia Metadata Standards 14
3.1 Dublin Core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 SMPTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 P/Meta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 MPEG-7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.5 MPEG-21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
iii
4 Topics in Multimedia Database Management 23
4.1 Multimedia DB-Schema . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Multimedia Index Structures . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.1 Definitions and Theory . . . . . . . . . . . . . . . . . . . . . . 29
4.2.2 Index Structures for High-Dimensional Data . . . . . . . . . . 32
4.3 Multimedia Query Optimization . . . . . . . . . . . . . . . . . . . . . 34
5 Database Extensions to support Multimedia 39
5.1 Query Extensions for Multimedia . . . . . . . . . . . . . . . . . . . . 40
5.1.1 SQL/MM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.1.2 MOQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2 Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3 IBM DB2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.4 IBM Informix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.5 Summarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6 MPEG-7 Databases 53
6.1 Classification of XML Databases . . . . . . . . . . . . . . . . . . . . . 54
6.1.1 Native XML Databases . . . . . . . . . . . . . . . . . . . . . . 54
6.1.2 XML Database Extension . . . . . . . . . . . . . . . . . . . . 56
6.2 Querying XML Databases . . . . . . . . . . . . . . . . . . . . . . . . 59
6.3 Usability of XML Databases for MPEG-7 . . . . . . . . . . . . . . . . 61
7 Application Scenarios 64
7.1 Image Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2 Audio Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.3 Video Browsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
II MPEG-7 Multimedia DataBase (MPEG-7 MMDB) 69
8 Core System 72
iv
8.1 Oracle’s Data Cartridge Technology . . . . . . . . . . . . . . . . . . . 73
8.1.1 Oracle’s Extensibility Services . . . . . . . . . . . . . . . . . . 74
8.2 DB-Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.2.1 Object-relational database features . . . . . . . . . . . . . . . 77
8.2.2 The XMLTYPE data type . . . . . . . . . . . . . . . . . . . . 84
8.2.3 Guidelines for mapping MPEG-7 to an object-relational DB
model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.2.4 Resulting DB-Schema . . . . . . . . . . . . . . . . . . . . . . 94
8.3 Index Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
8.3.1 Multimedia Indexing Framework (MIF) . . . . . . . . . . . . . 102
8.3.2 GiST Framework . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 108
8.4 Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.4.1 Motivation and Definitions . . . . . . . . . . . . . . . . . . . . 113
8.4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.4.3 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.4.4 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.4.5 Cluster Visualization Tool . . . . . . . . . . . . . . . . . . . . 125
8.4.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
9 Internal Libraries 132
9.1 InitLib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9.2 InsertLib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.3 DeleteLib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9.4 QueryLib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.5 MDC data type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
10 Application Libraries 143
10.1 Blobworld Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
v