On effective and efficient graph edge labeling

Oshini Goonetilleke, Danai Koutra, Kewen Liao, Timos Sellis

Research output: Contribution to journalArticle

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 Dive into the research topics of 'On effective and efficient graph edge labeling'. Together they form a unique fingerprint.

  • Cite this