TY - GEN

T1 - Storing and searching a multikey table

AU - Fiat, Amos

AU - Naor, Moni

AU - Scliäfer, Alejandro A.

AU - Schmidt, Jeanette P.

AU - Siegel, Alan

PY - 1988

Y1 - 1988

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

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

UR - http://www.scopus.com/inward/record.url?scp=84899031459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899031459&partnerID=8YFLogxK

U2 - 10.1145/62212.62245

DO - 10.1145/62212.62245

M3 - Conference contribution

AN - SCOPUS:84899031459

SN - 0897912640

SN - 9780897912648

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 344

EP - 353

BT - Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988

PB - Association for Computing Machinery

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

Y2 - 2 May 1988 through 4 May 1988

ER -