NDLI: Systolic algorithms for tree pattern matching

Content Provider	IEEE Xplore Digital Library
Author	Ejnioui, A. Ranganathan, N.
Copyright Year	1995
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Univ. of South Florida, Tampa, FL, USA (Ejnioui, A.; Ranganathan, N.)
Abstract	The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Several sequential and parallel algorithms have been proposed in the literature for this compute bound problem. Most of the parallel algorithms are based on the theoretical PRAM model of computation. In this paper, we propose two efficient parallel algorithms for tree pattern matching based on the linear systolic array model. The algorithms can be mapped onto any SIMD machine. The algorithms require O(n+m) time to perform the matching using either n or m processors, where n is the size of the subject tree and m is the size of the pattern tree. The algorithms represent a significant improvement over the existing ones in view of implementation.
Starting Page	650
Ending Page	655
File Size	641431
Page Count	6
File Format	PDF
ISBN	0818671653
ISSN	10636404
DOI	10.1109/ICCD.1995.528937
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-10-02
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Pattern matching Parallel algorithms Concurrent computing Computational modeling Phase change random access memory Object recognition Very large scale integration Microelectronics Computer science Computer vision
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Using parallel string matching algorithms for contour based 2-D shape recognition

A systolic algorithm and architecture for image thinning

A tree-matching chip

Minimum spanning tree on the HMESH architecture

Parallel algorithms for maximum matching in interval graphs

A parallel algorithm for computing polygon set operations

Image computations on reconfigurable VLSI arrays

A parallel algorithm and architecture for object recognition in images

Optimal parallel algorithms for cut vertices, bridges, and Hamiltonian path in bounded interval tolerance graphs

Systolic algorithms for tree pattern matching

Similar Documents

Using parallel string matching algorithms for contour based 2-D shape recognition

A systolic algorithm and architecture for image thinning

A tree-matching chip

Minimum spanning tree on the HMESH architecture

Parallel algorithms for maximum matching in interval graphs

A parallel algorithm for computing polygon set operations

Image computations on reconfigurable VLSI arrays

A parallel algorithm and architecture for object recognition in images

Optimal parallel algorithms for cut vertices, bridges, and Hamiltonian path in bounded interval tolerance graphs

Systolic algorithms for tree pattern matching