Edge importance identification for energy efficient graph processing

S. M. Faisal, G. Tziantzioulis, A. M. Gok, N. Hardavellas, S. Ogrenci-Memik, S. Parthasarathy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Modern graphs are large, often containing billions of nodes and edges that demand huge amount of processing for analysis purposes. The algorithms processing these graphs often run for long time and consume substantial amount of energy. However, not all edges in the graphs are equally important. Some edges play critical role in maintaining the community and other interesting structures in the graph, while the rest are less important for analysis. Identifying edges as important and unimportant allows one to apply elastic fidelity computing when processing edges of low importance, hence saving significant amount of energy while processing large graphs. In this paper we propose a novel technique for identifying important edges in a graph using a fast method that exploits locality sensitive hashing. We then propose a framework for energy-efficient computing that applies elastic fidelity computing when processing edges of low importance and applies full fidelity computing when processing important edges. This allows the framework to deliver good results while saving energy when processing a large number of low-importance edges. Our proposed technique reduces the power consumption by 3-30% while still producing results that are within acceptable range of the full-accuracy results.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015
EditorsFeng Luo, Kemafor Ogan, Mohammed J. Zaki, Laura Haas, Beng Chin Ooi, Vipin Kumar, Sudarsan Rachuri, Saumyadipta Pyne, Howard Ho, Xiaohua Hu, Shipeng Yu, Morris Hui-I Hsiao, Jian Li
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages347-354
Number of pages8
ISBN (Electronic)9781479999255
DOIs
StatePublished - Dec 22 2015
Event3rd IEEE International Conference on Big Data, IEEE Big Data 2015 - Santa Clara, United States
Duration: Oct 29 2015Nov 1 2015

Publication series

NameProceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015

Other

Other3rd IEEE International Conference on Big Data, IEEE Big Data 2015
CountryUnited States
CitySanta Clara
Period10/29/1511/1/15

Fingerprint

Processing
Energy conservation
Electric power utilization

Keywords

  • Algorithm
  • Energy Efficient Computing
  • Graph

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Software

Cite this

