tag:blogger.com,1999:blog-8890204.post4079385411018112225..comments2021-04-07T01:20:57.256-04:00Comments on My Biased Coin: Cuckoo Hashing, Theory and Practice: Part 3Michael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-8890204.post-22476688493109137982010-05-18T03:47:56.606-04:002010-05-18T03:47:56.606-04:00can you suggest a hash function. I'm using res...can you suggest a hash function. I'm using res = res ^ (res << 5 + res >> 2 + Ci) - ramakrishna SAX hash function. but it seem that this hash function is just proper for string processing. can u suggest a better hash function for bit string (exact from incoming packet). I want to use cuckoo hashing to classify the source port and destination port fields and TCAM with source address, destination address, protocol fields.Anonymoushttps://www.blogger.com/profile/11013942353240334889noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-81103825833273503112010-05-18T03:42:24.922-04:002010-05-18T03:42:24.922-04:00I want to use cuckoo hashing in packet classificat...I want to use cuckoo hashing in packet classification program. I used TCAM before but it seems that TCAM is much expensive, ,much power-consuming. I use snort rule set, but the problem is that cuckoo hashing just return only one rule that match the imcoming packet....Anonymoushttps://www.blogger.com/profile/11013942353240334889noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-47813473781207902262007-06-22T14:48:00.000-04:002007-06-22T14:48:00.000-04:00Michael, regarding your (1), I believe it is Okay ...Michael, regarding your (1), I believe it is Okay if theory and practice use different approaches that lead to the same behavior. If in theory, we say we have a high performance dictionary, and we have a footnote saying that in some practical settings you might want to replace that with a CAM, it's ok.<BR/><BR/>You see this behavior in a lot of places. For instance, we know radix sort works great, and we've developed the theory of integer sorting to have a theory behind it. The fact that all the sketching ideas used there don't beat radix sort yet just means the data isn't big enough for smaller order terms to really become smaller. But there's no disagreement between practice and theory: we know that mathematically there is an advantage to these schemes, and we even have practical things that can use the advantage.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-63643780918247154632007-06-21T15:04:00.000-04:002007-06-21T15:04:00.000-04:00Mihai,Lots of good points in your comment.1) Whil...Mihai,<BR/><BR/>Lots of good points in your comment.<BR/><BR/>1) While I agree we don't necessarily need to change the theoretical model, I think adopting something like a CAM in the description would be of great help in bridging theory/practice. It's a common language in hardware that we're not using, causing a translation problem. <BR/><BR/>In essence, maybe this boils down to the age-old difference of while theory provides O(x) type results, practitioners want to know and understand those constants, especially for these applications.<BR/><BR/>2) Regarding what hash functions to use -- I'm actually working on something related to that right now; hopefully I'll have something to report after the SODA deadline.<BR/><BR/>3) The Pagh/Pagh/Ruzic result is extremely nice, and I recommend the paper (as well as the many other nice results from the land of Pagh).Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-15105364642550651552007-06-21T14:43:00.000-04:002007-06-21T14:43:00.000-04:00Content addressable memory is not explicitly used ...Content addressable memory is not explicitly used in theory, but the idea is everywhere --- namely, do whatever you can for most elements, and then fall back to a high performance dictionary, or something like that. We don't need any augmentation to the model here, since there are (theoretical) dictionaries that give you O(n) space, O(1) worst-case query time and O(1) update whp.<BR/><BR/>As one who's thought a lot about cuckoo hashing, I'm surprised you don't mention anything about the type of hash functions needed. Right now, we have no nontrivial guarantee (lgN is kind of trivial). From a security perspective, using heuristic hash functions is not nice. Randomizing hash tables (which allows rebulding, say), instead of using heuristic hash functions is a great theoretical contribution, and we must teach it to "practical people".<BR/><BR/>Speaking of hash functions, I recommend the STOC paper by Pagh/Pagh/Ruzic, which gives an excellent independence result for linear probing.<BR/><BR/>As a general direction for research, I think getting a practical dictionary with theoretical guarantees, and worst-case lookup time is of huge importance. The paradigm of worst-case lookup has really not made it in practice (at least for dynamic dicitonaries), and we can't blame them. Cuckoo hashing is the only choice that seems practical, but unfortunately we don't have theoretical guarantees (about the hash functions needed).Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-2984299411953443672007-06-21T14:09:00.000-04:002007-06-21T14:09:00.000-04:00Sorry about that Wim; fixed now, and making sure ...Sorry about that Wim; fixed now, and making sure the defaults are really set for comments! (Another few months, I'll have the basics down.)Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-79196129751508434372007-06-21T13:55:00.000-04:002007-06-21T13:55:00.000-04:00Is it just me, or is there indeed no option to com...Is it just me, or is there indeed no option to comment on your latest posting "What we're doing wrong?"Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-45235751097823818512007-06-20T12:24:00.000-04:002007-06-20T12:24:00.000-04:00Your posts are very nice! I am very interested and...Your posts are very nice! I am very interested and appreciate this kind of research direction. Hope to learn more from you in the future. <BR/><BR/>If you have more research information of this kind (that is, how to turn Theory to Practice), do share with us:)<BR/><BR/>qin<BR/>HKUSTQinhttps://www.blogger.com/profile/02051810072653171809noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-48340818939605442452007-06-20T10:56:00.000-04:002007-06-20T10:56:00.000-04:00Thanks anonymous; you're right, we have an index e...Thanks anonymous; you're right, we have an index error. Nice to get feedback before the final deadline!<BR/><BR/>MMMichael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-35051075019274401602007-06-20T05:00:00.000-04:002007-06-20T05:00:00.000-04:00In the paper, Section III, par 2, shouldn't the mu...In the paper, Section III, par 2, shouldn't the multiplications be over F_k(.) and not F_i ?Anonymousnoreply@blogger.com