An Index for Two Dimensional String Matching Allowing Rotations

Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen

We present an index to search a two-dimensional pattern of size m x m in a two-dimensional text of size n x n, even when the pattern appears rotated in the text. The index is based on (path compressed) tries. By using O(n^2) (i.e. linear) space the index can search the pattern in O((log_sigma(n))^(5/2)) time on average, where sigma is the alphabet size. We also consider various schemes for approximate matching, for which we obtain either O(polylog_sigma(n)) or O(n^(2*lambda)) search time, where lambda < 1 in most useful cases. A larger index of size O(n^2(log_sigma(n))^(3/2)) yields an average time of O(log_sigma(n)) for the simplest matching model. The algorithms have applications e.g. in content based information retrieval from image databases.