## [Computational Complexity] Is FKS and other Data Structure Algorithms actuall...

Expand Messages
• 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
Message 1 of 1 , May 20, 2009
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).
1. They actually showed something stronger, that you can get s=n+o(n) and q=O(1). But this does not concern us.
2. The result with s=O(n) and q=O(1) is a simple algorithm with reasonable constants.
3. 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.
4. SO, here is my question/answer/new question:
1. Is anyone actually using the algorithm?
2. 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.
3. This paper does MEM in O(1), space O(n), and INSERT/DELETE in amortized expected time O(1).
4. 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
Your message has been successfully submitted and would be delivered to recipients shortly.