International Society for Computers and Their Applications (ISCA) 14th International Conference on Intelligent and Adaptive Systems and Software Engineering (IASSE-2005), July 20-22, 2005, Toronto, Ontario, Canada
arc-labeled and arc-weighted tree; tree similarity; tree simplicity; balanced k-ary trees; e-Business; buyer and seller trees
Our weighted-tree similarity algorithm matches buyers and sellers in e-Business environments. We use arc-labeled, arc-weighted trees to represent the products (or services) sought/offered by buyers/sellers. Partial product descriptions can be represented via subtrees missing in either or both of the trees. In order to take into account the effect of a missing subtree on the similarity between two trees, our algorithm uses a (complexity or) simplicity measure. Besides tree size (breadth and depth), arc weights are taken into account by our tree simplicity algorithm. This paper formalizes our buyer/seller trees and analyzes the properties of the implemented tree simplicity measure. We discuss how this measure captures business intuitions, give computational results on the simplicity of balanced k-ary trees, and show that they conform to the theoretical analysis.
Proceedings of the International Society for Computers and Their Applications (ISCA) 14th International Conference on Intelligent and Adaptive Systems and Software Engineering (IASSE-2005).