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 -