Multimedia Database Searching - NDBI030

• Title: Vyhledávání v multimediálních databázích
• Guaranteed by: Department of Software Engineering (32-KSI)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2010
• Semester: summer
• E-Credits: 6
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech
• Teaching methods: full-time
• Guarantor: prof. RNDr. Tomáš Skopal, Ph.D.
• Class: Informatika Mgr. - volitelný
• Classification: Informatics > Database Systems
• Pre-requisite : NDBI007, NDBI025

Annotation

English

The course gives an overview over the state-of-the-art techniques in content-based similarity search in multimedia databases (MDB) or, more generally, in collections of unstructured data. Unlike classic (relational) databases and exact-match querying, in MDB we need to extract features from the multimedia objects and provide a kind of similarity-based retrieval. The second part of the course is focused on indexing - in order to search the database efficiently (quickly).

Last update: T_KSI (28.04.2005)

Czech

Předmět seznamuje s problematikou vyhledávání v multimediálních databázích (MDB), obecně v kolekcích nestrukturovaných dat. Na rozdíl od klasických (relačních) systémů a dotazů na shodu je podstatou vyhledávání v MDB extrakce vlastností z multimediálních dokumentů a dotazování na podobnost. Druhá část kurzu je zaměřena na indexování multimediálních dat za účelem efektivního vyhledávání.

Last update: T_KSI (28.04.2005)

Literature

Similarity Search - The Metric Space Approach, P. Zezula, G. Amato, V. Dohnal, M. Batko, Springer, 2006

Image Databases, V. Castelli, L.D. Bergman (eds.), Wiley, 2002

Metric Indexing in Information Retrieval, T. Skopal, Ph.D. thesis, TU Ostrava, 2004 (k dispozici na webu přednášejícího)

Multimedia Systems and Content-based Management, S. Deb, Idea Group Publishing, 2004

Image Retrieval, C. Jorgensen, Scarecrow Press, 2003

+ internetové zdroje a odkazy na webu přednášejícího

Last update: Skopal Tomáš, prof. RNDr., Ph.D. (18.04.2006)

Syllabus

English

1. Introduction: Multimedia databases (MDB). The motivation for searching in MDB, applications. Modalities of searching and querying. Text-based vs. content-based retrieval. Feature extraction and similarity measures. Indexing.

2. MDB formalization, querying semantics, similarity as a relevance to a query. Query result quality (effectiveness) and search performance (efficiency) + measures.

3. Feature extraction and similarity measures. Vector representations, strings/sequences, sets, graphs. Properties of similarity measures, metric axioms. Discussion about measures and similarity theories.

4. Queries - range query, k nearest neighbors, reverse nearest neighbor, closest pair, similarity join.

5. Retrieval modalities. Querying, relevance feedback, browsing, navigation in query result, classification. Application interfaces. Examples.

6. Applications: Image retrieval (colors, textures and shape features). Fingerprint, iris, music, protein, text and XML retrieval.

7. Mapping methods and dimensionality reduction. Approximation vs. filtration. Latent semantics as a part of feature extraction. Linear projections: LSI, random projections, FastMap, SparseMap, MetricMap. Non-linear projections.

8. Metric access methods vs. spatial access methods. The curse of dimensionality. Distance distribution and intrinsic dimensionality.

9. Static MAM: (m)vp-tree, gh-tree, GNAT

10. Dynamic MAM: M-tree + modifications, PM-tree, LPM-tree

11. Pivot-based methods. Global and local pivots. M-tree vs. LAESA. vp-forest, D-index. Pivot selection methods.

12. Approximate and probabilistic methods of similarity search. AC and PAC search. Non-metric search.

Last update: T_KSI (28.04.2005)

Czech

1. Úvod: Multimediální databáze (MDB). Motivace k vyhledávání v MDB, aplikace. Modality vyhledávání a dotazování. Text-based vs. content-based retrieval. Extrakce vlastností a míry podobnosti. Indexování.

2. Formalizace MDB, sémantika dotazování, podobnost jako relevance k dotazu. Kvalita výsledku (effectiveness) a rychlost vyhledávání (efficiency) + míry.

3. Extrakce vlastností z multimediálních dokumentů a míry podobnosti. Vektorové reprezentace, řetězce/sekvence, množiny, grafy. Vlastnosti měr, metrické axiomy. Diskuse k mírám a příslušným teoriím podobnosti.

4. Dotazy - rozsahový dotaz, k nejbližších sousedů, reverse nearest neighbor, closest pair, similarity join.

5. Modality vyhledávání. Dotazování, relevance feedback, browsing, navigace ve výsledku dotazu, klasifikace. Aplikační rozhraní. Ukázky existujících aplikací.

6. Aplikace: podobnostní vyhledávání obrázků podle barev, textur, tvarů. Otisky prstů, oční duhovky, melodie, bílkoviny, text, XML.

7. Mapování do vektorů a redukce dimenze. Aproximace vs. filtrace. Skrytá sémantika jako součást extrakce vlastností. Lineární projekce: LSI, náhodné projekce, FastMap, SparseMap, MetricMap. Nelineární projekce.

8. Metrické přístupové metody (metric access methods) vs. prostorové přístupové metody (spatial access methods). Prokletí dimenzionality. Distribuce vzdáleností a vnitřní dimenze.

9. Statické MAM: (m)vp-strom, gh-strom, GNAT

10. Dynamické MAM: M-strom + modifikace (Slim-strom, PM-strom, SPM-strom)

11. Pivot-based metody. Globální a lokální pivoty. M-strom vs. LAESA. vp-forest, D-index. Techniky výběru globálních pivotů.

12. Aproximativní a probabilistické metody vyhledávání. AC a PAC dotazování. Nemetrické vyhledávání.

Last update: Skopal Tomáš, prof. RNDr., Ph.D. (20.07.2005)