Seminář: Designing a Path–oriented Indexing Structure for a Graph Structured Data

In the context of the Semantic Web, rho–operators were proposed as a mean to explore complex relationships between entities. The problem of searching for the complex relationships can be modeled as the process of searching paths in a graph where the entities form vertices and the edges in the graph are represented by the relationships between the entities. Our effort introduces an indexing structure for path–oriented queries in the graph structured data called rho–index. The design of the rho–index is based on a graph partitioning technique called graph segmentation. Which is meant to represent the indexed graph in a simpler manor yet having similar properties as the original graph had. This presentation will discuss the theoretical design of the rho–index. It will also describe the transformation used to simplify the indexed graph and the structures used to represent the rho–index. Finally, the preliminary experimental results of the use of the indexing structure will be demonstrated.