Font Size: a A A

Subgraph Query Process On Graph-Structure Data

Posted on:2012-10-07Degree:MasterType:Thesis
Country:ChinaCandidate:Y N ZhangFull Text:PDF
GTID:2218330362950408Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
The sub-graph queryretrieves all of the graphs in graph database that contain the query graph.This paper discussed sub-graph query problem from two different perspectives. The first problem is query processing on dynamic graph data. The other one is query processing on uncertain graph data.In this paper, we define dual-branches feature and code of graph. An iterative algorithm based on Dual-branches code is proposed to process sub-graph query. For efficiently filtering graph data in query processing, we design an index structure DBrIndex for dual -branches code. DBrIndex is built without frequent sub-graph miningand easy to maintainincrementally. Our query algorithm works well on dynamic graph data. The experiments shows that DBrIndex is smaller and easier to maintain than counterpart methods, and that DBrIndex can support high-efficiency sub-graph query processing.In this paper, we proposed the expectation sub-graph isomorphism matching and -βsub-graph isomorphism matching between uncertain graphs. The uncertainty of query graph represents user's expectation on the existence of variouselements in query graph. The expectation sub-graph isomorphism matching between uncertain graphs directly extends the definition ofsub-graph isomorphism matching between certain graphs. The -βsub-graph isomorphism matching evaluates the quality of matching between query pattern and data graph with two thresholds. This paper explained the semantic and properties of -βmatching, it also analyzed the probability meaning of -βmatching. We designed a search algorithm to solve the -βsub-graph isomorphism matching problem.
Keywords/Search Tags:Sub-graph Query, Query Processing, Index Structure, Uncertain Graph
PDF Full Text Request
Related items