Faster Relational Algorithms Using Geometric Data Structures

doi:10.1145/3801898

Faster Relational Algorithms Using Geometric Data Structures

2026-05-01

0

PRE

AI

DOI：10.1145/3801898

原文求助

摘要

En 中文

在关系数据上的优化任务，如聚类，通常因连接操作的高昂成本而受限，这些操作是访问完整数据集所必需的。虽然几何数据结构（如BBD树）在标准计算设置下能产生快速近似算法，但由于连接输出的规模问题，其应用于关系数据仍不明确。本文提出了一种利用几何见解来设计更快算法的框架，当数据以关系数据库中连接查询结果的形式存储时。我们的核心贡献是开发了RBBD树，一种为关系设置定制的BBD树的随机变体。通过利用关系连接上的高效采样和计数技术，我们无需完全构建RBBD树，而是实现了按需高效的树扩展，仅维护必要部分。这使得我们能够在不物化连接结果的情况下模拟几何查询过程。作为应用，我们提出了算法，在保持相同近似保证的同时，将关系k-中心/均值/中位数聚类的运行时间改进了k倍。我们的方法具有通用性，可应用于关系设置下的各种优化问题。

Keyword:

relational data

clustering

k-center

k-median

k-means

BBD tree

Faster Relational Algorithms Using Geometric Data Structures

摘要

期刊

机构

引用论文