Advanced

Implementing and Evaluating a Breadth-First Search in Cypher

Olsson, Alexander LU and Magnusson, Therese LU (2018) In LU-CS-EX 2018-16 EDAM05 20181
Department of Computer Science
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... (More)
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. (Less)
Popular Abstract (Swedish)
Grafdatabaser blir mer och mer populära. När populariteten ökar så önskas det att sökningar i grafdatabasen utförs snabbt och korrekt. Därför behövs det snabba och pålitliga sökalgoritmer för att genomföra sökningarna.
Please use this url to cite or link to this publication:
author
Olsson, Alexander LU and Magnusson, Therese LU
supervisor
organization
course
EDAM05 20181
year
type
H3 - Professional qualifications (4 Years - )
subject
keywords
Breadth-First Search, Graph Database, Neo4j, Cypher, Master’s Thesis
publication/series
LU-CS-EX 2018-16
report number
LU-CS-EX 2018-16
ISSN
1650-2884
language
English
id
8963993
date added to LUP
2018-12-19 13:38:23
date last changed
2018-12-19 13:38:23
@misc{8963993,
  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.},
  author       = {Olsson, Alexander and Magnusson, Therese},
  issn         = {1650-2884},
  keyword      = {Breadth-First Search,Graph Database,Neo4j,Cypher,Master’s Thesis},
  language     = {eng},
  note         = {Student Paper},
  series       = {LU-CS-EX 2018-16},
  title        = {Implementing and Evaluating a Breadth-First Search in Cypher},
  year         = {2018},
}