A 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- 1 k) 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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics