Efficient similarity measure for comparing tree structures
by Fatiha Souam; Ali Aït El Hadj
International Journal of Advanced Intelligence Paradigms (IJAIP), Vol. 8, No. 1, 2016

Abstract: The problem of comparing tree structures is known to be a task often characterised by a particularly high computational complexity. Any attempt to reduce this complexity by considering a tree as a linear structure has generally resulted in a loss of information. Indeed, a comparison of tree structures (based on their similarity in order to classify them) which considers a tree as a single vector, obviously takes less execution time, but unfortunately has less credibility with respect to the classification task. The hierarchical relationships are thus ignored or suppressed and tree structures then behave like sequential data structures. The goal in this paper is to find a compromise between the processing time, on the one hand, and the preservation of information, on the other hand. For this purpose, the proposed approach relies on two types of traversal algorithm, namely the depth-first traversal and breadth-first traversal. The strategy aims to exploit the advantages of combining the two types of algorithms. To validate our approach, we conducted experiments on two sets of tree structures obtained from two collections of real and synthetic XML documents, respectively.

Online publication date: Wed, 17-Feb-2016

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Advanced Intelligence Paradigms (IJAIP):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com