Graph databases are increasingly used for RDF(Resource Description Framework) data management. Mining reachability relationships between resources is one of important building blocks for graph databases. Reachability relationships in a graph and its corresponding directed acyclic graph(DAG) are equivalent when we focus on reachability alone, which allows to focus on DAGs in this thesis. Diverse labeling schemes have been proposed to e ciently determine the reachability of DAGs. We focus on a state-of-the-art 2-hop labeling scheme that is based on a permutation of vertices to achieve a linear index size and reduce on-line searches that are required when the reachability cannot be answered by 2-hop labels only. We observed that the approach can be improved in three di erent ways; 1) space-e ciency guarantee the minimized index size without randomness 2) update-e ciency update labels e ciently when graphs changes 3) parallelization labeling should be cluster-based, and solved in a distributed fashion. In these regards, this PhD thesis proposes optimization techniques that address these issues. In this paper in particular, a way of reducing the 2-hop label size is proposed with preliminary results on real-world DAG datasets. In addition, we will discuss the feasibilities of the other issues based on our on-going works.
A 2-hop labeling scheme of a DAG is to label each vertex v with a pair (Lout(v),
Lin(v)), where Lout(v) is a set of vertices that v can reach and Lin(v) is a set
of vertices reachable from v [
2-hop Labeling based on Independent Permutation (IP) Let G(V; E) be a DAG with V as a set of vertices and E as a set of edges pairing two vertices. u ↝ v is used to denote that u can reach v, and u v, otherwise. A permutation of V is a bijection denoted as ∶ V Ð→ V . Given G and a positive integer k, IP ࢜ ߪ ሺ࢜ሻ ࡸ ࢛࢚ ࢜ሻሺ ࡸ ሺ࢜ሻ
࢜ ߪ ሺ࢜ሻ ࡸ ࢛࢚ ሺ࢜ሻ ࡸ ሺ࢜ሻ randomly generates and then outputs the 2-hop index Ik ∶ V Ð→ H, where H is a set of pairs (Lout(v); Lin(v)) de ned as:
Lout(v) = mink{ (u)Sv ↝ u}
Lin(v) = mink{ (u)Su ↝ v} , where mink{A} is a sub-set of A, such that Ai < Aj if i < j and Smink{A}S ≤ k. In other words, mink{A} contains the k smallest integers in A.
In the original version of IP, is randomly generated using the Knuth shu e algorithm. We argue that the randomized way of generating a permutation is unable to ensure that the minimized size of index is obtained. Therefore, we de ne the rst problem that generates a space-e cient permutation de ned in De nition 1.
De nition 1. Space-e cient Permutation Given G(V; E) and a positive integer k, output such that
1 argmin size(Ik(V )) ∶= SV S v∈V
Q space(Lout(v)) + space(Lin(v)) , where space(L) is the space requirements for a set L of integers, which can be de ned according to the application requirements.
An illustrative example that shows the e ect of on the index size is depicted in Fig. 1, where we assume space(L) = ∑w∈L w to see the index size di erence for the very small DAG.
Linked Open Data1(LOD) evolves over time [
De nition 2. Update-e cient Permutation Assume we already have Gt(Vt; Et) and its 2-hop index Ik(Vt). Given Gt+1(Vt+1; Et+1), generate a new permutation t+1 such that × S{v ∈ Vt
Vt+1SIkt (v) ≠ I t+1 (v)}S + k × size(Ikt+1 (Vt+1))
Meanwhile, existing 2-hop labeling algorithms running on a single machine are not e cient enough to address the above problems for massive DAGs. Our third problem is thus to devise a cluster-based 2-hop labeling algorithm that supports De nition 1 and 2.
argmin
t+1
, where
≥ 0,
Reachability relationships in a graph and its corresponding DAG are equivalent,
since a graph can be transformed into a DAG by condensing every strongly
connected component(SCC) into a single vertex and retaining edges between
vertices in SCC and the other vertices that are connected to SCC [
There are extensive studies on labeling of DAGs for reachability queries
processing [
Recently, a state-of-the-art variation of 2-hop labeling has been proposed
in [
The research objective is to optimize the IP labeling [
1) Is it possible to deterministically choose a permutation of V that best minimizes the index size? Because the number of candidate permutations is n!, a brute-force algorithm is not feasible. One may choose a permutation by sorting V using a topological sort. Smaller numbers are assigned to vertices having more reachable vertices. It can be expected that this method allows Lin(v) to have smaller numbers. However, conversely, Lout(v) would have large numbers, o setting smaller size of Lin(v). A more sophisticated technique is required.
2) When a new vertex vnew is added to a DAG Gt(Vt; Et) that has already been labeled by t, which number should be assigned to t+1(vnew)? The simplest way is to make t+1(vnew) = max( t(Vt)) + 1. However, with this approach, the minimized index size is not always ensured.
3) In order to do 2-hop labeling in a cluster, when vertices are distributed, how can we know reachable vertices from a vertex? Given a set M of machines, we may distribute a subset Vi of V to a machine Mi and then perform labeling independently. The challenge is to obtain Lin(v) and Lout(v) for a vertex v ∈ Vi residing in Mi whereas some o ∈ Lin(v) ⋃ Lout(v) have been distributed to the other machines Mj , such that i ≠ j. 5
Several hypotheses regarding research questions are stated as follows. { If smaller numbers are assigned to 2-hop index size is reduced.
(v) because v has more edges, then the { The reachability query processing performance increases as index size is reduced. { If 2-hop labeling is carried out in a cluster, then the index construction and update would be faster than existing single machine based algorithms are. 6
To prove the rst hypotheses, we rst compute the degree of each of the vertices in V and then sort V in decreasing order by degree. The order is regarded as the desired permutation (V ) as follows.
(v) = i , where v is the i-th element in V degree such that V degree is a sorted set of V , sorted by decreasing degree of v.
In other words, the more degrees v has, the smaller the number assigned to v . This is derived by an expectation that if v has many edges, v is likely ( ) to become a reachable vertex from another vertex. The overall 2-hop index size could be reduced by making (v) smaller. Note that the current approach does not take into account the parameter k. We plan to introduce the parameter k to guarantee a reduced index size for arbitrary k.
Regarding a cluster-based algorithm, we are motivated by the approach in [
We implemented the rst proposed approach based on the source codes provided by the authors of IP2. The proposed approach (denoted as IP adv) is evaluated compared with the original approach (IP) and baseline (IP x). IP generates a 2 http://www1.se.cuhk.edu.hk/˜hwei/source/IP.zip 1 2 3 4 5 6 7 8 9 10 random permutation, which means that a di erent index is constructed for each run. IP x is based on the identity permutation such that (v) = j, where v is the j-th element in V . All the experiments were conducted on a machine with a 2.4 GHz CPU and 40 GB of RAM. We downloaded the real-world DAG datasets3. Statistics of the datasets are listed in Table 1.
The index sizes for each dataset are plotted in Fig. 2. The index size by IP adv and IP x are compared with the index sizes generated by 10 runs of IP. For each run, only IP showed the di erent index size due to its random nature. IP adv showed the best performance for all datasets. For small datasets with large degrees such as arxiv and pubmed, relatively small improvements are observed. For large datasets, we observed relatively large improvements, except 3 https://code.google.com/archive/p/ferrari-index/downloads for citeseer and yago. It can be seen in Table 1 that these datasets have relatively small median degrees. Since IP adv is based on degrees, too small or too large degrees would not signi cantly contribute to a reduction in the index size. In future works, we plan to utilize more graph metrics to work better against such datasets. 8
We plan to collect LOD datasets and then transform them into DAGs by
condensing SCC. Synthetic DAG datasets will also be considered, varying graph
metrics such as in/out-degree, diameter, and vertices with no ancestors or
descendants. In particular, several releases of DBpedia datasets4 will be collected
in order to evaluate the performance of updating the index. To examine the pros
and cons of our approach in greater details, we will compare it to a number
of notable existing approaches such as [
It remains a challenge to apply graph reachability indexing techniques to very
large sets of LOD. In this paper, we showed that simple graph metrics can
be exploited to reduce the index size. By improving the proposed approach
further, it will become more applicable to LOD. Another characteristic of LOD
is that it changes over time. We have some experience on scalable RDF change
detection [
I would like to acknowledge my advisors, Hong-Gee Kim (Seoul National University) and Dong-Hyuk Im (Hoseo University). This work was supported by Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No. R0101-16-0054, WiseKB: Big data based self-evolving knowledge base and reasoning platform). 4 http://wiki.dbpedia.org/services-resources/datasets/ previous-releases