## Abstract

Finding an optimal assignment between two sets of

objects is a fundamental problem arising in many applications,

including the matching of ‘bag-of-words’ representations in

natural language processing and computer vision. Solving the

assignment problem typically requires cubic time and its pairwise

computation is expensive on large datasets. In this paper, we

develop an algorithm which can find an optimal assignment in

linear time when the cost function between objects is represented

by a tree distance. We employ the method to approximate the edit

distance between two graphs by matching their vertices in linear

time. To this end, we propose two tree distances, the first of which

reflects discrete and structural differences between vertices, and

the second of which can be used to compare continuous labels.

We verify the effectiveness and efficiency of our methods using

synthetic and real-world datasets.

objects is a fundamental problem arising in many applications,

including the matching of ‘bag-of-words’ representations in

natural language processing and computer vision. Solving the

assignment problem typically requires cubic time and its pairwise

computation is expensive on large datasets. In this paper, we

develop an algorithm which can find an optimal assignment in

linear time when the cost function between objects is represented

by a tree distance. We employ the method to approximate the edit

distance between two graphs by matching their vertices in linear

time. To this end, we propose two tree distances, the first of which

reflects discrete and structural differences between vertices, and

the second of which can be used to compare continuous labels.

We verify the effectiveness and efficiency of our methods using

synthetic and real-world datasets.

Original language | English |
---|---|

Title of host publication | International Conference on Data Mining |

Publisher | IEEE Computer Society |

Number of pages | 10 |

Publication status | Accepted/In press - 6 Sep 2019 |