Locality-preserving hashing
In computer science, a locality-preserving hashing is a hash function f that maps a point or points in a multidimensional coordinate space to a scalar value, such that if we have three points A, B and C such that
In other words, these are hash functions where the relative distance between the input values is preserved in the relative distance between of the output hash values; input values that are closer to each other will produce output hash values that are closer to each other.
This is in contrast to cryptographic hash functions and checksums, which are designed to have maximum output difference between adjacent inputs.
Locality preserving hashes are related to space-filling curves and locality-sensitive hashing.
External links
- Indyk, Piotr; Motwani, Rajeev; Raghavan, Prabhakar; Vempala, Santosh (1997). "Locality-preserving hashing in multidimensional spaces". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. pp. 618–625. CiteSeerX 10.1.1.50.4927. doi:10.1145/258533.258656. ISBN 0-89791-888-6.
- Chin, Andrew (1994). "Locality-preserving hash functions for general purpose parallel computation" (PDF). Algorithmica. 12 (2–3): 170–181. doi:10.1007/BF01185209.
This article is issued from Wikipedia - version of the 11/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.