Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 290)
Detail práce
   Přihlásit přes CAS
Modifikace metody Pivot Tables pro perzistentní metrické indexování
Název práce v jazyce práce (slovenština): Modifikace metody Pivot Tables pro perzistentní metrické indexování
Název práce v češtině: Modifikace metody Pivot Tables pro perzistentní metrické indexování
Název v anglickém jazyce: Modification of Pivot Tables method for persistent metric indexing
Klíčová slova: podobnostné vyhľadávanie, metrické prístupové metódy, indexovanie, M-strom, pivot tables
Klíčová slova anglicky: similarity search, metric access methods, indexing, M-tree, pivot tables
Akademický rok vypsání: 2009/2010
Typ práce: diplomová práce
Jazyk práce: slovenština
Ústav: Katedra softwarového inženýrství (32-KSI)
Vedoucí / školitel: prof. RNDr. Tomáš Skopal, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 31.03.2010
Datum zadání: 31.03.2010
Datum a čas obhajoby: 30.05.2011 00:00
Datum odevzdání elektronické podoby:14.04.2011
Datum odevzdání tištěné podoby:15.04.2011
Datum proběhlé obhajoby: 30.05.2011
Oponenti: RNDr. David Hoksza, Ph.D.
 
 
 
Zásady pro vypracování
Implementujte vylepšenou indexační metodu pivot tables (PT), která využije předshlukování dat jinou indexační strukturou - M-stromem. Klasická metoda PT sestává ze dvou struktur - matice vzdáleností mezi pivoty a objekty databáze a samotného datového souboru. Implementace metody PT předpokládá uložení obou struktur v hlavní paměti. Cílem práce je metodu PT zobecnit spravováním datového souboru v sekundární paměti, a tím zvýšit její škálovatelnost. Zde ovšem nastává problém nadměrného zatížení disku v případě, kdy je během vyhledávání potřeba přistupovat na disk do datového souboru. Díky libovolnému uspořádání objektů v datovém souboru může docházet k mnoha čtením malých fragmentů z datového souboru, což v důsledku vede k neefektivnosti celé metody. Aby se minimalizoval počet přístupů na disk, modifikovaná varianta PT by měla před vlastním indexováním přeuspořádat vstupní datový soubor tak, aby následné vyhledávání v datovém souboru vedlo k menšímu počtu větších bloků a tím se minimalizovaly náklady na diskové operace. Jako metodu k přeuspořádání datového souboru použijte M-strom, který v tomto případě bude sloužit pouze jako shlukovací metoda. Součástí práce bude experimentální vyhodnocení výkonu klasické a modifikované varianty PT.
Seznam odborné literatury
[1] P. Zezula, G. Amato, V. Dohnal, M. Batko: Similarity Search - The Metric Space Approach, Springer, 2006
[2] Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435
[3] L. Micó, J. Oncina and E Vidal, A new version of the nearest neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing-time and memory requirements, Pattern Recogn. Lett. 15 (1994), pp. 9?17.
 
Univerzita Karlova | Informační systém UK