Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Asymmetry in large-scale graph analysis, explained
Show others and affiliations
2014 (English)In: 2nd International Workshop on Graph Data Management Experiences and Systems, GRADES 2014 - Co-located with SIGMOD/PODS 2014, Association for Computing Machinery (ACM), 2014Conference paper, (Refereed)
Abstract [en]

Iterative computations are in the core of large-scale graph processing. In these applications, a set of parameters is continuously refined, until a fixed point is reached. Such fixed point iterations often exhibit non-uniform computational behavior, where changes propagate with different speeds throughout the parameter set, making them active or inactive during iterations. This asymmetrical behavior can lead to a many redundant computations, if not exploited. Many specialized graph processing systems and APIs exist that run iterative algorithms efficiently exploiting this asymmetry. However, their functionality is sometimes vaguely defined and due to their different programming models and terminology used, it is often challenging to derive equivalence between them. We describe an optimization framework for iterative graph processing, which utilizes dataset dependencies. We explain several optimization techniques that exploit asymmetrical behavior of graph algorithms. We formally specify the conditions under which, an algorithm can use a certain technique. We also design template execution plans, using a canonical set of dataflow operators and we evaluate them using real-world datasets and applications. Our experiments show that optimized plans can significantly reduce execution time, often by an order of magnitude. Based on our experiments, we identify a trade-off that can be easily captured and could serve as the basis for automatic optimization of large-scale graph-processing applications.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2014.
Keyword [en]
Algorithms, Experiments, Information management, Automatic optimization, Fixed point iteration, Iterative algorithm, Iterative computation, Optimization framework, Optimization techniques, Real-world datasets, Redundant computation, Iterative methods
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-207258Scopus ID: 2-s2.0-85011660619ISBN: 9781450329828 (electronic)OAI: oai:DiVA.org:kth-207258DiVA: diva2:1115589
Conference
2nd International Workshop on Graph Data Management Experiences and Systems, GRADES 2014 - Co-located with SIGMOD/PODS 2014, 22 June 2014 through 27 June 2014, Snowbird, UT
Note

QC 20170627

Available from: 2017-06-27 Created: 2017-06-27 Last updated: 2017-06-27Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Kalavri, VasilikiVlassov, VladimirHaridi, Seif
By organisation
Software and Computer systems, SCS
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

Total: 1 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf