Indexing Graph Structured Data
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ží...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2007
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/608/fi_d/ |
| Shrnutí: | 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. This Ph.D. thesis concerns the problem of indexing techniques towards efficient discovery of complex relationships among entities in graph structured data. We propose a novel structure for evaluation of special type of operator denoting queries for all paths to a certain limiting length lying between a pair of inspected vertices in the indexed graph, rho-path operator queries. We have compared it to various approaches suitable for this task and conducted numerous experiments to verify its properties. The proposed approach is based on a graph simplification method that we call graph segmentation. Using the recursive process of the graph segmentation a multilevel tree-like indexing structure called rhoIndex is acquired. In this tree, each level represents a simplified graph and each node a path type matrix describing the particular graph segment. An algorithm concerning the rhopath queries using rhoIndex is proposed and evaluated. The experiments are conducted on synthetic randomly gen. |
|---|---|
| Popis jednotky: | Vedoucí práce: Pavel Zezula. |
| Fyzický popis: | vii, 149 s. |