Change search
ReferencesLink to record
Permanent link

Direct link
Performance Optimization Techniques and Tools for Distributed Graph Processing
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0001-8219-4862
2016 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis, we propose optimization techniques for distributed graph processing. First, we describe a data processing pipeline that leverages an iterative graph algorithm for automatic classification of web trackers. Using this application as a motivating example, we examine how asymmetrical convergence of iterative graph algorithms can be used to reduce the amount of computation and communication in large-scale graph analysis. We propose an optimization framework for fixpoint algorithms and a declarative API for writing fixpoint applications. Our framework uses a cost model to automatically exploit asymmetrical convergence and evaluate execution strategies during runtime. We show that our cost model achieves speedup of up to 1.7x and communication savings of up to 54%. Next, we propose to use the concepts of semi-metricity and the metric backbone to reduce the amount of data that needs to be processed in large-scale graph analysis. We provide a distributed algorithm for computing the metric backbone using the vertex-centric programming model. Using the backbone, we can reduce graph sizes up to 88% and achieve speedup of up to 6.7x.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2016. , 158 p.
TRITA-ICT, 2016:25
Keyword [en]
Graph processing, distributed systems, big data
National Category
Computer Systems
Research subject
Information and Communication Technology
URN: urn:nbn:se:kth:diva-192471ISBN: 78-91-7729-101-5OAI: diva2:968786
Public defence
2016-10-10, Sal C, Electrum, Kista, 13:00 (English)

QC 20160919

Available from: 2016-09-19 Created: 2016-09-12 Last updated: 2016-09-30Bibliographically approved

Open Access in DiVA

fulltext(1787 kB)17 downloads
File information
File name FULLTEXT03.pdfFile size 1787 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Kalavri, Vasiliki
By organisation
Software and Computer systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 93 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 244 hits
ReferencesLink to record
Permanent link

Direct link