New Parallel Order Maintenance Data Structure

The Order-Maintenance (OM) data structure is to keep a fully ordered list of items, supporting operations including insertions, deletions, and comparisons. As a crucial data structure, OM is widely used in various applications. With the increasing availability of multicore processors, there is a strong incentive to parallelize this essential data structure. This paper introduces a novel parallel OM data structure.