On effective and efficient graph edge labeling
Journal article
Goonetilleke, Oshini, Koutra, Danai, Liao, Kewen and Sellis, Timos. (2019). On effective and efficient graph edge labeling. Distributed and Parallel Databases. 37(1), pp. 5-38. https://doi.org/10.1007/s10619-018-7234-4
Authors | Goonetilleke, Oshini, Koutra, Danai, Liao, Kewen and Sellis, Timos |
---|---|
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 | edge labeling; consecutiveness; query processing |
Year | 2019 |
Journal | Distributed and Parallel Databases |
Journal citation | 37 (1), pp. 5-38 |
Publisher | Springer New York LLC |
ISSN | 0926-8782 |
Digital Object Identifier (DOI) | https://doi.org/10.1007/s10619-018-7234-4 |
Scopus EID | 2-s2.0-85051627165 |
Research or scholarly | Research |
Page range | 5-38 |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 09 Aug 2019 |
Publication process dates | |
Deposited | 21 Dec 2021 |
https://acuresearchbank.acu.edu.au/item/8x3v3/on-effective-and-efficient-graph-edge-labeling
Restricted files
Publisher's version
83
total views0
total downloads0
views this month0
downloads this month