Can I read Lower Bounds for Predecessor Searching in the Cell Probe Model on EtoBox?

Lower Bounds for Predecessor Searching in the Cell Probe Model by Pranab Sen; S. Venkatesh is a Computer Science article available to read on EtoBox.

What is Lower Bounds for Predecessor Searching in the Cell Probe Model about?

We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is the predecessor of x in S?" can be answered efficiently. We study this problem in the cell probe model introduced by Yao [A.C.-C. Yao, Should tables be sorted, J. Assoc. Comput. Mach. 28 (3) (1981) 615-628]. Recently, Beame and Fich [P. Beame, F. Fich, Optimal bounds for the predecessor problem and related problems, J. Comput. System Sci. 65 (1) (2002) 38-72] obtained optimal bounds as functions of either m or n only on the number of probes needed by any deterministic query scheme if the associated storage scheme uses only n O(1) cells of word size (log m) O(1) bits. We give a new lower bound proof for this problem that matches the bounds of Beame and Fich. Our lower bound proof has the following advantages: it works for randomised query schemes too, while Beame and Fich's proof works for deterministic query schemes only. In addition, it is simpler than Beame and Fich's proof. In fact, our lower bound for predecessor searching extends to the 'quantum address-only' query schemes that we define in this paper

Who reads Lower Bounds for Predecessor Searching in the Cell Probe Model?

Author

Pranab Sen; S. Venkatesh

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)

Published

2008

Language

EN

Field

Computer Science (Physical Sciences)