首页

来自Data Management Lab
172.31.104.89讨论2016年10月26日 (三) 14:45的版本

(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)
跳转至: 导航搜索
数据管理研究室从属于北京大学计算机科学技术研究所,负责人为邹磊 老师。研究所目前的研究工作以海量图数据管理为主。 海量图数据管理主要研究如何存储和检索基于RDF(统一资源描述框架)模型的海量语义数据; 图流数据分析、大规模分布式图数据库引擎的研发及图数据挖掘技术的应用;以及如何利用新硬件技术来提高图计算和图查询的性能。

新闻

  • [2017-09-28]李友焕关于数据流上进行最长上升子序列(LIS)计算的论文(Longest Increasing Subsequence Computation over Streaming Sequences)被TKDE 2017录用。这篇论文是之前李友焕发表在VLDB2017的LIS计算论文的扩展。这篇论文仍是围绕更新代价和空间代价均为线性的四邻链表数据结构对数据流下LIS计算的支持。核心的扩展内容在于四邻链表对已知的所有特征限制的LIS计算的高效支撑。在之前VLDB的工作中,四邻链表能够对极值上升差和极值权重的带限制LIS计算提供高效的支持,而在TKDE的工作中,我们一方面考虑了极值宽度的LIS计算,其中宽度定义为LIS的首尾元素的位置距离,毕竟在趋势分析中,对宽度的限制能够体现对趋势变化的紧凑性的需求;另一方面我们针对范围限制和坡度限制的LIS计算在四邻链表上设计了高效的计算算法,其中范围限制是要求LIS每两个连续元素之间的位置距离和值差都在给定的范围内,而坡度限制则是要求LIS每两个相邻元素值差相对距离的商(即斜率)必须不小于给定的一个参数m。针对范围和坡度限制的LIS计算与之前的极值计算有很大的区别,但在四邻链表上我们设计了很巧妙高效的计算算法,在理论结果优于已有工作的同时,还在多个数据集上的实验验证了我们算法的高效性。
  • [2017-08-05]韩硕关于使用图拼接方法来进行RDF图上关键字查询的论文(Keyword Search on RDF Graphs — A Query Graph Assembly Approach)被CIKM 2017录用。关键词检索为普通用户提供了一种简单易用的查询RDF数据的方式。本文的研究内容是如何将用户输入的关键词查询序列,高效地转化为一张能够准确表达用户查询意图的查询图。基于用户输入的关键词序列,我们首先将其划分标注为若干个语义单元,映射到一些查询图构建元素上,即一些实体/类别顶点和关系边。然后我们形式化地定义了查询图拼接(QGA)问题。我们在理论上证明了QGA问题是NP完全的。尽管如此,我们提出了一个基于二部图匹配模型的最佳优先搜索算法,并设计了一些启发式的剪枝下界。这一算法的时间复杂度并不依赖于RDF图的规模,从而保证了我们的系统具有良好的可扩展性,能够高效地应对真实的大规模RDF数据。
  • [2017-05-19]在2017年的SIGMOD编程竞赛中,我们的队伍gStreamPKU在100余只参赛队中脱颖而出并获得最终提名奖(前5名)。SIGMOD编程竞赛每年举办一次,由本科生或者研究生以组队的形式参加,尝试解决数据库领域中的一些富有挑战性的问题。今年的任务是在文档上进行多字符串查询匹配问题,并且字符串集合是动态更新的,详细信息请参见http://sigmod17contest.athenarc.gr。值得一提的是,在去年的竞赛中我们同样也获得了最终提名。
  • [2017-04-10]郑卫国的论文(Efficient SimRank-based Similarity Join)被ACM Transactions on Database Systems (ACM TODS)所录用。图模型已经被广泛用于建模实际应用中的复杂数据,回答图数据上的顶点集合的连接查询是一个十分有意义的研究任务,它可以用来辅助在社交网络上进行朋友推荐或链接预测。本文采用SimRank作为衡量两个顶点之间的相似度量,具体而言,给定两个顶点集合,计算出其中SimRank分值高于阈值的顶点对。为了提高计算效率,本文提出了一个基于最短路径计算SimRank上界来过滤顶点对的方法。此外,本文提出了一个有效的索引(h-go cover+)来计算单个顶点对之间的SimRank,即只需要物化一小部分的顶点对的SimRank,基于此任何顶点对之间的SimRank可以很容易地计算出来。为了计算这个索引,我提出了一个不需要构建顶点对图的方法,从而可以支持规模很大的图数据。在真实数据和人工数据上的大量实验验证了方法的有效性。
  • [2017-03-28]彭鹏的论文(Answering top-K query combined keywords and structural queries on RDF graphs)在Information System发表。尽管SPARQL作为RDF模型的主要查询语言已经被广泛地应用在各个领域,但是在实际应用中很多查询需求还是不能很容易地被SAPRQL语言所描述;同时,关键词检索作为信息检索领域常用检索手段虽然常用,但是也面临着低准确率的问题。为了将SPARQL查询和关键词查询的优点结合起来,本文提出了一个混合查询模式(SPARQL- Keyword (SK) 查询)。为了高效处理SK查询,本文分别提出了一个基于结构的索引机制和基于距离的索引机制。本文通过在三个真实的RDF数据上的实验验证了我们方法的有效性和效率。
  • [2017-03-08]张欣勃的论文(Improving the Precision of RDF Question/Answering Systems— A Why Not Approach)被WWW2017收录为poster。这篇论文提出了一种在Q/A系统中基于用户的反馈而自学习地修正原始查询图的方法。该方法能有效地完善原始查询,使得查询得到的答案排除错误答案,而涵盖遗失答案。另外,对于Q/A系统错误的修改被应用于一种规则挖掘算法,以自动地修正已有的映射词典,很好地解决了Q/A系统中存在的实体链接错误和关系映射错误的问题,从而提高Q/A系统今后的理解力和查询的准确性。
  • 更多...

通知

  • 实验室招聘信息详见左侧导航栏。
  • 常年招收北京地区的高校的优秀本科生来实验室实习,详见实习生招聘

近期会议

  • WWW 2017
  • ICDE 2017
  • SIGMOD 2017第二轮