Name
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 n k -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. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0022-0000(91)90022-W | JOURNAL OF COMPUTER AND SYSTEM SCIENCES |
Keywords | Field | DocType |
data structure | Discrete mathematics,Data structure,Combinatorics,Implicit data structure,Upper and lower bounds,Logarithm,Asymptotically optimal algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 3 | 0022-0000 |
Citations | PageRank | References |
7 | 0.92 | 10 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amos Fiat | 1 | 3977 | 685.20 |
| J. Ian Munro | 2 | 3010 | 462.97 |
| Moni Naor | 3 | 12948 | 1311.21 |
| Alejandro A. Schäffer | 4 | 827 | 136.66 |
| Jeanette P. Schmidt | 5 | 611 | 129.32 |
| Alan Siegel | 6 | 357 | 47.50 |