@inproceedings{firth_loom_2018,
	address = {Vienna, Austria},
	title = {Loom: {Query}-aware {Partitioning} of {Online} {Graphs}},
	url = {http://edbticdt2018.at/},
	abstract = {As with general graph processing systems, partitioning data over a cluster of machines improves the scalability of graph database management systems. However, these systems will incur additional network cost during the execution of a query workload, due to inter- partition traversals. Workload-agnostic partitioning algorithms typically minimise the likelihood of any edge crossing partition boundaries. However, these partitioners are sub-optimal with re- spect to many workloads, especially queries, which may require more frequent traversal of speci c subsets of inter-partition edges. Furthermore, they largely unsuited to operating incrementally on dynamic, growing graphs. We present a new graph partitioning algorithm, Loom, that op- erates on a stream of graph updates and continuously allocates the new vertices and edges to partitions, taking into account a query workload of graph pattern expressions along with their relative frequencies. First we capture the most common patterns of edge traversals which occur when executing queries. We then compare sub-graphs, which present themselves incrementally in the graph update stream, against these common patterns. Finally we attempt to allocate each match to single partitions, reducing the number of inter-partition edges within frequently traversed sub-graphs and improving average query performance. Loom is extensively evaluated over several large test graphs with realistic query workloads and various orderings of the graph updates. We demonstrate that, given a workload, our prototype produces partitionings of signi cantly better quality than existing streaming graph partitioning algorithms Fennel \& LDG.},
	booktitle = {Procs. 21st {International} {Conference} on {Extending} {Database} {Technology} ({EDBT})},
	publisher = {EDBT},
	author = {Firth, H and Missier, P},
	year = {2018},
	keywords = {distributed graphs, graph partitioning},
}

{"_id":"t66iMmomwSoCSDifi","bibbaseid":"firth-missier-loomqueryawarepartitioningofonlinegraphs-2018","downloads":0,"creationDate":"2017-11-29T07:53:18.397Z","title":"Loom: Query-aware Partitioning of Online Graphs","author_short":["Firth, H","Missier, P"],"year":2018,"bibtype":"inproceedings","biburl":"https://bibbase.org/network/files/tHMs8ic86gSWoTp44","bibdata":{"bibtype":"inproceedings","type":"inproceedings","address":"Vienna, Austria","title":"Loom: Query-aware Partitioning of Online Graphs","url":"http://edbticdt2018.at/","abstract":"As with general graph processing systems, partitioning data over a cluster of machines improves the scalability of graph database management systems. However, these systems will incur additional network cost during the execution of a query workload, due to inter- partition traversals. Workload-agnostic partitioning algorithms typically minimise the likelihood of any edge crossing partition boundaries. However, these partitioners are sub-optimal with re- spect to many workloads, especially queries, which may require more frequent traversal of speci c subsets of inter-partition edges. Furthermore, they largely unsuited to operating incrementally on dynamic, growing graphs. We present a new graph partitioning algorithm, Loom, that op- erates on a stream of graph updates and continuously allocates the new vertices and edges to partitions, taking into account a query workload of graph pattern expressions along with their relative frequencies. First we capture the most common patterns of edge traversals which occur when executing queries. We then compare sub-graphs, which present themselves incrementally in the graph update stream, against these common patterns. Finally we attempt to allocate each match to single partitions, reducing the number of inter-partition edges within frequently traversed sub-graphs and improving average query performance. Loom is extensively evaluated over several large test graphs with realistic query workloads and various orderings of the graph updates. We demonstrate that, given a workload, our prototype produces partitionings of signi cantly better quality than existing streaming graph partitioning algorithms Fennel & LDG.","booktitle":"Procs. 21st International Conference on Extending Database Technology (EDBT)","publisher":"EDBT","author":[{"propositions":[],"lastnames":["Firth"],"firstnames":["H"],"suffixes":[]},{"propositions":[],"lastnames":["Missier"],"firstnames":["P"],"suffixes":[]}],"year":"2018","keywords":"distributed graphs, graph partitioning","bibtex":"@inproceedings{firth_loom_2018,\n\taddress = {Vienna, Austria},\n\ttitle = {Loom: {Query}-aware {Partitioning} of {Online} {Graphs}},\n\turl = {http://edbticdt2018.at/},\n\tabstract = {As with general graph processing systems, partitioning data over a cluster of machines improves the scalability of graph database management systems. However, these systems will incur additional network cost during the execution of a query workload, due to inter- partition traversals. Workload-agnostic partitioning algorithms typically minimise the likelihood of any edge crossing partition boundaries. However, these partitioners are sub-optimal with re- spect to many workloads, especially queries, which may require more frequent traversal of speci c subsets of inter-partition edges. Furthermore, they largely unsuited to operating incrementally on dynamic, growing graphs. We present a new graph partitioning algorithm, Loom, that op- erates on a stream of graph updates and continuously allocates the new vertices and edges to partitions, taking into account a query workload of graph pattern expressions along with their relative frequencies. First we capture the most common patterns of edge traversals which occur when executing queries. We then compare sub-graphs, which present themselves incrementally in the graph update stream, against these common patterns. Finally we attempt to allocate each match to single partitions, reducing the number of inter-partition edges within frequently traversed sub-graphs and improving average query performance. Loom is extensively evaluated over several large test graphs with realistic query workloads and various orderings of the graph updates. We demonstrate that, given a workload, our prototype produces partitionings of signi cantly better quality than existing streaming graph partitioning algorithms Fennel \\& LDG.},\n\tbooktitle = {Procs. 21st {International} {Conference} on {Extending} {Database} {Technology} ({EDBT})},\n\tpublisher = {EDBT},\n\tauthor = {Firth, H and Missier, P},\n\tyear = {2018},\n\tkeywords = {distributed graphs, graph partitioning},\n}\n\n","author_short":["Firth, H","Missier, P"],"key":"firth_loom_2018","id":"firth_loom_2018","bibbaseid":"firth-missier-loomqueryawarepartitioningofonlinegraphs-2018","role":"author","urls":{"Paper":"http://edbticdt2018.at/"},"keyword":["distributed graphs","graph partitioning"],"metadata":{"authorlinks":{}},"downloads":0},"search_terms":["loom","query","aware","partitioning","online","graphs","firth","missier"],"keywords":["distributed graphs","graph partitioning"],"authorIDs":[],"dataSources":["zh27EpT9RPew3MWSE","nF6KkFb4XxGruanwy","BDjqJntjXzyBmLxhv","oiWqtmpFQ6ZtiMEK2","k75vCTghu54BjX5qH","j9tnaL2u4rifwAc2v","NCorZq2vkXK6BnhLF","ze2X9uz8Dcv2oGipf","afppXLgSuddAzAL9e","wJE4ynGem9MRsXBRn","9zrgMZfGdRkdkNXfZ","qTQGxWDYeue2pHBus"]}