Research On Graph Search Based On Feature Index

With the development of modern information technology, the demand for complex objects modeling is on the rise. As a data structure of simulating the relationships between complex objects, graph becomes more important in data mining because it contains enriched mearnings and structures. Graph is now used in many fields such as chemical elements, social network, pattern matching, XML, etc. Graph search is a classical application in graph data set, searching for the users the data they want from the mass graph data. The main strategy used in graph search at present is to create an index-filter-select process with database. Therefore, this paper will focus on the structure and filtering of graph index.Firstly, this paper will introduce the graph related concepts, the different types of graph search algorithm and graph indexing mechanism. Then the existing algorithms will be analyzed in-depth and their advantages and disadvantages will be pointed out. Based on this this paper will analyze the whole process of graph search and each cost during the process, give the final strategy of figure inquires. These analyses provide a basis for further research of graph index.Secondly, this paper will put forward a new algorithm based on the in-depth analysis of the whole process and the cost of graph search. Algorithm generates features of frequent subgraph at first, decomposes it and validate it weather added into nodes of direct acyclic graph, adds the decomposed DFS code into hash table. This new algorithm shows great advantage in the runtime when it processing large graph set. It is also the basis of algorithm of graph search, index and filtering.Thirdly, this paper will put forward a filtering algorithm based on graph-feature index. It transfers the query of graph on relex edge to allowed maximum feature lose, employs the feature collection and hierarchical-layers to create the relationships between graph features, sorts the feature set.Finally, this paper will verify the new algorithm by experiment, comparing the results with the existing algorithms, particularly analyze the results, thus confirmed the correctness and excute efficiency of new algorithm.