Lecture

Graph Pattern Matching: Work-sharing

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the optimization of graph pattern matching through work-sharing techniques, including transitioning from sequential to parallel matching, addressing load imbalance, and utilizing work-stealing strategies. It also discusses experimental setups, such as the Social Network Benchmark, and emphasizes the importance of context-aware parallelization and node dependencies in pattern mining at scale.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (32)

Dependency grammar

Dependency grammar (DG) is a class of modern grammatical theories that are all based on the dependency relation (as opposed to the constituency relation of phrase structure) and that can be traced back primarily to the work of Lucien Tesnière. Dependency is the notion that linguistic units, e.g. words, are connected to each other by directed links. The (finite) verb is taken to be the structural center of clause structure. All other syntactic units (words) are either directly or indirectly connected to the verb in terms of the directed links, which are called dependencies.

Dependency graph

In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph. Given a set of objects and a transitive relation with modeling a dependency "a depends on b" ("a needs b evaluated first"), the dependency graph is a graph with the transitive reduction of R.

Parse tree

A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term parse tree itself is used primarily in computational linguistics; in theoretical syntax, the term syntax tree is more common. Concrete syntax trees reflect the syntax of the input language, making them distinct from the abstract syntax trees used in computer programming.

Topological sorting

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

Program optimization

In computer science, program optimization, code optimization, or software optimization, is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources. In general, a computer program may be optimized so that it executes more rapidly, or to make it capable of operating with less memory storage or other resources, or draw less power. Although the word "optimization" shares the same root as "optimal", it is rare for the process of optimization to produce a truly optimal system.

Related lectures (64)

Advanced Spark: Partitioning and Optimization

Explores advanced Spark topics like partitioning strategies, memory optimization, and shuffle operations for efficient job execution.

Simplex Algorithm

Covers the Simplex algorithm for function minimization with linear constraints.

Optimization with Constraints: KKT Conditions

Covers the KKT conditions for optimization with constraints, essential for solving constrained optimization problems efficiently.

Optimization Techniques: Convexity in Machine Learning

Covers optimization techniques in machine learning, focusing on convexity and its implications for efficient problem-solving.

Interpreters and Virtual Machines