Similarity Hashing Based on Levenshtein Distances

Details

Serval ID
serval:BIB_689E756093D0
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Title
Similarity Hashing Based on Levenshtein Distances
Title of the conference
Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications
Author(s)
Breitinger Frank, Ziroff Georg, Lange Steffen, Baier Harald
Publisher
Springer International Publishing
ISBN
9783319125671
9783319125688
ISSN
0302-9743
1611-3349
Publication state
Published
Issued date
2014
Editor
Peterson Gilbert, Shenoi Sujeet
Volume
433
Pages
133-147
Language
english
Abstract
It is increasingly common in forensic investigations to use automated pre-processing techniques to reduce the massive volumes of data that are encountered. This is typically accomplished by comparing fingerprints (typically cryptographic hashes) of files against existing databases. In addition to finding exact matches of cryptographic hashes, it is necessary to find approximate matches corresponding to similar files, such as different versions of a given file.
This paper presents a new stand-alone similarity hashing approach called saHash, which has a modular design and operates in linear time. saHash is almost as fast as SHA-1 and more efficient than other approaches for approximate matching. The similarity hashing algorithm uses four sub-hash functions, each producing its own hash value. The four sub-hashes are concatenated to produce the final hash value. This modularity enables sub-hash functions to be added or removed, e.g., if an exploit for a sub-hash function is discovered. Given the hash values of two byte sequences, saHash returns a lower bound on the number of Levenshtein operations between the two byte sequences as their similarity score. The robustness of saHash is verified by comparing it with other approximate matching approaches such as sdhash.
Keywords
Fuzzy hashing, similarity digest, Levenshtein distance
Create date
06/05/2021 11:01
Last modification date
06/05/2021 11:34
Usage data