Data Structure Design for Skewed Dynamic Graph Processing

Speaker: Helen Xu , MIT

Date: Wednesday, April 07, 2021

Time: 3:00 PM to 4:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJUrdOqopj8uHdO4gUyVMnfglOFEqIye_Je0 (Registration required, only if you haven't registered for this series before; please read IMPORTANT NOTE below)

Event Type: Seminar

Room Description:

Host: Julian Shun, MIT CSAIL

Contact: Linda Lynch, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: https://people.csail.mit.edu/hjxu/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu

Reminder Subject: TALK: Data Structure Design for Skewed Dynamic Graph Processing (Please read the IMPORTANT NOTE regarding registration)

******************IMPORTANT NOTE ABOUT REGISTRATION******************
- If you have already registered for any previous Fast Code Seminar on Zoom, please use the Zoom link that you have received in the past. This link will stay the same for all subsequent Fast Code seminars on Zoom. Please save it to your calendar!
- Zoom does not recognize a second registration, and will not send out the link a second time. The organizers will not be notified of any second registration.
- If you have any problems with registration, please contact lindalynch@csail.mit.edu by 2:30pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************

Abstract: Various applications model problems as streaming graphs, which need to quickly
apply a stream of updates and run algorithms on the updated graph. Furthermore,
many dynamic real-world graphs, such as social networks, follow a skewed
distribution of vertex degrees, where there are a few high-degree vertices and
many low-degree vertices.

Existing static graph-processing systems optimized for graph skewness achieve
high performance and low space usage by preprocessing a cache-efficient graph
partitioning based on vertex degree. In the streaming setting, the whole graph
is not available upfront, however, so finding an optimal partitioning is not
feasible in the presence of updates. As a result, existing streaming
graph-processing systems take a "one-size-fits-all" approach, leaving
performance on the table.

We present Terrace, a system for streaming graphs that uses a hierarchical data
structure design to dynamically partition vertices based on their degrees and
adapt to skewness in the underlying graph. Our experiments show that Terrace
supports faster batch insertions for batch sizes up to 1M when compared to
Aspen, a state-of-the-art graph streaming system. On graph query algorithms,
Terrace is between 1.7x-2.6x faster than Aspen and between 0.5x-1.3x as fast as
Ligra, a state-of-the-art static graph-processing system.

Bio: Helen Xu (https://people.csail.mit.edu/hjxu/) is a PhD student in MIT
CSAIL with Professor Charles Leiserson. Her main interests are in parallel and
cache-friendly algorithms and data structures.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:
Big Data

See other events that are part of the Fast Code 2020 - 2021.

Created by Julian J. Shun at Friday, April 02, 2021 at 9:59 AM.