新闻

来自Data Management Lab
跳转至: 导航搜索
  • [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系统今后的理解力和查询的准确性。
  • [2016-11-17]杨硕的论文(Efficiently Answering Technical Questions — A Knowledge Graph Approach)被人工智能会议AAAI 2017接收。在这篇论文中,针对微软产品的技术问题,我们提出了一个新颖的基于语义图的问题理解的方法。首先,我们构建了一种层次的语义图的自动构建方法,语义图中包含了丰富的技术领域的信息,用来理解一个问题。第二部分,我们使用历史的用户问题,将构建的语义图和技术文档连接起来。在检索阶段,我们首先使用问题导向的方法来挑选出查询候选,最后使用随机游走的方法,来对技术文档重新排序,为了加快查询的效率,我们在语义图上构建了索引,并使用基于索引的随机游走算法来支持在线查询。
  • [2016-10-17]彭鹏关于分布式环境下RDF数据上的SPARQL查询处理的论文(“Processing SPARQL queries over distributed RDF graphs”)被VLDB 2016录用。论文针对不能进行数据划分的分布式RDF数据库系统提出了一个基于局部计算的查询处理框架。这个框架中,系统中每台机器根据自身上所存储的RDF数据计算出整个SPARQL查询的局部匹配。所找出的局部匹配被定义为本地局部匹配。基于本地局部匹配的定义,实现了一个高效的本地局部匹配求解算法。然后,所有被找出的局部匹配被归并起来并通过连接操作合并成最终匹配。因为这一框架是处理整个SPARQL查询而无需进行查询分解,所以这一方法是独立于数据划分的。而且根据我们定义所找出的本地局部匹配能保证计算过程中系统所产生中间结果涉及的点和边的数量是最少的。
  • [2016-10-17]李友焕的论文(Computing Longest Increasing Subsequences over Sequential Data Streams)被VLDB录用。论文内容是关于数据流模型下最长上升子序列的挖掘计算,提出了支持在数据流模型下快速进行最长上升子序列的枚举和特征枚举的四邻链表数据结构。