An optimal parallel dictionary

Abstract

A dictionary is one of the most basic dynamic data structures. It supports the instructions insert, delete, and lookup. In this paper we describe and analyze a dictionary that can be implemented on a parallel computer with p processors. This data structure is optimal, i. e., it is capable of processing n instructions in optimal time O(n/p) using space proportional to the current number of elements in the dictionary. Its construction is inspired by the sequential dictionary due to Dietzfelbinger et al. from [DKM], which in turn is based on the perfect hashing scheme due to Fredman et al. from [FKS].