港科广数据科学与分析学域及港科大计算机科学与工程学系19篇论文入选数据库顶会ACM SIGMOD 2023

近期，增量学习在研究社区和工业界引起了广泛关注。一般来说，增量学习的目标是让机器学习的模型在学习新的数据集的同时保持对过去数据集的有效性。尽管增量学习最近取得了一定成功，但现有的工作主要假设即将到来的数据集和过去数据集共享相同的特征空间，即同质特征空间。他们采用一个特征提取器将不同的特征空间强制投影到一个空间中。然而，在现实场景中，这种假设很难成立。特别是在表格学习中，不同表格的输入属性会不断变化并产生异构的特征空间。因此，经典的增量学习模型的假设可能会影响它们的有效性。在本文中，我们提出了一种新的方法——基于异构特征空间的增量表格学习（ILEAHE）来解决这个问题。我们首先提出了特征提取器应该分解成共享提取器和特殊提取器的想法，以分别处理不同数据集之间的共享和特殊特征。其次，我们提出了一个新的测量并提高特殊提取器判别能力的方法。由此，两种提取器获取的特征可以被区分开来，其中特殊提取器将更加关注那些数据集特定的特征。我们通过实验进一步证明了ILEAHE的有效性。

获取空间降雨量准确分布是水文分析和自然灾害预警的重要任务。但是，现实中不可能在每个角落都安装雨量计获取数据。空间插值是根据可用的雨量计数据推断降雨分布的常用方法。然而，现有研究依靠一些不切实际的预设来捕捉空间相关性，限制了其在真实场景中的表现。为了解决这个问题，我们提出了SSIN，这是一种新颖的数据驱动的自监督学习框架，通过从历史观测数据中挖掘潜在的空间模式来计算降雨空间插值。受填空任务和BERT的启发，我们充分考虑了空间插值的特点，设计了基于Transformer架构的SpaFormer模型作为SSIN的核心。我们的主要思想是：通过随机掩码构建丰富的自监督信号，SpaFormer 可以学习原始数据的信息嵌入，然后根据降雨空间上下文自适应地对空间相关性进行建模。在两个真实世界的雨量计数据集上进行的大量实验表明，我们的方法优于最先进的解决方案。此外，我们将交通空间插值作为另一个用例来进一步探索我们的方法的性能，SpaFormer 在一个大型真实世界的交通数据集上实现了最佳性能，这进一步证实了我们方法的有效性和通用性。

给定一个无向图G，有效电阻r(s,t)测量G中节点对s，t的不相异性，这在现实世界的问题中得到了许多应用，例如推荐系统，组合优化，分子化学和电力网络。现有的成对有效电阻估计技术要么以近似保证实际效率，反之亦然。特别是，最先进的解决方案基于大量的蒙特卡罗随机游走，使其在实践中效率相当低下，尤其是在大型图上。

有鉴于此，本文首先提出了一种改进的蒙特卡罗方法AMC，该方法通过仔细的理论分析和自适应采样方案，在不降低理论精度保证的情况下减少了所需的随机游走的长度和数量。此外，我们开发了一种贪婪的方法GEER，它以优化和非平凡的方式将AMC与稀疏矩阵向量乘法相结合。与AMC相比，GEER提供了显着提高的实际效率，而不会影响其渐近性能和精度保证。在多个基准数据集上进行的大量实验表明，在达到相同精度时，GEER 在计算时间方面比现有技术快几个数量级。

相似性搜索在实际应用中越来越有用。本文重点介绍了任意度量空间下的内存相似性搜索，即距离查询和k最近邻（kNN）查询，其中唯一已知的信息是用于测量两个对象之间相似性的距离函数。尽管有大量工作对这个问题进行了研究，但现有解决方案的查询效率仍然不尽如人意。为了进一步提高查询效率，我们受到了树嵌入方法仅根据距离就可以将每个对象映射到的树的唯一叶子中的启发。与用于相似性搜索的现有嵌入技术（例如，Lipschitz 嵌入和透视映射）需要额外的多维索引来索引嵌入空间（例如，Lp 度量）不同，我们直接使用树模型来回答相似性搜索。这听起来很有希望，但设计树嵌入方法以实现快速的相似性搜索仍然具有挑战性。面对这个挑战，我们提出了一个名为LiteHST的新索引方法，它基于最流行的树嵌入方法（HST），并针对节点结构和存储方案中的相似性搜索进行了大量调整。我们提出了一种时间复杂度低于现有方法的构造算法，证明了LiteHST在距离界限内的最优性。基于这个新索引方法，我们还设计了能够大大减少距离计算数量的优化技术，从而缩短了运行时间。最后，大量的实验表明，我们的解决方案在查询效率方面远远优于最先进的现有方法。

