<p>Although not specifically aimed at (rooted) trees, I think the <a href="http://dx.doi.org/10.1007/s10618-013-0303-4" rel="nofollow">G-trie data structure</a> might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.</p>

CC BY-SA 3.0
2014-10-07T19:20:42.617Z
2014-10-07T19:20:42.617Z
Joshua Grochow
<p>A while back I wrote up Ronald Read's tree canonization algorithm and <a href="http://en.wikipedia.org/wiki/Graph_canonization" rel="nofollow">put it on wikipedia</a>.</p>

<p>I would make a hashtable for each internal node signature, and label them with a list of pointers back to the subtrees they came from. However, it will only work for treelets with true leaves.</p>

CC BY-SA 3.0
2014-10-07T23:39:20.497Z
2014-10-07T23:39:20.497Z
Chad Brewbaker
<p>I have a large dataset of trees and I would like to search it by specifying a <em>treelet</em> (connected subgraph). The query should return all the occourrences of the treelet in the dataset.</p>

<p>Are there efficient algorithms to do so?</p>

<p>I was thinking of something like suffix arrays, however, naively encoding the trees as strings (by a fixed traversal ordering of their nodes) won't work, since the search treelet can be of any arbitrary shape. </p>

<p>UPDATE:</p>

<p>Some details about the typical instances I expect:</p>

<p>The dataset will consist in at least tens of thousands trees, each consisting in about twenty to thirty nodes.
The trees will not be not binary, but the typical children number per node will be small (usually no larger than four or five, although in some degenerate cases it can reach about thirty). The number of labels will be in the tens of thousands.</p>

<p>I need that for NLP applications: each tree will be the dependency parse of a sentence, each node representing a word occourrence and each label a dictionary word (with some decoration).</p>

CC BY-SA 3.0
2011-06-28T14:05:06.803Z
[This volume](http://books.google.com/books?id=ZqRsRLLHjK0C&pg=PA171&lpg=PA171&dq=subtree+isomorphism+parallel&source=bl&ots=0i-icahk-B&sig=jvbo4_bCdfY9-O73-_NU2wRsM1U&hl=en&ei=L98JTqD5IYqCOrHLxKMB&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBgQ6AEwAA#v=onepage&q=subtree%20isomorphism%20parallel&f=false) features a discussion of parallel algorithms for subtree isomorphism.
Anthony Labarre
CC BY-SA 3.0
2011-06-28T15:56:20.630Z
I don't think that's my problem.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-06-29T09:35:45.833Z
Sorry, I thought you were looking for a connected subgraph, which will necessarily be a tree, appearing in a given set of trees. Could you clarify in what aspects  your problem differs from this description?
Anthony Labarre
CC BY-SA 3.0
2011-06-29T12:01:31.297Z
I'm indeed looking for a connected subgraph, but not necessarily a subtree (the leaves of the treelet don't have to be the leaves of a tree in the dataset to match).
Moreover, I'm not looking for an isomorphism, rather I'm trying to match labeled nodes.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-07-02T17:19:34.773Z
Do you know anything about the trees in advance? Binary? How many different node labels do you expect? Any limitations on space efficiency? I ask because if you're running a ton of queries on the same dataset, a solution could involve some type of aggressive indexing.
Eli
CC BY-SA 3.0
2011-07-02T20:35:09.727Z
@Eli: I updated the question
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-07-03T06:12:56.657Z
Are you familiar with XML twig matching? Your problem seems to be a special case, so you can simply use any of the existing algorithms and software.
Marek Chrobak
CC BY-SA 3.0
2011-07-03T21:26:57.470Z
@Marek: Do you have any references? I can't find anything specific.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-07-05T19:18:14.697Z
We're looking at hundreds of thousands of nodes and tens of thousands of labels? Is it true that you can expect only around a dozen (or, some reasonably small number) trees to include any given label? If so, I'd start with a map from label to trees. Then even if you have to do something expensive, doing it on a dozen trees would be cheap.
Eli
CC BY-SA 3.0
2011-07-06T11:12:54.027Z
@Eli: the labels correspond to natural language words. Hence some labels (like "a", "the", "is", ...) are extremely common, while others are rare and may even appear only once in the dataset.
I was thinking of creating one string per tree consisting in the labels appearing with their multiplicity, sorted in some default (e.g. lexicographical) order. Hence I would be able to use some standard string searching technique to find candidate trees and then try to match their structure (maybe even using naive comparison).
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-07-07T19:10:07.997Z
I'd guess it might be best to ignore the graph structure. Given a typical query, if you discard structure, how many trees do you anticipate having all of these words? Do your queries have any wildcards or are they exact? If the words in a query are like "The cat ate the hat", how many graphs will actually have both the words "cat" and "hat" in them? If you just index each word to a set of trees, then intersect all the sets, potentially you could naively search the result without incurring too much of a cost.
Eli
<graph-algorithms><ds.data-structures><tree><graph-isomorphism><string-search>
Efficient algorithms for searching a collection of trees
Antonio Valerio Miceli-Barone
# Efficient algorithms for searching a collection of trees

