Finding approximate patterns in undirected acyclic graphs

Jason T.L. Wang; Kaizhong Zhang; George Chang; Dennis Shasha

doi:10.1016/S0031-3203(01)00055-3

Finding approximate patterns in undirected acyclic graphs

Jason T.L. Wang
, Kaizhong Zhang
, George Chang
, Dennis Shasha

Computer Science

Research output: Contribution to journal › Article › peer-review

18 Scopus citations

Abstract

We consider an approximate pattern matching problem for undirected acyclic graphs. Specifically, let P be a pattern graph, D a data graph and t an integer. We present an algorithm to locate a subgraph in D whose distance from P is at most t. The distance measure used here is the degree-2 metric published previously. The time complexity of our algorithm is O(N_pN_Dd √d log d) where N_p and N_D are the number of nodes in P and D, respectively; d = min d_P,d_D; d_p and d_D are the maximum degree of P and D, respectively. Central to our algorithm is a procedure for finding approximate patterns in rooted unordered trees and freely allowing cuts. We discuss two applications of the algorithms in chemical information search and website management on the Internet.

Original language	English (US)
Pages (from-to)	473-483
Number of pages	11
Journal	Pattern Recognition
Volume	35
Issue number	2
DOIs	https://doi.org/10.1016/S0031-3203(01)00055-3
State	Published - Feb 2002

All Science Journal Classification (ASJC) codes

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Keywords

Chemical substructure search
Distance metric
Graph matching
Pattern discovery
Website analysis

Access to Document

10.1016/S0031-3203(01)00055-3

Cite this

@article{f531b481508148b8abb27bf82d0eb53d,

title = "Finding approximate patterns in undirected acyclic graphs",

abstract = "We consider an approximate pattern matching problem for undirected acyclic graphs. Specifically, let P be a pattern graph, D a data graph and t an integer. We present an algorithm to locate a subgraph in D whose distance from P is at most t. The distance measure used here is the degree-2 metric published previously. The time complexity of our algorithm is O(NpNDd √d log d) where Np and ND are the number of nodes in P and D, respectively; d = min dP,dD; dp and dD are the maximum degree of P and D, respectively. Central to our algorithm is a procedure for finding approximate patterns in rooted unordered trees and freely allowing cuts. We discuss two applications of the algorithms in chemical information search and website management on the Internet.",

keywords = "Chemical substructure search, Distance metric, Graph matching, Pattern discovery, Website analysis",

author = "Wang, \{Jason T.L.\} and Kaizhong Zhang and George Chang and Dennis Shasha",

note = "Funding Information: We thank Zasha Weinberg for his contributions in the early phase of this project. We also thank Professor Carol Venanzi for useful discussions on chemical retrieval systems. This work was supported in part by NSF grants IIS-9988345, IIS-9988636, and by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGP0046373. ",

year = "2002",

month = feb,

doi = "10.1016/S0031-3203(01)00055-3",

language = "English (US)",

volume = "35",

pages = "473--483",

journal = "Pattern Recognition",

issn = "0031-3203",

publisher = "Elsevier Ltd",

number = "2",

}

TY - JOUR

T1 - Finding approximate patterns in undirected acyclic graphs

AU - Wang, Jason T.L.

AU - Zhang, Kaizhong

AU - Chang, George

AU - Shasha, Dennis

N1 - Funding Information: We thank Zasha Weinberg for his contributions in the early phase of this project. We also thank Professor Carol Venanzi for useful discussions on chemical retrieval systems. This work was supported in part by NSF grants IIS-9988345, IIS-9988636, and by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGP0046373.

PY - 2002/2

Y1 - 2002/2

N2 - We consider an approximate pattern matching problem for undirected acyclic graphs. Specifically, let P be a pattern graph, D a data graph and t an integer. We present an algorithm to locate a subgraph in D whose distance from P is at most t. The distance measure used here is the degree-2 metric published previously. The time complexity of our algorithm is O(NpNDd √d log d) where Np and ND are the number of nodes in P and D, respectively; d = min dP,dD; dp and dD are the maximum degree of P and D, respectively. Central to our algorithm is a procedure for finding approximate patterns in rooted unordered trees and freely allowing cuts. We discuss two applications of the algorithms in chemical information search and website management on the Internet.

AB - We consider an approximate pattern matching problem for undirected acyclic graphs. Specifically, let P be a pattern graph, D a data graph and t an integer. We present an algorithm to locate a subgraph in D whose distance from P is at most t. The distance measure used here is the degree-2 metric published previously. The time complexity of our algorithm is O(NpNDd √d log d) where Np and ND are the number of nodes in P and D, respectively; d = min dP,dD; dp and dD are the maximum degree of P and D, respectively. Central to our algorithm is a procedure for finding approximate patterns in rooted unordered trees and freely allowing cuts. We discuss two applications of the algorithms in chemical information search and website management on the Internet.

KW - Chemical substructure search

KW - Distance metric

KW - Graph matching

KW - Pattern discovery

KW - Website analysis

UR - https://www.scopus.com/pages/publications/0036466969

UR - https://www.scopus.com/pages/publications/0036466969#tab=citedBy

U2 - 10.1016/S0031-3203(01)00055-3

DO - 10.1016/S0031-3203(01)00055-3

M3 - Article

AN - SCOPUS:0036466969

SN - 0031-3203

VL - 35

SP - 473

EP - 483

JO - Pattern Recognition

JF - Pattern Recognition

IS - 2

ER -

Finding approximate patterns in undirected acyclic graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this