A Survey on Graph Queries Processing: Techniques and Methods

摘要

Graphs are widely used to model complicated structures and link them with each other. Some of such structures are XML documents, social networks, and computer networks. Information and model extraction from graph databases is a graph mining process. Efficient query search in graph databases, known as query processing, is one of the heated debates in the field of graph mining. One of the query processing techniques is sequential search over the whole dataset and isomorphism test on all sub-graphs in the database, which is not an optimal technique as to response time and storage. This problem brought in the issues of indexing graph databases to improve query processing performance. As the method implies, part of the database where the answer is expected to be found there is pruned and the number of needed isomorphism tests decreases. It might not be easy to compare the methods and techniques of graph query techniques as different techniques have different objectives. For instance, similarity search techniques reduce query time, while they cannot compete with exact matching techniques as to accuracy and vice versa. Input data volume might be also effective on query time as with immense datasets, similarity search techniques are more preferred than exact matching techniques. The present study is a survey of graph query processing techniques with emphasis on similarity search and exact matching.