Loading...
Edge labeling schemes for graph data
Goonetilleke, Oshini Koutra, Danai Sellis, Timos Liao, Kewen
Goonetilleke, Oshini
Koutra, Danai
Sellis, Timos
Liao, Kewen
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 significantly improved query I/O performance, including with indexes built on directed attributed edges. This ultimately leads to faster execution of neighborhood-related edge queries.
Keywords
Date
2017
Type
Conference item
Journal
Proceedings of the 29th International Conference on Scientific and Statistical Database Management (SSDBM '17 )
Book
Volume
Issue
Page Range
1-12
Article Number
ACU Department
Peter Faber Business School
Faculty of Law and Business
Faculty of Law and Business
Collections
Relation URI
Source URL
Event URL
Open Access Status
License
File Access
Controlled