The Order-Maintenance (OM) data structure maintains a total order list of items for insertions, deletions, and comparisons. As a basic data structure, OM has many applications, such as maintaining the topological order, k -core, and k -truss in graphs, and maintaining ordered sets in the Unified Modelling Language (UML) specification. The prevalence of multicore machines suggests parallelizing such a basic data structure. This paper proposes a new parallel OM data structure that supports insertions, deletions, and comparisons in parallel. Specifically, parallel insertions and deletions are efficiently synchronized using locks, which achieves up to 7x and 5.6x speedups with 64 workers. One significant advantage is that comparisons are lock-free, enabling them to execute highly in parallel with other insertions and deletions, which achieves up to 34.4x speedups with 64 workers. Typical real applications maintain order lists that always have a much larger portion of comparisons than insertions and deletions. For example, in core maintenance, the number of comparisons is up to 297 times larger compared with insertions and deletions in certain graphs. This shows that the lock-free order comparison provides a significant practical contribution.

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, Traversal and Order. The experiments show that the Order algorithm significantly outperforms the Traversal algorithm over a variety of real graphs.

This work presents the rationale behind tools and a guideline for the Universal Design of Jupyter notebooks containing programs, explanations, graphics, algorithms, and proofs, all of which may have mathematical symbols. The tools qualitatively improve accessibility and ease the authoring of such notebooks at the same time. The tools and guidelines are currently being used for a course on concurrent system design and a course on formal languages and compiler construction at McMaster University.