Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/24980

Title: A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries
Authors: Ketsman, Bas
Suciu, Dan
Issue Date: 2017
Publisher: ACM
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.
URI: http://hdl.handle.net/1942/24980
DOI: 10.1145/3034786.3034788
ISBN: 9781450341981
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A405.06 kBAdobe PDF
Proof of peer-review384.41 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.