Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size
Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size
复制标题
Delphic 集并集大小的估计：实现与流大小的独立性
DOI：
10.1145/3517804.3526222
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vinodchandran, N. V.
中科院分区：
文献类型：
--
作者：
Meel, Kuldeep S.;Chakraborty, Sourav;Vinodchandran, N. V.
给定一个集合族（S1，S2，. SM）的情况下，估计它们在数据流模型中的并集的大小是具有广泛应用的基本计算问题。流媒体领域的圣杯是寻求用poly（log）实现（ε，δ）-近似的算法设计|Ω|，ε-1，log δ-1）空间复杂度和更新时间复杂度。早期的研究实现了具有所需空间复杂度和更新时间复杂度的算法，这些算法适用于受限制的情况，如单元素问题（Distinct Elements problem）、一维范围、算术级数和子立方体。然而，在这些作品中使用的技术失败的许多其他简单的结构化集。一个突出的例子是克利测度问题（KMP），其中每个集合Si由d维空间中的轴平行矩形表示。尽管有大量的先前工作，但是对于这些情况中的许多情况，最著名的流算法取决于流的大小，并且因此存在是否存在用于估计具有多（log）的集合的并集的大小的流算法的问题|Ω|，ε-1，log δ-1）空间和更新时间复杂度仍然是开放的。在这项工作中，我们专注于称为Delphic族的某些一般集合族（它允许有效的成员资格，采样和基数查询）。这样的家庭集捕获几个著名的问题，包括KMP，测试覆盖率，和hypervolume estimation.The主要贡献，我们的工作是解决上述开放问题的流在德尔菲族。特别地，我们设计了第一个流算法，用于估计|Si =1M Si|使用多边形（对数|Ω|，ε-1，log δ-1）空间和更新时间复杂度（独立于M，流的长度）。我们进一步推广我们的结果，以更大的家庭的集合，称为近似德尔菲族，其中一组的大小可以知道近似，但不完全。我们的结果解决了Meel，Vinodchandran，Chakraborty（PODS-21）中列出的两个开放问题。
Given a family of sets (S1, S2,... SM) over a universe Ω, estimating the size of their union in the data streaming model is a fundamental computational problem with a wide variety of applications. The holy grail in the field of streaming is to seek design of algorithms that achieve (ε, δ)-approximation with poly(log |Ω|, ε-1, log δ-1) space and update time complexity.Earlier investigations achieve algorithms with desired space and update time complexity for restricted cases such as singletons (Distinct Elements problem), one-dimensional ranges, arithmetic progressions, and sub-cubes. However, techniques used in these works fail for many other simple structured sets. A prominent example is that of Klee's Measure Problem (KMP), wherein every set Si is represented by an axis-parallel rectangle in d-dimensional spaces. Despite extensive prior work, the best-known streaming algorithms for many of these cases depend on the size of the stream, and therefore the problem of whether there exists a streaming algorithm for estimations of size of the union of sets with poly(log |Ω|, ε-1, log δ-1) space and update time complexity has remained open.In this work, we focus on certain general families of sets called Delphic families (which allows efficient membership, sampling, and cardinality queries). Such families of sets capture several well-known problems, including KMP, test coverage, and hypervolume estimation.The primary contribution of our work is to resolve the above-mentioned open problem for streams over Delphic families. In particular, we design the first streaming algorithm for estimating |⋃i=1M Si| with poly(log |Ω|, ε-1, log δ-1) space and update time complexity (independent of M, the length of the stream) when each Si is a member from a Delphic family of sets. We further generalize our results to larger families of sets, called approximate-Delphic families, for which the size of a set can be known approximately but not exactly. Our results resolve two of the open problems listed in Meel, Vinodchandran, Chakraborty (PODS-21).
登录
查看更多内容
克利测量问题的（稍微）更快的算法
DOI：
10.1145/1377676.1377693
发表时间：
2008
期刊：
Comput. Geom.
影响因子：
--
作者：
Timothy M. Chan
通讯作者：
Timothy M. Chan
DOI：
10.1109/sfcs.1983.35
发表时间：
1983-11
期刊：
24th Annual Symposium on Foundations of Computer Science (sfcs 1983)
影响因子：
--
作者：
R. Karp;M. Luby
通讯作者：
R. Karp;M. Luby
两种改进的 F 0 估计范围有效算法
影响因子：
2.2
作者：
He Sun;C. Poon
通讯作者：
C. Poon
海量数据流中不同元素的范围有效计数
DOI：
10.1137/050643672
发表时间：
2007
期刊：
SIAM J. Comput.
影响因子：
--
作者：
A. Pavan;Srikanta Tirthapura
通讯作者：
Srikanta Tirthapura
空间数据流中的矩形高效聚合
DOI：
10.1145/2213556.2213595
发表时间：
2012
期刊：
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems
影响因子：
--
作者：
Srikanta Tirthapura;David P. Woodruff
通讯作者：
David P. Woodruff