5 ms·

Tabulation Hashing and Independence (2012)

18 points by Libertatea 13y ago

dang 13y ago
Can anyone suggest a better title? and more importantly, a better url? This story might be interesting, but it's hard to tell from the article.
- bentoner 13y ago
  This is a better article, but maybe it's too technical: http://rjlipton.wordpress.com/2012/04/14/tabulation-hashing-and-independence/ http://rjlipton.wordpress.com/2012/04/14/tabulation-hashing-...
  - dang 13y ago
    Ok, we changed it. Thanks. The original url [1] was clearly not a good one for HN. 1. http://sciencenordic.com/professor-revolutionises-computers-most-random-function-ever http://sciencenordic.com/professor-revolutionises-computers-...
trebor 13y ago
Sounds like this is "the most random hash function" rather than a random number generator, as I first thought. I wonder how well it'll stand up to scrutiny.
- deleted 13y ago
  [deleted]
- jordigh 13y ago
  Whenever I read mainstream news on topics I'm deeply familiar with, and I see how badly they are reported, I realise that mainstream news probably misreports all topics, not just the ones I'm familiar with.
  - Tenoke 13y ago
    "The Gell-Mann amnesia effect"
  - aptwebapps 13y ago
    I'm convinced this is true for most mainstream news reports on even slightly technical topics. It's not just IT - if you talk to people in other disciplines you get the same response. I think you could discount a little bit of it as experts being overly picky and journalists having to bring the topic to the masses, but it's often much worse than that.
  - lotsofmangos 13y ago
    I was thinking about this and wondering if it would be possible to have a news organisation with no article writers, just editors who solicit articles and interviews from domain experts.
    - trebor 13y ago
      It would be so different I'm sure that it has a chance to succeed, but it wouldn't necessarily be easy to get started. I'm thinking mainly about the difficulty in forming contacts, etc.
- evunveot 13y ago
  A hash function becomes a random number generator if you feed its output to its input.
ultimatedelman 13y ago
"But it will be the best for a great number of screws," he said, matter-of-factly.
lutusp 13y ago
This is the worst description of the randomness issue I have ever read. In trying to make itself accessible to nontechnical people, it manages to miss or misstate every key point about randomness and its uses. It also doesn't understand the meaning or purpose of the function being described. In the name of public accessibility, it's a perfect wash. Guideline: if an article about random generating functions doesn't include the word "entropy" in the first 1000 words, it's not worth reading.
- nhaehnle 13y ago
  Guideline: if an article about random generating functions doesn't include the word "entropy" in the first 1000 words, it's not worth reading. I don't feel like that applies to the field "covered" by this particular article, though. To give an example, one can write a useful and enlightening article about the usefulness of randomness for universal hashing without ever using the word "entropy". And it seems that hash functions is what this article is trying to be about. The article is a complete train wreck, but a lack of the word "entropy" is not the cause.
  - lutusp 13y ago
    I would agree, except for the fact that the article claims the described function produces a high degree of randomness -- "the most random function ever" -- which makes entropy an issue. If for no other reason, it would reveal the author's familiarity with the field's terminology. Otherwise we're entitled to assume that the hyperbolic claims have no basis (which I happen to believe is the case). I agree that the article ends up discussing hashing in a roundabout way, and randomness seems to have been dropped as a topic, but the title cries out for vindication.
- zem 13y ago
  the article itself was pretty rubbish, but i upvoted it anyway because it let me know about the new hash function and gave me terms to search for.
DanielStraight 13y ago
Professor Thorup's papers are here: http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thorup:Mikkel http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thorup:Mik... It would appear "Tabulation Hashing" is the key term. It's on Wikipedia here: https://en.wikipedia.org/wiki/Tabulation_hashing https://en.wikipedia.org/wiki/Tabulation_hashing (EDIT: This comment originally appeared on a version of the story with a different URL and different title, neither of which was particularly informative.)
bentoner 13y ago
I think that this is the paper: https://scirate.com/arxiv/1311.3121 https://scirate.com/arxiv/1311.3121
gesman 13y ago
How does randomness speeds up retrieval of data? You may pick up random girl in a bar but if you like to retrieve her the next day - you won't dial the random number, do you?

