学院新闻

4月27日，中国人民大学高瓴人工智能学院师生两篇论文被ACM Transactions on Database Systems（TODS）期刊接收。TODS是数据库领域的顶级期刊，期刊主题包括存储和检索、交易管理、分布式和联合数据库、数据语义学、智能数据库等。TODS被中国计算机学会（CCF）推荐为A类国际期刊，该期刊每年在全世界范围内收录论文数目不超过30篇。

论文题目：Persistent Summaries

作者：曾恬静、魏哲巍、罗戈、易珂、杜小勇、文继荣

通讯作者：魏哲巍

论文概述：随着大数据时代的到来，如何将体量巨大的信息留存下来成为一大难题。持久化数据结构能够将所有的数据流更新过程都存储下来以应对数据流上的历史查询，但其空间复杂度线性于数据量，这是大多数应用无法接受的。流算法虽然在亚线性空间下存储数据，但无法做到保存历史数据。为此，本文提出了一种能够应对数据流上的历史查询的Persistent Summaries。Persistent Summaries利用Sketch/Summary存储数据流的当前信息，并通过PLA算法近似记录摘要中各计数器数值的变化，进而能够回答过去任意时刻的historical point query和historical heavy hitter query。本文通过理论分析证明了Persistent Summaries的算法正确性。值得一提的是，这是一个亚线性空间算法，并且是on-line的，非常适合迁移至应用程序上。

论文题目：Influence Maximization Revisited: Efficient Sampling with Bound Tightened.

作者：郭钦填、王思博、魏哲巍、Wenqing Lin、Jing Tang

论文概述：影响力最大化（Influence Maximalization）问题的目标在于寻找社交网络中最具影响力的k个节点，以使选出的节点可以尽可能多地影响到网络上的其它节点，这在广告投放、疫情预测等领域都有广泛应用。影响力最大化算法的核心步骤在于随机反向可达集（Reverse Reachable Set）的生成，其生成效率直接影响整个算法的时间消耗。本篇论文深入研究了反向可达集的生成效率，并且在独立级联模型（Independent-Cascade model）下提高了反向可达集生成算法的时间复杂度。进一步地，本文关注到反向可达集的大小对算法可扩展性的负面影响问题，不降低影响力最大化查询质量的前提下，成功减小了反向可达集的大小。