About: We study the problem of finding a given [Formula: see text] matrix as a submatrix of a given Boolean matrix. Three variants are considered: search for a matching submatrix of any area, of minimum area, or of maximum area. The problem relates to 2D pattern matching, and to fields such as data mining, where the search for submatrices plays an important role. Besides these connections, the problem itself is very natural and its investigation helps to demonstrate differences between search tasks in one-dimensional and multidimensional topologies. Our results reveal that the problem variants are of different complexities. First, we show that given an [Formula: see text] Boolean matrix, the any variant can be solved in [Formula: see text] time for any given [Formula: see text] matrix, but requires various strategies for different [Formula: see text] matrices. This contrasts with the complexity of the task over matrices with entries from the set [Formula: see text], where the problem is Triangle Finding-hard and hence no algorithm with similar running time is known for it. Then, we show that the minimization variant in the case of Boolean matrices can also be solved in [Formula: see text] time. Finally, in contrast, we prove Triangle Finding-hardness for the maximization variant and show that there is a rectangular matrix multiplication-based algorithm solving it in [Formula: see text] time.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • We study the problem of finding a given [Formula: see text] matrix as a submatrix of a given Boolean matrix. Three variants are considered: search for a matching submatrix of any area, of minimum area, or of maximum area. The problem relates to 2D pattern matching, and to fields such as data mining, where the search for submatrices plays an important role. Besides these connections, the problem itself is very natural and its investigation helps to demonstrate differences between search tasks in one-dimensional and multidimensional topologies. Our results reveal that the problem variants are of different complexities. First, we show that given an [Formula: see text] Boolean matrix, the any variant can be solved in [Formula: see text] time for any given [Formula: see text] matrix, but requires various strategies for different [Formula: see text] matrices. This contrasts with the complexity of the task over matrices with entries from the set [Formula: see text], where the problem is Triangle Finding-hard and hence no algorithm with similar running time is known for it. Then, we show that the minimization variant in the case of Boolean matrices can also be solved in [Formula: see text] time. Finally, in contrast, we prove Triangle Finding-hardness for the maximization variant and show that there is a rectangular matrix multiplication-based algorithm solving it in [Formula: see text] time.
Subject
  • Matrices
  • Multi-dimensional geometry
  • Conditional constructs
  • History of Panama
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software