随着来自不同存储库的图的数量的指数级增长，现在急需能够分析包含大量中小型数据图（例如化合物）的图数据库。尽管子图枚举和子图挖掘技术已经通过发掘一组子图结构的方式为图数据库提供了分析方法，但这些方法获取的子图通常最终具有相似或同质的拓扑，这在许多图应用场景中是不可取的。为了解决这一局限性，我们提出了 Top-k 多样化边模式发现问题，以检索一组覆盖数据库中最大边数的子图。为了快速地处理此类查询，我们提出了一个名为 TED 的通用且可扩展的框架，该框架保证了近似结果与最佳结果的近似比率。我们进一步开发了两个优化策略以提升表现。对真实世界数据集的实验研究表明，TED 优于传统技术。

动态图上的表示学习对于许多实际应用程序（如社交网络服务和推荐系统）至关重要。时态图神经网络（T-GNN）是强大的表示学习方法，在连续时间动态图上取得了显著的有效性。然而，T-GNN仍然具有很高的时间复杂度，它随着时间戳的数量上升线性增加，并随着模型深度加深呈指数增长，这导致它们无法扩展到大型动态图。为了解决这些局限性，我们提出了Orca，这是一种新颖的框架，它通过复杂的缓存和重用中间嵌入来加速T-GNN训练。我们在实际缓存限制下设计了名为 MRU 的最佳缓存替换算法。MRU 不仅通过最大化缓存命中数来提高训练 T-GNN 的速度，而且还通过避免保留和重用极其陈旧的嵌入来减少近似错误。同时，我们对复用方案引入的近似误差进行了深入的理论分析，并提供严格的收敛保证。大量的实验已经证明，Orca可以在最先进的基线上获得两个数量级的加速，同时在大型动态图上实现更高的精度。

图神经网络已被广泛用于学习现实世界静态图的节点表示。通常，它们通过递归聚合邻居的信息来学习节点表示。然而，许多应用场景中的图是动态的，随着连续的图事件（如节点特征和图结构更新）演变，图上节点的表示会被影响，所以需要对节点的表示进行更新。目前，由于下层任务实时性的需求，如何在连续图事件下高效可靠地更新节点表示仍然是一个尚未完全解决的问题。最近的研究提出了两种解决方案来部分解决这个问题，但它们的性能仍然有限。首先，基于局部的GNN只更新直接参与事件的节点，它们遇到了质量缺陷的问题，因为它们忽略了受这些事件影响的其他节点。其次，邻居采样GNN建议对邻居进行采样以加速邻居聚合计算，从而遇到邻居冗余问题。这些采样的邻居可能相似，并且不能反映所有邻居的分布，导致在这些冗余邻居上聚合的节点表示可能与在所有邻居上聚合的节点表示不同。在本文中，我们提出了一种高效可靠的图神经网络，即EARLY，用于更新动态图的节点表示。我们首先确定受图事件影响最大的前 k 个影响节点。然后，为了对邻居进行多样化的采样，我们提出了一种多样性感知的逐层采样技术。我们从理论上证明了这种技术可以减少采样期望误差并学习更可靠的节点表示。因此，top-k 节点选择和多样性感知采样使 EARLY 能够以可靠的方式有效地更新节点表示。我们在五个真实世界图上的实验验证了EARLY具有效果好和效率高的优势。

最近，图神经网络（GNN）在许多下游应用中取得了巨大的成功。而小批量（mini batch）训练也成为在巨型图上训练GNN的广泛使用的训练范式。我们发现训练中的mini batch生成任务非常耗时，拖慢了整个GNN训练的过程。此前研究人员提出了几种加速mini batch生成的方案，但是，它们（1）未能利用邻接矩阵的局部性（locality），（2）无法充分利用GPU的内存，以及（3）对不同工作负载的适应性差。在这项工作中，我们提出了DUCATI双缓存系统来克服这些缺点。除了传统的Nfeat-Cache之外，DUCATI还提出了新的Adj-Cache，以进一步加速mini batch的生成并更好地利用GPU内存。DUCATI还开发了一种工作负载感知的双缓存分配器，可在不同设置下自适应地找到最佳的缓存分配计划。我们在四个十亿量级的图数据集上，将DUCATI与各种GNN训练系统在不同工作负载设置下进行了比较。实验结果表明，在训练时间方面，DUCATI对比DGL可实现高达3.33倍的加速（平均2.07倍），与最先进的单缓存系统相比，DUCATI可实现高达1.54倍（平均1.32倍）的训练加速。我们还分析了DUCATI和四个最先进的GNN训练系统在时间与精度两个维度上的权衡取舍。我们的分析结果为用户提供了在不同输入大小和硬件资源场景下的系统选择指南。

