Correlation Search in Graph Databases

author: Yiping Ke, The Hong Kong University of Science and Technology
published: Aug. 14, 2007,   recorded: August 2007,   views: 2012
Categories
You might be experiencing some problems with Your Video player.

Slides

0:03 Slides Correlation Search in Graph Databases Outline Introduction pt 1 Introduction pt 2 Introduction - Motivation pt 1 Introduction - Motivation pt 2 Introduction - Motivation pt 3 Introduction - Motivation pt 4 Introduction - Motivation pt 5 Introduction - Correlation Search in Graph Databases pt 1 Introduction - Correlation Search in Graph Databases pt 2 Introduction - Correlation Search in Graph Databases pt 3 Introduction - Correlation Search in Graph Databases pt 4 Introduction - Contributions pt 1 Introduction - Contributions pt 2 Problem Definition - Correlation Measure pt 1 Problem Definition - Correlation Measure pt 2 Problem Definition - Correlation Measure pt 3 Problem Definition Solution - Candidate Generation pt 1 Solution - Candidate Generation pt 2 Solution - Candidate Generation pt 3 Solution - Candidate Generation (cont’) pt 1 Solution - Candidate Generation (cont’) pt 2 Solution - Candidate Generation (cont’) pt 3 Solution - Candidate Generation (cont’) pt 4 Solution - Heuristic Rules pt 1 Solution - Heuristic Rules pt 2 Solution - CGSearch Algorithm Performance Evaluation Effect of Candidate Generation when Varying Query Support Effect of Graph Size Conclusions Thank You

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Description

Correlation mining has gained great success in many application domains for its ability to capture the underlying dependency between objects. However, the research of correlation mining from graph databases is still lacking despite the fact that graph data, especially in various scientific domains, proliferate in recent years. In this paper, we propose a new problem of correlation mining from graph databases, called Correlated Graph Search (CGS). CGS adopts Pearson’s correlation coefficient as a correlation measure to take into consideration the occurrence distributions of graphs. However, the problem poses significant challenges, since every subgraph of a graph in the database is a candidate but the number of subgraphs is exponential. We derive two necessary conditions which set bounds on the occurrence probability of a candidate in the database. With this result, we design an efficient algorithm that operates on a much smaller projected database and thus we are able to obtain a significantly smaller set of candidates. To further improve the efficiency, we develop three heuristic rules and apply them on the candidate set to further reduce the search space. Our extensive experiments demonstrate the effectiveness of our method on candidate reduction. The results also justify the efficiency of our algorithm in mining correlations from large real and synthetic datasets.