A Weighted-Tree Simplicity Algorithm for Similarity Matching of Partial Product Descriptions

  1. (PDF, 285 KB)
AuthorSearch for: ; Search for: ; Search for: ; Search for:
ConferenceProceedings of The 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
Subjectarc-labeled and arc-weighted tree; tree similarity; tree simplicity; balanced k-ary trees; e-Business; buyer and seller trees; similitude entre les arborescences; simplicité d'arborescence; arborescences « k-ary » équilibrées; affaires électroniques; arborescences des acheteurs et des vendeurs
AbstractOur 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.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number48534
NPARC number5759932
Export citationExport as RIS
Report a correctionReport a correction
Record identifier09d77fb1-40ec-459e-a11d-473e39b316aa
Record created2009-01-30
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: