Friday, May 9, 2008

What is a "Tree Pattern"?

Perhaps this may be obvious to you, but it was not to me. I was recently reading "Mining tree patterns with Almost Smallest Supertrees" from Proceedings of the 2008 SIAM International Conference on Data Mining. My first question was what is a "tree pattern"? On first skim, I could not find an example or a simple definition of what a tree pattern was. This paper is referring to frequent trees in tree structured data. For example one of the data sets uses a web log containing user session data. A session could be described as a tree where each page visited is a node and the edge between pages is a directed edge originating at the earlier page and proceeding to the later page in time. In this case a tree pattern could be that people coming from the "edu" domain often go to page A followed by page B. However it is still not clear to me if part of a session could be a pattern or if a frequent tree only refers to entire trees. Help me out if you know the answer.