Subspace exploration: Bounds on Projected Frequency Estimation.
Subspace exploration: Bounds on Projected Frequency Estimation.
复制标题
子空间探索：投影频率估计的界限。
DOI：
10.1145/3452021.3458312
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Woodruff DP
中科院分区：
文献类型：
--
作者：
Cormode G;Dickens C;Woodruff DP
给定n × d维数据集A，投影查询指定列的子集C [d]，其产生新的n × d| C|阵我们研究了在这样的子空间上计算数据分析函数的空间复杂性，包括重打击者和范数，当子空间只有在观察数据后才被揭示时。我们证明了这类重要的问题通常是困难的：对于许多问题，我们证明了2Ω（d）的下界。然而，我们提出的上限，证明空间依赖性优于2D。也就是说，对于c，c′ ∈（0，1）和参数N = 2d，可以在空间中获得Nc-近似，这表明可以改进保持d列的所有2d子集的信息的朴素方法。我们的研究结果是基于仔细建设的实例，使用编码理论和新颖的组合减少表现出这种空间近似的权衡。
Given an n × d dimensional dataset A, a projection query specifies a subset C ⊆ [d] of columns which yields a new n × |C| array. We study the space complexity of computing data analysis functions over such subspaces, including heavy hitters and norms, when the subspaces are revealed only after observing the data. We show that this important class of problems is typically hard: for many problems, we show 2Ω(d) lower bounds. However, we present upper bounds which demonstrate space dependency better than 2d. That is, for c, c′ ∈ (0, 1) and a parameter N = 2d an Nc-approximation can be obtained in space , showing that it is possible to improve on the naïve approach of keeping information for all 2d subsets of d columns. Our results are based on careful constructions of instances using coding theory and novel combinatorial reductions that exhibit such space-approximation tradeoffs.
影响因子：
1.4
作者：
Kremer, I;Nisan, N;Ron, D
通讯作者：
Ron, D
影响因子：
1.1
作者：
Alon, N;Matias, Y;Szegedy, M
通讯作者：
Szegedy, M