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

作者:

Highlights:

摘要

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− 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.

论文关键词:

论文评审过程:Received 17 May 1989, Available online 2 December 2003.

论文官网地址:https://doi.org/10.1016/0022-0000(91)90022-W