子图匹配是图分析中的基本操作，在数据图G中查找查询图Q的所有匹配项。一种常见的方法是首先过滤掉G中不是候选顶点的部分，然后对Q中的顶点进行排序以枚举结果。最近的工作已经开始研究利用GPU来加速子图匹配。但是，当前基于 GPU 的过滤和排序方法的有效性有限，结果枚举通常会很快耗尽内存。为了解决这些问题，我们提出了EGSM，一种基于GPU的快速匹配子图的方法。具体来说，我们设计了一种名为Cuckoo trie的数据结构，支持动态维护过滤候选项，并根据估计的候选顶点数量实时排序查询顶点。此外，我们采用一种混合广度优先和深度优先的搜索方法并且使用内存管理来进行结果枚举。因此，EGSM 的性能明显优于最先进的 GPU 加速算法，包括 GSI 和 CuTS。

数据准备对于实现机器学习 （ML） 的优化结果至关重要。然而，对于 ML 从业者来说，拥有一个良好的数据准备管道非常重要，这不仅是特定于领域的，而且是特定于数据集的。有两种常见的做法。人工生成的管道 （HI-pipelines） 通常使用各种任何操作或库，但高度基于经验和启发式。相比之下，机器生成的管道（AI-pipelines），又名AutoML 通常采用一组预定义的复杂操作，并且基于搜索和优化。这两种常见做法是相辅相成的。在本文中，我们研究了一个新问题，即给定一个 HI 管道和一个用于相同 ML 任务的 AI 管道，我们是否可以将它们组合起来以获得比提供的 HI 管道和 AI 管道更好的新管道（HAI-pipeline）？我们提出了 HAIPipe，这是一个用于解决此问题的框架，它采用枚举采样策略来仔细选择性能最佳的组合管道。我们还介绍了一种基于强化学习 （RL） 的方法来搜索优化的 AI 管道。使用1400+真实世界的HI管道（来自Kaggle的Jupyter笔记本）进行的广泛实验验证了HAIPipe可以显着优于单独使用HI管道或AI管道的方法。

在具有不完整数据（例如，缺失值）的数据集中针对不完整的数据训练机器学习模型需要两个步骤。首先，需要一个数据有效的步骤来清理数据，以提高数据质量（以及清理数据的模型质量）。其次，需要一个数据高效的步骤，选择数据的核心子集（称为coreset），使整个数据和核心集上的训练模型具有相似的模型质量，以提高训练效率。清理整个数据的成本很高导致“先有效数据后数据高效“的方法成本太高，;而“先数据高效后数据有效”的方法模型质量较低，因为它们无法为不完整的数据选择高质量的核心集。

在本文中，我们研究了不完整数据的核心集选择问题，以实现数据效率和数据高效的机器学习。根本的挑战是如何对不完整的数据进行建模，以选择高质量的核心集。为此，我们提出了GoodCore框架，以低成本选择不完整的数据来选择良好的核心集。为了对未知的完整数据进行建模，我们利用可能的修复组合作为不完整数据的可能世界。基于可能的世界，GoodCore 通过梯度近似选择预期的最佳核心集，而无需训练 ML 模型。我们正式定义了预期最优核心集选择问题，证明了其NP硬度，并提出了一种具有近似比的贪婪算法。为了使GoodCore更高效，我们进一步提出了优化方法，将人机在环插补或自动插补方法纳入我们的框架。实验结果表明了该框架在低成本下的有效性和效率。

