Biblio

Graph pattern matching is one of the most fundamental problems in graph database and is associated with a wide spectrum of applications. Due to its computational intensiveness, researchers have primarily devoted their efforts to improving the performance of the algorithm while constraining the graphs to have singular labels on vertices (edges) or no label. Whereas in practice graphs are typically associated with rich properties, thus the main focus in the industry is instead on powerful query languages that can express a sufficient number of pattern matching scenarios. We demo PatMat in this work to glue together the academic efforts on performance and the industrial efforts on expressiveness. To do so, we leverage the state-of-the-art join-based algorithms in the distributed contexts and Cypher query language - the most widely-adopted declarative language for graph pattern matching. The experiments demonstrate how we are capable of turning complex Cypher semantics into a distributed solution with high performance.

Graph pattern matching in network topologies is a building block of many distributed algorithms. Based on a limited local view of the topology, pattern-based algorithms substantiate the decision-making of each device on the occurrence of graph patterns in its surrounding topology. Existing pattern-based algorithms require that each device has a sufficiently large local view to match patterns without support of other devices. In practical environments, the local view is often restricted to one hop. Thus, algorithms matching non-trivial patterns are locked out from such environments today. This paper presents the first algorithm for distributed topology pattern matching, enabling pattern matching beyond the local view. Outgoing from initiating devices, our pattern matcher delegates the matching procedure to further devices in the network. Exploring major contextual parameters of our algorithm, we show that the optimal local view size depends on scenario-specific conditions. Our pattern matcher provides the flexibility for adaptations of the local view size at runtime. Making use of this flexibility, we optimize the execution of an established pattern-based algorithm and evaluate our pattern matcher in two topology control case studies for the Internet of Things. By scaling the view size of each device in a distributed way, our adaptive approach achieves significant communication cost savings in face of dynamic conditions.