This document was created in addition to a recital for the seminar Pattern Matching at Chemnitz University of Technology in term 2001/2002. It is a description of basic text search approaches, which are the algorithms of Brute Force, Knuth-Morris-Pratt, Boyer-Moore and Boyer-Moore-Horspool. / Dieses Dokument entstand parallel zu einem Vortrag für das Proseminar Pattern Matching im Wintersemester 2001/2002 an der Technischen Universität Chemnitz. Es stellt die Funktionsweise der grundlegenden Suchalgorithmen Brute Force, Knuth-Morris-Pratt, Boyer-Moore sowie Boyer-Moore-Horspool dar.

This document was created in addition to a recital for the seminar Pattern Matching at Chemnitz University of Technology in term 2001/2002. It is a description of basic text search approaches, which are the algorithms of Brute Force, Knuth-Morris-Pratt, Boyer-Moore and Boyer-Moore-Horspool. / Dieses Dokument entstand parallel zu einem Vortrag für das Proseminar Pattern Matching im Wintersemester 2001/2002 an der Technischen Universität Chemnitz. Es stellt die Funktionsweise der grundlegenden Suchalgorithmen Brute Force, Knuth-Morris-Pratt, Boyer-Moore sowie Boyer-Moore-Horspool dar.

This paper presents novel tree-based search algorithms that exploit the SIMD instructions found in virtually all modern processors. The algorithms are a natural extension of binary search: While binary search performs one comparison at each iteration, thereby cutting the search space in two halves, our algorithms perform k comparisons at a time and thus cut the search space into k pieces. On traditional processors, this so-called k-ary search procedure is not beneficial because the cost increase per iteration offsets the cost reduction due to the reduced number of iterations. On modern processors, however, multiple scalar operations can be executed simultaneously, which makes k-ary search attractive. In this paper, we provide two different search algorithms that differ in terms of efficiency and memory access patterns. Both algorithms are first described in a platform independent way and then evaluated on various state-of-the-art processors. Our experiments suggest that k-ary search provides significant performance improvements (factor two and more) on most platforms.