日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

Eﬃcient Query Evaluation on Distributed
Graph with Hadoop Environment
Le-Duc Tung, Quyet Nguyen-Van, Zhenjiang HuGraph has emerged as a powerful data structure to describe the variety of data. Query evaluation on
distributed graphs takes much cost due to the complexity of links among sites. Dan Suciu has proposed
algorithms for query evaluation on semi-structured data which is a rooted, edge-labeled graph, the algorithms are proved to be eﬃcient in term of communication steps and data transferring during the evaluation.
However, the disadvantage is that communication data are collected to one single site, this leads to a bottleneck in the evaluation for real-life data. In this paper, we propose two algorithms to improve Dan Suciu’s
algorithms: one algorithm is to significantly reduce a large amount of redundant data in the evaluation,
named one-step evaluation, and the other is to resolve the bottleneck with the amount of data transferring
via network being linear. We also design an eﬃcient implementation with only one MapReduce job for ouralgorithms in Hadoop environment by utilizing highlight features of Hadoop file system. Experiments on
cloud system show that our algorithms can detect and remove 50% of data being redundant in the evaluation
process on YouTube and DBLP datasets. Besides, experimental results also show that our algorithms isrunning without the bottleneck even when we double the size of input data.

tributed graph, consider simple graph queries de-

1 Introduction
Currently, graphs are ubiquitous.

fined in terms of regular expressions [6]. The proThe world

cess of evaluating a query is to find paths in thewide web is a graph whose nodes correspond tograph that satisfies the regular expression, and re-static pages, and whose edges correspond to links

turn nodes and edges relating to that paths. There-

between these pages [3]. Social network graph con-fore, query evaluation on a centralized graph is ef-

sists of edges denoting many complex relationships

ficiently performed by DFS/BFS algorithms. How-

[7] [13]. Despite of the popular of graph, there are

ever, with a distributed graph, query evaluation isstill not so many research studies focusing on query

more diﬃcult in the sense that the amount of data

evaluation on distributed graph whose nodes andtransferred via network in the evaluation process isedges are distributed on diﬀerent sites.

large. The reason is that on each site we just have

To see the diﬃculties of query evaluation on disLe-Duc Tung, 総合研究大学院大学（総研大), Dept. ofInformatics, The Graduate University for Advanced
Studies (SOKENDAI).
Quyet Nguyen-Van, Hung Yen University of Technology and Education, Vietnam.
Zhenjiang Hu, 国立情報学研究所, Programming Research Laboratory, Information Systems Architecture Research Division, National Institute of Informatics (NII).

the local information of the graph, hence sites haveto communicate and exchange a lot of information
with others.
Dan Suciu [12] has proposed an eﬃcient algorithm to evaluate query on distributed graph with
distinguished properties as follows:• The number of communication steps is four(independent on the data or query).

• The total amount of data exchanged during communications has size of O(n2 ) + O(r),where n denotes the number of cross-links(edges between two nodes at two diﬀerent sites)in distributed database, r the size of the resultof query.
However, in Dan Suciu’s algorithms the amountof data O(n2 ) are sent to only one site to process.
This results in a bottleneck in the algorithm whenevaluating on social graphs where the number ofcross-links is quickly increasing [8]. In this paper,
we show an approach to overcoming this bottleneckwith following contributions:• We improve Dan Suciu’s algorithm so that we
can remove a large number of redundant nodes
and edges in the evaluation (Session 3. 1), andreduce the total amount of data transferring

Figure 1

A graph of Youtube’s data. The red

via network to O(|N | × |S| × |P |), where |N |node is the root node.

denotes the number of input and output nodes,|S| the number of state in automaton, |P | thenumber of partitions (Session 3. 2).
• We propose an eﬃcient implementation for

2 Query

evaluationon

distributed

graph

our algorithms using MapReduce programming

2. 1 Distributed graphmodel in the Hadoop environment. The imple-

We will represent a database by a rooted, edge-

mentation utilizes the features of Hadoop dis-labeled directed graph. It is a graph with a uniquetributed file system (HDFS) to make program

root. Each vertex (in this paper we call it a node)correct and eﬃcient. Details will be mentioned

has its unique identity. Each edge from a node u

in Section 3. 3.

to node v has a label, and is denoted by u → v.

