听了林学民教授的一个学术报告

                  Graph-based Structure Search

林学民教授是数据库理论方面的专家。今天的学术报告,林教授给我们简单介绍了他的研究团队在海量数据检索方面的研究成果。

在快带发展的互联网社会,越来越多的应用需要检索快速地检索基于图结构的海量数据。比如近两三年兴起的,我们非常熟悉的社交网络。对于图的结构化检索是一个NPC问题。海量的数据规模使得问题变得非常的棘手。我搜索了一些资料也没搞清楚什么叫NPC问题。我简单地理解,是当问题的规模变得越来越大时,就不能确定是否能在确定的时间内求出解。

林教授先简单地提到对图的研究方向大致分Mining Graphs,Quering GraphsMining Graphs方面有Frequent Patterns, structure Similarityies, clustering, Ranking, classificationProf. Lin的团队主要做了Structure Similarities方面的一些研究。对于Querying Graphs,又大致分为Readibility, Connectivity between two nodes, substructure search, shortest paths, stringsProf. Lin话:对于shortest path,理论上求解很simple,但是应用到大量数据的时候,就要做很多工作。比如要做非常高效的索引。对于strings,一个很长的text可以看成一个长string。比于现在的internet搜索引擎,要解决区分互联网上太多冗余数据的问题,就属于这方面的研究。我知道搜索引擎是鼓励原创的,会给原创的页面比较高的page rank。针对这点,black hat SEO就会搞伪原创,怎样让搜索引擎快速区分出真正的原创内容呢?应该也属于这方面的课题吧。

林教授开始讲他的科研团队的第一个贡献。这个contribution是解决了关于图与图之间包含的问题。问题描述为:给出一个Data Graph和一个Query Graph,要在一个规模非常大的Data Graph里面找到这个Query Graph。林教授介绍了这个过程中的FilteringVerification算法简要思路。对于不懂学术的我,这部分真是相当地难以理解啊!!!设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显著降了一下,而且思路非常地clearsimple。他总结了三条经验: 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 graphdata 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

冬大过年!无痛终结2011年.展望2012

写在冬至日,总结2011展望2012。冬大过年是广东的俗语。无痛终结是因为人心态早已看得化(开)。
首先:在无比苦逼的11年里,最大的贡献就是返校读书了。基本上确定可以了结本科毕业时被取消学位的心愿。
其次工作上没有什么好说的。在东莞光大集团工作了半年,不能说辛苦也不算闲。工作上没学到什么东东,没明显地进步。在此谢谢赵经理了,如果我有赵经理的硬件水平我就笑哈哈哈哈。以识了几位有意思的同事。
感情上则一如既往地Fail, Fail, Fail 。。。完全木有信心了。哥爱无力了。到了年尾心态竟变得更无所谓,该怎样就怎样吧。只是让家人操心了,对不起啊,尽力了啊。奶奶,对不起啊。也想让你开心的。哎!想起过年回家要去那么多亲戚拜年,555,拜托你们不要问不要问吖。
最后讲讲返校后的生活。在中大的生活第一学期课程非常多,非常忙。我还有我的plan要投入很多时间。时间无论如何不够用!同学关系远没本科时紧密。可能我的心态跟刚毕业的后生仔们相差甚远吧。写到这里,想起今年国庆时去了其它地方没有参加强强和敏的婚礼。唉!什么时候去江苏再给我机会补偿好吗。我做人是越来越失败了,完全是不分好坏敌我的混乱!
2012年是世界的最后一年。可恶的地球人,觉悟吧!
以前每年年尾都会许好多愿望。结果第二年能实现的却渺渺无几。反正都2012了,哥的愿望就务实一点好吧。维护世界和平的任务还是不要勉强啦!
明年必须在寒假结束前看完Unix网络编程.
通过六月的BEC高级考试。
全年选择性的读完Essential Linux Device Drivers和Understanding linux Kernel.
上半年看paper,形成写论文的思路。下半年动手写论文。
下半年拿到offer。银行?民航?其它国企?还是互联网公司抑或其它什么公司?…
感情的事务不设定目标。苦逼的技术宅男果断必然无解!