c++ - Locality Sensitive Hash or pHash? -

i'm trying implement general fingerprint memoizator: have file can expressed through intelligent fingerprint (like phash images or chromaprint audio) , if our desidered (expensive) function has been computed on similar file, return same result (avoiding expensive computation).

locality sensitive hash (lsh) popular , well-performant solution approximate nearest neighbor problem in expensive multi-dimensional space.

phash library implements perceptual hashing images.

so phash transform multi-dimensional input (an image) one-dimensional object (an hash code), different lsh (again, multi-dimensional objects in lsh).

so i'm wondering how implement mono-dimensional lsh phash hash values? or in few words: how can group in bins similar phash values? alternative classic lsh approach (and if not why)?

you use n random projections split phash space 2^n buckets, similar images found same bucket. xor hash 64 possible integers hamming weight 1 check neighboring buckets conveniently , sure you'd find approximate matches.

this efficient if interested on images identical hashes (small hamming distance). if want tolerate larger hamming distances (such 8) gets tricky find matches efficiently , accurately. got performance scanning through whole table gpu, 3 year old laptop's gt 650m check 700 million hashes / second!

edit 1: can think 64-bit hash single corner on 64-dimensional cube, math easier if normalize corner coordinates -1 , 1 (this way center in origin). can express m images matrix m of size m x 64 (one row / image, 1 bit of hash / column).

simplest way split 2^n distinct groups generate n 64-dimensional vectors v_0, v_1, ..., v_n (pick each vector element normal distribution n(0,1)), can expressed matrix v of size 64 x n (one column / vector). there orthogonality enforcement mentioned @ random projection i'll skip here.

now calculating a = (m * v) > 0 m x n matrix (one image / row, 1 projection / column). next convert each row's binary representation number, 2^n different possibilities , similar hashes end same bucket.

this algorithm works orthogonal representation of data (such surf features), not binary strings. i'm sure there simpler (and computationally more efficient) algorithms binary hashes 1 way implement random projections.

i suggested xorring because if images don't have identical hashes aren't guaranteed end in same bucket. checking possible small deviations original hash can see other bins possible matches.

in way similar how computer game engine might split 2d map grid of cells of size x, find units within radius x point need check 9 cells (the 1 containing point + 8 surrounding cells) 100% accurate answer.