MEM PROBLEM: Let n,U be such that n < < U. We want to do the following:
For all sets A &sube {1,...,U} such that A=n we want to
store A in s(n,U) cells
and be able to tell MEMBERSHIP in q(n,U) probes
where a probe is just LOOKING at the contents of a cell.
A cell may have O(log U) bits in it.
Fredman, Komlos, and Szemeredi
showed (in
this paper)
that MEM PROBLEM can be done with s=O(n) and q=O(1).

They actually showed something stronger, that you can get s=n+o(n)
and q=O(1). But this does not concern us.

The result with s=O(n) and q=O(1) is a simple algorithm
with reasonable constants.

Part of the algorithm involves showing that a randomly picked
hash function works with nonzero probability; however, with a slight
change in some parameters you can get that most hash functions work
(of the type they use) work, so this is not an obstacle to
actually using their algorithm.

SO, here is my question/answer/new question:

Is anyone actually using the algorithm?

I would suspect NO because it does not allow for INSERT and DELETE.
However, if you just INSERT or DELETE a few things I think
it should be fine. So maybe YES.

This paper
does MEM in O(1), space O(n), and
INSERT/DELETE in amortized expected time O(1).

There has been alot of work on data structures with this model.
The model seems reasonable, the problems seem like ones people
in the real real world want to do quickly.
SO are the data structures being used?
If not, then are variants being used?
This seems like an area where the gap between theory and
practice is small and could be bridged.
Has it been? If not why not?

Posted By GASARCH to
Computational Complexity at 5/20/2009 10:35:00 AM