Is there a name for the following data structure? Are there papers and citations available?
One way to implement an efficient set abstract data type is to have a collection of sorted arrays, where each array has a unique power-of-2 size.
For example, a set of 13 elements {1, 2, ..., 13} can be represented by this collection of sorted arrays: {[5], [2, 3, 9, 13], [1, 4, 6, 7, 8, 10, 11, 12]}.
In general, the arrays that are in the collection have sizes that correspond to the 1 bits in the binary representation of the size of the set. The data structure is efficient because insertion can be performed in amortized Θ(log n) time, and search can be performed in Θ((log n)2) time (which is better than linear search). Also, it uses only Θ(log n) space overhead for pointers, unlike balanced binary trees and B-trees which use Θ(n) extra space for pointers. Thus, almost all the space is used for payload data.
I've looked at Wikipedia's list of data structures but didn't find a match. It's true that the book Introduction to Algorithms ("CLRS") describes this data structure as a homework problem in the "Amortized Analysis" section, but because it's a question rather than an example, the book doesn't say much about it.
A similar idea dates back at least to Jean Vuillemin's original publication on binomial heaps in the April 1978 issue of CACM. I would expect the paper that introduced this data structure to cite or be cited by Vuillemin, but none of the papers on the "references" and "cited by" lists look promising.
If I were you, I would ask cstheory and then write to CLRS, but given the suboptimal bounds and lack of deletion, I don't expect anything to turn up unless the succinct data structure community took an interest at some point.
Is there something in particular you wanted to know?