Article ID Journal Published Year Pages File Type
10342428 Digital Investigation 2014 9 Pages PDF
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
, , ,