Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431008 | Journal of Discrete Algorithms | 2012 | 13 Pages |
Abstract
Many applications have a need for indexing unstructured data. It turns out that a similar ad-hoc method is being used in many of them – that of considering small particles of the data.In this paper we formalize this concept as a tiling problem and consider the efficiency of dealing with this model in the pattern matching setting.We present an efficient algorithm for the one-dimensional tiling problem, and the one-dimensional tiled pattern matching problem. We prove the two-dimensional problem is hard and then develop an approximation algorithm with an approximation ratio converging to 2. We show that other two-dimensional versions of the problem are also hard, regardless of the number of neighbors a tile has.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Amihood Amir, Haim Paryenty,