18 points by Libertatea 13y ago

dang 13y ago

Can anyone suggest a better title? and more importantly, a better url? This story might be interesting, but it's hard to tell from the article.

bentoner 13y ago
This is a better article, but maybe it's too technical: http://rjlipton.wordpress.com/2012/04/14/tabulation-hashing-and-independence/ http://rjlipton.wordpress.com/2012/04/14/tabulation-hashing-...
- dang 13y ago
  Ok, we changed it. Thanks. The original url [1] was clearly not a good one for HN. 1. http://sciencenordic.com/professor-revolutionises-computers-most-random-function-ever http://sciencenordic.com/professor-revolutionises-computers-...

trebor 13y ago

Sounds like this is "the most random hash function" rather than a random number generator, as I first thought. I wonder how well it'll stand up to scrutiny.

deleted 13y ago
[deleted]
jordigh 13y ago
Whenever I read mainstream news on topics I'm deeply familiar with, and I see how badly they are reported, I realise that mainstream news probably misreports all topics, not just the ones I'm familiar with.
- Tenoke 13y ago
  "The Gell-Mann amnesia effect"
- aptwebapps 13y ago
  I'm convinced this is true for most mainstream news reports on even slightly technical topics. It's not just IT - if you talk to people in other disciplines you get the same response. I think you could discount a little bit of it as experts being overly picky and journalists having to bring the topic to the masses, but it's often much worse than that.
- lotsofmangos 13y ago
  I was thinking about this and wondering if it would be possible to have a news organisation with no article writers, just editors who solicit articles and interviews from domain experts.
  - trebor 13y ago
    It would be so different I'm sure that it has a chance to succeed, but it wouldn't necessarily be easy to get started. I'm thinking mainly about the difficulty in forming contacts, etc.
evunveot 13y ago
A hash function becomes a random number generator if you feed its output to its input.

ultimatedelman 13y ago

"But it will be the best for a great number of screws," he said, matter-of-factly.

lutusp 13y ago

This is the worst description of the randomness issue I have ever read. In trying to make itself accessible to nontechnical people, it manages to miss or misstate every key point about randomness and its uses. It also doesn't understand the meaning or purpose of the function being described. In the name of public accessibility, it's a perfect wash. Guideline: if an article about random generating functions doesn't include the word "entropy" in the first 1000 words, it's not worth reading.

nhaehnle 13y ago
Guideline: if an article about random generating functions doesn't include the word "entropy" in the first 1000 words, it's not worth reading. I don't feel like that applies to the field "covered" by this particular article, though. To give an example, one can write a useful and enlightening article about the usefulness of randomness for universal hashing without ever using the word "entropy". And it seems that hash functions is what this article is trying to be about. The article is a complete train wreck, but a lack of the word "entropy" is not the cause.
- lutusp 13y ago
  I would agree, except for the fact that the article claims the described function produces a high degree of randomness -- "the most random function ever" -- which makes entropy an issue. If for no other reason, it would reveal the author's familiarity with the field's terminology. Otherwise we're entitled to assume that the hyperbolic claims have no basis (which I happen to believe is the case). I agree that the article ends up discussing hashing in a roundabout way, and randomness seems to have been dropped as a topic, but the title cries out for vindication.
zem 13y ago
the article itself was pretty rubbish, but i upvoted it anyway because it let me know about the new hash function and gave me terms to search for.

DanielStraight 13y ago

Professor Thorup's papers are here: http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thorup:Mikkel http://www.informatik.uni-trier.de/~ley/pers/hd/t/Thorup:Mik... It would appear "Tabulation Hashing" is the key term. It's on Wikipedia here: https://en.wikipedia.org/wiki/Tabulation_hashing https://en.wikipedia.org/wiki/Tabulation_hashing (EDIT: This comment originally appeared on a version of the story with a different URL and different title, neither of which was particularly informative.)

bentoner 13y ago

I think that this is the paper: https://scirate.com/arxiv/1311.3121 https://scirate.com/arxiv/1311.3121

gesman 13y ago

How does randomness speeds up retrieval of data? You may pick up random girl in a bar but if you like to retrieve her the next day - you won't dial the random number, do you?