Storing and searching a multikey table

Amos Fiat, Moni Naor, Alejandro A. Scliäfer, Jeanette P. Schmidt, Alan Siegel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988
PublisherAssociation for Computing Machinery
Pages344-353
Number of pages10
ISBN (Print)0897912640, 9780897912648
DOIs
StatePublished - 1988
Event20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States
Duration: May 2 1988May 4 1988

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other20th Annual ACM Symposium on Theory of Computing, STOC 1988
CountryUnited States
CityChicago, IL
Period5/2/885/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

    Fiat, A., Naor, M., Scliäfer, A. A., Schmidt, J. P., & Siegel, A. (1988). Storing and searching a multikey table. In 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