Locality preserving hashing
Encyclopedia
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 checksum
s, which are designed to have maximum output difference between adjacent inputs.
Locality preserving hashes are related to space-filling curve
s and locality sensitive hashing
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a locality preserving hashing is a hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
f that maps a point or points in a multidimensional coordinate space
Coordinate space
In mathematics, specifically in linear algebra, the coordinate space, Fn, is the prototypical example of an n-dimensional vector space over a field F. It can be defined as the product space of F over a finite index set.-Definition:...
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
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
hash functions and checksum
Checksum
A checksum or hash sum is a fixed-size datum computed from an arbitrary block of digital data for the purpose of detecting accidental errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and...
s, which are designed to have maximum output difference between adjacent inputs.
Locality preserving hashes are related to space-filling curve
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
s and locality sensitive hashing
Locality sensitive hashing
Locality-sensitive hashing is a method of performing probabilistic dimension reduction of high-dimensional data. The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability .-Definition:An LSH family \mathcal F is defined fora...
.