The organization of the rest of this paper is asfollows: In Session 2 we briefly review the key fea-

label

Label could be atomic values such as: Int, Long,
String, Bool, Image, . . ..

tures of a well-known method for query evaluation

A distributed graph DG is a graph whose nodes

on distributed graph. The main contributions is inare partitioned into m sets located on m sites. At

Session 3 where we show improvements on Dan Su-

each site α, nodes and correspondent edges makeciu’s algorithm and propose an eﬃcient implemen-a fragment DGα of distributed graph. An edge

tation in Hadoop environment. Session 4 shows ex-

u → v is a cross-link if u and v are stored on dif-perimental results of our algorithms with data fromferent sites.

Youtube and DBLP. Related works and Conclusion
will be mentioned in Sessions 5 and 6.

a

For any cross-link u → v from site α to site β, wea

ϵreplace it with u → v ′ → v, where v ′ is just a copyof v and resides on the site α, ϵ is a special label
denoting an empty label. Now, v ′ → v becomes aϵwhere a is a label include ϵ label.

denotes anylabel, R | R is an alternation, R ⇒ R denotes concatenation, and R∗ is the Kleene closure.
Evaluation of a query Q on a graph DG is denoted by DG(Q).
A problem of query evaluation on a distributedgraph is stated as follows: Given a distributedgraph DG =

∪

α=1,m

DGα , and a query Q, com-pute DG(Q).
A well-known method for query evaluation [10][12] consists of 6 steps:

Step 1: Client computes an automaton A for the
regular expression R in the query Q, then sends A
to each sites.
Step 2: At each site α, we compute a partial
A distributed graph for Youtube’s

result Pα as in Algorithm 1. If a node u is a root

data. The red node is the root. Green nodes

node then (1) it is also an input node, (2) a node

are output ones. Yellow nodes are input ones.

(s, u) is an input node, where s is a state in the au-

Figure 2

tomaton A. If u is an input or output node, thencross-link and u → v ′ is an edge in fragment DBα .
a(s, u) is an input or output respectively.

a

We call u → v ′ an ϵ-edge. v ′ is called an output
node of fragment DBα , and v is an input node offragment DBβ .

Algorithm 1: Partial result computation
input : A fragment DGα , an automaton A
output: A partial result Pα

Figures 1 and 2 are examples of a rooted edgelabeled directed graph whose root is the node with1

value “1”, and dotted edges are cross-links with ϵ2label. Input nodes are in green and output nodes
are in yellow.

begin
Pα ← DGα ;/* copy nodes andedges from DGα to Pα */3foreach u ∈ InputN odes(DGα ) do
foreach s ∈ States(A) do

4

2. 2 Query evaluation5

S ← visit(s, u);A query Q on a graph DG is a select-where query6

foreach p ∈ S dothat is a subset of unQL query language [4]. For

7ϵadding an edge (s, u) → p tosimplicity, we just consider a query with one regularpath expression:Pα ;select t

9where R ⇒ t in DG

10

Here t is a variable that stores records returned,
R is a regular path expression:
R = a | | R|R | R ⇒ R | R ∗ | R

end

8

11

end
end
end

Algorithm 2: Visiting algorithm
input : A node s, a state s
output: A set of node
1
2

visit(s, u) begin
if (s, u) ∈ visited thenreturn global matches[(s,u)];

3
4

end

5

visited ← (s,u);6

matches ← {};7

if u is output node then8matches ← (s,u);
global matches[(s,u)] ← matches;

910else if s is terminal state then11

matches ← u;12

global matches[(s,u)] ← matches;

13

Figure 3a14

foreach u → v in DGα doforeach s → s′ satisfies x == a do

System overview

x

15

matches ← matches ∪16

visit(s′ , u);global matches[(s,u)] ←17

matches;
end

18
19

end

20

return matches;

21

end

Step 5: At each site, compute a partial answer
as follows: with each element in the set of accessible nodes, we find its successors in the partial result
and add them to the partial answer. Finally, send
the partial answer to client.
Step 6: Client will combine partial answers together to get a final answer of the query. The final
answer is the result of DG(Q).
In step 4, the total amount of data transferringis O((|N | × |S|)2 ) where |N | is the number of cross-

