MinG: An efficient algorithm to mine graphs for semantic associations
Zohaib Hassan, Muhammad Abdul Qadir · 2011
Data in semantic web is modelled in terms of directed labelled graph. Vertices of that graph represent entities and edges represent relationships between those entities. Semantic web allows the discovery of relations between entities using the ρ-operators. In this paper an algorithm to answer ρ-operators, that is, to find all paths between any two nodes from a graph is proposed. The algorithm is based on ρ-index, an indexing scheme presented in the PhD thesis of Barton. Our algorithm reduces the computational and space complexity of indexing by not creating a special type of adjacency matrix called Path Type Matrix at each level of indexing which Barton's algorithm did. We only need Path Type Matrices at first and last level of indexing. Thus if an indexing has 100 levels, Barton requires Path Type Matrices at each level and we only require Path Type Matrices at level 1 and level 100.