数据匹配 – 确定两个数据元素（例如，字符串、元组、列或知识图谱实体）是否“相同”（也称为匹配） – 是数据集成中的一个关键概念，例如实体匹配和模式匹配。广泛使用的做法是构建特定于任务甚至特定于数据集的解决方案，这些解决方案很难推广，并且禁用了可以从不同数据集和多个任务中学习的知识共享机会。在本文中，我们提出了Unicorn，一个通用支持常见数据匹配任务的统一模型。Unicorn 可以通过从多个任务和多个数据集中学习来实现知识共享，还可以支持对具有零标记匹配/非匹配对的新任务进行零样本预测。然而，由于输入数据元素的异构格式和多个任务的各种匹配语义，构建这样一个统一的模型具有挑战性。为了应对这些挑战，Unicorn 使用了一个通用编码器，它将任何一对数据元素 （a， b） 转换为学习的表示形式，并使用一个匹配器（一个二进制分类器）来确定 a 是否匹配 b。为了协调多个任务的匹配语义，Unicorn 采用了专家混合模型，将学习的表示增强为更好的表示。我们使用 20 个数据集对七个经过充分研究的数据匹配任务进行了广泛的实验，发现与分别为临时任务和数据集训练的最先进的特定模型相比，我们的统一模型可以在大多数任务和平均上实现更好的性能。此外，Unicorn还可以很好地通过零镜头学习来执行新的匹配任务。

在数据库系统中采用文本到 SQL 转换的一个常见问题是泛化不佳。具体来说，当新数据集上的训练数据有限时，现有的少量文本到 SQL 技术，即使在预训练语言模型 （PLM） 上使用精心设计的文本提示，也往往无效。在本文中，我们提出了一个分而治之的框架，以更好地支持少数镜头的文本到SQL翻译，它将文本到SQL的翻译分为两个阶段（或子任务），使得每个子任务都更容易处理。第一阶段称为结构阶段，它引导 PLM 生成 SQL 结构（包括 SELECT、FROM、WHERE 等 SQL 命令和 <“、”？>“）等 SQL 运算符，并带有缺少标识符的占位符。第二阶段称为内容阶段，它指导 PLM 使用具体值（包括表名、列名和常量值等 SQL 标识）填充生成的 SQL 结构中的占位符。我们提出了一种混合提示策略，该策略结合了可学习向量和固定向量（即文本提示的单词嵌入），使得混合提示可以学习上下文信息，以更好地指导PLM在两个阶段进行预测。此外，我们设计了关键字约束解码以保证生成的SQL结构的有效性，并设计了结构引导解码以保证模型填充正确的内容。在撰写本文时，通过与十个最先进的文本到 SQL 解决方案进行比较，广泛的实验表明，SC-Prompt 在少数镜头场景中的性能明显优于它们。特别是在广泛采用的Spider数据集上，给定少于500个标记的训练样本（官方训练集的5%），SC-Prompt在准确性上比以前的SOTA方法高出约5%。

可视化结果的应用场景越来越广泛，逐渐成为一种新的数据类型，并启发了新的数据管理问题，例如可视化结果的相似性搜索。在探索式数据分析和可视查询系统中，检索相似的折线图是一项常见的任务，如查找股票价格波动的相似趋势。现有的方法通常考虑数据级相似性或图像级相似性。当折线图的原始数据在查询阶段可用时，通过使用DTW等距离函数直接度量数据级相似性，这种方法简单且有效；当原始数据在查询阶段不可用时，可以通过捕捉折线图的图像信息来衡量图像级相似性，这种方法能反映人类视觉感知的相似性，最近受到了学术界的广泛关注。

该研究工作提出了一种新型的学习框架LineNet，通过融合折线图原始数据和图像，以学习更好的折线图表示进而支持精准的可视化搜索。该工作的核心思想是在模型训练期间可以通过收集到的原始数据和折线图图像来学习融合数据相似性的图像表示，而在查询（即模型推理）阶段，可支持仅提供折线图图像的情况。为此，该工作提出了 LineNet，这是一种基于 Vision Transformer 的三元自动编码器模型，用于学习折线图的数据感知图像表示以支持相似性搜索，并设计了一种新颖的伪标签选择机制来指导 LineNet 捕获折线图的数据感知和图像级相似性。该工作进一步提出了多样化的训练样本选择策略，以优化学习过程并提高性能。量化实验和案例研究表明 LineNet 在搜索相似折线图图像方面明显优于最先进的方法。

由于地理定位技术的进步，地形数据越来越受欢迎，并吸引了学术界和工业界的大量研究工作。地形表面的距离计算是地理信息系统和三维建模中广泛应用的基础且重要的问题。从现有研究中可以看出，在线计算地形表面的距离需要非常高的代价。现在所有的基于索引的方法仅能在一小组预定义的先验点中执行距离查询时才能保证效率。但是，在一般情况下，由于构建oracle的时间和空间消耗过高，它们无法被扩展到大型的数据集。

