Master's Thesis Opportunity - Spring of 2027 (Kernel)

 
Force Directed Drawing Algorithms and Parameter Optimisation:
Through my thesis I have implemented and compared some different graph drawing algorithms in addition to some methods to speed up the slow parts of these algorithms. These algorithms were then used to test what to the best of my knowledge is a novel approach to select parameter values for graph drawing algorithms. For this, I use methods similar to those used in Machine Learning to select parameter values and measure the utility of any set of parameters by creating my own utility function. I created this function by looking at objective measures of drawing quality that are commonly known, such as the number of edge crossings, along with the time it took to draw a given graph. The resulting method for parameter optimisation could find significant increases in the speed of graph drawing for several of my implemented drawing algorithms without compromising drawing quality. Furthermore, the approach is not specific to any parameter set, and can with some modification be applied to any graph drawing algorithm dependent on some constants.

Modeling Profiling Data in a Graph Database for Performance Analysis:
Benchmarking is an important part of the development process for any mission-critical application. By inspecting profiling data, developers can identify bottlenecks and performance regressions before they reach the customers. 

Neo4j runs an extensive benchmarking suite on its database, resulting in a huge collection of profiling data collected each week. These profiles are commonly visualized individually as flame graphs which are inspected manually. Finding patterns and differences among multiple profiles is difficult to do manually, due to the size and complexity of the data. We propose a framework for identifying bottlenecks and regressions by modeling the profiling data as call-stack trees in a graph database. We demonstrate the usefulness of the framework for cross-profile analysis such as time series analysis and aggregation-based methods. We conclude that there is much potential in this approach and our thesis can be used as a decision basis for organizations wanting to implement a similar framework.
Using a graph database to model profiling data has many advantages and is suitable for the tree-like structure of the data. It makes the data more accessible and facilitates flexible querying in which the user can ask questions about the data and perform non-trivial aggregation. It has already aided Neo4j in the process of pinpointing the cause of some performance issues. The main disadvantage is the complexity involved in importing large quantities of data.

Navigating Failures in Distributed Systems: A Comparative Study of Failure Detection Algorithms:
Failure detection algorithms are used to identify unhealthy nodes in distributed systems. The goal of this study was to improve Neo4j’s use of failure detection algorithms by exploring two paths: either optimising their existing Lighthouse algorithm or by implementing a new algorithm. Existing algorithms were surveyed and the SWIM algorithm was implemented. A baseline was established and evaluated against parameter-optimized versions of SWIM and Lighthouse in a simulated network. The results show that Baseline is scalable and reliable but slow, Lighthouse is fast but less accurate, and SWIM is moderately fast and the least accurate but generates the least network load. In conclusion, the chosen parameters of a failure detector are to a great extent more important than the algorithm itself. Furthermore, to successfully optimise parameters it is crucial to have a scalable simulator and precise system requirements to manage the trade-off between speed, accuracy, and network load.

Cache replacement policies and their impact on graph database operations:
In this master thesis project, the page caching strategy of the Neo4j database is researched and attempted to be improved. Focusing on the eviction protocol of the page cache, several different algorithms are evaluated in both experimental prototyping using Python, and in the Neo4j database kernel. Using the measurements of the prototypes and the results of the Neo4j benchmarks conclude that the current page replacement policy is hard to beat with a different strategy. However, modifying the current page replacement policy by using a global instead of thread-local data structure and tuning parameters increased the hit rate and throughput. Furthermore, the measurements on the different implementations showed that the hit rate can be increased at the cost of some overhead, but implementing a complicated algorithm quickly increases the overhead and might decrease the throughput enough to make the algorithm ineffective.

Randomly generating execution plans for bug detection in Neo4j:
In recent years, Graph Database Management Systems(GDBMS) has increased in popularity for many use cases. One of the most popular GDBMS is Neo4j, which uses Cypher as a query language. With the increasing use of GDBMS in many business-critical applications, the need to test Neo4j and its competitors has become critical. One common practice for identifying bugs in a database system is using randomly generated tests, known as fuzz testing. Previously, this has been done by randomly generating queries, and several tools are currently available for this purpose. When executing a Cypher query, the query goes through several processing steps to ensure a correct result returns quickly. One of the intermediate structures used in the query processing is the execution plan, which details how the runtime should solve the query. In this thesis, we propose a novel approach to fuzz testing GDBMS by randomly generating execution plans. Our tool utilizes differential testing between different Neo4j runtimes, which allows for identifying incorrect results returned from one or more of the runtimes. These types of bugs are known as logic bugs. We can also identify situations when the Neo4j runtimes throw unexpected exceptions. The testing suite identified 20 bugs within the Neo4j, of which 11 were logic bugs. This approach to fuzz testing has proven helpful in identifying errors within the Neo4j runtimes, which previously received insufficient coverage by fuzz testing using queries. Other database management systems that utilize execution plans can benefit from the approach proposed by this thesis. The main drawbacks of this new approach are that it is not easily portable between different GDBMS and requires access to the query processing source code.

We tackle challenges in: