SimG: A Semantic based Graph Similarity Search Engine

RDF knowledge graphs have received more attention in recent years. Many graph similarity search approaches are proposed to help users get the desired knowledge. However, few of them consider storage architecture and semantic similarity search together. We believe that a complete query engine requires not only an efficient search approach, but also a reliable storage architecture to support. In this paper, we design a semantic-based graph similarity search engine SimG with carefully designed architecture and data structures over an RDF Knowledge graph, which can quickly get the best k answers even given a simplified queries (e.g., Basic Graph Pattern (BGP)) by users. The outstanding features of SimG are as follows: (1) To improve RDF data management efficiency and reduce storage overhead, we first divide the RDF knowledge graph into multiple topic graphs based on the type similarity model. Then we store these topic graphs in a distributed manner(e.g., all topic-graphs are managed and maintained independently). (2) In order to manage topic graphs efficiently, we utilize the adjacency list as the fundamental data structure to store each topic graph. Moreover, we design a skip list based index to accelerate the data accessing. On the top of this topic graph storage, we implement several basic APIs such as access, add, delete and update to support the following semantic query approach. (3) The semantic similarity query module is deployed on the topic graph storage, which returns top-k answers by considering the semantic feature based on the APIs implemented above. Finally, extensive experiments on our query algorithm and storage architecture confirm the effectiveness and efficiency of SimG.