Graph-based Structure Search
林学民教授是数据库理论方面的专家。今天的学术报告，林教授给我们简单介绍了他的研究团队在海量数据检索方面的研究成果。
在快带发展的互联网社会，越来越多的应用需要检索快速地检索基于图结构的海量数据。比如近两三年兴起的，我们非常熟悉的社交网络。对于图的结构化检索是一个NPC问题。海量的数据规模使得问题变得非常的棘手。我搜索了一些资料也没搞清楚什么叫NPC问题。我简单地理解，是当问题的规模变得越来越大时，就不能确定是否能在确定的时间内求出解。
林教授先简单地提到对图的研究方向大致分Mining Graphs,和Quering Graphs。Mining Graphs方面有Frequent Patterns, structure Similarityies, clustering, Ranking, classification。Prof. Lin的团队主要做了Structure Similarities方面的一些研究。对于Querying Graphs，又大致分为Readibility, Connectivity between two nodes, substructure search, shortest paths, strings。Prof. Lin话：对于shortest path，理论上求解很simple，但是应用到大量数据的时候，就要做很多工作。比如要做非常高效的索引。对于strings，一个很长的text可以看成一个长string。比于现在的internet搜索引擎，要解决区分互联网上太多冗余数据的问题，就属于这方面的研究。我知道搜索引擎是鼓励原创的，会给原创的页面比较高的page rank。针对这点，black hat SEO就会搞伪原创，怎样让搜索引擎快速区分出真正的原创内容呢？应该也属于这方面的课题吧。
林教授开始讲他的科研团队的第一个贡献。这个contribution是解决了关于图与图之间包含的问题。问题描述为：给出一个Data Graph和一个Query Graph，要在一个规模非常大的Data Graph里面找到这个Query Graph。林教授介绍了这个过程中的Filtering和Verification算法简要思路。对于不懂学术的我，这部分真是相当地难以理解啊！！！设D是要处理的图。First index a set F of features from D。对于任意f属于F, 求f的超图。索引的算法思路是。如果q是一个frequent subgraph,则 1. 如果q已经被索引，则返回q的超图。2.如果q是一个超图，次q被索引了，不需要给次q的超图做verification。如果q不是一个frequent subgraph的情况下，验证受制于sigmal|D|。林教授认为这个求解过程的主要开销在verification阶段。他们的团队就是把这个cost显著降了一下，而且思路非常地clear和simple。他总结了三条经验： 1. Access infrequent labels as early as possible. 2. Retain connectivity。 3. Effectively use degree information.
The second contribution of Prof. Lin is to put the the theoretic algorithm into practice.有两个问题，一个是query graph被data graph包含(contained)，另一个是query graph包含了data graph.林教授的团队的最结成果比已经发表了论文的另一个科研团队的成果的速度要快了一个数量级。Prof. Lin的语气显得有些遗憾，他们的思路是正确的，实现的效率也很高，但是时间上慢了小小。
http://ykyi.net zausiu's blog
发言队段，研究这个方向的甘同学问了非常专业的问题，我不懂啊！还有一位信科院的研一同学问到了留学的问题，Prof. Lin说他要最top的学生，非常地talented，非常地diligent, 非常地good at algorithm，还要有非常好的practical ability。朝红阳教授向林教授打听有没有做图象search方面的大牛。
学术报告好难啊！我想听工程类的报告。但都是academic report啊！
//////////////////
Topic:
Graph-based Structure Search
Speaker:
Prof. Xuemin Lin
School of Computer Science and Enmgineering,University of New South Wales
and
School of Software ,Eastern China Normal University
Abstract:
Recent years have witnessed an emergence of graph-based applications that strongly demand efficient processing of graph-based queries and searches.
In many real applications such as chem- and bio-informatics, road neworks, social networks, etc., efficiently and effectively conducting structure search on graphs is a key.
The problem of structure search on graphs and its variants are NP-complete. The presence of a large number of graphs makes the problem computationally more intractable.
In this talk, I will introduce recent techniques in graph structure search with the focus on our recent work published in SIGMOD, VLDB, ICDE, etc. My talk will cover the problems of substructure search, superstructure search, and substructure similarity search.
Brief Bio:
林学民，新南威尔士大学大学计算机科学及工程学院教授，数据库研究实验室主任。自2009年4月起，在华东师范大学担任兼职教授，2010年入选国家第四批千人计划学者，2011年6月起受聘于华东师范大学软件学院千人学者。生于上海市，1984年毕业于复旦大学数学系，1992年在昆士兰大学获得博士学位。长期从事数据库理论、算法与技术研究，包括空间数据、不确定数据、流数据、图数据等领域。近年来在数据库领域顶级国际学术会议及顶级杂志上共发表了70余篇学术论文；累计在数据库和算法领域重要的国际学术会议和国际学术期刊发表并录用了170余篇论文，其中10篇国际会议优秀论文，包括ICDE'07上的优秀学生论文奖 (best student paper award) ICDE'10上的优秀论文(one of the best papers) , 及SIGMOD'11 上的优秀论文(one of the best papers)。他目前的研究兴趣是海量数据的处理，包括图数据、时空数据、字符串数据、不确定数据等。学民先后在4th Australasian Theory Symposium (CATS'98), 6th International Computing and Combintorics Conference (COCOON2000), 6th Asia Pacific Web Conference (APweb04), the joint conference of 9th Asia Web Conference and 8th Web-Age Information Management Conference (APweb/WAIM2007), 和 19th and 20th Australasian Database Conference (ADC08, ADC09) 担任会议程序委员会主席，在14th International Conference on Database Systems for Advanced Applications (DASFAA09) 上担任大会主席。目前他是ACM TODS的编委。
Presided by
Prof. Jianlin Feng
Date and Venue
Dec 21, 2011(Wed.) 14：00-15：00
Lecture Theater A101, School of Software, Sun Yat-sen University