Step 3: Using Pα , we compute a local accessible

links, |S| is the number of state in the automaton.

graph LAGα . LAGα contains all input and output

In step 5, that is O(r), where r is the size of querynodes from partial result and an edge from an in-answer. Therefore, the total data in communica-

put node to an output node if there exists a pathtion for the evaluation is O((|N | × |S|)2 ) + O(r))

between them in the partial result.

[12] [6].

Step 4: Each site α sends its LAGα to client
where LAGs will be combined together, then addedcross-links to get a global accessible graph GAG.

3 Eﬃcient evaluation with Hadoop environment

Starting from the node (sinital , uroot ) where sinital

In this section we focus on describing our frame-is the initial state in A, uroot is the root node ofwork that eﬃciently evaluate queries on distributed

DG, we find all nodes accessible in GAG. We sendgraph.

the set of accessible nodes back to each site.

Figure 3 shows the overview of the frameworkthat consists of three phases. In the first phase, weemanating from these nodes.

compute both a partial result and a local accessible

A local accessible graph contains all input andgraph in one step. This computation is performed

output nodes from a partial result and an ϵ-edge

locally at each site. In the second phase, we com-from an input node to an output node if there ex-pute accessible nodes from LAGs in the distributed

ists a path between them. Figure 5 is an example

way. Each site will communicate with others toof a local accessible graph for the parital result in

update its LAG. The amount of data in commu-

figure 4.

nication will be computed in detail in Session 3. 2.
After that, we get new LAGs at each site. These

We have some important observations on LAGs
as follows:

new LAGs contain oaccessible nodes from the root

Observation 1: If an input node (s, u) has nonode (sinital , uroot ). Note that our partial results

links to other nodes, then we remove it from LAG.

are unchanged in the phase 2. Finally, we extract

We prove this by considering the state s: if s isaccessible nodes from new LAGs locally, and con-a terminal state, then there always exists an edge

struct partial answers by doing a DFS for each ac-(s, u) → u (Alogrithm 2), therefore in this case, s

cessble nodes over partial results. Partial answers

is not a terminal state. Because s is not a terminal

are fragments of the query’s final answer. A com-state, u is not the final node yet that sastifies thebinator is used to gather partial answers and add

automaton. Besides, we can not go further alongcross-links between them to make the final answer.

the automaton, so the node u does not contributeto the final result, it means that we can remove the3. 1 One-step evaluation
3. 1. 1 Observations

node (s, u).
Observation 2: For a terminal state sterminal ,ϵBefore going to the detail of our one-step evalu-

if there is an ϵ-edge (sterminal , uin ) → uin in par-ation, we briefly review the form of partial results

tial result, then in LAG only ϵ-edges uin → vout isand local accessible graphs.

enough, where vout is an output node that is reach-

A partial result consists of the whole nodes andϵable from uin . It means that, we do not need to add
ϵBesides, it has additionaledges (sterminal , uin ) → vout to LAG. This is eas-

nodes in the form of (s, u), where s is a state in

ily proved by showing that if existing a path fromthe automaton, u an input or output node. An ex-(sterminal , uin ) to vout , then the path must con-ample of a partial result is shown in the figure 4.

tain uin . According to Algorithm 2, when visiting

The input fragment for that partial result includes

node (sterminal , uin ), because sterminal is a termi-

nodes indexed from 1 to 8 and edges between them.

nal state, we add an edge (sterminal , uin ) → uin to

Here we have two input nodes: node 1 and node 2;

LAG and finish the visit of (sterminal , uin ). There-

three output nodes: node 5, node 6, and node 8.

fore, the only way to go from (sterminal , uin ) to voutedges in a fragment.

ϵThe edge (s1, 1) → (s2, 5) is there because, start-

ϵis via uin .

ing from node 1 with state s1, we can reach node 5

Observation 3: Assuming that between frag-at state s2 by following transitions in the automa-

ment Fi and fragment Fj there is a cross-link

ton. Since s3 is the terminal state, we have edges

u′ → u, u′ ∈ Fi , u ∈ Fj . Then, there alwaysϵϵ(s3, 1) → 1, (s3, 2) → 2. We can not find any

exists edges (sterminal , u) → u in LAGj of Fj . We

node matches the automaton starting from node 1

