Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

- Harry Buhrman, Denmark
- Peter Bro Miltersen
- Jaikumar Radhakrishnan, Denmark
- Srinivasan Venkatesh, Denmark

- Department of Computer Science

We study the *it static membership problem*: Given a set *S* of at most *n* keys drawn from a universe *U* of size *m*, store it so that queries of the form "Is *u* in *S*?" can be answered by making few accesses to the memory. We study schemes for this problem that use space close to the information theoretic lower bound of $\Omega(n\log(\frac{m}{n}))$ bits and yet answer queries by reading a small number of bits of the memory.

We show that, for $\epsilon > 0$, there is a scheme that stores $O(\frac{n}{\epsilon^2}\log m)$ bits and answers membership queries using a randomized algorithm that reads just one bit of memory and errs with probability at most $\epsilon$. We consider schemes that make no error for queries in *S* but are allowed to err with probability at most $\epsilon$ for queries not in *S*. We show that there exist such schemes that store $O((\frac{n}{\epsilon})^2 \log m)$ bits and answer queries using just one bitprobe. If multiple probes are allowed, then the number of bits stored can be reduced to $O(n^{1+\delta}\log m)$ for any $\delta > 0$. The schemes mentioned above are based on probabilistic constructions of set systems with small intersections.

We show lower bounds that come close to our upper bounds (for a large range of *n* and $\epsilon$): Schemes that answer queries with just one bitprobe and error probability $\epsilon$ must use $\Omega(\frac{n}{\epsilon\log(1/\epsilon)} \log m)$ bits of storage; if the error is restricted to queries not in *S*, then the scheme must use $\Omega(\frac{n^2}{\epsilon^2 \log (n/\epsilon)}\log m)$ bits of storage.

We also consider deterministic schemes for the static membership problem and show tradeoffs between space and the number of probes.

Original language | English |
---|---|

Journal | S I A M Journal on Computing |

Volume | 31 |

Issue | 6 |

Pages (from-to) | 1723-1744 |

Number of pages | 22 |

ISSN | 0097-5397 |

DOIs | |

Publication status | Published - 2002 |

- bit probe model, data structures, set membership problem, set systems

See relations at Aarhus University Citationformats

ID: 280861