Browse by author
Lookup NU author(s): Hugo Firth, Professor Paolo MissierORCiD
Full text for this publication is not currently held within this repository. Alternative links are provided below where available.
© 2017 The Author(s) Graph partitioning has long been seen as a viable approach to addressing Graph DBMS scalability. A partitioning, however, may introduce extra query processing latency unless it is sensitive to a specific query workload, and optimised to minimise inter-partition traversals for that workload. Additionally, it should also be possible to incrementally adjust the partitioning in reaction to changes in the graph topology, the query workload, or both. Because of their complexity, current partitioning algorithms fall short of one or both of these requirements, as they are designed for offline use and as one-off operations. The TAPER system aims to address both requirements, whilst leveraging existing partitioning algorithms. TAPER takes any given initial partitioning as a starting point, and iteratively adjusts it by swapping chosen vertices across partitions, heuristically reducing the probability of inter-partition traversals for a given path queries workload. Iterations are inexpensive thanks to time and space optimisations in the underlying support data structures. We evaluate TAPER on two different large test graphs and over realistic query workloads. Our results indicate that, given a hash-based partitioning, TAPER reduces the number of inter-partition traversals by (Formula presented.)80%; given an unweighted Metis partitioning, by (Formula presented.)30%. These reductions are achieved within eight iterations and with the additional advantage of being workload-aware and usable online.
Author(s): Firth H, Missier P
Publication type: Article
Publication status: Published
Journal: Distributed and Parallel Databases
Year: 2017
Volume: 35
Issue: 2
Pages: 85-115
Print publication date: 01/06/2017
Online publication date: 02/05/2017
Acceptance date: 02/04/2016
Date deposited: 24/05/2017
ISSN (print): 0926-8782
ISSN (electronic): 1573-7578
Publisher: Springer New York LLC
URL: https://doi.org/10.1007/s10619-017-7196-y
DOI: 10.1007/s10619-017-7196-y
Altmetrics provided by Altmetric
