Implementing and Evaluating a Breadth-First Search in Cypher

Abstract: This report covers the implementation and evaluation of a Breadth-First Search operand for the Neo4j graph database and the Cypher query language. The evaluation compared the pre-existing Depth-First Search operand with both a non-optimized and two different optimized Breadth-First Searches. The focus of this evaluation was the runtime and memory usage for the different operands and to find out for which kind of graph and query that each operand is the better choice. The evaluation was performed through different benchmarks and selfconstructed test cases. We concluded that using Breadth-First Search on graph databases is beneficial for smaller graphs where we got improvements up to 90% faster and that the Breadth-First Search uses more memory than Depth-First Search. The optimizations gave huge improvements, however they are harder to fit into real world usage. The Breadth-First Search operand should in theory be used on smaller graphs with smaller queries with more restrictions on the relationships. The better the machine the better results. Breadth-First Search should not be applied to the whole path, instead each relationship shall be evaluated case by case.