9
$\begingroup$

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).

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ This volume features a discussion of parallel algorithms for subtree isomorphism. $\endgroup$
    – Anthony Labarre
    Jun 28, 2011 at 14:05
  • 1
    $\begingroup$ 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? $\endgroup$
    – Anthony Labarre
    Jun 29, 2011 at 9:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Eli
    Jul 2, 2011 at 17:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marek Chrobak
    Jul 3, 2011 at 6:12
  • 2
    $\begingroup$ 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. $\endgroup$
    – Eli
    Jul 7, 2011 at 19:10

2 Answers 2

Reset to default
3
$\begingroup$

Although not specifically aimed at (rooted) trees, I think the G-trie data structure might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.

Improve this answer
$\endgroup$
1
$\begingroup$

A while back I wrote up Ronald Read's tree canonization algorithm and put it on wikipedia.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.