Goonetilleke, O., Koutra, D., Sellis, T. & Liao, K. (2017). Edge labeling schemes for graph data. Proceedings of the 29th International Conference on Scientific and Statistical Database Management (SSDBM '17 ), 1-12. United States of America: Association for Computing Machinery. Retrieved from https://doi.org/10.1145/3085504.3085516
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.
Peter Faber Business School
Access may be restricted.