Answering Subset Query Over Multi-Attribute Data Streams Using Hyper-USS

Ce Zheng

doi:10.1109/TKDE.2025.3611502

Answering Subset Query Over Multi-Attribute Data Streams Using Hyper-USS

2025-09-22

0

PRE

AI

DOI：10.1109/TKDE.2025.3611502

原文链接

原文求助

摘要

En 中文

近似查询为在可接受误差范围内分析海量数据流提供了一种高效手段。其中，针对多属性的子集查询在许多实际应用中较为常见。尽管草图技术为海量数据流提供了有前景的近似解决方案，但高效支持多统计属性上的子集查询仍是一个重大挑战。为解决这一问题，我们提出了Hyper-USS，一种新型草图解决方案，能够准确高效地支持涉及多统计属性的数据流上的子集查询。通过联合方差优化，Hyper-USS提供无偏估计并联合优化估计方差，解决了草图设计中准确估计多统计属性的挑战。该算法在一个草图中记录键和所有属性的信息，确保了高插入效率。此外，还介绍了其三种速度优化版本，以应对数据流中统计属性数量的增长。实验结果表明，Hyper-USS及其三种速度优化版本在估计精度和插入吞吐量方面均持续优于支持子集查询的最先进方法。具体而言，Hyper-USS将精度提高了至少38%，而该算法及其三种速度优化版本分别实现了高达31.90×、45.31×、49.21×和58.03×的吞吐量提升。

Keyword:

Sketch

multi-attribute data streams

subset query

unbiased estimation

Answering Subset Query Over Multi-Attribute Data Streams Using Hyper-USS

摘要

期刊

机构

引用论文