Dfs-based cycle detection on pregel model

Abstract

A method, system and computer program product are presented for reducing memory consumption in depth first search (DFS)-based cycle detection processes to detect an n-length cycle on a Pregel model. The method includes generating a graph including a plurality of vertices and edges connecting the plurality of vertices, commencing a cycle from a first vertex of the plurality of vertices, setting an ID of the first vertex to a path and the first vertex as a target vertex, and iterating the following n−1 times: send the path to out-edges starting from the first vertex and transferring the path, via out-edges, n−1 times by subsequent received vertices, find one vertex before returning to the target vertex, add an ID of a found vertex to the path, and set the found vertex as the target vertex such that n=n−1, where is a number of iterations.