Reachability in big graphs : A distributed indexing and querying approach

dc.contributor.authorHocine, Imane
dc.contributor.authorYahiaoui, Saïd
dc.contributor.authorBendjoudi, Ahcene
dc.contributor.authorNouali-Taboudjemat, Nadia
dc.description.abstractThe advent of Big graphs characterized by their enormous number of nodes, with multiple edges between them makes the existing reachability query indexing approaches unable to guarantee a reasonable time for both the index construction and query steps. Therefore a novel approach that takes into account these new characteristics during the graph processing is needed. In this paper, we propose an Overlay Graph-based Distributed Reachability Indexing approach (ODRI), an indexing scheme through which the index construction and reachability query are processed in a parallel and distributed manner. The key idea of ODRI is to process a Big graph as a set of smaller subgraphs (partitions) interconnected to each other through an overlay graph. In this way, the partitions can be indexed in parallel and, at the same time, the reachability information can also be extracted. Hence, the index construction and query processing time will be reduced significantly. Therefore, ODRI ensures the scalability of Big graphs, which is a challenge for the existing reachability approaches. Besides, we formally prove that this strategy preserves the reachability properties. Using real-life data, we experimentally verify that our approach outperforms the state-of-the-art methods, and is scalable in terms of the number of partitions, regardless of how graphs are distributed.
dc.relation.ispartofseriesInformation Sciences; Vol. 573
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)
dc.subjectBig graphs
dc.subjectDistributed reachability
dc.subjectOverlay graph
dc.subjectGraph indexing
dc.titleReachability in big graphs : A distributed indexing and querying approach