Static dictionaries on AC0 RAMs: query time (√log n/log log n) is necessary and sufficient

Arne Andersson; Peter Bro Miltersen; Søren Riis; Mikkel Thorup

doi:10.1109/SFCS.1996.548503

Static dictionaries on AC⁰ RAMs: query time (√log n/log log n) is necessary and sufficient

Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

In this paper we consider solutions to the static dictionary problem on AC⁰ RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC⁰. Our main result is a tight upper and lower bound of θ(√log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2^{polylog n}. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth Ω(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984)

Originalsprog	Engelsk
Titel	37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.
Antal sider	10
Forlag	IEEE Computer Society Press
Publikationsdato	1996
Sider	441-450
DOI	https://doi.org/10.1109/SFCS.1996.548503
Status	Udgivet - 1996
Begivenhed	Annual Symposium on Foundations of Computer Science - Burlington, VT, USA Varighed: 14 okt. 1996 → 16 okt. 1996 Konferencens nummer: 37

Konference

Konference	Annual Symposium on Foundations of Computer Science
Nummer	37
Land/Område	USA
By	Burlington, VT
Periode	14/10/1996 → 16/10/1996

Adgang til dokumentet

10.1109/SFCS.1996.548503

Citationsformater

@inproceedings{1bfffae0b1b211df8c1a000ea68e967b,

title = "Static dictionaries on AC0 RAMs: query time (√log n/log log n) is necessary and sufficient",

abstract = "In this paper we consider solutions to the static dictionary problem on AC0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC0. Our main result is a tight upper and lower bound of θ(√log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2polylog n. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth Ω(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984)",

author = "Arne Andersson and Miltersen, {Peter Bro} and S{\o}ren Riis and Mikkel Thorup",

year = "1996",

doi = "10.1109/SFCS.1996.548503",

language = "English",

pages = "441--450",

booktitle = "37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.",

publisher = "IEEE Computer Society Press",

note = "Annual Symposium on Foundations of Computer Science ; Conference date: 14-10-1996 Through 16-10-1996",

}

Andersson, A, Miltersen, PB, Riis, S & Thorup, M 1996, Static dictionaries on AC⁰ RAMs: query time (√log n/log log n) is necessary and sufficient. i 37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.. IEEE Computer Society Press, s. 441-450, Annual Symposium on Foundations of Computer Science, Burlington, VT, USA, 14/10/1996. https://doi.org/10.1109/SFCS.1996.548503

Static dictionaries on AC⁰ RAMs: query time (√log n/log log n) is necessary and sufficient. / Andersson, Arne; Miltersen, Peter Bro; Riis, Søren et al.
37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.. IEEE Computer Society Press, 1996. s. 441-450.

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Static dictionaries on AC0 RAMs: query time (√log n/log log n) is necessary and sufficient

AU - Andersson, Arne

AU - Miltersen, Peter Bro

AU - Riis, Søren

AU - Thorup, Mikkel

N1 - Conference code: 37

PY - 1996

Y1 - 1996

N2 - In this paper we consider solutions to the static dictionary problem on AC0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC0. Our main result is a tight upper and lower bound of θ(√log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2polylog n. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth Ω(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984)

AB - In this paper we consider solutions to the static dictionary problem on AC0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC0. Our main result is a tight upper and lower bound of θ(√log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2polylog n. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth Ω(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984)

U2 - 10.1109/SFCS.1996.548503

DO - 10.1109/SFCS.1996.548503

M3 - Article in proceedings

SP - 441

EP - 450

BT - 37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.

PB - IEEE Computer Society Press

T2 - Annual Symposium on Foundations of Computer Science

Y2 - 14 October 1996 through 16 October 1996

ER -