BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20230124T171522Z
LOCATION:C144-145
DTSTART;TZID=America/Chicago:20221118T103000
DTEND;TZID=America/Chicago:20221118T111000
UID:submissions.supercomputing.org_SC22_sess445_misc258@linklings.com
SUMMARY:IA^3 – Invited Talk 2: Parallel Batch-Dynamic Graph Algorithms
DESCRIPTION:Workshop\n\nIA^3 – Invited Talk 2: Parallel Batch-Dynamic Grap
 h Algorithms\n\nShun\n\nAs many real-world graphs change rapidly, it is cr
 ucial to design dynamic algorithms that efficiently maintain graph statist
 ics upon updates, since the cost of re-computation from scratch can be pro
 hibitive. Furthermore, due to the high frequency of updates, we can improv
 e performance by using parallelism to process batches of updates at a time
 . This talk presents new graph algorithms in this parallel batch-dynamic s
 etting. \n\nSpecifically, we present the first parallel batch-dynamic algo
 rithm for approximate k-core decomposition that is efficient in both theor
 y and practice. Our algorithm is based on our novel parallel level data st
 ructure, inspired by the sequential level data structures of Bhattacharya 
 et al. and Henzinger et al. Given a graph with n vertices and a batch of B
  updates, our algorithm maintains a (2 + epsilon)-approximation of the cor
 eness values of all vertices (for any constant epsilon > 0) in O(B log^2(n
 )) amortized work and O(log^2(n) loglog(n)) span (parallel time) with high
  probability. We implement and experimentally evaluate our algorithm, and 
 demonstrate significant speedups over state-of-the-art serial and parallel
  implementations for dynamic k-core decomposition. \n\nWe have also design
 ed new parallel batch-dynamic algorithms for low out-degree orientation, m
 aximal matching, clique counting, graph coloring, minimum spanning forest,
  single-linkage clustering, some of which use our parallel level data stru
 cture.\n\nSession Format: Recorded\n\nTag: Accelerator-based Architectures
 , Algorithms, Architectures, Big Data, Data Analytics, Parallel Programmin
 g Languages and Models, Productivity Tools\n\nRegistration Category: Works
 hop Reg Pass
END:VEVENT
END:VCALENDAR