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?
On a related note, what's the latest gossip on who's going where? :)
ReplyDeleteMake them a part of STL and other standard libraries. They will soon be used
ReplyDeleteFKS obviously competes with Bloom filters. The Wikipedia claims Bloom filters are used to speed up miss determination and digests in things like BigTable and SquidCache, so these might be some of the places to look.
ReplyDeleteAs John points out, there are (more modern) alternatives to FKS for most applications. For example, multiple choice hashing/cuckoo hashing have similar properties to FKS, and are more flexible (in terms of handling inserts and deletes).
ReplyDeleteAs a starting point for some modern usage of these and related hashing tools, can I point you to for example:
A. Kirsch, M. Mitzenmacher, and G. Varghese
HashBased Techniques for HighSpeed Packet Processing
It's on my web page (and the book it's in is apparently finally about to come out).
It seems Godel Prize for 2009 has been announced.
ReplyDeleteThere exists few open source libraries for practical implementations of static perfect hashing. For example:
ReplyDeletehttp://cmph.sourceforge.net/index.html (in c)
http://sux4j.dsi.unimi.it/ (in java)