Mining, Indexing, and Searching Graphs in Large Data Sets

author: Jiawei Han, Department of Computer Science, University of Illinois at Urbana-Champaign
published: Sept. 6, 2007,   recorded: August 2007,   views: 13997


Related Open Educational Resources

Related content

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.
Lecture popularity: You need to login to cast your vote.


Recent research on pattern discovery has progressed from mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. As a general data structure, graph can model complicated relations among data with wide applications in Web, social network analysis, and bioinformatics. However, mining and searching large graphs in graph databases is challenging due to the presence of an exponential number of frequent subgraphs. In this talk, we present our recent progress on developing efficient and scalable methods for mining and searching of graphs in large databases. We introduce gSpan and CloseGraph, two efficient methods for mining frequent graph patterns in graph databases. Then we introduce constraint-based graph mining methods. Further, we introduce a graph indexing method, gIndex, and a graph approximate searching method, grafil, both taking advantages of frequent graph mining to construct a compact but highly effective graph index and perform similarity search with such indexing structures. These methods not only facilitate mining and querying graph patterns in massive datasets but also claim broad applications in other fields, including DB/OS systems and software engineering.

See Also:

Download slides icon Download slides: mlg07_han_jiawei.ppt (3.8┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Ed Garcia, February 22, 2008 at 5:05 p.m.:

At the same time VideoLectures is a great initiative,
it is frustrating...
Simply I don't have a full and pleasure experience to watch any video over there...
Although this ones seems great, interesting,
and it surely is, but
it freeze for 3 to 15 seconds all the time... from here where I am: Brazil!
And you don't give me an option to upload it.
I'm really bored because I'd like and need to watch that...

Thank you.

Write your own review or comment:

make sure you have javascript enabled or clear this field: