Computer Engineering Commons^™

On The Database Lookup Problem Of Approximate Matching, Frank Breitinger, Harald Baier, Douglas White

Electrical & Computer Engineering and Computer Science Faculty Publications

Investigating seized devices within digital forensics gets more and more difficult due to the increasing amount of data. Hence, a common procedure uses automated file identification which reduces the amount of data an investigator has to look at by hand. Besides identifying exact duplicates, which is mostly solved using cryptographic hash functions, it is also helpful to detect similar data by applying approximate matching.

Let x denote the number of digests in a database, then the lookup for a single similarity digest has the complexity of O(x). In other words, the digest has to be compared against …

An Efficient Similarity Digests Database Lookup -- A Logarithmic Divide And Conquer Approach, Frank Breitinger, Christian Rathgeb, Harald Baier

Electrical & Computer Engineering and Computer Science Faculty Publications

Investigating seized devices within digital forensics represents a challenging task due to the increasing amount of data. Common procedures utilize automated file identification, which reduces the amount of data an investigator has to examine manually. In the past years the research field of approximate matching arises to detect similar data. However, if n denotes the number of similarity digests in a database, then the lookup for a single similarity digest is of complexity of O(n). This paper presents a concept to extend existing approximate matching algorithms, which reduces the lookup complexity from O(n) to O(log(n)). Our proposed approach is based …