A method of searching tree-structured data can be provided by identifying all labels associated with nodes in a plurality of trees including the tree-structured data, determining which of the labels is included in a percentage of the plurality of trees that exceeds a frequent threshold value to provide frequent labels, defining frequent candidate sub-trees for searching within the plurality of trees using combinations of only the frequent labels, and then searching for the frequent candidate sub-trees in the plurality of trees including the tree-structured data using a plurality of pruning kernels instantiated on a non-deterministic finite state machine to provide a less than exact count of the frequent candidate sub-trees in the plurality of trees.