Edge labeling schemes for graph data

Oshini Goonetilleke, Timos Sellis, Danai Koutra, Kewen Liao

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

Given a directed graph, how should we label both its outgoing and incoming edges to achieve better disk locality and support neighborhood-related edge queries? In this paper, we answer this question with edge-labeling schemes GrdRandom and FlipInOut, to label edges with integers based on the premise that edges should be assigned integer identifiers exploiting their consecutiveness to a maximum degree. We provide extensive experimental analysis on real-world graphs, and compare our proposed schemes with other labeling methods based on assigning edge IDs in the order of insertion or even randomly, as traditionally done. We show that our methods are efficient and result in signiicantly improved query I/O performance, including with indexes built on directed attributed edges. This ultimately leads to faster execution of neighborhood-related edge queries.

Original languageEnglish
Title of host publicationSSDBM 2017
Subtitle of host publication29th International Conference on Scientific and Statistical Database Management
PublisherAssociation for Computing Machinery (ACM)
Number of pages12
VolumePart F128636
ISBN (Electronic)9781450352826
DOIs
Publication statusPublished - Jun 2017
Externally publishedYes
Event29th International Conference on Scientific and Statistical Database Management, SSDBM 2017 - Chicago, United States
Duration: 27 Jun 201729 Jun 2017

Conference

Conference29th International Conference on Scientific and Statistical Database Management, SSDBM 2017
CountryUnited States
CityChicago
Period27/06/1729/06/17

Fingerprint Dive into the research topics of 'Edge labeling schemes for graph data'. Together they form a unique fingerprint.

  • Cite this

    Goonetilleke, O., Sellis, T., Koutra, D., & Liao, K. (2017). Edge labeling schemes for graph data. In SSDBM 2017: 29th International Conference on Scientific and Statistical Database Management (Vol. Part F128636). [a12] Association for Computing Machinery (ACM). https://doi.org/10.1145/3085504.3085516