prove that these edges are redundant. In LAGj ofor node 2 with state s2, therefore there is no edge

Fj , we consider two cases: (1) If there exists anϵ-edge w → (sterminal , u′ ), then we have a path asfollows: w → (sterminal , u′ ) → (sterminal , u) → u.
ϵϵϵThat path can be replaced by w → u′ → u. (2) ifϵϵ

Algorithm 3: One step algorithm
input : A fragment DGα , an automaton A
output: A partial result Pα , a LAGαthere does not exist an ϵ-edge w → (sterminal , u′ ),then there is no path coming to node (sterminal , u),we can remove the edge (sterminal , u) → u.

1
2large of redundant nodes and edges from LAGs
(Example in figure 6), leading to significantly decreasing the amount of data during the computation of accessible nodes. Also by the observations, we re-organize a local accessible graph into
three parts: the first part contains only edges between non-state input nodes and non-state output
nodes (nodes without state); the second part includes of only edges between nodes having states

Pα ← DGα ;3foreach u ∈ InputN odes(DGα ) do

4

IO ← F indOutN odes(u);5foreach v ∈ IO doϵ

LAGα ← (u → v);

6
7

end

8

foreach s ∈ States(A\sterminal ) do

9S ← visit(s, u);10

foreach p ∈ S do
if u has a state then11ϵadding an edge (s, u) → p

12

to Pα ;

(these nodes and edges are computed from visiting algorithm); and the remaining part consists ofϵadding an edge (s, u) → p

13

to LAGα ;edges from an input node having state to other nonstate output node, these edges show us that there
is a strong probability that result of query can be/* copy nodes andedges from DGα to Pα */3. 1. 2 One-step Algorithm
Applying above observations, we can remove a

begin

else

14

IO ←

15

F indOutN odes(u);appeared in current site.
We re-design algorithms in Section 2 so thatit computes both partial result and LAGs without non-redundant data. The algorithm is shownin Algorithm 3. For each input node, firstly wecompute output nodes that can be reached fromthat input node, this constructs the first part of
LAG. The second part and third part of LAG is
copied from result of the visiting algorithm for each

foreach v ∈ IO do

16ϵLAGα ← (u → v);

17

end

18
19

end

20

end

21
22
23

end
end

node of (s, uin ), here we do not visit with terminal state in order to remove all redundant edgesϵof (sterminal , uin ) → uin . The visiting algorithm

3. 2 Eﬃcient computation of accessible
nodes(Algorithm 4) is almost the same as the former

As discussed in Section 2, to compute accessi-

one. There is only one diﬀerence that is we checkble nodes we have to combine all LAGs into awhether a node reaches a terminal state or not be-

global accessible graph (GAG). The size of GAG

fore checking whether it is an output node, thisis O((|N | × |S|)2 ). This is also the amount of dataϵwill replace all edges of (s, u) → (sterminal , vout ) byϵ(s, u) → vout .

we have to send over network. In social networks
where the number of relationship is large then theAlgorithm 4: A modified visiting algorithm
input : A node s, a state s
output: A set of nodevisit(s, u) begin
..
2
.

1

3

if s is terminal state then4matches ← u;5

global matches[(s,u)] ← matches;

6

Figure 6

else if u is output node then7matches ← (s,u);8

global matches[(s,u)] ← matches;

LAG after reducing redundantvertices

number of cross-links is also increasing. This causes
a bottleneck in evaluation of query. We see that the

9

10

..
.

11

end

number of accessible nodes is not more than thenumber of node in final answer because we use accessible nodes to extract final answer from partial
results. Therefore sending out all nodes and edges
in LAGs is not necessary.
Borrowing the idea of distributed BFS [9], we
propose an eﬃcient iterative algorithm to computeaccessible nodes, named iter acc algorithm. In thecomputation process, each node in LAG will haveone of two values: either ACC node or OR node,
hence we refer a LAG as an ACC/OR graph. Ouralgorithm is as follows:
Figure 4

Partial result

