Combining Local and Global Features to Reduce 2-Hop Label Size of Directed Acyclic Graphs


Jinhyun Ahn, Dong-Hyuk Im, Journal of Information Processing Systems Vol. 16, No. 1, pp. 201-209, Feb. 2020

10.3745/JIPS.04.0159
Keywords: Degree, Directed Acyclic Graphs, Topological Sort, 2-Hop Label
Fulltext:

Abstract

The graph data structure is popular because it can intuitively represent real-world knowledge. Graph databases have attracted attention in academia and industry because they can be used to maintain graph data and allow users to mine knowledge. Mining reachability relationships between two nodes in a graph, termed reachability query processing, is an important functionality of graph databases. Online traversals, such as the breadth-first and depth-first search, are inefficient in processing reachability queries when dealing with large-scale graphs. Labeling schemes have been proposed to overcome these disadvantages. The state-of-the-art is the 2-hop labeling scheme: each node has in and out labels containing reachable node IDs as integers. Unfortunately, existing 2-hop labeling schemes generate huge 2-hop label sizes because they only consider local features, such as degrees. In this paper, we propose a more efficient 2-hop label size reduction approach. We consider the topological sort index, which is a global feature. A linear combination is suggested for utilizing both local and global features. We conduct experiments over real-world and synthetic directed acyclic graph datasets and show that the proposed approach generates smaller labels than existing approaches.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from November 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Jinhyun Ahn and Dong-Hyuk Im (2020). Combining Local and Global Features to Reduce 2-Hop Label Size of Directed Acyclic Graphs. Journal of Information Processing Systems, 16(1), 201-209. DOI: 10.3745/JIPS.04.0159.

[IEEE Style]
J. Ahn and D. Im, "Combining Local and Global Features to Reduce 2-Hop Label Size of Directed Acyclic Graphs," Journal of Information Processing Systems, vol. 16, no. 1, pp. 201-209, 2020. DOI: 10.3745/JIPS.04.0159.

[ACM Style]
Jinhyun Ahn and Dong-Hyuk Im. 2020. Combining Local and Global Features to Reduce 2-Hop Label Size of Directed Acyclic Graphs. Journal of Information Processing Systems, 16, 1, (2020), 201-209. DOI: 10.3745/JIPS.04.0159.