Project: Constraint Optimization for Enhanced Graph Data Processing
Description
Graph databases are now standard for managing highly connected data such as social networks, knowledge graphs and transport networks. Querying them under complex constraints (integrity constraints, distribution constraints, domain-specific rules) is another matter: traditional query optimization techniques were not designed for this and often fall short. Julia, with mature optimization libraries such as JuMP, offers a well-developed toolbox for constraint programming that has barely been connected to graph data management.
In this project you will investigate how Julia-based constraint optimization can be integrated into a graph database. The work has three parts: modelling complex constraints over graph data in Julia, designing an integration that lets the query engine call a constraint solver during processing, and building an efficient interface between the two. Optionally, you can explore constraint-based query rewrites that prune traversals and cut resource consumption. The approach is evaluated on public transit accessibility: a transit network modelled in Neo4j with accessibility attributes (elevators, ramps, step-free routes), where the optimizer computes routes for travellers with reduced mobility, compared against standard routes on accessibility, travel time, query execution time and resource utilisation.
Prerequisites: solid background in databases and graph data management; experience with Julia (or willingness to learn it); a background in optimization or constraint programming is an advantage.
Reference: C. Le Hasif, A. Araldo, S. Dumbrava, D. Watel. A graph-database approach to assess the impact of demand-responsive services on public transit accessibility. IWCTS@SIGSPATIAL 2022.
Details
- Supervisor
-
Nick Yakovets
- Secondary supervisor
-
SDStefania Dumbrava (ENSIIE / SAMOVAR, France)
- Interested?
- Get in contact