Edge labeling schemes for graph data

Conference item


Goonetilleke, Oshini, Koutra, Danai, Sellis, Timos and Liao, Kewen. (2017) Edge labeling schemes for graph data. 29th International Conference on Scientific and Statistical Database Management. United States of America: Association for Computing Machinery. pp. 1 - 12 https://doi.org/10.1145/3085504.3085516
AuthorsGoonetilleke, Oshini, Koutra, Danai, Sellis, Timos and 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.

Year2017
JournalProceedings of the 29th International Conference on Scientific and Statistical Database Management (SSDBM '17 )
PublisherAssociation for Computing Machinery
Digital Object Identifier (DOI)https://doi.org/10.1145/3085504.3085516
Publisher's version
File Access Level
Controlled
Page range1 - 12
Research GroupPeter Faber Business School
Place of publicationUnited States of America
Permalink -

https://acuresearchbank.acu.edu.au/item/85948/edge-labeling-schemes-for-graph-data

Restricted files

Publisher's version

  • 1
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month
These values are for the period from 19th October 2020, when this repository was created.

Export as

Related outputs

Temporal betweenness centrality in dynamic graphs
Tsalouchidou, Ioanna, Baeza-Yates, Ricardo, Bonchi, Francesco, Liao, Kewen and Sellis, Timos. (2020) Temporal betweenness centrality in dynamic graphs. International Journal of Data Science and Analytics. 9(3), pp. 257 - 272. https://doi.org/10.1007/s41060-019-00189-x
Contextual community search over large social networks
Chen, Lu, Liu, Chengfei, Liao, Kewen, Li, Jianxin and Zhou, Rui. (2019) Contextual community search over large social networks. 35th International Conference on Data Engineering (ICDE). Macao, China: IEEE Computer Society. pp. 88 - 99 https://doi.org/10.1109/ICDE.2019.00017
A fast algorithm for optimally finding partially disjoint shortest paths
Guo, Longkun, Deng, Yunyun, Liao, Kewen, He, Qiang, Sellis, Timos and Hu, Zheshan. (2018) A fast algorithm for optimally finding partially disjoint shortest paths. Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), Stockholm, Sweden, July 13-19, 2018. Stockholm, Sweden: International Joint Conferences on Artificial Intelligence. pp. 1456 - 1462 https://doi.org/10.24963/ijcai.2018/202
A cost model for long-term compressed data retention
Liao, Kewen, Moffat, Alistair, Petri, Matthias and Wirth, Anthony. (2017) A cost model for long-term compressed data retention. 10th International Conference on Web Search and Data Mining. United States of America: Association for Computing Machinery. pp. 241 - 249 https://doi.org/10.1145/3018661.3018738
Effective construction of relative Lempel-Ziv dictionaries
Liao, Kewen, Petri, Matthias, Moffat, Alistair and Wirth, Anthony. (2016) Effective construction of relative Lempel-Ziv dictionaries. WWW '16: 25th International World Wide Web Conference. Switzerland: Association for Computing Machinery. pp. 807 - 816 https://doi.org/10.1145/2872427.2883042
Effect of off-zenith observations on reducing the impact of precipitation on ground-based microwave radiometer measurement accuracy
Xu, Guirong, Stick Ware, Randolph, Zhang, Wengang, Feng, Guangliu, Liao, Kewen and Liu, Yibing. (2014) Effect of off-zenith observations on reducing the impact of precipitation on ground-based microwave radiometer measurement accuracy. Atmospheric Research. 140-141, pp. 85 - 94. https://doi.org/10.1016/j.atmosres.2014.01.021