文档介绍：Instructor: ZOU’ lei
******@.
北京大学计算机科学技术研究所
Institute puter Science and Technology of Peking University
Graph Data Management
1
Outline
Applications and Challenges of Graph Data
Exiting Graph Database Systems
About the course
2
Outline
Applications and Challenges of Graph Data Management
Exiting Graph Database Systems
About the course
3
Graph Data
4
(a) work
(b) work
Some Challenges in Large Graph Data Management
An Example:
Considering a SNS website, there are more than 1 billion active users.
Query:
I want to know whether “Tom is a friend of Jack, or a friend of his friends…?”
Possible Solutions:
(Storage) Store the connections between individuals in a relational table
(Query) Perform Self-join Recursively….
5
Some Challenges in Large Graph Data Management
6
recursive queries
Network Motifs: Simple Building Blocks works (R. Milo, et al.***@SCIENCE03)
7
Network Motifs: Simple Building Blocks works (R. Milo, et al.***@SCIENCE03)
Network motifs are patterns (sub-graphs) that recur within work much more often than expected at random. Network motifs always correspond to some functional patterns in works.
Questions:
How to find such motifs efficiently ?
Given a motif, how to find all embeddings of this motif efficiently?
8
01 December 2017
9
Frequent Subgraph Pattern Mining
(A)
(B)
(C)
Graph Dataset
Frequent Patterns
(min support is 2)
(1)
(2)
Subgraph Search
10
query graph
graph database
Query:
pounds contain “benzene ring”?