本文研究了在地形表面上任意两点之间的距离查询问题，其中查询点的选择不包含任何假设，并且支持在完全任意对两个点上的距离计算。我们提出了名为Efficient Arbitrary Point-to-Arbitrary Point Distance Oracle（EAR-Oracle）的索引结构，我们在oracle的准确性、oracle构建时间、oracle大小和查询时间上都提供了理论上的保证。我们的实验表明，我们的预言机具有出色的可扩展性，可以扩展到现有的基于索引的方法都无法处理的巨大的地形表面，。此外，在查询时间方面，它以几个数量级的显著优势超过了所有现有的在线计算方法。

近年来，由于人们对隐私问题的关注日益增加，如何在差分隐私下回答关系型数据库中的查询被广泛研究。目前，已有算法针对单个查询实现最优的误差。但是，大多数现实世界的数据分析任务都需要在一个总隐私保护目标下回答多个查询。这一问题的标准解决方案是将单查询算法扩展到多个查询。但是，这会导致一个误差比最优误差差d^0.5（ d 是查询数）。在本文中，我们提出了一种不同的、更全面的方法来解决这一差距。除了实现理论上的最优误差，我们的新机制在实践中也有明显的优势，特别是在高偏差的数据和高查询数d的情况下。

图神经网络 （GNN） 已成为从图结构数据中捕获结构信息的强大工具，在推荐、知识图谱和搜索等应用场景上实现了最优的性能。这些领域中的图通常包含数亿个节点和数十亿条边。然而，以前的GNN系统表现出较差的可扩展性，因为GNN训练中的大型交错计算依赖关系为当前的并行化方法中带来了巨大的额外开销。在这里我们提出了G3，这是一个分布式系统，可以大规模快速地训练超过十亿条边图的GNN。G3引入了GNN混合并行性方法，它综合了并行性的三个维度，通过以细粒度点对点共享中间结果来扩展GNN训练，消除了全局集体通信或邻居复制的逐层障碍，如以前的工作所示。G3 利用局部感知迭代分区和多级管道调度，通过在工作线程之间分配均衡的工作负载，并在层间和层内训练过程中将计算与通信重叠，从而充分利用加速空间。我们通过原型实现和综合实验表明，G3 可以在 16 节点集群中实现高达 2.24 倍的加速，并且比以前的工作具有更好的最终精度。

路线规划是日常生活的基础。然而，现有的地图应用程序侧重于通过优化单个目标来推荐路线，这与在一些场景下用户对受约束的最优路线的需求不符。受约束的最短路径 （CSP） 查询虽符合此要求，但由于 CSP 的 问题是NP-hard的 ，以前解决方案的查询效率通常较低。在大数据时代，最先进的索引越来越大，以支持更快的查询处理。最近尝试预处理更多中间结果并减少表查找次数的尝试已被证明在解决CSP方面是成功的。但是，最知名的算法会忽略 CSP 查询中的某些信息，并尝试在处理确切的 CSP 之前解决更常见的问题。在本文中，我们提出了迄今为止最快的算法QHL，它充分利用了CSP查询信息的修剪能力。具体来说，我们通过生成可以提高查询速度的修剪条件来预处理索引。我们还在真实世界的数据集上进行了广泛的实验，以证明我们提出的算法的优越性。QHL可以在大约50 μs内回答每个CSP查询，并且运行速度比最知名的算法快几个数量级。

鉴于探索性数据分析（EDA）的日益普及，了解EDA获得知识的根本原因至关重要。然而，它仍然没有得到充分研究。这项研究促进了数据分析中的透明性和可解释性方面的研究，这方面也被称为可解释数据分析（XDA）。出于这个原因，我们提出了Xnsight，一个XDA的一般框架。XInsight 提供数据分析，包括因果和非因果语义的定性和定量解释。这样，它将显着提高人类对数据分析结果的理解和信心，促进现实世界中准确的数据解释和决策。XInsight 是一个三模块的端到端流程，旨在提取因果图，将因果原语转换为 XDA 语义，并量化每个解释对数据事实的定量贡献。XInsight 使用一套设计概念和优化来解决与将因果关系集成到 XDA 中相关的固有困难。对合成的和真实世界的数据集的实验以及用户研究证明了 XInsight 非常有前途。