Algorithmics and applications of tree and graph searching

By Dennis E. Shasha, Jason Tsong-Li Wang, R. Giugno. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

478 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/728bf604d9200c440417df5623dafa1b11a79178

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A survey of frequent subgraph mining algorithms (2012, background): “2004; Huang & Lai 2006; Newman 2004) Graph indexing (Shasha et al. 2002; Yan et al. 2004) Graph searching (Yan et al.”
Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, background): “The similarity is typically deﬁned by either exact matches (full-graph or sub-graph isomorphism) (Berretti et al., 2001; Shasha et al., 2002; Yan et al., 2004; Srinivasa & Kumar, 2003) or some measure of structural similarity, e.g. in terms of graph edit distances (Willett et al., 1998; Ray-mond et…”
Scalable SPARQL querying of large RDF graphs (2011, background): “Our work on searching for patterns in graphs leverages previous work on pushing this effort into database systems [28].”
gStore: Answering SPARQL Queries via Subgraph Matching (2011, methodology): “Although many subgraph matching methods have been proposed (e.g., [17, 24]), they are not scalable to very large graphs.”
Computational approaches for detecting protein complexes from protein interaction networks: a survey (2010, background): “The fact that many graph-based problems, such as subgraph isomorphisms [99,100] and enumeration [101,102], are NP-hard [103,104], indicates that mining the PPI networks is intrinsically computationally challenging.”
Efficient algorithms for processing XPath queries (2002, methodology): “The intuition that XPath can be used to match a large class of tree patterns [Shasha et al. 2002; Kilpel(cid:127)ainen 1992; Bruno et al. 2002] in XML documents also implies to a certain degree that queries may be of some size.”
Graphs-at-a-time: query language and access methods for graph databases (2008, methodology): “In graph indexing, GraphGrep [29] uses enumerated paths as index features to .lter unmatched graphs.”
Graph indexing: a frequent structure-based approach (2004, methodology): “For more complicated graph queries, Shasha et al. [14] extends the path-based technique to do full scale graph retrieval, which is also used in Daylight system [8].”
Substructure similarity search in graph databases (2005, methodology): “tain the query graph, or vice versa [19, 20, 25]; and (3) full structure similarity search: find structures that are similar to the query graph [17, 24, 18].”
Fg-index: towards verification-free query processing on graph databases (2007, background): “Therefore, it is evident that graph databases will become more and more prevalently used in the near future.”
Comparing Stars: On Approximating Graph Edit Distance (2009, background): “…graph q , almost all existing algorithms of processing graph search can be classiﬁed into the following three categories: 1. full graph search : ﬁnd all graphs g i in D s.t. g i is the same as q [4]; 2. subgraph search : ﬁnd all graphs g i in D containing q [5, 26, 27, 37] or contained by q [9].”