Research Article Open Access

Efficient Processing for Binary Submatrix Matching

Azzam Sleit, Wesam AlMobaideen, Mohammad Qatawneh and Heba Saadeh

Abstract

The heavy demand for large volumes of digital data has increased the interest in matrix-like representation. Matrices are well organized data structures which are suitable to store uniform data in order to simplify data access and manipulation. For several applications, the need is critical to efficiently search for a specific pattern in matrix structures. A pattern can be represented as an n-dimensional matrix which can be searched for within other larger n-dimensional matrices. This query will be referred to as matrix submatching. In this paper, we present and compare two algorithms for binary matrix submatching on the basis of time requirement. The first algorithm is a naive brute force approach with O(n2m2) time requirement. The second approach is based on chain code transformation which reduces the sizes of matrices resulting in less time requirement.

American Journal of Applied Sciences
Volume 6 No. 1, 2009, 78-88

DOI: https://doi.org/10.3844/ajassp.2009.78.88

Submitted On: 23 February 2008 Published On: 31 January 2009

How to Cite: Sleit, A., AlMobaideen, W., Qatawneh, M. & Saadeh, H. (2009). Efficient Processing for Binary Submatrix Matching. American Journal of Applied Sciences, 6(1), 78-88. https://doi.org/10.3844/ajassp.2009.78.88

  • 3,258 Views
  • 3,832 Downloads
  • 1 Citations

Download

Keywords

  • Matrix submatching
  • brute-force search
  • submatrix matching
  • chain code
  • transformation