Font Size: a A A

Research On Graph Pattern Matching Method Based On Kinship Network

Posted on:2017-02-07Degree:MasterType:Thesis
Country:ChinaCandidate:H ZhangFull Text:PDF
GTID:2308330482985944Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Kinship network is a network which describes kinship and marriage relationship between people. With the increasing scale and complexity of data, it is a difficult problem how to find special pattern structure in the kinship network. Relational databases can’t meet the requirements of the complex relational queries. By contrast, Graph database has obvious advantages in certain areas such as data modeling, data management etc. Kinship structure querying is one kind of graph pattern matching in kinship network. Subgraph isomorphism method can’t match specific structure pattern because of missing semantic restrictions about the pattern graph.In this thesis, we use the graph modeling kinship network compared with relational model. We propose semantic restrictions graph pattern matching method by adding quantity and type restrictions on the nodes and relationships. We apply semantic restrictions graph pattern matching method in searching family structure in the kinship network with family data. We visualize and analysis the experiment result.(1) Modeling and storing kinship networks in graph database.In order to search the complex kinship network efficiently, we should store the data reasonably. In this thesis, we analyze the size and meaning of the kinship network and use property graph to describe the kinship network. Compared with relational model, we model the network in the graph model. We implement the data storage conversion from relational model to graph model. Experiment shows that the queries base on graph pattern is more neatly and more efficiently than relational queries as the relationship depth growing.(2)Semantic restrictions graph pattern matching method.Kinship structure querying is one kind of graph pattern matching in the kinship network. The graph pattern’s semantic expression is important in special structure pattern matching. In this thesis, we find out that subgraph isomorphism method can’t match specific structure pattern because of missing semantic restrictions about the pattern graph. So we propose the Semantic restrictions graph pattern matching method by adding quantity and type restrictions on the nodes and edges. We describe the matching rules and restrictions rules to achieve the special structure pattern matching. The restrictions let the pattern graph has richer expression meaning. Experiment shows validity and accuracy of the method.(3)Experiment about the query ability between graph model and relation model.We store the H province kinship network data both in relational database and graph database. To get the comparison in query method and query effectiveness, we use same size kinship network data to achieve the same query result. Experiment shows that the query efficiency in the graph model is better than the relational one.(4) Applying the Semantic restrictions graph pattern matching method to find family structure. To match the family structures we expand the kinship network by add family node and family relationships. We use the method in the specific type family pattern. By the rules of the semantic restrictions graph pattern, we match several family types in the expanded kindship network and analyze the result.
Keywords/Search Tags:kinship network, graph pattern matching, graph database, restrictions graph pattern
PDF Full Text Request
Related items