Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10342428 | Digital Investigation | 2014 | 9 Pages |
Abstract
In this paper we present and evaluate a concept to extend existing approximate matching algorithms, which reduces the lookup complexity from O(x) to O(1). Therefore, instead of using multiple small Bloom filters (which is the common procedure), we demonstrate that a single, huge Bloom filter has a far better performance. Our evaluation demonstrates that current approximate matching algorithms are too slow (e.g., over 21Â min to compare 4457 digests of a common file corpus against each other) while the improved version solves this challenge within seconds. Studying the precision and recall rates shows that our approach works as reliably as the original implementations. We obtain this benefit by accuracy-the comparison is now a file-against-set comparison and thus it is not possible to see which file in the database is matched.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Frank Breitinger, Harald Baier, Douglas White,