An implicit data structure for searching a multikey table in logarithmic time

AbstractA data structure is implicit if it uses no extra strorage beyond the space needed for the data and a constant number of parameters. We describe an implicit data structure for storing nk-key records, which supports searching for a record, under any key, in the asymptotically optimal search time O(1g n). This is in sharp contrast to an Ω(n1− 1k) lower bound which holds if all comparisons must be against the sought key value. The theoretical tools we develop also yield a more practical way to halve the number of memory references used in obvious non-implicit solutions to the multikey table problem