Exact Pattern Matching with Feed-Forward Bloom Filters

This paper presents a new, memory efficient and cacheoptimized algorithm for simultaneously searching for a large number of patterns in a very large corpus. This algorithm builds upon the Rabin-Karp string search algorithm and incorporates a new type of Bloom filter that we call a feed-forward Bloom...

Full description

Saved in:
Bibliographic Details
Main Authors: Moraru, Iulian, Andersen, David G
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Cache
Computer architecture
Filtering software
Optimization algorithms
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a new, memory efficient and cacheoptimized algorithm for simultaneously searching for a large number of patterns in a very large corpus. This algorithm builds upon the Rabin-Karp string search algorithm and incorporates a new type of Bloom filter that we call a feed-forward Bloom filter. While it retains the asymptotic time complexity of previous multiple pattern matching algorithms, we show that this technique, along with a CPU architecture aware design of the Bloom filter, can provide speedups between 2x and 30x, and memory consumption reductions as large as 50x when compared with grep. [PUBLICATION ABSTRACT]
ISSN:2164-0300