### 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 O(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 O(log^{k} 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988 |

Publisher | Association for Computing Machinery |

Pages | 344-353 |

Number of pages | 10 |

ISBN (Print) | 0897912640, 9780897912648 |

DOIs | |

State | Published - 1988 |

Event | 20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States Duration: May 2 1988 → May 4 1988 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 20th Annual ACM Symposium on Theory of Computing, STOC 1988 |
---|---|

Country | United States |

City | Chicago, IL |

Period | 5/2/88 → 5/4/88 |

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Storing and searching a multikey table'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988*(pp. 344-353). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/62212.62245