velikost textu

Tree-based indexing methods for similarity search in metric and nonmetric spaces

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Tree-based indexing methods for similarity search in metric and nonmetric spaces
Název v češtině:
Stromové indexační metody pro podobnostní vyhledávání v metrických a nemetrických prostorech
Typ:
Disertační práce
Autor:
RNDr. Jakub Lokoč, Ph.D.
Školitel:
doc. RNDr. Tomáš Skopal, Ph.D.
Oponenti:
RNDr. Vlastislav Dohnal, Ph.D.
Prof. Marco Patella, Ph.D.
Id práce:
44747
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra softwarového inženýrství (32-KSI)
Program studia:
Informatika (P1801)
Obor studia:
Softwarové systémy (4I2)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
3. 9. 2010
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Abstrakt:
M-strom je dnes již klasická indexační metoda používaná pro efektivní podobnostní vyhledávání v metrických prostorech. Ačkoliv M-strom již nepatří mezi nejnovější metody, věříme, že stále nabízí zatím neobjevený poteciál. V této práce sr proto zaměřujeme na způsoby, jak vylepšit jeho původní algoritmy a strukturu. Abychom umožnili rychlejší zpracování dtazů pomocí M-stromu, navrhli jsme několik nových metod jeho konstrukce (i paralelních), které vedou k vytváření kompaktnějších metrických hierarchií a přitom nejsou extrémně drahé. Dále jsme ukázali snadný způsob, jak rozšířit M-strom na novou indexační metodu NM-strom, která slouží k efektivnímu nemetrickému podonostnímu vyhledávání za pomocí algoritmu TriGen. Všechna tato experimentálně ověřená vyplepšení prokazují, že můžeme M-strom stále ještě považovat za důležitou dynamickou metrickou přístupovou metodu vhodnou pro správu rozsáhlých kolekcí nestrukturovaných dat. Všechna prezentovaná vylepšení mohou být navíc implementována do následníků M-stromu (např. do PM-stromu), což otevírá dveře pro další výzkum v této oblasti.
Abstract v angličtině:
The M-tree is a well-known indexing method enabling efficient similarity search in metric spaces. Although the M-tree is an aging method nowadays, we believe it still offers an undiscovered potential. We present several approaches and directions that show how the original M-tree algorithms and structure can be improved. To allow more efficient query processing by the M-tree, we propose several new methods of (parallel) M-tree construction that achieve more compact M-tree hierarchies and preserve acceptable construction cost. We also demonstrate that the M-tree can be simply extended to a new indexing method – the NM-tree, which allows efficient nonmetric similarity search by use of the TriGen algorithm. All these experimentally verified improvements show that the M-tree can still be regarded as an important dynamic metric access method suitable for management of large collections of unstructured data. Moreover, all the improvements can be further adopted by M-tree descendants (e.g. the PM-tree), so that the results presented in this thesis open the door for future research in this area.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Jakub Lokoč, Ph.D. 1.5 MB
Stáhnout Abstrakt v českém jazyce RNDr. Jakub Lokoč, Ph.D. 80 kB
Stáhnout Abstrakt anglicky RNDr. Jakub Lokoč, Ph.D. 80 kB
Stáhnout Posudek vedoucího doc. RNDr. Tomáš Skopal, Ph.D. 74 kB
Stáhnout Posudek oponenta RNDr. Vlastislav Dohnal, Ph.D. 133 kB
Stáhnout Posudek oponenta Prof. Marco Patella, Ph.D. 97 kB
Stáhnout Záznam o průběhu obhajoby 44 kB