Parallel Text Search

Description

This application is a trivial parallelization of agrep program from University of Arizona. agrep is capable of partial match and approximate searches [1]. Our parallel version, called pgrep , can operate in one of two modes. In the first mode, the list of files to be searched is partitioned, round-robin, among the processors. In the second mode, each input file is block-partitioned among the processors, so that each processor searches a distinct portion of the file. This application performs I/O using synchronous read() operations.

Input Dataset

To drive this application, we used the "/users" document hierarchy on the University of Maryland web server. The hierarchy contained 475~MB in 18,655 files.

Workload

We used a complex pattern including wildcards, disjunction and substitution: "b#dy,[a-z]#gif,l#[n-z]t#,F#" .
In this pattern, "," is OR-construct; "#" is wildcard; and "[a-z]" is all the characters between "a" and "z". We allowed 3 substitutions on this pattern, i.e. any string which can be obtained by substituting 3 characters is also accepted by the pgrep.

Traces

You can download the trace files in the following formats:

Compressed, ASCII format (954 KB).

References

[1] Sun Wu and Udi Manber. agrep - a fast approximate pattern-matching tool . In USENIX Conference Proceedings, pages 153-162, San Fransisco, CA, Winter 1992.

Last updated on Tue May 27 12:37:44 EDT 1997 by Mustafa Uysal (uysal@cs.umd.edu ).