Subset Sampling over Joins

doi:10.1145/3801913

Subset Sampling over Joins

2026-05-01

1

PRE

AI

DOI：10.1145/3801913

原文求助

摘要

En 中文

子集采样（又称泊松采样），即决定是否将任何特定元素包含在样本中的过程与其他元素独立进行，是数据分析中的一个基本操作，通过处理代表性子集而非大规模数据集实现高效近似。尽管从显式列表中进行采样已被充分理解，但现代应用（如关系数据上的机器学习）通常需要从由关系连接隐式定义的集合中进行采样。本文研究了连接上的子集采样问题：从连接结果中抽取随机子集，其中每个连接结果以一定概率独立包含。我们处理了一般情况，其中概率通过可分解函数（如乘积、求和、最小值、最大值）从输入元组权重中得出。由于连接规模可能比输入大指数级，直接物化所有连接结果以进行子集采样的朴素方法在计算上不可行。我们提出了针对无环连接的子集采样的首批高效算法：(1) 用于在连接上生成多个（独立）子集样本的静态索引；(2) 用于在连接上生成单个子集样本的一步算法；(3) 支持元组插入的动态索引，同时能维护一个一步样本或生成多个（独立）样本。我们的技术在输入规模和期望样本规模方面实现了接近最优的时间和空间复杂度。

Keyword:

ALGORITHM

Subset Sampling over Joins

摘要

期刊

机构

引用论文