Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

SimHash slicing algorithm incorrect & inefficient #19

Open
tfmorris opened this issue Mar 15, 2016 · 0 comments
Open

SimHash slicing algorithm incorrect & inefficient #19

tfmorris opened this issue Mar 15, 2016 · 0 comments

Comments

@tfmorris
Copy link
Contributor

The current implementation will never output the top 16-bit slice of the simhash. It also computes the remaining slices incorrectly, but that's less serious since the computations are consistent, so the comparisons aren't effected.

Given input 0X0800040002000100L the current algorithm will generate

[0_{8}, 1_{8}, 2_{8}]

when it should generate:

[0_{8}, 1_{9},  2_{10}, 3_{11}]

It would actually be much more efficient (and easier to understand) if it switched the Hadoop type to Long instead of Text and just generated:

[0X0000000000000100L,
 0X0000000002000000L,
 0X0000040000000000L,
 0X0800000000000000L]

This would also speed up sorting and comparisons, particularly for the more common cases where many bits are set and the text strings become very long and inefficient to compare.

tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Mar 15, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Mar 15, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Mar 25, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Mar 25, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Mar 29, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Apr 1, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Apr 9, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Apr 9, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Apr 15, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
tfmorris added a commit to tfmorris/dkpro-c4corpus that referenced this issue Apr 28, 2016
Also includes a more efficient slicing algorithm that
could be used, but requires changes elsewhere in the system
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant