Name
Abstract | ||
|---|---|---|
We consider the following set intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence of n updates (insertions into and deletions from individual sets) and q queries (reporting the intersection of two sets). We cast this problem in the arithmetic model of computation of Fredman IF1) and Yao (Ya2) and show that any algorithm that fits in this mode/must take time ~'/(q + nx/q) to process a sequence of n updates and q queries, ignoring factors that are polynomial in log n. We also show that this bound is tight in this model of computation, again to within a polynomial in log n factor, improving upon a result of Yellin (Ye). Furthermore, we consider the case q = O(n) with an additional space restriction. We only allow the use of m memory locations, where m < n 3/2. We show a tight bound of O(n2/m 1/3) for a sequence of n operations, again ignoring the polynomial in log n factors. 1. Introduction. We consider the complexity of maintaining a collection of sets with a very simple but fundamental set of operations: we would like to support updates, which are insertions into and deletions from individual sets and intersec- tion queries reporting the intersection of two sets. Other variations could include returning the size of the intersection, or retrieving some values associated with the elements in the intersection. A unifying way of studying these problems is as follows: we are given a universe q/of keys, a set M of information items that will be associated with elements of q/, a function I: q/~ M that associates values from M with keys in q/, and a collection cg of initially empty subsets of q/. Assume further that M = (M, +, 0) is a monoid, i.e., that M is closed under some associative and commutative operator + and that 0 is the identity element for +. We want to maintain (g while processing a sequence of update operations of the form insert(x, A) and delete(x, A), for x~q/ and A ~ (g, so as to answer efficiently queries of the form intersect(A, B), A, B ~ cg, which returns ~x~a~B l(x), where the sum is taken with respect to +. We also consider a variant of the problem, where the number of memory locations available is restricted. It is easy to cast the intersection problem and its variants in this framework. The basic problem defined above can be obtained by letting M = (2 ~u, u, { }) and I(x) = {x} for all x, and the problem where one merely has to report the size of the intersection can be obtained by setting M = (N, +, 0) and I(x) = 1 for all x, where here + is arithmetic addition. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1145/313559.313686 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
Algorithms,Arithmetic model,Data structures,Intersection reporting,Lower bounds,Memory restriction,Set handling,Upper bounds | Intersection (set theory),Data structure,Discrete mathematics,Combinatorics,Empty set,Polynomial,Model of computation,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 2 | 0178-4617 |
ISBN | Citations | PageRank |
0-89871-313-7 | 4 | 0.54 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul F. Dietz | 1 | 362 | 26.22 |
| Kurt Mehlhorn | 2 | 5314 | 853.36 |
| Rajeev Raman | 3 | 1550 | 110.81 |
| Christian Uhrig | 4 | 739 | 99.73 |