Tato disertační práce se zabývá problematikou indexačních
technik určených pro efektivní vyhledávání komplexních vztahů
mezi entitami v grafově strukturovaných datech. Součástí této
práce je návrh struktury pro vyhodnocování speciálního typu
operátoru pro dotazy na všechny cesty do určité délky ležící
mezi dvojicí zkoumaných vrcholů v indexovaném grafu. Tento typ
dotazů nazýváme rho-path dotazy. Tuto strukturu jsme porovnali
s mnoha přístupy, které se jevily jako vhodné pro řešení tohoto
problému. Provedli jsme také mnohé experimenty za účelem
ověření vlastností této struktury.

Navrhovaná struktura je založena na metodě postupného
zjednodušování indexovaného grafu, kterou jsme nazvali grafovou
segmentací. Použitím rekurzivního procesu grafové segmentace je
získána více-úrovňová stromová indexační struktura. Každá
úroveň tohoto stromu představuje jeden zjednodušený graf a
každý uzel potom matici cest popisující jednotlivé grafové
segmenty na této úrovni. Součástí návrhu je i algoritmus určený
pro vyhodnocení rho-path dotazů, který využívá tento rhoIndex. 

Experimenty uvedené v této práci jsou provedeny na syntetických
náhodných grafech. Tyto grafy byly vygenerovány použitím
vlastního inkrementálního algoritmu. Grafy představují
nejobecnější případ pro studování vlastností rhoIndexu, protože
nemají žádnou uspořádanější strukturu. Přesto naše práce
zahrnuje i sadu experimentů vyhodnocených na grafu
představující data z reálného života a to citačního grafu
sestávajícího se z 30 000 vědeckých publikací získaných z
databáze CiteSeer. Tato část disertační práce také navrhuje
nové přístupy k získávání informací o důležitých vrcholech –
publikacích v citačním grafu ovlivňovaných uživatelovým
předdefinovaným kontextem.