Faisal, S. M., Tziantzioulis, G., Gok, A. M., Hardavellas, N., Ogrenci-Memik, S., & Parthasarathy, S. (2015). Edge importance identification for energy efficient graph processing. In F. Luo, K. Ogan, M. J. Zaki, L. Haas, B. C. Ooi, V. Kumar, S. Rachuri, S. Pyne, H. Ho, X. Hu, S. Yu, M. H-I. Hsiao, ... J. Li (Eds.), Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015 (pp. 347-354). [7363775] (Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2015.7363775
Faisal, S. M. ; Tziantzioulis, G. ; Gok, A. M. ; Hardavellas, N. ; Ogrenci-Memik, S. ; Parthasarathy, S. / Edge importance identification for energy efficient graph processing. Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015. editor / Feng Luo ; Kemafor Ogan ; Mohammed J. Zaki ; Laura Haas ; Beng Chin Ooi ; Vipin Kumar ; Sudarsan Rachuri ; Saumyadipta Pyne ; Howard Ho ; Xiaohua Hu ; Shipeng Yu ; Morris Hui-I Hsiao ; Jian Li. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 347-354 (Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015).
@inproceedings{f740ef33a07f4e4a8c3e893e4b45aa11,
title = "Edge importance identification for energy efficient graph processing",
abstract = "Modern graphs are large, often containing billions of nodes and edges that demand huge amount of processing for analysis purposes. The algorithms processing these graphs often run for long time and consume substantial amount of energy. However, not all edges in the graphs are equally important. Some edges play critical role in maintaining the community and other interesting structures in the graph, while the rest are less important for analysis. Identifying edges as important and unimportant allows one to apply elastic fidelity computing when processing edges of low importance, hence saving significant amount of energy while processing large graphs. In this paper we propose a novel technique for identifying important edges in a graph using a fast method that exploits locality sensitive hashing. We then propose a framework for energy-efficient computing that applies elastic fidelity computing when processing edges of low importance and applies full fidelity computing when processing important edges. This allows the framework to deliver good results while saving energy when processing a large number of low-importance edges. Our proposed technique reduces the power consumption by 3-30{\%} while still producing results that are within acceptable range of the full-accuracy results.",
keywords = "Algorithm, Energy Efficient Computing, Graph",
author = "Faisal, {S. M.} and G. Tziantzioulis and Gok, {A. M.} and N. Hardavellas and S. Ogrenci-Memik and S. Parthasarathy",
year = "2015",
month = "12",
day = "22",
doi = "10.1109/BigData.2015.7363775",
language = "English (US)",
series = "Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "347--354",
editor = "Feng Luo and Kemafor Ogan and Zaki, {Mohammed J.} and Laura Haas and Ooi, {Beng Chin} and Vipin Kumar and Sudarsan Rachuri and Saumyadipta Pyne and Howard Ho and Xiaohua Hu and Shipeng Yu and Hsiao, {Morris Hui-I} and Jian Li",
booktitle = "Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015",
address = "United States",

}

Faisal, SM, Tziantzioulis, G, Gok, AM, Hardavellas, N, Ogrenci-Memik, S & Parthasarathy, S 2015, Edge importance identification for energy efficient graph processing. in F Luo, K Ogan, MJ Zaki, L Haas, BC Ooi, V Kumar, S Rachuri, S Pyne, H Ho, X Hu, S Yu, MH-I Hsiao & J Li (eds), Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015., 7363775, Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015, Institute of Electrical and Electronics Engineers Inc., pp. 347-354, 3rd IEEE International Conference on Big Data, IEEE Big Data 2015, Santa Clara, United States, 10/29/15. https://doi.org/10.1109/BigData.2015.7363775

Edge importance identification for energy efficient graph processing. / Faisal, S. M.; Tziantzioulis, G.; Gok, A. M.; Hardavellas, N.; Ogrenci-Memik, S.; Parthasarathy, S.

Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015. ed. / Feng Luo; Kemafor Ogan; Mohammed J. Zaki; Laura Haas; Beng Chin Ooi; Vipin Kumar; Sudarsan Rachuri; Saumyadipta Pyne; Howard Ho; Xiaohua Hu; Shipeng Yu; Morris Hui-I Hsiao; Jian Li. Institute of Electrical and Electronics Engineers Inc., 2015. p. 347-354 7363775 (Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Edge importance identification for energy efficient graph processing

AU - Faisal, S. M.

AU - Tziantzioulis, G.

AU - Gok, A. M.

AU - Hardavellas, N.

AU - Ogrenci-Memik, S.

AU - Parthasarathy, S.

PY - 2015/12/22

Y1 - 2015/12/22

N2 - Modern graphs are large, often containing billions of nodes and edges that demand huge amount of processing for analysis purposes. The algorithms processing these graphs often run for long time and consume substantial amount of energy. However, not all edges in the graphs are equally important. Some edges play critical role in maintaining the community and other interesting structures in the graph, while the rest are less important for analysis. Identifying edges as important and unimportant allows one to apply elastic fidelity computing when processing edges of low importance, hence saving significant amount of energy while processing large graphs. In this paper we propose a novel technique for identifying important edges in a graph using a fast method that exploits locality sensitive hashing. We then propose a framework for energy-efficient computing that applies elastic fidelity computing when processing edges of low importance and applies full fidelity computing when processing important edges. This allows the framework to deliver good results while saving energy when processing a large number of low-importance edges. Our proposed technique reduces the power consumption by 3-30% while still producing results that are within acceptable range of the full-accuracy results.

AB - Modern graphs are large, often containing billions of nodes and edges that demand huge amount of processing for analysis purposes. The algorithms processing these graphs often run for long time and consume substantial amount of energy. However, not all edges in the graphs are equally important. Some edges play critical role in maintaining the community and other interesting structures in the graph, while the rest are less important for analysis. Identifying edges as important and unimportant allows one to apply elastic fidelity computing when processing edges of low importance, hence saving significant amount of energy while processing large graphs. In this paper we propose a novel technique for identifying important edges in a graph using a fast method that exploits locality sensitive hashing. We then propose a framework for energy-efficient computing that applies elastic fidelity computing when processing edges of low importance and applies full fidelity computing when processing important edges. This allows the framework to deliver good results while saving energy when processing a large number of low-importance edges. Our proposed technique reduces the power consumption by 3-30% while still producing results that are within acceptable range of the full-accuracy results.

KW - Algorithm

KW - Energy Efficient Computing

KW - Graph

UR - http://www.scopus.com/inward/record.url?scp=84963777219&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963777219&partnerID=8YFLogxK

U2 - 10.1109/BigData.2015.7363775

DO - 10.1109/BigData.2015.7363775

M3 - Conference contribution

AN - SCOPUS:84963777219

T3 - Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015

SP - 347

EP - 354

BT - Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015

A2 - Luo, Feng

A2 - Ogan, Kemafor

A2 - Zaki, Mohammed J.

A2 - Haas, Laura

A2 - Ooi, Beng Chin

A2 - Kumar, Vipin

A2 - Rachuri, Sudarsan

A2 - Pyne, Saumyadipta

A2 - Ho, Howard

A2 - Hu, Xiaohua

A2 - Yu, Shipeng

A2 - Hsiao, Morris Hui-I

A2 - Li, Jian

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Faisal SM, Tziantzioulis G, Gok AM, Hardavellas N, Ogrenci-Memik S, Parthasarathy S. Edge importance identification for energy efficient graph processing. In Luo F, Ogan K, Zaki MJ, Haas L, Ooi BC, Kumar V, Rachuri S, Pyne S, Ho H, Hu X, Yu S, Hsiao MH-I, Li J, editors, Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 347-354. 7363775. (Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015). https://doi.org/10.1109/BigData.2015.7363775