You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Lance Norskog (JIRA)" <ji...@apache.org> on 2011/07/03 23:37:21 UTC
[jira] [Created] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
-------------------------------------------------------------------------
Key: MAHOUT-753
URL: https://issues.apache.org/jira/browse/MAHOUT-753
Project: Mahout
Issue Type: New Feature
Components: Math
Reporter: Lance Norskog
Priority: Minor
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069431#comment-13069431 ]
Sean Owen commented on MAHOUT-753:
----------------------------------
This suggests something is incorrect about MurmurHash. For example nextDouble() generates a value from the uniform distribution in [0,1]. The standard deviation ought to be sqrt((1-0)/12) ~= 0.2887. Random and MersenneTwister show this value but MurmurHash is generating a deviation of twice that.
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurBench.java, MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen resolved MAHOUT-753.
------------------------------
Resolution: Won't Fix
Assignee: Sean Owen
Surely that's fine though, it's a PRNG; it is meant to return a different stream of values.
Do we have good reason to believe that this particular algo returns well-distributed numbers? A few things here look innocent but might not be: alternately returning high/low 32 bits, collapsing the high/low 32 bits before hashing, using the last output as input to hash for next value.
We don't use java.util.Random, but the Mersenne twister. Do you have evidence this provides better properties than that? Otherwise I am not clear on the reason for adding this to the project.
As you say maybe reopen this later.
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069877#comment-13069877 ]
Lance Norskog commented on MAHOUT-753:
--------------------------------------
There are time-tested (like us!) test suites for the metaphysically ineffable quality known as randomness, from NIST and something called ENT. If I really want to go after this, I would do a web site where you upload a pile-o-bits and it runs all the tests.
Anyone who considers arithmetical methods of producing random digits is, of course, [in the state of sin|http://www.todayinsci.com/N/Neumann_John/NeumannJohn-Quotations.htm].
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurBench.java, MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069420#comment-13069420 ]
Lance Norskog commented on MAHOUT-753:
--------------------------------------
Here are some benchmarks of 3 random generators: the JDK one, the MurmurHashRandom.java on this patch, and the Mersenne Twister used by Mahout. The first table is the standard deviations for 1000 samples, the second is the standard deviations for 10 million samples, and the third is the time for 10 million in milliseconds. (The times are all 0 for 1000 samples.) All three work by generating one 32-bit int per random cycle, and the same code turns those ints into the various returned types.
h5. Standard Deviations for 1000 samples
|| |JDK|MurmurHash|MersenneTwister||
|Double|0.289|0.579|0.291|
|Gaussian|1.016|0.988|0.996|
|Float|0.286|0.582|0.290|
|Integer|1.241e9|1.225e9|1.227e9|
|Integer(100)|28.491|29.320|29.036|
|Long|5.320e18|5.298e18|5.299e18|
|Boolean|0.5|0.435|0.499|
h5. Standard deviations for 10 million samples
|| |JDK|MurmurHash|MersenneTwister||
|Double|0.288|0.577|0.288|
|Gaussian|1.000|1.000|0.999|
|Float|0.288|0.576|0.288|
|Integer|1.239e9|1.241e9|1.239e9|
|Integer(100)|28.869|28.933|28.875|
|Long|5.324e18|5.318e18|5.324e18|
|Boolean|0.500|0.432|0.500|
h5. Execution time for 10 million samples, in milliseconds
|| |JDK|MurmurHash|MersenneTwister||
|Double|905|937|1826|
|Gaussian|2543|6257|3777|
|Float|515|469|937|
|Integer|468|501|192|
|Integer(100)|592|1155|1033|
|Long|920|923|1795|
|Boolean|530|547|1001|
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurBench.java, MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069447#comment-13069447 ]
Lance Norskog commented on MAHOUT-753:
--------------------------------------
Thanks! It turns out the generator method for java.lang.Random receives a request for N random bits, and it masks a generated int to give the requested number of random bits (starting from position 0).
[http://www.javamex.com/tutorials/random_numbers/java_util_random_subclassing.shtml]
Quote from the net: "MurmurHash is good if fed by a linear congruent generator, but not by directly refeeding the seed. But it is very fast for random access." Meaning, for continuous setSeed() uses like deterministically projecting matrices, it is a good choice.
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurBench.java, MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Lance Norskog updated MAHOUT-753:
---------------------------------
Attachment: MurmurHashRandom.java
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Priority: Minor
> Attachments: MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Lance Norskog updated MAHOUT-753:
---------------------------------
Attachment: MurmurBench.java
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurBench.java, MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Ted Dunning (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069863#comment-13069863 ]
Ted Dunning commented on MAHOUT-753:
------------------------------------
Murmur hash should also be good if fed from a sequence counter multiplied by a large prime. This is a weak form of congruential generator.
Lance, the best test for distribution would be a one-sided KS test. I don't think that we have one handy, but it is very easy to build one from spare parts. See http://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test
The basic idea is that you find the largest positive and negative differences of the empirical cumulative distribution function from the theoretically desired cumulative distribution function. The size of these errors is a good measure of how different the distributions should be. At 1 mega-sample, this difference should be less than about 0.002. Commons math has a way to compute the test statistic distribution if we really care about the details.
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Assignee: Sean Owen
> Priority: Minor
> Attachments: MurmurBench.java, MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13059286#comment-13059286 ]
Lance Norskog commented on MAHOUT-753:
--------------------------------------
Minimally tested. Gives better randomness that java.util.Random with the Gaussian distribution.
Is exactly as fast as j.u.Random.
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Priority: Minor
> Attachments: MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-753) MurmurHashRandom class: subclass of
java.util.Random that uses MurmurHash
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-753?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13063706#comment-13063706 ]
Lance Norskog commented on MAHOUT-753:
--------------------------------------
This has some problems. MurmurHashRandom.next() overrides Random.next() and supplies a different stream of ints to the public Random methods. Those methods seem to have some weird dependencies on what Random.next() returns.
So, it's an active (and badly needed) project, but not finished.
> MurmurHashRandom class: subclass of java.util.Random that uses MurmurHash
> -------------------------------------------------------------------------
>
> Key: MAHOUT-753
> URL: https://issues.apache.org/jira/browse/MAHOUT-753
> Project: Mahout
> Issue Type: New Feature
> Components: Math
> Reporter: Lance Norskog
> Priority: Minor
> Attachments: MurmurHashRandom.java
>
>
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira