PhD Seminar • Data Systems — Streaming Graph Querying

Please note: This PhD seminar will be given online.

Anil Pacaci, PhD candidate
David R. Cheriton School of Computer Science

Graphs are used to model complex interactions in various domains ranging from social network analysis to communication network monitoring, from retailer customer analysis to bioinformatics. Many of these real-world graphs are massive in size and continuously evolve at very high rates that can be modelled as a streaming graph. Efficient querying of streaming graphs is a crucial task for applications that monitor complex patterns and, in particular, persistent queries that are registered to the system and whose results are generated incrementally as the graph edges arrive.

We study the problem of persistent query processing over streaming graphs. We first focus on navigational queries that determine if a path between two entities that satisfies a user-specified constraint. We adopt the Regular Path Query (RPQ) model that specifies navigational patterns with labeled constraints. We propose deterministic algorithms to efficiently evaluate persistent RPQs under both arbitrary and simple path semantics in a uniform manner. We then discuss how to support more complex graph patterns and attribute-based predicates that are featured in real-world applications. In particular, we investigate Regular Queries and their extensions to the property graph model as a candidate framework for modelling complex graph queries over streaming graphs.

To join this PhD seminar on Zoom, please go to https://zoom.us/j/96984420943?pwd=RW5ZT1EweStlM29sMHpQdks0bFdlZz09

Meeting ID: 969 8442 0943
Password: 086820