Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries|
|Authors: ||Ketsman, Bas|
|Issue Date: ||2017|
|Citation: ||Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, ACM,p. 417-428|
|Abstract: ||We study the optimal communication cost for computing a full conjunctive query Q over p distributed servers. Two prior results were known. First, for one-round algorithms over skew-free data the optimal communication cost per server is m/p^(1/tau*), where m is the size of the largest input relation, and tau* is the fractional vertex covering number of the query hypergraph. Second, for multi-round algorithms and unrestricted database instances, it was shown that any algorithm requires at least m/p^(1/rho*) communication cost per server, where rho* is the fractional edge covering number of the query hypergraph; but no matching algorithms were known for this case (except for two restricted queries: chains and cycles).
In this paper we describe a multi-round algorithm that computes any query with load m/p^(1/rho*) per server, in the case when all input relations are binary. Thus, we prove this to be the optimal load for all queries over binary input relations. Our algorithm represents a non-trivial extension of previous algorithms for chains and cycles, and exploits some unique properties of graphs, which no longer hold for hyper-graphs.|
|Type: ||Proceedings Paper|
|Appears in Collections: ||Research publications|
Files in This Item:
|N/A||405.06 kB||Adobe PDF|
|Proof of peer-review||384.41 kB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.