We extended tree similarity algorithm for buyer/seller matchmaking to a DAG (Directed Asyclic Graph) similarity algorithm. Using a DAG to represent the buyer/seller product/service descriptions, we allow several nodes to share the same subtree(s). Thus, the shared (sub)tree similarity and simplicity values may be reused in later calculation. We use linked lists to store the similarity and simplicity values for future reuse. In this way, we save both time and space for computing the tree similarity and stroing the product/service trees. Please find below the documents for DAG similarity.
DAG Similarity (MCS Thesis Jing Jin) (Doc,
Oral defense powerpoint slides