并行查询处理中的偏斜
通过在具有大量服务器的大型输入数据库上计算关系查询来解决分布式计算中通信协议的瓶颈,并且在单个和多个通信步骤中建立了下限,同时其下限证明了任何算法需要 epsilon 大于等于 1-1/tau*,同时结果也蕴含了不能在 O(1)个通信步骤内计算传递闭包。
Jun, 2013
本文研究了从理论角度出发,如何通过计算连接大小的估计值以及查找连接序列的良好执行计划来解决数据库查询优化问题。我们发现,在最坏情况下,查询的最坏大小由其底层超图的分数边覆盖数特征化,而在平均情况下,则是通过底层超图的最大密度属性来消除连接中的投影,提高连接性能。
Nov, 2017
本文探讨了在 map-reduce 计算中并行性和通信成本之间的权衡问题,并引入了单轮 map-reduce 计算问题的模型,以发现以分配给一个缩小器的最大输入数为函数的通信成本下界。作者对三个问题进行了分析:找到两个距离为 $d$ 的字符串、在较大的图形中查找三角形和其他模式以及矩阵乘法。
Jun, 2012
本文研究了高维分布统计估计问题的统计误差和通信成本之间的权衡,并提供了分布式稀疏高斯均值估计问题的紧密的权衡分析结果,这直接导致了分布式稀疏线性回归问题的下界,并给出了在稠密情况下均值估计的第一个最优同时协议。
Jun, 2015
本文研究在高维假设检验中的受限计算模型,特别是统计查询框架和低次多项式,在测试问题上的表现。主要结果表明,在测试问题的温和条件下,这两类算法在能力上基本等效,并提供了有限制的统计查询下界和植入团问题的几个变种。
Sep, 2020
本研究提出了两个结果,第一个结果说明了在 Kearns' SQ 模型中,对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度;第二个结果能高效地解决问题,只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用,使其得到了重大进展。
Nov, 2010
本研究探讨了在随机,密集的情况下,通过信息量论问题来解决在数据库中确定每个个体类型所需要的最小查询次数,我们建立了最小查询次数的上下边界,并解决了该问题。结论为解决该问题,通过图的欧拉流的高斯积分与其生成树多项式之间的恒等式,计算了该模型的退火自由能。
Nov, 2016
研究如何在分布式网络中学习高维、非参数和结构化(如高斯)分布,并考虑不同通信模型(包括独立、顺序和黑板模型)的交互限制对于最小化风险和 Fisher 信息的影响。
Feb, 2019