ISSN:
1432-0541
Schlagwort(e):
Algorithms
;
Arithmetic model
;
Data structures
;
Intersection reporting
;
Lower bounds
;
Memory restriction
;
Set handling
;
Upper bounds
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract We consider the followingset intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence ofn updates (insertions into and deletions from individual sets) andq queries (reporting the intersection of two sets). We cast this problem in thearithmetic model of computation of Fredman [F1] and Yao [Ya2] and show that any algorithm that fits in this model must take time Ω(q+n√q) to process a sequence ofn updates andq queries, ignoring factors that are polynomial in logn. We also show that this bound is tight in this model of computation, again to within a polynomial in logn factor, improving upon a result of Yellin [Ye]. Furthermore, we consider the caseq=O(n) with an additional space restriction. We only allow the use ofm memory locations, wherem ≤n3/2. We show a tight bound of Θ(n2/m1/3) for a sequence ofn operations, again ignoring the polynomial in logn factors.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01293666
Permalink
