  The core numbers of vertices in a graph are one of the most well-studied
cohesive subgraph models because of the linear running time. In practice, many
data graphs are dynamic graphs that are continuously changing by inserting or
removing edges. The core numbers are updated in dynamic graphs with edge
insertions and deletions, which is called core maintenance. When a burst of a
large number of inserted or removed edges come in, we have to handle these
edges on time to keep up with the data stream. There are two main sequential
algorithms for core maintenance, \textsc{Traversal} and \textsc{Order}. It is
proved that the \textsc{Order} algorithm significantly outperforms the
\alg{Traversal} algorithm over all tested graphs with up to 2,083 times
speedups.
  To the best of our knowledge, all existing parallel approaches are based on
the \alg{Traversal} algorithm; also, their parallelism exists only for affected
vertices with different core numbers, which will reduce to sequential when all
vertices have the same core numbers. In this paper, we propose a new parallel
core maintenance algorithm based on the \alg{Order} algorithm. Importantly, our
new approach always has parallelism, even for the graphs where all vertices
have the same core numbers. Extensive experiments are conducted over
real-world, temporal, and synthetic graphs on a 64-core machine. The results
show that for inserting and removing 100,000 edges using 16-worker, our method
achieves up to 289x and 10x times speedups compared with the most efficient
existing method, respectively.
