Processing Regular Path Queries on Giraph

In the last few years social networks have reached an ubiquitous diffusion. Facebook, LinkedIn, and Twitter now have billions of users, that daily interact together and establish new connections. Users and interactions among them can be naturally represented as data graphs, whose vertices denote users and whose edges are labelled with information about the different interactions. In this paper we sketch a novel approach for processing regular path queries on very large graphs. Our approach exploits Brzozowski’s derivation of regular expressions to allow for a vertex-centric, message-passing-based evaluation of path queries on top of Apache Giraph.