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?