Summary about Locality-Sensitive Hashing (LSH) Algorithms

The major minutia features of fingerprint ridges are ridge ending, bifurcation, short ridge or dot.
A minutia, in the context of fingerprint descriptions, is a place where something unusual happens, such as two ridges merging or a ridge ending.
Minutiae and patterns are very important in the analysis of fingerprints since no two fingers have been shown to be identical 1.
- Global minutiae matching
- local minutiae structure

MCC representation associates a local structure to each minutia.
fingerprints are normalized for size and orientation, so that if we took two images of the same finger.
A local structure associated to a given minutia is represented by a cylinder .
The local minutiae representation is based on 3D data structures (called Cylinders), built from invariant distances and angles in a neighbourhood of each minutia.

LSH projects the data into a low-dim space; Similar items are mapped to the same buckets with high probability. Candidate pairs are those that hash to the same bucket.

LSH drastically reduce the number of distances to be calculated by considering only those vectors that collide with the query vector under one or more of the hash functions.
Generalized LSH: Amplify using AND-OR cascades ......
LSH for Euclidean Distance A set of basis functions to start LSH for Euclidean distance can be obtained by choosing random lines and projecting points onto those lines 3. Each line is broken into fixed-length intervals, and the function answers "yes" to a pair of points that fall into the same interval. Nearby points are always close and distant points are rarely in the same bucket.
Exact Euclidean LSH (E2LSH) E2LSH package provides a randomized solution for the high-dim near neighbour problem in the Euclidean space.

[2]: "Minutia Cylinder-code: A new Representation and Matching Technique for Fingerprint Recognition" "MCC"