On effective and efficient graph edge labeling

Oshini Goonetilleke, Danai Koutra, Kewen Liao, Timos Sellis

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Graphs, such as social, road and information networks, are ubiquitous as they naturally model entities and their relationships. Many query processing tasks on graphs are concerned about efficiently accessing nodes and edges stored in some order on disk or main memory. A natural following question we focus on here is: given a directed graph, how should we label/order its edges to achieve better disk locality and support various neighborhood queries efficiently? We answer this question by introducing two edge-labeling schemes, GrdRandom and FlipInOut, that label edges with natural number ordering based on the premise that edges should be assigned integer identifiers exploiting their consecutiveness to a maximum degree. We conduct extensive experimental analysis on real-world graphs, and compare our proposed schemes with various baseline labeling methods. We demonstrate that our methods are efficient and result in significantly improved query I/O performance. Finally, we propose an effective streaming graph partitioning method, FlipCut, which leverages the FlipInOut edge labeling.

Original languageEnglish
Pages (from-to)5-38
Number of pages34
JournalDistributed and Parallel Databases
Volume37
Issue number1
Early online date9 Aug 2018
DOIs
Publication statusPublished - 1 Mar 2019
Externally publishedYes

Fingerprint

Labeling
Labels
Query processing
Directed graphs
Data storage equipment
Graph
Query

Cite this

Goonetilleke, Oshini ; Koutra, Danai ; Liao, Kewen ; Sellis, Timos. / On effective and efficient graph edge labeling. In: Distributed and Parallel Databases. 2019 ; Vol. 37, No. 1. pp. 5-38.
@article{85e9f83342b2402da18d3b12fbdca0b3,
title = "On effective and efficient graph edge labeling",
abstract = "Graphs, such as social, road and information networks, are ubiquitous as they naturally model entities and their relationships. Many query processing tasks on graphs are concerned about efficiently accessing nodes and edges stored in some order on disk or main memory. A natural following question we focus on here is: given a directed graph, how should we label/order its edges to achieve better disk locality and support various neighborhood queries efficiently? We answer this question by introducing two edge-labeling schemes, GrdRandom and FlipInOut, that label edges with natural number ordering based on the premise that edges should be assigned integer identifiers exploiting their consecutiveness to a maximum degree. We conduct extensive experimental analysis on real-world graphs, and compare our proposed schemes with various baseline labeling methods. We demonstrate that our methods are efficient and result in significantly improved query I/O performance. Finally, we propose an effective streaming graph partitioning method, FlipCut, which leverages the FlipInOut edge labeling.",
keywords = "Consecutiveness, Edge labeling, Query processing",
author = "Oshini Goonetilleke and Danai Koutra and Kewen Liao and Timos Sellis",
year = "2019",
month = "3",
day = "1",
doi = "10.1007/s10619-018-7234-4",
language = "English",
volume = "37",
pages = "5--38",
journal = "Distributed and Parallel Databases",
issn = "0926-8782",
publisher = "Springer Netherlands",
number = "1",

}

Goonetilleke, O, Koutra, D, Liao, K & Sellis, T 2019, 'On effective and efficient graph edge labeling' Distributed and Parallel Databases, vol. 37, no. 1, pp. 5-38. https://doi.org/10.1007/s10619-018-7234-4

On effective and efficient graph edge labeling. / Goonetilleke, Oshini; Koutra, Danai; Liao, Kewen; Sellis, Timos.

In: Distributed and Parallel Databases, Vol. 37, No. 1, 01.03.2019, p. 5-38.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - On effective and efficient graph edge labeling

AU - Goonetilleke, Oshini

AU - Koutra, Danai

AU - Liao, Kewen

AU - Sellis, Timos

PY - 2019/3/1

Y1 - 2019/3/1

N2 - Graphs, such as social, road and information networks, are ubiquitous as they naturally model entities and their relationships. Many query processing tasks on graphs are concerned about efficiently accessing nodes and edges stored in some order on disk or main memory. A natural following question we focus on here is: given a directed graph, how should we label/order its edges to achieve better disk locality and support various neighborhood queries efficiently? We answer this question by introducing two edge-labeling schemes, GrdRandom and FlipInOut, that label edges with natural number ordering based on the premise that edges should be assigned integer identifiers exploiting their consecutiveness to a maximum degree. We conduct extensive experimental analysis on real-world graphs, and compare our proposed schemes with various baseline labeling methods. We demonstrate that our methods are efficient and result in significantly improved query I/O performance. Finally, we propose an effective streaming graph partitioning method, FlipCut, which leverages the FlipInOut edge labeling.

AB - Graphs, such as social, road and information networks, are ubiquitous as they naturally model entities and their relationships. Many query processing tasks on graphs are concerned about efficiently accessing nodes and edges stored in some order on disk or main memory. A natural following question we focus on here is: given a directed graph, how should we label/order its edges to achieve better disk locality and support various neighborhood queries efficiently? We answer this question by introducing two edge-labeling schemes, GrdRandom and FlipInOut, that label edges with natural number ordering based on the premise that edges should be assigned integer identifiers exploiting their consecutiveness to a maximum degree. We conduct extensive experimental analysis on real-world graphs, and compare our proposed schemes with various baseline labeling methods. We demonstrate that our methods are efficient and result in significantly improved query I/O performance. Finally, we propose an effective streaming graph partitioning method, FlipCut, which leverages the FlipInOut edge labeling.

KW - Consecutiveness

KW - Edge labeling

KW - Query processing

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

U2 - 10.1007/s10619-018-7234-4

DO - 10.1007/s10619-018-7234-4

M3 - Article

VL - 37

SP - 5

EP - 38

JO - Distributed and Parallel Databases

JF - Distributed and Parallel Databases

SN - 0926-8782

IS - 1

ER -