Locality-sensitive hashing

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, locality-sensitive hashing (LSH) is a fuzzy hashing technique that hashes similar input items into the same "buckets" with high probability. (The number of buckets is much smaller than the universe of possible input items.) Since similar items end up in the same buckets, this technique can be used for <a href="/facts/Cluster_analysis/HUeDnWPt">data clustering</a> and <a href="/facts/Nearest_neighbor_search/R6QTyAph">nearest neighbor search</a>. It differs from <a href="/facts/Hash_function/rk6MlCt3">conventional hashing techniques</a> in that <a href="/facts/Hash_collision/QwAesPFG">hash collisions</a> are maximized, not minimized. Alternatively, the technique can be seen as a way to <a href="/facts/Dimension_reduction/XoRpcrB0">reduce the dimensionality</a> of high-dimensional data; high-dimensional input items can be reduced to low-dimensional versions while preserving relative distances between items.
Hashing-based approximate <a href="/facts/Nearest-neighbor_search/R6QTyAph">nearest-neighbor search</a> algorithms generally use one of two main categories of hashing methods: either data-independent methods, such as locality-sensitive hashing (LSH); or data-dependent methods, such as locality-preserving hashing (LPH).
Locality-preserving hashing was initially devised as a way to facilitate <a href="/facts/Pipeline_(computing)/xmHjrPMP">data pipelining</a> in implementations of <a href="/facts/Parallel_RAM/G1pCFgWP">massively parallel</a> algorithms that use <a href="/facts/Routing/Ml6MVCaC">randomized routing</a> and <a href="/facts/Universal_hashing/NICffew4">universal hashing</a> to reduce memory <a href="/facts/Resource_contention/eAh3Rtrs">contention</a> and <a href="/facts/Network_congestion/9ohkRMso">network congestion</a>.

Locality-sensitive hashing open-in-new

Locality-sensitive hashing