Browse Prior Art Database

Optimal Parallel Algorithms for Matching Problems

IP.com Disclosure Number: IPCOM000128209D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 33 page(s) / 84K

Publishing Venue

Software Patent Institute

Related People

Z. Kedern: AUTHOR [+5]

Abstract

Computing characteristics of lineage functions of forests is a fundamental step in solving several problems such as term matching and 2-dimensional pattern matching. We design optimal speedup parallel algorithms for computing such characteristics on a CRCW PRAM. We use these algorithms to design optimal speedup parallel algorithms for solving the following classical problems: 1. anti-unification, 2. classes off unification, 3. teen matching, and 4. Z-dimensional pattern matching. All of these problems have a rich history in that optimal sequen-tial algorithms, as well as suboptimal parallel algorithms for solving them have been reported before. We also extend our algorithms to run on the weaker CREW PRAM with optimal speedup as well. This will involve a simple randomization scheme for simulating concurrent writes through a use of hashing.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 33

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Optimal Parallel Algorithms for Matching Problems

Z. Kedern G. Landau K. Palern

Technical Report 470

November 1988 This report is supported in part by the Office of Naval Research under Contract Number N00014-85-K-0046. Optimal Parallel Algorithms for Matching Problemst't

(Extended Summary)

Zvi M. Kedem Department of Computer Science Courant Institute of Mathematical Sciences New York University

Gad M. Landau Division of Computer Science Polytechnic University

Krishna V. Palem IBM Research Division Thomas 3. Watson Research Center

November 1988

Abstract

Computing characteristics of lineage functions of forests is a fundamental step in solving several problems such as term matching and 2-dimensional pattern matching. We design optimal speedup parallel algorithms for computing such characteristics on a CRCW PRAM. We use these algorithms to design optimal speedup parallel algorithms for solving the following classical problems: 1. anti-unification, 2. classes off unification, 3. teen matching, and 4. Z-dimensional pattern matching. All of these problems have a rich history in that optimal sequen-tial algorithms, as well as suboptimal parallel algorithms for solving them have been reported before. We also extend our algorithms to run on the weaker CREW PRAM with optimal speedup as well. This will involve a simple randomization scheme for simulating concurrent writes through a use of hashing.

research was partially supported by the Office of Naval Research undue Contract Number 00014-85-K-0046. Authoas' addresses: Zvi M. Kedem, 251 Mercer St., New York, NY 10012- 1185* USA, (212) 998-3101, kedern[ nyu.nyuedu; Krishna V. Palem. P. O. Boat 704, Yorktown Heights, NY

10598, USA, (914) 789-7846, kpaletnea ibm.com; Gad M. Landau, 333 Jay St., Brooklyn, NY

11201, USA, (718) 260-3154, landan@polycatt.poly.edu

1. Introduction

Unification of terms arises often in symbolic computation problems. It is used in logic program- ming systems [CM81, K74], typo inferencing [M78], and in term rewriting systems [H080]. Term matching is a very important special case of unification. As observed by Dwork et al. in [DKS86]

New York University Page 1 Dec 31, 1983

Page 2 of 33

Optimal Parallel Algorithms for Matching Problems

and by Ramesh et al. in [RVKR87], a recent study performed on extant PROLOG pro- s grams revealed that very often, the full power of general unification is not needed by these sys- tems, and indeed term matching suffices. Anti-unification has been used in inductive inference [P70], theorem proving [R71], resolution and equation solving [H76] and in optimization of logic programs [NL84]. The 2-dimensional pattern matching problem has a rich history[Ba78, Bi77, KMR72, KR87]. Pattern matching in two dimensions is motivated by areas such as image processing and scene (or pattern) recognition [Ba78, Bi77]. The one dimensional case of this problem is the well-know string matching pr...