Sökning: id:"swepub:oai:DiVA.org:kth-236053" >
Streaming Graph Par...
Streaming Graph Partitioning: An Experimental Study
-
- Abbas, Zainab, 1991- (författare)
- KTH,Programvaruteknik och datorsystem, SCS
-
- Kalavri, Vasiliki, 1986- (författare)
- Systems Group, ETH, Zurich, Switzerland
-
- Carbone, Paris, 1986- (författare)
- KTH,Programvaruteknik och datorsystem, SCS
-
visa fler...
-
- Vlassov, Vladimir, 1957- (författare)
- KTH,Programvaruteknik och datorsystem, SCS
-
visa färre...
-
(creator_code:org_t)
- 2018-07
- 2018
- Engelska.
-
Ingår i: Proceedings of the VLDB Endowment. - : ACM Digital Library. - 2150-8097. ; 11:11, s. 1590-1603
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Graph partitioning is an essential yet challenging task for massive graph analysis in distributed computing. Common graph partitioning methods scan the complete graph to obtain structural characteristics offline, before partitioning. However, the emerging need for low-latency, continuous graph analysis led to the development of online partitioning methods. Online methods ingest edges or vertices as a stream, making partitioning decisions on the fly based on partial knowledge of the graph. Prior studies have compared offline graph partitioning techniques across different systems. Yet, little effort has been put into investigating the characteristics of online graph partitioning strategies.In this work, we describe and categorize online graph partitioning techniques based on their assumptions, objectives and costs. Furthermore, we employ an experimental comparison across different applications and datasets, using a unified distributed runtime based on Apache Flink. Our experimental results showcase that model-dependent online partitioning techniques such as low-cut algorithms offer better performance for communication-intensive applications such as bulk synchronous iterative algorithms, albeit higher partitioning costs. Otherwise, model-agnostic techniques trade off data locality for lower partitioning costs and balanced workloads which is beneficial when executing data-parallel single-pass graph algorithms.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- graph partitioning
- streaming graph processing
- stream processing
- Computer Science
- Datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas