Distributed algorithms for tree pattern matching

Gurdip Singh, Scott A. Smolka, I. V. Ramakrishnan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We present efficient distributed algorithms for the Tree Pattern Matching problem. To the best of our knowledge, these are the first distributed algorithms of this nature. Tree pattern matciffng is a fundamental operation in many programming task such as code optimization and automated theorem proving, and has a number of applications in distributed systems. We present both a top-down and bottom-up algorithm for linear tree pattern matching (where any variable occurs at most once in the pattern) for the case in which tile subject tree is completely distributed as a node per processor. Tile pattern is assumed to reside within the local memory of each processor. Let the subject tree have n nodes and height hs, and the pattern m nodes and height hp. The top-down algorithm has bit complexity O(n log m hp) and time complexity O(hs), while the bottom-up algorithm has bit complexity O(n hp) and time complexity O(hp). However, the bottom-up algorithm requires preprocessing of the subject and pattern trees. An efficient extension of these distributed algorithms to the case of multiple patterns is also given.

Original languageEnglish (US)
Title of host publicationDistributed Algorithms - 2nd International Workshop, Proceedings
PublisherSpringer Verlag
Pages92-107
Number of pages16
Volume312 LNCS
ISBN (Print)9783540193661
DOIs
StatePublished - Jan 1 1988
Externally publishedYes
Event2nd International Workshop on Distributed Algorithms, WDAG 1987 - Amsterdam, Netherlands
Duration: Jul 8 1987Jul 10 1987

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume312 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Distributed Algorithms, WDAG 1987
CountryNetherlands
CityAmsterdam
Period7/8/877/10/87

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Distributed algorithms for tree pattern matching'. Together they form a unique fingerprint.

  • Cite this

    Singh, G., Smolka, S. A., & Ramakrishnan, I. V. (1988). Distributed algorithms for tree pattern matching. In Distributed Algorithms - 2nd International Workshop, Proceedings (Vol. 312 LNCS, pp. 92-107). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 312 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0019797