• DocumentCode
    279064
  • Title

    Parallel template matching on a restricted addressing mode

  • Author

    Fujita, Satoshi ; Yamashita, Masafumi ; Ae, Tadashi

  • Author_Institution
    Fac. of Eng., Hiroshima Univ., Japan
  • Volume
    i
  • fYear
    1991
  • fDate
    8-11 Jan 1991
  • Firstpage
    27
  • Abstract
    Discusses the limitation on the speedup of the template matching by an ideal parallel processing scheme. The authors treat it through the following simplified pattern matching problem, i.e., on an ideal parallel processing scheme with significantly large number of processing elements and the interconnection, identify the position of a template in a text as fast as possible. Assuming a single instruction constraint on the scheme, the matching operation takes O(log2n /loglogn) time, while without the constraint, it takes O(logn) time where n is the size of the template
  • Keywords
    computational complexity; parallel algorithms; parallel architectures; parallel processing; pattern matching; restricted addressing mode; single instruction constraint; template matching; Automata; Automatic generation control; Computer science; Data structures; Detection algorithms; Formal languages; Parallel processing; Pattern matching; Pattern recognition; Search methods;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    System Sciences, 1991. Proceedings of the Twenty-Fourth Annual Hawaii International Conference on
  • Conference_Location
    Kauai, HI
  • Type

    conf

  • DOI
    10.1109/HICSS.1991.183868
  • Filename
    183868
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=279064