A time-efficient mechanism for representing sparse sets on a predetermined universe is presented. If the universe contains u elements, and the elements are represented by the integers from 0 to u - 1, the set is represented by two integer arrays and an integer. A dense array contains all the elements in the set in the first n positions. A sparse array contains, in position k if k is an element of the set, the position of k in the dense array. The integer is n, the number of elements in the set. Addition of a new element and deletion of an element are constant-time operations. Iteration over all elements of the set takes time proportional to the number of elements in the set, not to the size of the universe (as is true of bit-vector implementations).

The paper provides algorithms, efficiency analyses, and cost comparisons with bit vectors. It also lists a number of applications where the representation has been used  successfully.