3 ms·
> You can use LSHs […] to help with nearest neighbor searches. Yes! A good example of this in graphics is a spatial nearest neighbor search. Space filling curv
by dahart 3y ago
> You can use LSHs […] to help with nearest neighbor searches.
Yes! A good example of this in graphics is a spatial nearest neighbor search. Space filling curves like the Morton and Hilbert curves are often used as hash functions that can preserve some amount of locality for 2-D / 3-D / N-D points. A locally sensitive hash function can basically be used to provide a sort key for data that doesn’t otherwise have a key, while increasing the odds that any two keys that are similar point to data that are also similar. This is useful on GPUs in order to improve coherence/performance of threads operating on spatial points.
https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
https://en.wikipedia.org/wiki/Hilbert_curve https://en.wikipedia.org/wiki/Hilbert_curve
- marginalia_nu 3y agoYeah there's a ton of really cool things you can do with LSHs. They're really overlooked outside of a few niches.
- Solvency 3y agoThe OP mentioned murmur3 due to its speed and high avalanche effect. So what's the best LSH function for this use case?
- dahart 3y agoHi I’m not sure I understand the question. Avalanche and local sensitivity are opposing goals, so typically the more avalanche, the less locally sensitive, and vice versa. You could even state the avalanche goal as being locally insensitive - the whole idea of avalanche is one bit change in the input produces a maximally different and uniformly distributed output.
- Solvency 3y agoI'm basically asking for the most efficient and unavalanched hash map library recommended for the purposes of this use case.
- marginalia_nu 3y agoI don't think you're gonna get one-size-fits-all answers the same way you will with avalanching hash functions. They can be one-size-fits-all because the requirement is that there is no (discernible) correlation between the input and output. Locality-sensitive hashes depend on what sort of thing you are hashing. Is the data ordered, is it a sequence, is it points in space? The requirement is that given similarity in the input given a specific metric, there is a similarity in the output given another metric. There are no universal locality sensitive hash functions because the function depends on in what sense you're trying to preserve locality.
- dahart 3y agoAh, got it. I don’t even know of one, TBH, let alone have a best one in mind. Every time I’ve used an LSH, the hashing code has been ad-hoc and tailored to pretty specific data and optimization goals. (An added layer of difficulty is that “locality” isn’t universally defined.) I’m not sure but it might be simplest to just look for a decent Map library in your favorite language, and keep the hashing part separate. It’s generally very easy to insert your own hash transform wherever you need, whether it’s on the fly, or saved as a sort key in memory. This way all you would need is to find a Morton order function, for example, if you want to hash with a z-order curve.