(Asked by: username_0 on 2011-06-28)

I have a large dataset of trees and I would like to search it by specifying a *treelet* (connected subgraph). The query should return all the occourrences of the treelet in the dataset.

Are there efficient algorithms to do so?

I was thinking of something like suffix arrays, however, naively encoding the trees as strings (by a fixed traversal ordering of their nodes) won't work, since the search treelet can be of any arbitrary shape.

UPDATE:

Some details about the typical instances I expect:

The dataset will consist in at least tens of thousands trees, each consisting in about twenty to thirty nodes.
The trees will not be not binary, but the typical children number per node will be small (usually no larger than four or five, although in some degenerate cases it can reach about thirty). The number of labels will be in the tens of thousands.

I need that for NLP applications: each tree will be the dependency parse of a sentence, each node representing a word occourrence and each label a dictionary word (with some decoration).

**Tags:** graph-algorithms, ds.data-structures, tree, graph-isomorphism, string-search

> **Comments:**
> **username_1**: [This volume](http://books.google.com/books?id=ZqRsRLLHjK0C&pg=PA171&lpg=PA171&dq=subtree+isomorphism+parallel&source=bl&ots=0i-icahk-B&sig=jvbo4_bCdfY9-O73-_NU2wRsM1U&hl=en&ei=L98JTqD5IYqCOrHLxKMB&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBgQ6AEwAA#v=onepage&q=subtree%20isomorphism%20parallel&f=false) features a discussion of parallel algorithms for subtree isomorphism.  
> **username_0**: I don't think that's my problem.  
> **username_1**: Sorry, I thought you were looking for a connected subgraph, which will necessarily be a tree, appearing in a given set of trees. Could you clarify in what aspects  your problem differs from this description?  
> **username_0**: I'm indeed looking for a connected subgraph, but not necessarily a subtree (the leaves of the treelet don't have to be the leaves of a tree in the dataset to match). Moreover, I'm not looking for an isomorphism, rather I'm trying to match labeled nodes.  
> **username_2**: Do you know anything about the trees in advance? Binary? How many different node labels do you expect? Any limitations on space efficiency? I ask because if you're running a ton of queries on the same dataset, a solution could involve some type of aggressive indexing.  
> **username_0**: @username_2: I updated the question  
> **username_3**: Are you familiar with XML twig matching? Your problem seems to be a special case, so you can simply use any of the existing algorithms and software.  
> **username_0**: @Marek: Do you have any references? I can't find anything specific.  
> **username_2**: We're looking at hundreds of thousands of nodes and tens of thousands of labels? Is it true that you can expect only around a dozen (or, some reasonably small number) trees to include any given label? If so, I'd start with a map from label to trees. Then even if you have to do something expensive, doing it on a dozen trees would be cheap.  
> **username_0**: @username_2: the labels correspond to natural language words. Hence some labels (like "a", "the", "is", ...) are extremely common, while others are rare and may even appear only once in the dataset. I was thinking of creating one string per tree consisting in the labels appearing with their multiplicity, sorted in some default (e.g. lexicographical) order. Hence I would be able to use some standard string searching technique to find candidate trees and then try to match their structure (maybe even using naive comparison).  
> **username_2**: I'd guess it might be best to ignore the graph structure. Given a typical query, if you discard structure, how many trees do you anticipate having all of these words? Do your queries have any wildcards or are they exact? If the words in a query are like "The cat ate the hat", how many graphs will actually have both the words "cat" and "hat" in them? If you just index each word to a set of trees, then intersect all the sets, potentially you could naively search the result without incurring too much of a cost.  

---

## 2 answers

### Answer by username_4 on 2014-10-07. Score: 3

Although not specifically aimed at (rooted) trees, I think the [G-trie data structure](http://dx.doi.org/10.1007/s10618-013-0303-4) might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.


---

### Answer by username_5 on 2014-10-07. Score: 1

A while back I wrote up Ronald Read's tree canonization algorithm and [put it on wikipedia](http://en.wikipedia.org/wiki/Graph_canonization).

I would make a hashtable for each internal node signature, and label them with a list of pointers back to the subtrees they came from. However, it will only work for treelets with true leaves.


---

