An implicit data structure for searching a multikey table in logarithmic time

Amos Fiat; J. Ian Munro; Moni Naor; Alejandro A. Schäffer; Jeanette P. Schmidt; Alan Siegel

doi:10.1016/0022-0000(91)90022-W

An implicit data structure for searching a multikey table in logarithmic time

Amos Fiat, J. Ian Munro, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, Alan Siegel

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A data structure is implicit if it uses no extra strorage beyond the space needed for the data and a constant number of parameters. We describe an implicit data structure for storing nk-key records, which supports searching for a record, under any key, in the asymptotically optimal search time O(1g n). This is in sharp contrast to an Ω(n^{1- 1 k}) lower bound which holds if all comparisons must be against the sought key value. The theoretical tools we develop also yield a more practical way to halve the number of memory references used in obvious non-implicit solutions to the multikey table problem.

Original language	English (US)
Pages (from-to)	406-424
Number of pages	19
Journal	Journal of Computer and System Sciences
Volume	43
Issue number	3
DOIs	https://doi.org/10.1016/0022-0000(91)90022-W
State	Published - Dec 1991

ASJC Scopus subject areas

Theoretical Computer Science
Applied Mathematics
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1016/0022-0000(91)90022-W

Cite this

@article{7a5d9fcd866f4487a3a6439dfe1b9c0f,

title = "An implicit data structure for searching a multikey table in logarithmic time",

abstract = "A data structure is implicit if it uses no extra strorage beyond the space needed for the data and a constant number of parameters. We describe an implicit data structure for storing nk-key records, which supports searching for a record, under any key, in the asymptotically optimal search time O(1g n). This is in sharp contrast to an Ω(n1- 1 k) lower bound which holds if all comparisons must be against the sought key value. The theoretical tools we develop also yield a more practical way to halve the number of memory references used in obvious non-implicit solutions to the multikey table problem.",

author = "Amos Fiat and {Ian Munro}, J. and Moni Naor and Sch{\"a}ffer, {Alejandro A.} and Schmidt, {Jeanette P.} and Alan Siegel",

year = "1991",

month = dec,

doi = "10.1016/0022-0000(91)90022-W",

language = "English (US)",

volume = "43",

pages = "406--424",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - An implicit data structure for searching a multikey table in logarithmic time

AU - Fiat, Amos

AU - Ian Munro, J.

AU - Naor, Moni

AU - Schäffer, Alejandro A.

AU - Schmidt, Jeanette P.

AU - Siegel, Alan

PY - 1991/12

Y1 - 1991/12

N2 - A data structure is implicit if it uses no extra strorage beyond the space needed for the data and a constant number of parameters. We describe an implicit data structure for storing nk-key records, which supports searching for a record, under any key, in the asymptotically optimal search time O(1g n). This is in sharp contrast to an Ω(n1- 1 k) lower bound which holds if all comparisons must be against the sought key value. The theoretical tools we develop also yield a more practical way to halve the number of memory references used in obvious non-implicit solutions to the multikey table problem.

AB - A data structure is implicit if it uses no extra strorage beyond the space needed for the data and a constant number of parameters. We describe an implicit data structure for storing nk-key records, which supports searching for a record, under any key, in the asymptotically optimal search time O(1g n). This is in sharp contrast to an Ω(n1- 1 k) lower bound which holds if all comparisons must be against the sought key value. The theoretical tools we develop also yield a more practical way to halve the number of memory references used in obvious non-implicit solutions to the multikey table problem.

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

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

U2 - 10.1016/0022-0000(91)90022-W

DO - 10.1016/0022-0000(91)90022-W

M3 - Article

AN - SCOPUS:0026366892

SN - 0022-0000

VL - 43

SP - 406

EP - 424

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -

An implicit data structure for searching a multikey table in logarithmic time

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this