Paper Info
Title
Lower Bounds for Dynamic Data Structures on Algebraic RAMs
Abstract
   Abstract. In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important data-structure problems in the cell probe model. This model assumes that data structures are stored in memory with a known word length. In this paper we consider random access machines (RAMs) that can add, subtract, compare, multiply and divide integer or real numbers, with no size limitation. These are referred to as algebraic RAMs . We prove new lower bounds for two important data-structure problems, union-find and dynamic prefix sums . To this end we apply the generalized Fredman—Saks technique introduced by the authors in a previous paper. The generalized technique relies on a certain well-defined function, Output Variability , that characterizes in some sense the power of the computational model. Fredman and Saks' work implied bounds on output variability for the cell probe model; in this paper we provide the first bounds for algebraic RAMs, and show that they suffice for proving tight lower bounds for useful problems. An important feature of the problems we consider is that in a data structure of size n , the data stored are members of {0,\ldots,n} . This makes the derivation of lower bounds for such problems on a RAM without word-size limitations a particular challenge; previous RAM lower bounds we are aware of depend on the fact that the data for the computation can vary over a large domain.
Year
DOI
Venue
2002
10.1007/s00453-001-0079-6
Algorithmica
Keywords
Field
DocType
Key words. Random access machine,Cell-probe lower bounds,Union-find,Dynamic prefix sum.
Integer,Discrete mathematics,Data structure,Combinatorics,Algebraic number,Upper and lower bounds,Prefix,Real number,Cell-probe model,Mathematics,Random access
Journal
Volume
Issue
ISSN
32
3
0178-4617
Citations 
PageRank 
References 
3
0.60
15
Authors
2
Name
Order
Citations
PageRank
Amir M Ben-Amram132730.52
Zvi Galil236341426.98