5 ms·
There is a fourth category of hash functions: find similar items. For English words, this is usually done with soundex / metaphone / doublemetaphone. Fun fact,
by adamzochowski 3y ago
There is a fourth category of hash functions: find similar items.
For English words, this is usually done with soundex / metaphone / doublemetaphone. Fun fact, soundex was developed over 100 years ago to help immigrants find their families in USA even if they didn't know how to spell their last name. Soundex is supported by most DBs.
For images, there are hashes like ahash/phash/dhash/whash/blockmeat/colormoment/colorhas/marrHildreth .
Most popular Audio hash is acoustid. There was also EchoPrint (with two incompatible versions), but once EchoNest was bought out by Spotify the public support and development into echoprint died. Some groups of people tried to keep echoprint alive but I am unaware if it is still used by anyone publicly.
- esafak 3y agoToday you would use embeddings optimized for similarity search.
- nighthawk454 3y agoEmbedding models are still essentially a hash function, just very complex ones
- esafak 3y agoMoreover, and crucially, they are learned.
- scentoni 3y agoThose are examples of useful functions. They are not examples of useful hash functions.
- gabetax 3y agoSpecifically, these functions to not provide "uniform distribution".
- jagged-chisel 3y agoThat isn’t a requirement of an algorithm called a hash function
- gabetax 3y agoFrom the article: > For a function to be useful as a hash function, it must exhibit the property of uniform distribution It's also listed as the first property on the Wikipedia page: https://en.wikipedia.org/wiki/Hash_function#Uniformity https://en.wikipedia.org/wiki/Hash_function#Uniformity
- jagged-chisel 3y agoI can’t find the text you quoted. The article starts off: > A hash function is any function that can be used to map data of arbitrary size to fixed-size values And the first sentence in the section you link says > A good hash function should map the expected inputs as evenly as possible over its output range. It doesn’t have to be “good” to be a hash function.
- anamexis 3y agoThat's not a meaningful definition of a hash function, then. def hash(val): return 0
- jagged-chisel 3y agoYes, this is a hash function. Whether it’s “useful” or “good” is the purview of the architect. Tangential edit: https://xkcd.com/221/ https://xkcd.com/221/
- pcthrowaway 3y agoThe best thing about that one is that it seeds the panel with a random number every time you refresh
- derefr 3y agoI think you're conflating "functions used to build a hash table" with "functions used to build a dictionary ADT." A hash table doesn't have to serve the purpose of storing items in a dictionary ADT. A hash table where everything that's similar collides into the same buckets is just as useful for finding "a linked list of similar items" in O(1), as a hash table where everything gets its own unique bucket is useful for finding items in O(1).
- dimatura 3y agoIt's true that these functions are in some sense very different to traditional hash functions, because they are designed to create "collisions" (or at least be similar) for elements that are similar. But I still think it is intuitive to use the term, maybe qualified as a "similarity hash" (I've also seen "perceptual hash" or "semantic hash"). In both cases we are describing a (potentially) large object with a short code. In normal hashes, the hash is supposed to be the same for objects that are exactly the same - in similarity hashes, that is softened to similar hashes for similar objects.
- pcthrowaway 3y agoFunctions that create collisions can still hashes can't they? Things like CRCs, Checksums are loosely considered hash functions: https://en.wikipedia.org/wiki/List_of_hash_functions https://en.wikipedia.org/wiki/List_of_hash_functions MD5SUM is a classic example of a hash function with a low (but still reasonable) chance of a collision
- lynndotpy 3y agoIf I remember correctly, Apple's Voxel Net (~2018 neural network, used for doing machine learning on sparse lidar point-cloud data) uses a simple "spatial hash" for this purpose, using the coordinate of the voxel as a key.
- dimatura 3y agoYeah, hashing for spatial data is a fairly common technique (and not invented for that paper). It totally makes sense for applications where there is a need to index sparse data in a potentially very large or even unbounded physical space. There's some hashes that are specialized for keys that are 3-dimensional points or voxel coordinates, but almost any off-the-shelf hash will do if applied to say, the concatenated indices of a voxel in a given coordinate frame.
- joezydeco 3y agoSoundex is still out there. If you live in Illinois, Florida, or Wisconsin your drivers license number is a soundex hash of your name combined with your birthday. http://www.highprogrammer.com/alan/numbers/dl_us_shared.html http://www.highprogrammer.com/alan/numbers/dl_us_shared.html
- xorvoid 3y agoTIL! Fascinating! Of course my first thought was.. “what about hash collisions?” And naturally each state has selected their own resolution. In Illinois you can apparently be detained for a while due to a hash collision with a suspect.. plate numbers aren’t unique apparently!?
- joezydeco 3y agoLicense plate numbers are unique. Two somewhat similar names can resolve to the same Drivers License number, but in those (extremely rare) cases it's just a matter of checking the actual name against the warrant.
- jll29 3y agoRobert C. Russell (and Margaret King Odell) invented SOUNDEX, which is described in US Patent 1,261,167 (1918) -see also Knuth (1973) TAOCP vol. 3. https://patentimages.storage.googleapis.com/31/35/a1/f697a3ab85ced6/US1261167.pdf https://patentimages.storage.googleapis.com/31/35/a1/f697a3a...
- michaelcampbell 3y agoWhile researching Soundex in the mid/late 80's, I of course soundex'd my last name and realized that it was the first part of my state's driver's license #.
- metadat 3y agoIntriguing, I just checked mine and it seems California doesn't appear to do this. If you're comfortable sharing, would like to find out which state you're referring to. Cheers.
- ComputerGuru 3y agoAnother poster shared this link: http://www.highprogrammer.com/alan/numbers/dl_us_shared.html http://www.highprogrammer.com/alan/numbers/dl_us_shared.html It has the encoding formula for Wisconsin, Illinois, and Florida (which match the parent's comment) but there may be others.
- michaelcampbell 3y agoMine was Illinois. I got it in the early 1980's, and moved away shortly thereafter, so no idea if they still do. Weirdly, I remember that # even now. Soundex-???-2DigitYearOfBirth-??? Looks like at least the format has changed since then.
- deleted 3y ago[deleted]
- preseinger 3y agohash functions are ultimately just a mapping of an input set of high/infinite cardinality to an output set of fixed/finite cardinality you correctly point out that some hash functions exist which map input words in some specific language into similarity groups based on some concept of semantics but this is essentially unrelated to the topics raised in the linked article
- Genbox 3y agoThey are called similarity digests or sometimes "fuzzyhashing". For generic files there are Context Triggered Piecewise Hashing (CTPH), Trend Micro Locality Sensitive Hash (TLSH) and Similary Digest Hash (SDHash)