Step 1: Represent LAGs by adjacent lists, inwhich for each input node we have a set of output
node linked to it. Let a list of adjacent nodes of u
be adj(u). Marking all nodes in LAGs as an OR
node.
Step 2: Create a list to keep accessible nodes
during the computation process, named acc nodesα
for site α. Initially, acc nodesα contains only theroot node (s, r) (s is initial state of the automaton,r is the root node of the input graph DG.

Figure 5

Local accessible graph (LAG)

Step 3: Each site α sends its acc nodesα to allother sites.
Step 4: Each site α receives acc nodesi , i =1..n, i ̸= α, from others and combines them into its
acc nodesα , then removes duplicate nodes.

the number of state in automaton, |P | the number of partitions. By using a hash data structure
to store input nodes of LAGs, we check whether u
in LAGα or not in the time complexity of O(1).
Because the organization of LAGs is simple in thesense that it just contains edges between input andoutput nodes, the number of levels to explore ineach iteration is only one. This will significantly
reduce the overhead between iterations.

3. 3 Eﬃcient Hadoop-based implementation
3. 3. 1 Hadoop environment
Hadoop [1] is an open source framework for
MapReduce programming model [5]. It is proved tobe eﬃcient and scalable. In MapReduce programFigure 7

An example of computation ofaccessible nodes with five iterations. acc nodes
contains a list of accessible nodes before each
iteration.

ming model, we only need to write two functions:
Map and Reduce. Map functions produce a list ofpair of (key, value). After that, Shuﬄe and Sorting phase will collect pairs with the same key andgroup them into pairs of (key, list of values), thisStep 5: Each site α uses its acc nodesα to up-phase is automatically done by Hadoop system. For

date its LAGα . The process of update is as follows:each diﬀerent key and its list of values, the system

For each nodes u ∈ acc nodesα :will invoke a reduce function to process. Reduce• If u ∈ LAGα , then (1) if u is an OR node, thenfunctions will emit results that are pairs of (key’,

update its to an ACC node. (2) for each node

value’). Data, which are used during computationv in adj(u), if v is an OR node, then update vof a MapReduce job, are stored in a high perfor-

to an ACC node, then add v to acc nodesα .

mance distributed file system named HDFS. Map• If u ∈/ LAGα , do nothing.

tasks and reduce tasks will be eﬃciently scheduled• Removing u from acc nodesα .

so that they are “nearest” to its input data. “Near-

Step 6: Repeat Step 3 until all acc nodesı ,est” in the sense that tasks and its input data are in

i = 1..n, is empty.
Step 7: At each site α, extract all ACC nodes
from LAGα , we have a set of accessible nodes for
its fragment Fα .
An example of the above algorithm is shown infigure 7.
The amount of data transferring over network inthe same machine or in the same subset of network.
3. 3. 2 An intuitive implementation
Intuitively, our iter acc algorithms can be performed by iterating over MapReduce jobs. In thefirst MapReduce job, each map task takes accountinto a partition and performs one-step evaluation
algorithm.

There is no reduce task in the first

our algorithm is O(|N | × |S| × |P |), where |N | de-job, so map task will directly write its result tonotes the number of input and output nodes, |S|

HDFS. Next, we have a loop of MapReduce jobs foriter acc algorithm. Each loop has one MapReduce• Synchronization between iteration: How

job. The loop finish when there is no new accessible

to know that, at each iteration i-th, map tasks

nodes found. In each iteration, Map task will com-only read files of accessible node from the pre-pute new accessible nodes following the algorithm

vious iteration (i − 1)-th.

described in Section 3. 2, with each accessible node

As of consistency, the problem is that how to

it emits a pair (1, accessible node). Because allknow when HDFS finished writing to a file. HDFS

pairs emitted by map phase has the same key 1,

uses the length of a file to do its magic [2]. The

every accessible nodes will come to the same Re-

length of a file stays at 0 while the first block isduce task where we will remove duplicate nodes

being written to. After the first block is fully writ-and emit a list of new accessible nodes, this list

ten, the length of file will be updated to the length

will be used for the next MapReduce job. The finalof data written so far, this update continues until

MapReduce job will compute partial answers in its

all blocks of data written to the file. The default

Map tasks and send them to a reduce task to get

value of a block is 64MB. Because in our model thethe final answer.

size of files is not greater than the size of a file that

However, we recognize that the time for initializ-contains all input and output nodes, therefore, toing a MapReduce job is not small, this leads to an

keep the length of a file is always 0 we set up the

ineﬃcient program as it iterates over many jobs.

default value is the size of a file of input and output

Besides, after each job finished, we have to write

nodes. Now, we just check the length of a file to see

results (here, LAGs and accessible nodes) to HDFS

whether other task has finished writing it or not.

and read them back for next jobs. Because the size

To ensure the synchronization between iterationof LAGs is large, the algorithm takes much time.

we name files by using two parameters: iteration

The problem is that how to design an implemen-

identity and partition identity. The algorithm is astation with only one MapReduce job and avoiding

follows:

as much as possible reading/writing so much data
from/to HDFS.
3. 3. 3 An eﬃcient implementation
Our idea is that: we keep LAGs and partial result• Each partition has a unique identity p, p =1..n, n the number of partition.
• At each iteration i, each map task for partitionp does:in memory, and only send out new accessible nodes.

– output a file containing new accessible

In figure 8, we propose an implementation for that

nodes to HDFS, with the file name of form

idea using HDFS. At each iteration, a map taskof : i p.txt.

writes its new accessible nodes to a file in HDFS,
then it reads back all other files what have written– read back n files i p.txt from HDFS, p =1..n.

by other map tasks, combines them together, and– check whether it completely finished read-checks whether the whole list of accessible nodes is

ing all files i p.txt or not, p = 1..n. If

empty or not in order to decide if we should finish

finished, increasing the value of i. If not,the loop or not. There are two problems we havecontinuing to read.

to handle in that process:• Consistency: A task can not read the content of a file in HDFS before other task completely finish writing it to HDFS.

4 Experimental results
In this session, we present experiments for our
implementation using datasets of YouTube andHDFS file system. When the algorithm is executed,
each map task will read a file to process.
For each graphs, we randomly chose the nodewith id “3307” as the root node. We used two different queries with following regular expression foreach dataset.
DatasetRegular expression

YouTube“∗ => category => M usic”

DBLP“∗ => year => 2002”

A query for YouTube graph is to find videos thathave Music as its category, and the one for DBLP
to fine papers published in 2002.

4. 2 Results
We compared the total size of all local accessible
Figure 8

Hadoop-based implementation ofgraphs generated by Dan Suciu’s algorithm withthat generated by our one-step algorithm. Figure 9

evaluation systemand Figure 10 shows that we can reduce almost 50%
DBLP.

of the size of LAGs for both YouTube and DBLP
graphs.

4. 1 Experimental environment

To simulate a bottleneck, we decreased the heap

Our experiments are performed on Edubase
Cloud System †1 , we built a Hadoop environment

size for a reduce task to 1024MB. We comparedfrom five virtual machines on the Cloud: one ma-

gorithm to compute LAGs, however one programchine for master node, and four others for computesends all LAGs to one reduce task to compute ac-

nodes. Each compute node has 8 CPUs and 24GB

cessible nodes and the other uses our iterative algo-

of RAM.

rithm. Figure 11 shows that the program without

We used real-life data from YouTube †2 and
DBLP †3 to generate edge-labeled directed graphswith the sizes as follows:

between two programs: both use the one-step al-

the iterative algorithm can not pass when evaluating the dataset of the size of 8 milions, meanwhile
the other can compute with the data that is two

Dataset|V||E|

Size (|V|+ |E|)

times larger. Besides, we can see that when theYouTube

7,354,581

8,297,699

15,652,280

data size becomes larger, the diﬀerence in running

DBLP

3,976,588

4,303,895

8,280,483

time is also increased. Experiments with DBLP

To make distributed graphs, we used GraphLablibrary †4 to partition these graphs into 32 partitions stored by 32 diﬀerent files and put them on
†1
†2
†3
†4

(Figure 12) also show the same performance.

5 Related works
Evaluating regular path queries on rooted, edge-

http://edubase.jp/cloud
http://netsg.cs.sfu.ca/youtubedata/
http://arnetminer.org/citation
http://graphlab.org/

labeled directed graphs are studied by Dan Suciu
in [12], and extended in [11] based on message passing. In [11], the algorithm will create a set of pro-

Figure 9

Reduction of redundant data

Figure 12

Running time with DBLP dataset.

(YouTube dataset).

cesses, each process starts by creating an initialtask for itself and a table to store results duringcomputation. Tasks then communicate with others to update their tables in an iterative way. Thisis diﬀerent to our approach: (1) We only use theiterative way to compute accessible nodes, almost
computations of the algorithm is done locally; (2)The amount of data sending over the network in[11] is O(n2 ), where n is the number of cross-links

between diﬀerent sites.
Figure 10

Reduction of redundant data
(DBLP dataset).

In [6], Fan Wenfei proposed an algorithm forreachability problem with regular path expressions.
He used Boolean formulas to keep local accessible
nodes, and then combine them together to make adependent graph. This algorithm only needs one
visit for each sites and therefore fits to the MapReduce model.

Basically, the approach in [6] still

follows the query evaluation model in [12], therefore the amount of data transferred is quadratic to
the number of cross-links. Besides, our algorithm
can evaluate more general queries of regular expression (queries that return data extracting from the
input graph) other than reachability queries with
True/False answer.
Figure 11

Running time with YouTube
dataset.

The Netherlands, North-Holland Publishing Co.,
2000, pp. 309–320.
[ 4 ] Buneman, P., Davidson, S., Hillebrand, G., andWe have proposed an improvement for query
Suciu, D.: A query language and optimization techniques for unstructured data, Proceedings of theevaluation on distributed graph, which reduces a1996 ACM SIGMOD international conference onlarge amount of redundant data and avoids the botManagement of data, SIGMOD ’96, New York, NY,
USA, ACM, 1996, pp. 505–516.
tleneck during the evaluation. The total amount of[ 5 ] Dean, J. and Ghemawat, S.: MapReduce: simdata transferred over network of our algorithm isplified data processing on large clusters, Commun.
ACM, Vol. 51, No. 1(2008), pp. 107–113.
linear to the number of cross-links between diﬀer[ 6 ] Fan, W., Wang, X., and Wu, Y.: Perent sites. We have also proposed an eﬃcient impleformance guarantees for distributed reachability
queries, Proc. VLDB Endow., Vol. 5, No. 11(2012),
mentation based on Hadoop file system HDFS and
pp. 1304–1316.
used HDFS to ensure the consistency of data and[ 7 ] Kwak, H., Lee, C., Park, H., and Moon, S.:
What is Twitter, a social network or a news media?,to synchronize between iterations in the algorithm.
Proceedings of the 19th international conference on
In the future, we will apply our approach to deal
World wide web, WWW ’10, New York, NY, USA,ACM, 2010, pp. 591–600.
with more other queries of unQL query language,[ 8 ] Lang, K.: Finding good nearly balanced cuts inand to evaluate queries on multiple sources of data.
power law graphs, Technical Report YRL-2004-036,
Yahoo! Research Labs, November 2004.
Another direction is to extend our approach to in[ 9 ] Mark, S.: From prefix computation on PRAM
crementally maintain views to database.
for finding euler tours, www.cs.hut.fi.
[10] Serge, A., Peter, B., and Suciu, D.: Data on
the Web: From Relations to Semistructured Data
References
and XML, Morgan Kaufmann Publishers, San Francisco, California, 2000.
[ 1 ] : Apache Hadoop, http://hadoop.apache.org/.
[11] Shoaran, M. and Thomo, A.: Fault-tolerant
2013.
computation of distributed regular path queries,[ 2 ] Borthakur, D.: HDFS Architecture Guide,
Theoretical Computer Science, Vol. 410, No. 1(2009),
http://hadoop.apache.org/docs/stable/hdfs_design.
pp. 62–77.
html. Online, accessed: 2013-07-10.
[12] Suciu, D.: Distributed query evaluation on[ 3 ] Broder, A., Kumar, R., Maghoul, F., Raghasemistructured data, ACM Trans. Database Syst.,van, P., Rajagopalan, S., Stata, R., Tomkins, A.,
Vol. 27, No. 1(2002), pp. 1–62.
and Wiener, J.: Graph structure in the Web,[13] Ugander, J., Karrer, B., Backstrom, L., andProceedings of the 9th international World Wide
Marlow, C.: The anatomy of the facebook social
Web conference on Computer networks : the ingraph, arXiv preprint arXiv: . . . , (2011), pp. 1–17.
ternational journal of computer and telecommunications netowrking, Amsterdam, The Netherlands,

6 Conclusion