Storing and searching a multikey table
- 1 January 1988
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 344-353
- https://doi.org/10.1145/62212.62245
Abstract
We describe an implicit data structure for n multikey records that supports searching for a record, under any key, in the asymptotically optimal search time &Ogr;(log n). This improves on [Mun87] in which Munro describes an implicit data structure for the problem of storing n k-key records so that search on any key can be performed in &Ogr;(logk n(log log n)k-1) comparisons. The theoretical tools we develop also yield practical schemes that either halve the number of memory references over obvious solutions to the non-implicit version of the problem, or alternatively reduce the number of pointers involved significantly.This publication has 0 references indexed in Scilit: