Minimizing Data Transfers for Regular Reachability Queries on Distributed Graphs

Nowadays, there is an explosion of Internet information, which is normally distributed on different sites. Hence, effi-cient finding information becomes difficult. Efficient query evaluation on distributed graphs is an important research topic since it can be used in real applications such as: so-cial network analysis, web mining, ontology matching, etc. A widely-used query on distributed graphs is the regular reachability query (RRQ). A RRQ verifies whether a node can reach another node by a path satisfying a regular ex-pression. Traditionally RRQs are evaluated by distributed depth-first search or distributed breadth-first search meth-ods. However, these methods are restricted by the total network traffic and the response time on large graphs. Re-cently, Wenfei Fan et al. proposed an approach for improv-ing reachability queries by visiting each site only once, but it has a communication bottleneck problem when assembling all distributed partial query results. In this paper, we propose two algorithms in order to im-prove Wenfei Fan’s algorithm for RRQs. The first algorithm filters and removes redundant nodes/edges on each local site, in parallel. The second algorithm limits the data transfers by local contraction of the partial result. We extensively eval-uated our algorithms on MapReduce using YouTube and DBLP datasets. The experimental results show that our method reduces unnecessary data transfers at most 60%, this solves the communication bottleneck problem