4 ms·

> An efficient implementation of a hash function (based on SimHashing) which calculates a 128-bit hash from disassembled functions - and which preserves similar

> An efficient implementation of a hash function (based on SimHashing) which calculates a 128-bit hash from disassembled functions - and which preserves similarity (e.g. “distance” of two functions can be calculated by simply calculating the hamming distance between two hashes - which translates to two XOR and two POPCNT instructions on x64). Huh! This obviously desirable property of a good hash function for this application is one of the classic undesirable properties of a good hash function for cryptography. I don't think that I was previously familiar with this sort of hash function, very cool. Are space-filling curves related to these hash functions?

viraptor 8y ago
Another hash with a similar property uses close pronunciation as distance: https://en.m.wikipedia.org/wiki/Soundex https://en.m.wikipedia.org/wiki/Soundex
- simcop2387 8y ago
  Soundex however is only designed for English names. Take a look at Metaphone or Double-Metaphone for a more generic version of the same idea. https://en.wikipedia.org/wiki/Metaphone https://en.wikipedia.org/wiki/Metaphone
tylersmith 8y ago
Not all hashes are intended for cryptographic applications or want the Avalanche effect. Some are simply succinct digests of data and some attempt to retain important information like the hash described here.
livueta 8y ago
Another example of this sort of hash function (where the hamming distance between the hashes of similar inputs will be small) is pHash[1]. I've been playing with it recently for deduping bit-different but perceptually-identical images, and it works pretty well and the low hamming distance property makes it dead simple to use. --- [1] https://www.phash.org/ https://www.phash.org/
snovv_crash 8y ago
Space filling curves would work in some situations, but wouldn't be as efficient as a purpose-designed hash. A space filling curve, for example, would break down under 50+ dimensions, which is why you'd be using one of these hashes in the first place rather than a tree. If you want to know more, I'd suggest researching Locality Sensitive Hashing. Flann[1] has a decent implementation. 1. https://www.cs.ubc.ca/research/flann/ https://www.cs.ubc.ca/research/flann/
hawski 8y ago
Pardon if I'm not well informed, that's why I ask. Is the problem similar to string search with multiple patterns? Could Rabin-Karp algorithm be used for searching? It also uses hashing. Or could this algorithm be used instead of Rabin-Karp?
matthewaveryusa 8y ago
You can use bad hashing functions for a lot of applications. In the traditional interview question: find all anagrams in a list of words, you can sort the letters of a word as the hashing function, and use a traditional hashmap that does conflict-resolution with a linked list as a solution. Fun stuff
- jimktrains2 8y ago
  Bad isn't the right word here. It's a bad cryptographic hash, sure, but a hash doesn't necessarily need to be cryptographic to be a hash. P-hash for finding similar images; sounded/metaphone for similar English pronunciation; crcs, cityhash, siphash, &c for fast checksums and hashtables; and location sensitive hashes like simhash for "close matches" for spam filtering and content aggregation all have a long history of being good and useful hashes without being cryptographically secure.

viraptor 8y ago

Another hash with a similar property uses close pronunciation as distance: https://en.m.wikipedia.org/wiki/Soundex https://en.m.wikipedia.org/wiki/Soundex

simcop2387 8y ago
Soundex however is only designed for English names. Take a look at Metaphone or Double-Metaphone for a more generic version of the same idea. https://en.wikipedia.org/wiki/Metaphone https://en.wikipedia.org/wiki/Metaphone

tylersmith 8y ago

Not all hashes are intended for cryptographic applications or want the Avalanche effect. Some are simply succinct digests of data and some attempt to retain important information like the hash described here.

livueta 8y ago

Another example of this sort of hash function (where the hamming distance between the hashes of similar inputs will be small) is pHash[1]. I've been playing with it recently for deduping bit-different but perceptually-identical images, and it works pretty well and the low hamming distance property makes it dead simple to use. --- [1] https://www.phash.org/ https://www.phash.org/

snovv_crash 8y ago

Space filling curves would work in some situations, but wouldn't be as efficient as a purpose-designed hash. A space filling curve, for example, would break down under 50+ dimensions, which is why you'd be using one of these hashes in the first place rather than a tree. If you want to know more, I'd suggest researching Locality Sensitive Hashing. Flann[1] has a decent implementation. 1. https://www.cs.ubc.ca/research/flann/ https://www.cs.ubc.ca/research/flann/

hawski 8y ago

Pardon if I'm not well informed, that's why I ask. Is the problem similar to string search with multiple patterns? Could Rabin-Karp algorithm be used for searching? It also uses hashing. Or could this algorithm be used instead of Rabin-Karp?

matthewaveryusa 8y ago

You can use bad hashing functions for a lot of applications. In the traditional interview question: find all anagrams in a list of words, you can sort the letters of a word as the hashing function, and use a traditional hashmap that does conflict-resolution with a linked list as a solution. Fun stuff

jimktrains2 8y ago
Bad isn't the right word here. It's a bad cryptographic hash, sure, but a hash doesn't necessarily need to be cryptographic to be a hash. P-hash for finding similar images; sounded/metaphone for similar English pronunciation; crcs, cityhash, siphash, &c for fast checksums and hashtables; and location sensitive hashes like simhash for "close matches" for spam filtering and content aggregation all have a long history of being good and useful hashes without being cryptographically secure.