Similarity Search on a Very Large Scale
David Novák · 2008
Koncept podobnosti je vysledovatelný v různých oblastech informatiky i jiných oborů. Jednou z nejvýraznějsich aplikaci tohoto konceptu je podobnostni vyhledavani. Toto vyhledavaci paradigma se stalo důležitým zejmena diky soucasnemu fenomenu tzv. datove exploze, který můžeme pozorovat ve dvou směrech: jednak v soucasnosti velmi rychle stoupaji objemy produkovaných dat a jednak se znatelně zvysuje rozmanitost vytvařených dat. Tato prace se zaměřuje pravě na problem efektivniho zpracovani velkých objemů dat na zakladě podobnosti. Data a podobnost modelujeme pomoci metrickeho prostoru, což je velmi univerzalni a pružný koncept. Představujeme M-Chord, novou distribuovanou datovou strukturu pro podobnostni vyhledavani v metrických prostorech. Architektura M-Chordu je založena na principu strukturovaných peer-to-peer (P2P) siti. Abychom spravně identifikovaly silne a slabe stranky existujicich přistupů k tomuto problemu, studujeme nejdřive oblast metrickeho indexovani a oblast P2P siti. Výkon M-Chordu je podrobně analyzovan na zakladě serie realných experimenů, jejichž výsledky jsou konfrontovany s ostatnimi řesenimi. Výsledky ukazuji, že M-Chord je se svými soupeři v některých směrech srovnatelný a v těch ostatnich je dokonce předci. Struktura M-Chord ma tu schopnost, že sdružuje podobna data blizko, což ma za důsledek lepsi prořezavani vyhledavaciho prostoru. Dale take použiva standardni P2P navigacni techniky, ktere maji stabilni komunikacni naklady. V dalsi casti prace představujeme LOBS, techniku pro vyrovnavani výpocetni zatěže mezi jednotlivými uzly sitě. Tento přistup je vhodný pro M-Chord i ostatni P2P podobnostni struktury. Výsledky experimentů ukazuji, že LOBS zlepsuje jak využivani zdrojů tak výkonost systemu. V posledni casti prace popisujeme prototypni aplikaci pro podobnostni vyhledavani v rozsahlých kolekcich digitalnich obrazků, ktera využiva M-Chord jako indexacni a vyhledavaci stroj. Tato aplikace demonstruje pružnost naseho přistupu tim, že urcuje podobnost pomoci jedinecne kombinace pěti MPEG-7 deskriptorů. Skalovatelnost systemu je prokazana tim, že indexujeme a prohledavame databazi padesati milionů obrazků, což je o jeden až dva řady vice než spravuje jakýkoli jiný soucasný system.