Abstract:

Graph is a general data structure for modeling in varies of fields. With the development of information and network technology, it is widely applied for representing relationship between entities. In this way, most valuable information is hidden in entities. So as to mine the hidden information in graph, related researches on this topic are becoming popular. The key to solve the problem is how to efficiently search on graph. In the graph database, there are two kinds of graph data sets: Single Graph and Graphs. However, it is time consuming in searching either Single Graph or Graphs. Thus, graph indexing is proposed to be a promising way to minimize the search space on graph in order to speed up graph search algorithms. This paper categorizes graph search into subgraph search and supergraph search.They are subdivided into smaller categories in terms of selected graph structure in building graph indexing. Meanwhile, the paper describes graph indexing building methods and detailed explanation on typical graph indexing. It compares kinds of graph indexing and analyzes their specific applications. At last, it discusses the development trend of graph indexing.

Key words: graph indexing; graph search; feature; subgraph; supergraph