Indexing Graph Structured Data - Bartoň, Stanislav, 1979- (2007)
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.