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