Topology Dependent Bounds For FAQs
Topology Dependent Bounds For FAQs
复制标题
常见问题解答的拓扑相关边界
DOI：
10.1145/3294052.3319686
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Rudra, Atri
中科院分区：
文献类型：
--
作者：
Langberg, Michael;Li, Shi;Mani Jayaraman, Sai Vikneshwar;Rudra, Atri
本文证明了Abo Khamis等人研究的计算函数聚集查询($\FAQ$S)所需轮数的拓扑界。[PODS 2016]在Chattopadhyay等人考虑的模型下的同步分布式网络中。[聚焦2014年，汽水2017年]。与最近在大规模并行计算模型中计算数据库查询的工作不同，在Chattopadhyay等人的模型中，节点只能通过专用的点对点通道进行通信，我们对工作在任意通信拓扑上的界限感兴趣。该模型更接近于分布式计算中已被广泛研究的拥塞模型，并推广了姚的两方通信复杂性模型，到目前为止只研究了两方通信复杂性文献中常见的问题。这是第一个在这个分布式模型中考虑更实际激励问题的工作。为了便于说明，本文着重讨论了两个具体问题：布尔合取查询($\BCQ$)和概率图模型(PGMS)中变量/因子边际的计算。只要查询的底层超图是退化的且具有一致性，我们就得到了计算这类查询所需轮数的严格界。具体地说，-退化条件涵盖了大多数经过充分研究的查询，这些查询在集中式计算模型中是可以高效计算的，比如具有恒定树宽的查询。这些紧界依赖于非圈超图的广义超树分解(GHD)的一个新的‘宽度’(即内部节点宽度)的概念，它最小化了GHD子类中的内部节点数。就我们所知，在理论数据库文献中还没有明确地研究过这个宽度。最后，我们考虑了计算一个向量与一个矩阵链的乘积的问题，并使用一个新的基于最小熵的论点证明了它的轮复杂性的紧界(在两个元素的有限域上)。
In this paper, we prove topology dependent bounds on the number of rounds needed to compute Functional Aggregate Queries ($\FAQ$s) studied by Abo Khamis et al. [PODS 2016] in a synchronous distributed network under the model considered by Chattopadhyay et al. [FOCS 2014, SODA 2017]. Unlike the recent work on computing database queries in the Massively Parallel Computation model, in the model of Chattopadhyay et al., nodes can communicate only via private point-to-point channels and we are interested in bounds that work over an \em arbitrary communication topology. This model, which is closer to the well-studied $\congest$ model in distributed computing and generalizes Yao's two party communication complexity model, has so far only been studied for problems that are common in the two-party communication complexity literature. This is the first work to consider more practically motivated problems in this distributed model. For the sake of exposition, we focus on two specific problems in this paper: Boolean Conjunctive Query ($\BCQ$) and computing variable/factor marginals in Probabilistic Graphical Models (PGMs). We obtain tight bounds on the number of rounds needed to compute such queries as long as the underlying hypergraph of the query is-degenerate and has-arity. In particular, the-degeneracy condition covers most well-studied queries that are efficiently computable in the centralized computation model like queries with constant treewidth. These tight bounds depend on a new notion of 'width' (namely \em internal-node-width ) for Generalized Hypertree Decompositions (GHDs) of acyclic hypergraphs, which minimizes the number of internal nodes in a sub-class of GHDs. To the best of our knowledge, this width has not been studied explicitly in the theoretical database literature. Finally, we consider the problem of computing the product of a vector with a chain of matrices and prove tight bounds on its round complexity (over a finite field of two elements) using a novel min-entropy based argument.
登录
查看更多内容
矩形是非负 Juntas
DOI：
10.1145/2746539.2746596
发表时间：
2015
期刊：
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Mika Göös;Shachar Lovett;Raghu Meka;Thomas Watson;David Zuckerman
通讯作者：
David Zuckerman
DOI：
--
发表时间：
2016
期刊：
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
影响因子：
--
作者：
G. Gottlob;G. Greco;N. Leone;Francesco Scarcello
通讯作者：
Francesco Scarcello
DOI：
--
发表时间：
2004
期刊：
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
影响因子：
--
作者：
Francesco Scarcello;G. Greco;N. Leone
通讯作者：
N. Leone
小树宽图的 NC 算法
DOI：
--
发表时间：
1988
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
H. Bodlaender
通讯作者：
H. Bodlaender
影响因子：
1.4
作者：
Mika Göös;Pritish Kamath;T. Pitassi;Thomas Watson
通讯作者：
Mika Göös;Pritish Kamath;T. Pitassi;Thomas Watson