Indexing Graph Structured Data
Stanislav Bartoň · 2007
Tato disertacni prace se zabýva problematikou indexacnich technik urcených pro efektivni vyhledavani komplexnich vztahů mezi entitami v grafově strukturovaných datech. Soucasti teto prace je navrh struktury pro vyhodnocovani specialniho typu operatoru pro dotazy na vsechny cesty do urcite delky ležici mezi dvojici zkoumaných vrcholů v indexovanem grafu. Tento typ dotazů nazývame rho-path dotazy. Tuto strukturu jsme porovnali s mnoha přistupy, ktere se jevily jako vhodne pro řeseni tohoto problemu. Provedli jsme take mnohe experimenty za ucelem ověřeni vlastnosti teto struktury. Navrhovana struktura je založena na metodě postupneho zjednodusovani indexovaneho grafu, kterou jsme nazvali grafovou segmentaci. Použitim rekurzivniho procesu grafove segmentace je ziskana vice-urovňova stromova indexacni struktura. Každa uroveň tohoto stromu představuje jeden zjednodusený graf a každý uzel potom matici cest popisujici jednotlive grafove segmenty na teto urovni. Soucasti navrhu je i algoritmus urcený pro vyhodnoceni rho-path dotazů, který využiva tento rhoIndex. Experimenty uvedene v teto praci jsou provedeny na syntetických nahodných grafech. Tyto grafy byly vygenerovany použitim vlastniho inkrementalniho algoritmu. Grafy představuji nejobecnějsi připad pro studovani vlastnosti rhoIndexu, protože nemaji žadnou uspořadanějsi strukturu. Přesto nase prace zahrnuje i sadu experimentů vyhodnocených na grafu představujici data z realneho života a to citacniho grafu sestavajiciho se z 30 000 vědeckých publikaci ziskaných z databaze CiteSeer. Tato cast disertacni prace take navrhuje nove přistupy k ziskavani informaci o důležitých vrcholech – publikacich v citacnim grafu ovlivňovaných uživatelovým předdefinovaným kontextem.