近日，南方科技大学计算机系唐博老师带领的数据库课题组在数据库领域取得一系列科研进展。该研究团队三项成果被数据库领域国际顶会ACM SIGMOD 2023长文接收。研究内容涉及到带权地形上最短路径查询算法、大规模图数据可视化技术和数据库查询优化器的基数估计技术。ACM SIGMOD会议关注数据库管理系统和数据管理技术的原理、技术和应用，是数据库领域具有最高学术地位的国际性学术会议。

1、EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface

在空间信息技术相关的问题中，地形表面的最短距离问题是一个非常重要的问题，是多种应用（如3D物体相似度查询、基于位置信息的推荐系统等）中必不可少的基本算子。

针对现有解决地形表面任意点间最短距离算法时延大和对大数据上处理难等问题，我们提出了基于索引的全新算法EAR-Oracle,它根据地形的几何特征，将其投影到二维平面并将其划分为若干网格。根据距离查询起止点的位置信息将距离查询分为两类：同一网格内距离查询和跨网格间的距离查询。针对同一网格内的距离查询，我们采用了在线算法来计算其最短距离。针对跨网格间的距离查询，EAR-Oracle根据地形的几何性质选取了少量地形节点建立了一个轻量的索引结构。借助该索引结构，实现用户给定的误差范围内高效计算有误差理论保证的近似最短距离。我们为EAR-Oracle的时间复杂度、空间复杂度、查询时间以及查询误差进行了详实的理论分析。我们的实验结果表明，与现有最先进的基于索引的算法相比，EAR-Oracle在索引建立时间上以及内存空间占用上有着两个数量级以上的提升。与现有最快的在线算法相比，EAR-Oracle在查询时间上有着一个数量级以上的提升。

图1. EAR-Oracle在unweighted terrain surface的对比实验结果

该研究工作第一作者是唐博老师指导的2019级硕士生黄博同学，该工作由南方科技大学数据库研究团队与香港理工大学Victor Junqiu Wei教授、香港科技大学Raymond Chi-Wing Wong教授合作完成。

2、Effective and Efficient PageRank-based Positioning for Graph Visualization

图可视化是许多现实应用中的重要组成部分，它使用户能够从复杂的数据中挖掘出重要的信息。图可视化的核心是节点距离度量，它决定了节点在屏幕上的放置方式。一个有利的节点距离度量应该能够反映节点之间的完整结构信息，并有效地优化视觉美学。然而，现有的距离度量因无法达到这些要求而产生较差可视化效果。此外，大多数现有度量在计算上效率低下，在可视化大型图时会导致较长的响应时间。为了克服这些缺陷，我们提出了如下图所示图可视化框架PPRviz。

图2. PPRviz可视化流程

PPRviz包含一种新的节点距离度量PDist，其通过利用个性化页面排名来实现图形可视化。此外，我们提出了一种有效的Tau-Push 算法，用于在单级和多级可视化设置下估计 PDist，其为估计精度和计算复杂性提供了重要的理论保证。大量实验表明，PPRviz在效率和有效性（包括审美标准和用户反馈）方面和12个真实数据集上，明显优于13个最先进的图可视化解决方案。特别地，PPRviz可以在一秒内以交互方式为十亿边图生成令人满意的可视化效果。

该研究工作的第一作者是唐博老师指导的2019级南方科技大学-新加坡国立大学联培博士张诗奇。该工作由南科大数据库课题组与香港浸会大学Renchi Yang教授，新加坡国立大学Xiaokui Xiao教授合作完成。

3、Speeding Up End-to-end Query Execution via Learning-based

Progressive Cardinality Estimation

基数估计器对数据库查询执行优化生成高质量执行计划至关重要。传统基数估计方法多基于直方图或抽样，预估准确度较低。AI for DB的思路提出用基于深度学习的模型实现基数估计。已有的基于学习的基数估计器可分为三类: data-driven, query-driven和hybrid。Data-driven和Hybrid方法具有较高的预测准确性，但预测时间消耗过高。Query-driven方法可较快完成预测，但准确度较低。然而，端到端的快速查询要求基数估计需同时满足高准确度和快速预测。

在这个工作中，我们提出基于学习并可渐进式优化的query-driven基数估计器。LPCE采用执行中再优化的思路，满足高准确度，轻量优化和执行中渐进优化估计的特点。LPCE由两个组件组成：1）LPCE-I作为初始基数估计优化模型，在查询执行前为查询优化服务从而帮助执行计划的初始生成；2）LPCE-R作为运行时基数估计再优化模型，在查询执行中从已执行的操作中学习经验，对剩余未执行的操作进行持续再优化基数估计，执行计划从而可动态调整到更优。LPCE集成在开源数据库系统PostgreSQL中，实验结果表明LPCE对多join查询端到端执行时间的显著加速。

 图3. LPCE解决方案架构图

该工作由南科大数据库课题组与香港理工大学Man Lung Yiu教授团队合作完成，第一作者香港理工大学王方博士在南方科技大学数据库课题组担任访问学生期间在唐博老师和晏潇老师指导下完成该工作。

上述研究工作得到了南方科技大学计算机科学与工程系、斯发基斯可信自主系统研究院、南科大-华为新型数据库技术联合创新研究中心的支持。

南方科技大学计算机科学与工程系